ちゃんと回ってる？

26日にFunctional道産子の集い（北海道関数型言語勉強会-3 in 札幌）に参加してきました。
一応Haskellのお勉強をしてるんですが、気付けばRubyだのC++だのBinary Hacksだの（一部PythonだのC#だの）で盛り上がってました。面白かったなぁ。まあこれが勉強会の醍醐味ですよね。笑

最後、「遅延評価なのは分かるけど、たらいまわし関数ちょっと速すぎね？」という、普通の人なら疑わないような内容に疑問を抱き始め（！）、最終的にはコンパイラが生成した実行ファイルの解析に至ります。
Haskellが簡約やコンパイル時最適化によって、「print 20」とかいう次元にまでなってるんじゃないか？という疑惑が浮上。そしてバイナリ中に$20という定数を発見！そこを試しに40に書き換えると、出力は見事40となりました。たらいまわし関数は実行されてなかった！

という感じで勉強会は終わったのですが、その後参加者のK賀さんがmixiに「実行されてないわけじゃないかも？」と書き込まれてました。こうなると気になってしまうので自分でも調べてみましたが、ちゃんと実行されてるっぽいです。
taraiに渡す引数を8192 4096 2048とかにするとHaskellでも実行に1秒前後かかりました。一応外部からパラメータを渡すようにプログラムを書き換えてみてもほぼ同様の結果。
バイナリ中の$20は、tarai関数に渡す引数のひとつ(x)だったのかもしれません。
C++のtemplate版はコンパイル時に完全に展開されてるから、「実行時には計算されてない」と言って間違いではないはず（間違ってたらご指摘を！＞C++の人
でも多分あまりに巨大な数を渡すと死んでしまうと思う...

やっぱり計算量の差だったのかな。
先日書いたC#版も計算回数を数えてみましたが、もの凄い差でした。
さて、そもそもtaraiと遅延評価の関係ですが、ここで

tak --s

 tak (x-1) y z --a

 tak (y-1) z x --b

 tak (z-1) x y --c

とした場合、3つめのCがミソですよね？（ちょっと自信が...
先行評価でかつクロージャ等で包んでないとaとbの戻り値が<=になってたとしても、（もう不要な）cが実行されてしまう。ああやめられないとまらない。そしてさらにその先で再帰して再帰して・・・という感じですよね？

クロージャで渡した時のイメージはつかめるけど、簡約の場合はちょっとあやふやだなぁ。。後でもうちょっと考えやう。