継続に関する感想 - 算術の夢の楽園

どうもAaronです。

今回はちょっと継続について考えていて思ったことがあるので書きます。

証明どころか解説ですらないどころか感想なので決して真に受けぬよう。

1.束縛付き継続スタック付きマシン

束縛付き継続スタック付きマシンとはTuring完全なマシン $\it M$ (マシンモデルはここではあまり重要ではない)と「引数を表す $\it M$ のデータ(値)(ラムダ計算ならラムダ項、帰納的に定義された関数やレジスタ機械なら自然数…)の可変長リストと継続( $\it M$ のプログラム、関数…etc)の組が積まれるスタック $\it S$ 」と「束縛(シンボルと $\it M$ のデータの組)のリスト $\it B$ 」の組 $({\it M},{\it S},{\it B})$ である。

$\it M$ が行う処理は「原始的な処理」と「処理の合成」に分けられる。

直感的には原始的な処理は組み込み関数、処理の合成はユーザー定義の関数である。

$\it M$ は $\it B$ の環境下で挙動し、 $\it S$ に積まれた処理を上から順に実行する。原始的な処理ならばそれは直ちに実行され、逆に処理の合成ならばそれはより簡単な処理に分解され $\it S$ に積まれ、それぞれの処理の結果を表すために「衝突のないシンボル」が予約される。従って処理の合成はそれ単体として解決されるものではないが、再び同じ場所まで $\it S$ が進行したとき処理の合成が終了したとみなす。このため、ある原始的な処理の終了が処理の合成の終了でもあるという事が起きる。さらに言えばある原始的な処理の終了によって複数の処理の合成が同時に終了することもある。実在機械の実装上は $\it S$ に処理の合成を分解したことを表すマーカー(呼び出しマーカーとでも呼ぶことにしよう)を積むことでこれを実装するかもしれない。

原始的な処理であれ、処理の合成であれ実行を終わるとその返り値を「事前に予約された衝突のないシンボル」に束縛するように(こうしておかないと多変数関数の呼び出しで複数の関数コールが同時に発生したときとかに困る。) $\it B$ を更新し、 $\it S$ をポップし新たな処理を行う。

(e.x.

(f (g x) (h y) (i z) 4)

なら

$\it S$

(g x)

(h y)

(i z)

(f temp1 temp2 temp3 4)

という感じにスタックに積まれて処理される。

)

ある処理がほかの処理の合成に分解されるか、それ以上分解できないものとして(一般には値を返して)スタックから取り除かれるかはそのモデルに依存する。

このモデルの下でいくつかのプログラミング言語の概念を説明してみよう。

2.動的寿命

「衝突のない予約されたシンボル」に束縛された値がもう呼び出されないとわかったならそれを $\it B$ から取り除いても問題ない。GCがあるような実用プログラミング言語においてはこれを管理して「もう呼び出されない(動的寿命を終えた)」値を $\it B$ から取り除く。

3.副作用

$\it M$ に $\it B$ を強制的に変更するような挙動があることをゆるすならば、そのような挙動を副作用と呼ぶ。(例：定義、代入…etc)

4.継続に関する副作用

$\it M$ に $\it S$ を強制的に変更するような挙動があることをゆるすならば、そのような挙動を継続に関する副作用と呼ぶ。(例:call/cc、条件分岐(後述))

5.継続による条件分岐

理論的には「ラムダ計算による『純粋関数型的な』if」や「再帰的に定義された関数による『純粋算術的な』if」が可能であるにも関わらず、ほとんどのプログラム言語では利便や簡単性のためそのようなifではなく、継続のダイナミックな変更によるifを実装している。そのため理論と異なり関数型言語で副作用やcall/ccを用いないコードであってもifの内側を先に評価してよいことにはならないのである。

6.末尾再帰最適化

末尾再帰最適化とは「処理の合成」がスタック上で分解されたときにスタックの容量を節約するため、ある処理の合成Pの解決中、Pを構成する処理のうち構文上「最後に処理される」処理P’を呼び出したときP'の呼び出しマーカーと引き換えにPの呼び出しマーカーをオミットしてしまうことである。これによりP’がPの本来の継続から呼び出されたのと同等になる。