私がRubyで書いているLisp方言、 [Nendo]について。

最新の[Nendo] version 0.3.2ではまだ末尾再帰最適化がサポートされていない。 これは無限ループが記述できないということを意味する。 whileやuntilといった、無限ループ構文は[Nendo]の初期化スクリプトでマクロで定義されているが、[Nendo]のプリミティブにループという概念が無いため、ただの再帰呼び出しに変換してある。つまり無限ではなく、いつかはスタックオーバーフローするということである。 無限ループが書けないと何が困るかというと、デーモン化したとき、肝心のメインループ(普通は無限ループ)が書けないとか、無限ストリームを読み込む tail -f のようなものも書けない。

さて、どうやって無限ループを実現するかを考えはじめているのだが、まだまとまっていない。 案としては、継続をサポートするという正統派な方法と、Rubyのwhileと同様にプリミティブなループ構文を用意してSchemeからは遠ざかるという案だ。 しかし、何とかしてSchemeと同様の末尾再帰最適化を実現して、Schemeのライブラリをなるべく簡単にポーティングできるようにしたい。 継続を実現する具体策としてはRubyのcallccがあるが、例外等との絡みで安全性が低いというのをどこかで読んだことがあるので、できればそのまま使わないほうが良いだろう。 (それに、今ちょっと調べた範囲ではJRuby 1.5.0とRubinius 1.0が callccを完全にサポートしていないみたいだ。callccの優先順位は非常に低いということか…)

なんてぼんやり考えたのだけど、R5RSを再度確認したら末尾呼び出しになる箇所はこんだけあるよと書いてある。多い！ つまり、これらの箇所をループに最適化せよということか。 うわー、めんどくせー。

(if <式> <末尾式> <末尾式>) (if <式> <末尾式>) (cond +) (cond * (else <末尾列>)) (case <式> +) (case <式> * (else <末尾列>)) (and <式>* <末尾式>) (or <式>* <末尾式>) (let (<束縛仕様>*) <末尾本体>) (let <変数> (<束縛仕様>*) <末尾本体>) (let* (<束縛仕様>*) <末尾本体>) (letrec (<束縛仕様>*) <末尾本体>) (let-syntax (<構文仕様>*) <末尾本体>) (letrec-syntax (<構文仕様>*) <末尾本体>) (begin <末尾列>) (do (<繰返し仕様>*) (<テスト> <末尾列>)

<式>*) たぶん、上の式を全て lambdaにコンパイルして 最終的には lambda の末尾呼び出しだけを解析して最適化すればいいのだろうが、今の*[Nendo*]はそうなっていない。 if と let と lambda くらいだけで勘弁してほしい。たぶんそれで実用レベルにはなるだろう。 それともいっそ named letだけが末尾再帰最適化の対象になるとわりきるとか。Clojure も recur という予約語を使って再帰呼び出しを明示した場合のみ最適化されるわりきった仕様だったっけ。 そして、マニュアルの注意書きで逃げると。 ^_^; *[Nendo*]の用途から考えると本気でがんばる部分じゃない気がしてならないので。 もうちょっと考えてみよう。 ちなみに今の*[Nendo*]は次のようにマクロ展開される。これを全部最適化対象にするのは骨が折れるのでやりたくない。 - case, cond, and, or → if ( Rubyのifで実現 ) - let*, named let → let ( Rubyのlambdaで実現 ) - begin → begin ( Rubyのbegin,endで実現 ) - lambda → lambda ( Rubyのlambdaで実現 ) - lterecはプリミティブ ( Rubyのlambdaで実現 )  処理系の実装って本当に地道な作業が多いなあ。 やっぱり、named letだけ最適化するというあたりが落としどころかな。 *[Nendo*]の場合は、一番めんどくさい作業であるライブラリ開発をRubyに丸投げしているので、だいぶ楽できているとは思うのだが、それでも大変な作業だ。 それを考えると、Gaucheのライブラリまで含めたの整備状況は凄いよなあ。(最適化も凄いけど) 追記: 先程、Ruby 1.9.1でcallccを試してみたら 実行速度が非常に遅かった。もし、callccを使うとしたら、例えば、named letの内側の末尾再帰呼出しだけをcallccでジャンプに置きかえる位が現実的かも。