sumiiの日記

■末尾再帰

一部で微妙に:-)盛り上がっている件。単に「帰ってこなくて良い関数呼び出しをジャンプにする（ので、再帰呼び出しはループになる）」こと（いわゆる末尾呼び出し／末尾再帰）と、「メモリ消費が定数オーダーになる」ことを混同しているだけかと。

追記：いつも他人のふんどしだけでは恐縮なので情報提供（といっても、これも他人の研究ですが）：CPS変換をすれば、すべての関数呼び出しは末尾呼び出しになります。が、（当然ながら）すべてのプログラムが定数メモリで動作するわけではなく、継続を表現するクロージャがヒープやスタックに確保されるだけで、メモリ消費は減少しません。

しかしながら、CPS変換をすると、末尾呼び出し最適化も簡単になります。「関数呼び出しf(x)の返り値yを継続kに渡す」というCPS項はf x (λy. k y)のようになりますが、λy. k yをη簡約するとkになるので、先のf x (λy. k y)はf x kとなり、末尾呼び出し最適化と同様にメモリ使用量が減少します。

…というようなことを学部時代のコンパイラ演習で習いました。元はこのあたりから辿れると思います。

Permalink | コメント(1) | トラックバック(2)