Lispインタープリター「Liyad」における末尾再帰最適化

テクノロジー development 言語

拙作のLispインタープリター「Liyad」においても、 (無いとLisp処理系として格好が付かないので) 非常に限定的に末尾再帰最適化を実装しています。

Liyadにおける末尾再帰最適化

Liyadでは、単純にASTのS式が特定のパターン(1種類)に合致するときのみ末尾再帰最適化を行い、 関数の再帰呼び出しをループに展開します。

パターンの疑似コード:

($lambda (f-arg-1 ... f-arg-N)
    expr-a-1 ... expr-a-M
    ($if cond-expr
        expr-t
        ($self r-arg-expr-1 ... r-arg-expr-N) ))

これを次のようにASTを変換します。

疑似コード:

($lambda (f-arg-1 ... f-arg-N)
    ($until cond-expr
        ($clisp-let (tempsym-1 ... tempsym-N)
            expr-a-1 ... expr-a-M
            ($set tempsym-1 r-arg-expr-1) ... ($set tempsym-N r-arg-expr-N)
            ($set f-arg-1 tempsym-1) ... ($set f-arg-N tempsym-N) ))
    expr-a-1 ... expr-a-M
    expr-t )

手抜きですね。

一般的な処理系における末尾再帰最適化

当たり前ですが、if 以外の条件文(switch 等)でも最適化します。
また、静的に決定できるならば、関数のシンボル名に関係なく最適化してくれることでしょう (Liyadでは $self という名前で参照していなければ最適化しません)。
関数内の複数のコードパスのうち、1つ以上の末尾が自身の呼び出しであれば適用できます。
また頭の良いコンパイラならば、2つの関数が相互に呼び合っている場合も最適化します。

処理系によっては、何かしらの形 (キーワードやデコレーターの類) で明示的に指示する必要があります。

参考