Recursive Lambda in C++14

- arata-furukawa

( ^ω^) ⊃std::function⊂

std::function< int( int ) > f;
f = [&]( int a ){ return a <= 0 ? 1 : a * f( a - 1 ); };
f( 5 ); // 120

BOMB!

( ^ω^) ≡⊃⊂≡

std::functionを使ってそのまま再帰定義してはいけない。

( ^ω^) ⊃ .. ⊂ ‘∵ ‘:’;

std::functionは理論上、そして事実上速度が良いとは言えない。関数、関数オブジェクト、関数ポインタ、ラムダを統一的に扱うために、少なからずType Erasureが行われる。同時に再代入を許容するため、コンパイル時に呼び出しが解決できず、インライン展開がされることがないなど、様々な最適化が効かない。もちろん速度のネックが気にならない状況ならその程度は構わないが、関数を参照でキャプチャする必要が有るため、必ずしもstd::functionが同じラムダを指しているとは限らないという問題がある

じゃあどうするか。答えは簡単である。引数で自分自身を受け取ればいいのだ。受け取る引数が自分自身で、それを呼び出せばそれはれっきとした再帰関数だ。(不動点コンビネータ)

一番簡単な解は以下のとおりである。

template< typename F >
auto recursive( F f )
{
    return [ f ]( auto... a ) { return f( f, a... ); };
}

auto f = recursive(
    []( auto f, int a ) -> int {
        return a <= 0 ? 1 : a * f( f, a - 1 ); } );
f( 5 ); // 120

第一引数で自分自身を受け取る関数を、通常の再帰関数のようなインターフェースに変換するラッパのようなものだ。これは不動点コンビネータの一種である。

数日前の記事で載せたcurryを使ったカリー化で実装することも出来る。

auto f = []( auto f, int a ) -> int { return a <= 0 ? 1 : a * f( f, a - 1 ); };
auto f2 = curry( f )( f );
f2( 5 ); // 120

recusiveをカリー化で実装することも出来る。

template< typename F >
auto recursive( F f )
{
    return curry( f )( f );
}

美しい…。

余談だが、速度を気にするなら末尾再帰にするといい。GCCなどでは先ほどのコードすら末尾再帰に自動変換して最適化してくれるらしいが[要確認]。

auto f = recursive( []( auto f, int a, int r ) -> int { return a <= 0 ? r : f( f, a - 1, r ); } );

これで、recursiveを完全転送に対応すれば理論上はstd::functionよりはるかに高速に最適化する余地がある。末尾再帰が効くかは処理系の最適化能力次第であるが、少なくとも呼び出しアドレスが静的に解決できる時点で、弱い最適化でもstd::functionが不利なのは間違いない。

更に余談だが、この場合、戻り値の推論が出来ない(-> intの部分が省略出来ない)。これは条件演算子と推論ルールの問題である。ifステートメントにすれば問題ない。

auto f = recursive( []( auto f, int a, int r ){ if( a <= 0 ){ return r; } else { return f( f, a - 1, r ); } } );

今回のサンプルの場合は文字数的には増えたものの、推論させることによりジェネリック度が向上するので最初からこうしておけば良いだろう。

尚、C++11で同様のことを実現する場合はHereを参照のこと。