リリカル☆Lisp開発日記

リリカルLisp ver1.7を公開しました。
約11ヶ月ぶりの更新です。

TL;DR: 主な変更点は高速化です。(fib 12)がver1.6と較べて1.57倍程速くなりました。

今回の変更では環境の構造を大きく変えました。
ver1.6までは環境は連想リスト(のリスト)で表現されており、
ローカル変数、グローバル変数は特に区別されていませんでした。
今回の変更で、ローカル変数はde Bruijn indexを使って表現するようになり、
ローカル変数の環境は連想リストではなく、
値のみ入った(名前が入っていない)リストになりました。

de Bruijn indexを付けるにはコードウォークをする必要があるのですが、
すべてのスペシャルフォームのためのコードウォークを書くのは骨が折れるので、
letやcondなどのスペシャルフォーム(Schemeの言葉で言うとlibrary syntax)は、
lambdaやifなど(Schemeの言葉で言うとsyntax)に変換してから、
変換した式を対象にコードウォークをすることにしました。
この式の変換やコードウォークはLispで書くという案もあったのですが、
わずか2900セルしかないNScLisperの貴重なヒープを、
内部用のプログラムで使ってしまうのは問題があるだろうと考え、
すべてNScripter側で実装しました。
実に1299 insertions, 940 deletionsという壮大な変更となりました。
(NScLisperのコードは4000行程度です)

ベンチマークに使ったfibの定義は次のようなものです。

(eval
 '(letrec ((fib
            (lambda (n)
              (if (<= n 1)
                  1
                  (+ (fib (- n 1)) (fib (- n 2)))))))
    (fib 12)))

evalでクォートされた式を評価しているのは、
式の変換などにかかる時間も含めるためです。
式の変換時間(の近似値)を図るために(fib 1)も計測しました。

なかなか良い感じです。(fib 1)も54msしか遅くなっていません。

リリカルLispを作り始めてもう6年になり、
私zickはいつの間にか大学生から不幸なことに社会人になってしまいましたが、
今後も可能な範囲でリリカルLispのメンテを続けていこうと思います。

--

と、ここまでの話だけを見ると
「de Bruijn indexを使うことによって速くなってよかったね！」
と錯覚してしまいそうになりますが、実は違うんです。
本当に、本当に悲しいのですが違うんです。

ver1.6まではifやdefineなどのスペシャルフォームを
FEXPRというオブジェクトとして表現していました。
式を評価する際にifといったシンボルが現れると、これを環境から探し出し、
FEXPRという事がわかったら、対応する処理が実行されるという感じです。
これらのスペシャルフォームは大域環境の末尾の方にあるため、
探索に結構な時間が掛かっていました。
上記fibなどは頻繁にifが現れるため、そのコストは顕著なものとなります。

一方、ver1.7ではFEXPRは無くなり、フォーム自身が特別扱いされるようになりました。
式を評価する際に(if ...)というフォームが現れると、
対応する処理が実行されるという感じです。
その際に環境からシンボルを探す処理は行われません。
また、ディスパッチの処理も簡略化され速くなります。

実は、今回の高速化の大部分は、
このスペシャルフォームに対する変更によりもたらされたもので、
de Bruijn indexはあまり速さに貢献していません。

あんまりな感じです。十分速いじゃないですか。
式の変換やコードウォークのための変更は千行以上。
FSUBRに対する変更はわずか数百行。
それでこの結果は泣きそうになってしまいます。

でもまあ、de Bruijn indexを付けて、
環境が連想リストからただのリストになったのが大事なのではなく、
コードウォークをできるようにしたのが大切だと考えてます。
これにより、変数を可能な限りスタックに置くような
最適化の下地が出来上がりました。
いつしか、大幅な高速化ができたら、と考えています。