Ozと末尾再帰の最適化

コンピュータプログラミングの概念・技法・モデル」という本で、
Ozというプログラミング言語の説明を見ていたら、驚かされる記述がありました。
それは、ただの、素朴なmapの定義です。

fun {Map Xs F}
case Xs
of nil then nil
[] X|Xr then {F X} | {Map Xr F}
end
end

独特な記法の言語なので、Schemeで書き直すと、次のようなものです。

(define (map xs f)
(cond ((null? xs) '())
(else (cons (f (car x))
(map (cdr x) f)))))

このプログラムですが、末尾再帰に書き直されて、
反復構造になるらしいです。
リストを構成する途中で再帰呼び出しをしているため、
普通は末尾再帰の形に直らないだろうと思っていたのですが、
Ozの場合、このプログラムが以下のように直せるようです。

proc {Map Xs F Ys}
case Xs of nil then nil
else case Xs of X|Xr then
local Y Yr in
Ys = Y|Yr
{F X Y}
{Map Xr F Yr}
end
end
end

procは手続きの定義で、第三引数Ysは参照渡しで結果が格納されます。
『Ys=Y|Yr』とすることにより、CAR部がY、CDR部がYrのコンスをYsに格納しますが、
この時点でYとYr(という識別子の指す変数)は束縛されていません。
しかし、これはOzの上では全く問題ありません。
続く、二つの手続き呼び出しにより、YとYrに値が格納され、
結果として、Ysにも値が入っているという仕組みらしいです。
これはかなり衝撃的でした。
痺れる……

2 Responses to “Ozと末尾再帰の最適化”

  1. スーパー浪人生 より:

    Prologみたいだお・・・
    ところで、{Map Xr F}は {Map Xr F Yr}じゃないすか?

  2. zick より:

    >スーパー浪人生さん
    ご指摘ありがとうございます。
    修正しておきました。

Leave a Reply