Shiro Kawai
shiro****@lava*****
2004年 5月 15日 (土) 19:44:36 JST
ご指摘の通り、「呼び出して戻って来ない」というモデルは、計算過程の 説明にはなりますが、その計算を利用するためには、どうにかして計算の 結果を得る必要があります。そして、(lambda (x) x) が実際に計算の 結果を得るための終端点になります。 末尾呼び出しのことなどを考えずに、普通の手続き型モデルで考えると、 (lambda (x) x) は引数をそのまま「返す」関数ですね。 従って、CPS形式で書かれた手続きに継続として (lambda (x) x)を 渡してやると、ずーっと計算が進んで最後まで行った時にその時点での値が (lambda (x) x) で「折り返されて」、次々と戻って来る、というような イメージになります。 但し、それはひとつの解釈にすぎません。「手続き呼び出しにスタックを使う機械」 というモデルに当てはめた場合に、(lambda (x) x) は「引数を返り値として 返す」という動作をする、というだけです。 プログラムの解釈方法はそのモデルだけではありません。 「計算そのものを全て継続渡し形式で行う機械」というモデルも考えられます。 その場合、(lambda (x) x) は「それまでの計算結果をどこか(例えばレジスタ) に置いて計算を止める」という意味になります。 「((lambda (x) M) N) を見たら、 Mの中に表れるxをNで置き換える」 というモデルもあります。そういうモデルを使ってもCPSは同じように 定義できて、(lambda (x) x) が終端点として使えます (*)。 従って、「最後に何が起こるか」という話の具体的な答えは、どのような 計算機モデルを想定しているのかによって違って来ます。が、どのモデルを 採るにせよ、「『CPSなプログラムの値を得る』ということは、ある特別な 終端点を継続として渡してプログラムを評価することである」と抽象化 できるということです。 > でも、その他のドキュメントでは、処理の途中のあるポイントをみたとき、その > 関数は最後に引数に継続を適用する式で締めくくっている、その書き方が CPS > だ、とも読めます。 > > それから、そもそも、自分が read-eval-print-loop の中にいる時は終りってな > んだ? という話もありますね。 はっきりしているのは、「CPSプログラムの値を得る＝終端点(lambda (x) x)を プログラムに渡して評価する」ということです。従って、何かのバイナリを起動して それが標準出力に結果を書き出すことをもってそのプログラムの値を得ることだと するなら、終端点オペレータは具体的には値を標準出力に書き出してプロセスを終わる、 ということになるでしょうし、read-eval-print-loopのようにプロンプト に対して打ち込まれた式を評価して値を表示する場合は、打ち込まれた式 を評価器に放りこむ時に、「結果を印字して再びプロンプトを出す」という 動作を終端点オペレータとして渡す、という解釈になります。 「値を得るとはどういうことか」という具体的な動作は実装者次第、というわけです。 プログラムとしてrepl自体を含むようなモデルは、 Mattias Felleisen, The theory and practice of first-class prompts, POPL 1988 でフォーマルに議論されています。上の(*)で示したモデルの話も説明されています。 --shiro
