たまには Lua も書かないと忘れてしまいそうなので，久しぶりに Lua を書いてみた．
お題は，最近の日記でも扱った，不動点コンビネータ．
散々既出だろうし，新規性は全くないけど，まぁ個人の blog だし その辺りは勘弁してください，ってことで．
さて，知らない人のために説明すると，不動点コンビネータとは，
function fix(f) -- 実装 end local fact = fix( function( fact, x ) return x > 1 and x * fact(x-1) or 1 end )
って感じで，ラムダ式で再帰を書けるようにする，ちょっと不思議な関数 fix のこと．
勿論，これは local function を使って
local function fact(x) return x > 1 and x * fact(x-1) or 1 end
と書けばいいけど*1，高階関数*2や for 文では，やはりラムダ式のまま書けると便利でしょ，ってこと．
で，実際に書いてると，こんな感じ．
function fix(f) local function fixed(...) return f( fixed, ... ) end return fixed end local fact = fix( function( fact, x ) return x > 1 and x * fact(x-1) or 1 end )
特に何も捻ってないので，分かる人なら問題なく分かる筈．
さて，こいつが実際に使い物になるかどうかが気になったので，
竹内関数を使ってベンチマークを取ってみます．
-- 不動点コンビネータ function fix(f) local function fixed(...) return f( fixed, ... ) end return fixed end -- ベンチマーク関数 do local collectgarbage = collectgarbage local clock = os.clock local print, format = print, string.format function benchmark( f, ... ) -- 予め GC を呼ぶ collectgarbage("collect") -- 測定 local t = clock() local result = f(...) local dt = clock() - t -- 表示 print( format( "%d, %fs", result, dt ) ) end end -- 実際に測定（竹内関数を使う） -- 普通に再帰で書いた場合 print( "rec. version:" ) local function tarai( x, y, z ) if x <= y then return y else return tarai( tarai( x-1, y, z ), tarai( y-1, z, x ), tarai( z-1, x, y ) ) end end benchmark( tarai, 12, 6, 0 ) print( "" ) -- 不動点コンビネータ print( "fix version:" ) benchmark( fix( function( tarai, x, y, z ) if x <= y then return y else return tarai( tarai( x-1, y, z ), tarai( y-1, z, x ), tarai( z-1, x, y ) ) end end ), 12, 6, 0 ) print( "" )
ideone.com で走らせてみたら， time limit exceeded と怒られてしまった*3ので，
手元で走らせてみた結果がこちら：
rec. version: 12, 1.638000s fix version: 12, 3.572000s
流石に再帰で書いたほうが速いが（当たり前），この程度なら気にならない，筈．
なので，気に入ったら使ってみてもいいんじゃないでしょうか．
おまけ
ついでなので，関数に名前を付けられない場合の不動点コンビネータ，すなわち Y コンビネータも書いてみた．
参考： http://d.hatena.ne.jp/willowlet/20091122/1258894948
上の参考ページの例だと，渡す関数がカリー化されている必要があるが，
今回作った fix は，カリー化されてない関数を受け取るものだったので，
折角なので，カリー化された関数を受け取るものと，カリー化されていない関数を受け取るもの，両方を作ることに．
まずカリー化された関数を受け取る版：
Y1 = function(f) return ( function(x) return x(x) end )( function(m) return f( function(a) return m(m)(a) end ) end ) end tarai1 = Y1( function( tarai ) return function(x) return function(y) return function(z) if( x <= y ) then return y else return tarai( tarai(x-1)(y)(z) )( tarai(y-1)(z)(x) )( tarai(z-1)(x)(y) ) end end end end end ) print( tarai1(12)(6)(0) )
…すごく，キモいです．
ので，せめて tarai( 12, 6, 0 ) と書けるようにします：
Y2 = function(f) return ( function(x) return x(x) end )( function(m) return f( function(...) return m(m)(...) end ) end ) end tarai2 = Y2( function( tarai ) return function( x, y, z ) if x <= y then return y else return tarai( tarai( x-1, y, z ), tarai( y-1, z, x ), tarai( z-1, x, y ) ) end end end ) print( tarai2( 12, 6, 0 ) )
これなら，まぁ，許容範囲ですかね．
続いて，カリー化されていない関数を受け取る版は，こちら（ちょい変更）：
Y3 = function(f) return ( function(x) return x(x) end )( function(m) return function(...) return f( m(m), ... ) end end ) end tarai3 = Y3( function( tarai, x, y, z ) if x <= y then return y else return tarai( tarai( x-1, y, z ), tarai( y-1, z, x ), tarai( z-1, x, y ) ) end end ) print( tarai3( 12, 6, 0 ) )
m(m) が fixed に対応する，ということに気づけば，特に難しくありません．
ともあれ，こんな感じで書けば，不動点コンビネータ自身からも再帰を取り除くことが可能になります．
この辺の話は，なかなか面白いので，興味があれば調べてみるといいんじゃないでしょうか．
あ，言うまでもないですが，これらの tarai1, tarai2, tarai3 は，かなり遅いです．
特に tarai1 の遅さは壊滅的で，実用には全く向きません．
tarai2 なら少しはマシですが，本文で定義した fix と比べるとイマイチですし，
普通に再帰で書いた場合に比べると，その性能差は歴然です．
そうなる理由は，変数束縛を行っていない変数の再束縛が行えないために，本来なら１回作れば良いクロージャを，
関数呼び出しの度に制作しているからで，変数束縛変数の再束縛を解禁すれば，速度的には かなりマシになります．((というか，最終的に，本文で定義した fix と同じになります．))
変数束縛変数の再束縛を使って効率化した具体例は，そろそろ面倒になってきたので，後の機会に回すことにします．
まぁ，要するに，変数や再帰呼び出しは偉大だ，ってことですね．
// ループで書ける場合は，再帰で書かずにループで書けば ずっと高速になる，というのは内緒です．
おまけ２
実のところ， Lua は無名関数の中に関数を定義できるので，
( function() local function tarai( x, y, z ) if x <= y then return y else return tarai( tarai( x-1, y, z ), tarai( y-1, z, x ), tarai( z-1, x, y ) ) end end return tarai end )()
とでも書けば， fix とか使わなくても，再帰関数を式の中で生成できたりします．
これは，普通に再帰関数を定義した場合と比較しても，速度の劣化は殆ど無いですので，
高階関数や for 文に再帰関数を渡したいケースが どの程度あるかは謎ですが，
そのようなケースでは， fix よりむしろ こっちを積極的に使っていくといいと思います．
