ORNEW

Recursive Lambda in C++14

Share on Facebook
Pocket

There is the recursive factorial function with std::function.

( ^ω^)
⊃std::function⊂

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

This is…

( ^ω^)
⊃)std::function(⊂

BOMB!

( ^ω^)
≡⊃⊂≡

std::functionを使ってそのまま再帰定義してはいけない。
You MUST NOT USE std::function for declare recursive lambda.

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

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

std::function is not good performance in theory and practically a pretty much environment. It’s done type erasure for implementing polymorphism for such as a function, a function object, a function pointer, and a lambda expression. Moreover, it will not be usually optimized calling. It have allowed reassignment, so compiler cannot be resolved function address at the compile time. Consequently, it will not be expanded inline. Although you might think, “No problem. I don’t mind performance!”. Think twice. It have allowed reassignment. Its instance is modifiable. Do you know what contain in variable? Really? In case of std::function, You must not initialize with lambda expression. The lambda expression need capture the variable for recursively. However, if you use itself in initialize expression, behavior is undefined; therefore, we cannot define it const. Maybe this will be produced a bug. It’s unnecessary risk.

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

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

What would you do? If I were you, I use Fixed Point Combinator. Most easy answer is following:

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

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

This recursive function is wrapper for it convert to interface like a normal recursive function. The parameter type is function. That function need a first parameter is itself. It get itself by a first argument. If call it, this is recursive function.

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

Alternatively, you can use currying.

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をカリー化で実装することも出来る。

recursive function can define also be by currying.

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

美しい…。

Beautiful…

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

If you mind performance, you should use tail recursion.

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

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

If it implemented Perfect Forwarding for recursive function, there is more a very fast possibility than std::function in theory. Whether it will be optimized is implementation dependent, though. At least, It should be more advantageous than std::function because it can optimize by inline-expansion at compile time.

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

Incidentally, In this case, it cannot be done auto deduction for return-value. This is conditional operator and auto deduction rule problem. It’s fix by use if statement.

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

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

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

P.S.
If you want to the same way in C++11, refer the following link.
Here