忍者ブログ

LAL 昭和な気まぐれ飛行機

LALのブログです。 http://eisl.kan-be.com/index.html

FAST末尾再帰最適化

EISLのコンパイラ、FASTの主要な機能の実装がなんとかものになってきました。本人にも予想外な速度を出せており、最適化前のSBCLを超える速度も出しています。覚書として、機能や考え方について記しておきたいと思います。


まずは、末尾再帰最適化です。EISLインタプリタはとても素朴な実装であり、簡単にスタックオーバーフローを起こしていました。ちょっと再帰が深くなると計算不能に陥っていました。ISLispの仕様には末尾再帰最適化は要求されていないのですが、FASTでは末尾再帰最適化を実装しています。

(defun dectail (n)
  (cond ((= n 0) t)
        (t (dectail (- n 1)))))

上記のコードはFASTでは繰り返しに変換されています。スタックは消費しません。

> (load "test.o")
T
> (dectail 1000000000)
T
>

この程度なら問題なく実行できます。また速度も高速です。

> (time (dectail 1000000000))
Elapsed Time(second)=1.717000
<undef>
>
PR

コメント

プロフィール

HN:
笹川
性別:
非公開

P R