リリカル☆Lisp開発日記

「コンピュータプログラミングの概念・技法・モデル」という本で、
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にも値が入っているという仕組みらしいです。
これはかなり衝撃的でした。
痺れる……

This entry was posted on 火曜日, 2月 19th, 2008 at 9:31 PM and is filed under プログラミング. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.