Common Lispのラムダリストと末尾再帰最適化

Common Lispを使い始めてからというもの、Common Lispの流儀に慣れるためにと思い、 do系のマクロやloop、或は外部ライブラリのiterator等を使っていてが、ようやく慣れてきた。それで再帰する関数を余り書く事がなく、今まで気が付かなかったんだけど。ふと、リストを操作する関数を末尾再帰で定義してみると、面白い事に気づいた。何気なく引数にoptional変数を使っていたのだ。

特に面白くも無く突っ込みどころのあるリストの長さを返す関数が例だけど、

(defun f (ls &optional (n 0))
  (if (not ls)
      n
      (f (cdr ls) (+ 1 n))))

optional変数を使う事によって、普通ならletやlabelが有ったり二つに分けたりしていた定義が、スッキリしていて分かりやすいものになっていた。何より末尾再帰を用いるメリットとは簡便さに有るのだからこれは良いと思う。また末尾再帰になれない人に取っては、こちらの方が分かりやすいのではないだろうか？まぁ、上の例のような無用心に引数を晒すという事は行儀がよくないが。

末尾再帰の最適化を確認する

ところで、上に書いた関数は長大なリストになるとスタックオーバーフローしていた。どうやら最適化はなされていないようである。こういうときはディスアセンブルして内部を見てみたいが、どうすればいいのだろう？

実はCommon Lispには標準で関数disassembleが用意されているのでこれを使って中身を見ていけば良いだけだ。この関数、関数単位でdisassemble出来て、もちろんREPLからも扱える。ついでにSLIMEだとC-c M-dでシンボルを入力すればアセンブリを見ることが出来る。

さてdisassembleして見ると、残念な事にPUSHしている。だから、オーバーフローしてしまっていたのだ。

それもその筈でScheme等とは違い、他の多くの言語と同じくANSI Common Lispでは末尾再帰の最適化は定められてはいない。つまりC等と変わらず処理系しだいという事で、処理系ごとに見ていく必要がある。

一寸調べてみると以下のページを見つけた、また見つけることになると思う。 Common Lispの各処理系毎の末尾最適化有無が纏められていて、大変に参考になる。

http://0branch.com/notes/tco-cl.html

それによると、私が今使っている処理系のSBCLではoptimizeすれば良いようである。

試してみたところ適切に末尾呼び出しがジャンプ命令のみになった。またcondやcase等でもうまくいった。

Schemeの規格だけどR7RSに書かれているような末尾文脈の例の範囲なら適切に処理してくれそうだ。

まとめ

こういうその場しのぎ的な定義の場合は取り敢えず動けばいいので、最適化を気にする程には使う事もないかもしれないけど。これに限らず、最適化する方法が残されているところがCommon Lisp的な気がする。この場合は処理系依存だけど、後で最適化していけばいいかと言うような。

それと、幾度と無く思い知らされるのがREPLとEmacsとSLIMEが自然に融合した開発環境だ。本当にすばらしいので全人類に使っていただきたい。もちろんVimmerにも。