関数型言語がよろしいのか命令型言語がよろしいのか、または List がよろしいのか Array がよろしいのか、はたまた再帰がよろしいのか、goto がよろしいのかというのは同じ問題であるという話。
を、いつか真面目に書きたいんだけど、眠いので感情に任せて概要だけ書きます。
関数型言語、特に scheme を学び始めるとつい口に出してしまう言葉が、「末尾再帰」です。プログラムを再帰でエレガントに書いても処理系がちゃんとループに翻訳してくれるのでスゲー！という話です。これは関数型言語の最適化として効果的な物の一つです。そして、より大きな問題の特殊解であると言う意味で大きな意味があります。
大きな問題とは、一方向リンクリストを配列として実装する方法です。計り知れない価値を持つ純粋関数型言語でも、使えるデータ構造が一方向リンクリストしか無いというのではさすがに現実の問題に対処するには無理があります。この目の前に広がる画面の点々も、ネットの向こうで駄文の山を抱えているのも、書き換え可能でランダムアクセス可能な「配列」なので、結局関数型言語の実用化というのは List をどう Array に変換するかにかかってると思うのです。
そういう意味で、末尾再帰というのはその典型的な例です。関数呼び出しに使われるフレームは、呼び出し元へのリンクを持つ一方向リストとして表現出来ます。という事は無限ループを作ると無限のメモリが必要になってしまうのですが、末尾再帰というのはある条件でリンクを作らないで同じフレームを再利用する仕組みです。これは、List を Array に変換する最も単純な例とみなせます。
もしもこれを一般化出来たらどうなるでしょう。あらゆるリストを配列に最適化する努力をして、その過程として末尾再帰も行われるのです。むしろ、リンクを作るのを特殊条件にして、同じメモリの使いまわしをデフォルトにしてしまっても良いでしょう。逆ガベコレ http://d.hatena.ne.jp/propella/20070522/p1 を逆から見た図とも言えます。コンピュータは人間よりある意味賢く、こういった最適化こそ人間より機械にやらせるべきだと思います。
