Tech記事

# Recursive Lambda in C++14

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.

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…

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.

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 ); } } );


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

RELATED POST