Archive for 9月, 2013

リリカルLisp ver1.8

月曜日, 9月 16th, 2013

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

TL;DR: (fib 12)がver1.7と較べて3.2倍程速くなりました。無限ループやスタックオーバフローの際に強制終了ではなくエラーを返すようになりました。

ver1.7のリリース時に
「de Bruijn indexはあまり速さに貢献せず、スペシャルフォームへのアクセスをO(1)にしたのが効果的だった」
と書いている最中に気づいた
「それじゃあグローバル変数のアクセスをO(1)にしたら大幅に速くなるだろ」
という自明なことを実装したのがver1.8となります。
シンボルと値のペアを用意して、グローバル変数を参照する式を直接このペアを参照するように変換することでアクセス時間をO(1)にしています。ただし、式の変換の際にはペアのリストを線形探索するのでO(n)の時間(nはグローバル変数の個数)が必要となります。

肝心の効果のほどですが、
(define(fib n)(if (<= n 1)1(+(fib(- n 1))(fib(- n 2)))))
(fib 12)を評価したところ、ver1.7は16292ms、ver1.8は5097msとなりました。
約3.2倍です。馬鹿みたいに速くなりました。ver1.7とは何だったのか。

もう1つの大きな変更は、評価の安全な中断です。
これまでのバージョンでは、無限ループの(可能性がある)ときは、式の評価を中断するか尋ね、「中断する」が選択された場合はプログラム自体を終了していました。また、スタックオーバフローが起きた際には問答無用でプログラム自体を終了していました。
ver1.8ではプログラム自体を終了する代わりに、(Lispの値としての)エラーを返すように変更しました。

プログラム自体を終了するというのはあんまりなような気がしますが、最初のバージョンでは時間の関係からこのような仕様となっていました。
そして、その後は、面倒で放置し続けていたものをようやく直したという感じです。