継続について更に考える
世界の隅で誰ともなしに書いた先日のエントリに、光の速さでコメントが書き込まれていてちょっとビックリ＆わざわざありがとうございます ＞ id:practicalscheme, id:hominato
コメントを解釈
とりあえず、頂いたコメントそのままだと、まだちょっと理解が及ばないので、無い知恵を絞ってコメントを解釈してみる。
id:practicalscheme 氏のコメントは:
Schemerからすると話が逆で、継続渡しの方がモデルとして先にあって、スタックを使う通常の手続き呼び出しはその特殊例の最適化戦略なのです。だから継続を説明しようとすると継続渡しの話になってしまうのかもしれません。
継続渡しはあくまで計算過程のモデルで、その実装としてスタックを使うこともでき、現実のScheme処理系もスタックはスタックのまま継続を実装しています。動的に継続渡し形式のようなコードを生成するわけではありません。(コンパイラの実装方式としてソースを一度継続渡し形式に変換するというものはありますが。マシンコードに落ちる段階では単なるスタック操作になります)
なのだけれど、ここでの「スタック」は全てが同一の意味合いで書かれているわけでは無いような気が。
多分私が、継続実装方式の予想として:
スタック等に代表される「実行コンテキスト」情報を保存しておく。継続実施の際にはコンテキストを復旧して実行を再開。
と書いてしまったのに対して、お二方が合わせてくれたのではなかろうか、と勝手に解釈。
上記の私の記述における「スタック」は、あくまで「実行コンテキスト」の格納先の one of them であって、「スタック」という形式／領域に対しては、あまりこだわっていません。ゴミ集め (GC) で言うところの「ルートセット」(root set) をイメージしています。
大学時分に、「ヒープ上に実行コンテキストを構築」する言語処理系を題材にして、ゴミ集めの研究をやっていたことがあるので、id:hominato 氏の言う以下のモデルは、比較的違和感が無い感じ。
実装方法から極力離れた見方をするなら、スタック的なメモリ管理は一切なく全てがヒープ上に永遠に残り続けている、ただしどこからも見えなくなったデータや見えなくなった呼び出しコンテクストは密かに回収してくれる(GC+末尾最適化)のでメモリリークの心配はいらない、みたいな理解でもいいかもしれません。
で、id:practicalscheme 氏のコメントに戻ると、まず最初の:
Schemerからすると話が逆で、継続渡しの方がモデルとして先にあって、スタック(1)を使う通常の手続き呼び出しはその特殊例の最適化戦略なのです。だから継続を説明しようとすると継続渡しの話になってしまうのかもしれません。
上記部分における「スタック」は、手続き型言語的な「呼び出し元に戻る」処理の実現方式として、戻りアドレスを FILO で積むためのデータ格納形式としての「スタック」、というニュアンスが強いような気がする。
その次の:
継続渡しはあくまで計算過程のモデルで、その実装としてスタック(2)を使うこともでき、現実のScheme処理系もスタックはスタックのまま(2)継続を実装しています。
という部分における「スタック」は、「一時的／局所的なコンテキストを保存」するための「領域」としての「スタック」、というニュアンスではなかろうか、と。
(1) の「スタック」が FILO であることを重視している一方で、(2) の「スタック」は「一時的／局所的な領域確保」を重視しているイメージと言えば良いのかな？(2) にとっては、メモリ管理上の利便性等に問題が無ければ、id:hominato 氏の言うような「ヒープ」に格納するモデルでも構わないぐらい。
で、最後の:
マシンコードに落ちる段階では単なるスタック操作(3)になります
という部分における「スタック」は、これまでの「スタック」が「Scheme プログラム」にとっての「Scheme 処理系」上の「スタック」であるのに対して、「Scheme 処理系」にとっての「CPU アーキテクチャ」上の「スタック」というニュアンスの気が。
ひょっとしたら、(2) と (3) は同意かも？という気もしていて、それならそれでOKです。
で、以下は上記の解釈が合っているという前提で。
コメントを元に継続について考える
例えば「なんでも継続」においては、以下のような「与えられた木の全ての葉の数を数える関数」に対して:
(define (leaf-count tree) (if (pair? tree) (+ (leaf-count (car tree)) (leaf-count (cdr tree))) 1))
これを「継続渡し」化した結果として、以下のコードを示している。
(define (leaf-count/cps tree cont) (if (pair? tree) (leaf-count/cps (car tree) (lambda (n) (leaf-count/cps (cdr tree) (lambda (m) (cont (+ n m)))))) (cont 1)))
この「継続渡し」化したものが Schemer にとっては「モデルとして先にある」っていうのは、ちょっと無くねぇ？っていうか、普通に呼び出し元に戻ってくる形式で考えた方が楽じゃねぇ？
と、最初は思ったのだけれど、「なぜSchemeにはreturnが無いのか」での「変数束縛っていうのは本質的にはlambda」であり「共通するパターンに気づき、リファクタリングして異なる部分だけをクロージャでパラメタライズ」するのは Schemer にとってはごく自然な行為、というくだりを読むと、Schemer ならそういった変態チック別な視点での見方をしててもおかしくないかも？と思えてきた(笑)。
しかも、一旦「そういう見方もあるなぁ」と思ってしまったら、まるで「自転車に乗れるようになった」時みたいに、何かもう、そういう見方が普通な気も！ (← ちょっと誇張)
とはいえ、処理としての等価性とか、モデルの妥当性に対する論理的な裏付けという点では、確かに「継続渡し」による説明の方が妥当なのかもしれないけれど、「継続」によって実現される事象に対して、簡易なメンタルモデルを提示しようとするなら、やっぱり「ルートセットと実行位置の保存／復旧」的なものの方が妥当な気がするなぁ。
まぁ、(1) Scheme をある程度使えて、(2) 「継続」に関する詳細を知りたいと思っている層を説明対象として想定するなら、一般的なメンタルモデルよりも、「継続渡し」を元にした論理的裏付けを元にした説明の方が妥当じゃね？という判断は、Schemer の変人パラメタライズ中毒振りからすると、確かに肯定せざるをえないかもなぁ、という気もするのだが、せめて Schemer じゃない人(＝ 初学者とか、単にまだ Scheme を知らない人)が「Scheme とかで実現されている継続ってモノは一体どんなものなのよ？」と興味を持った時に、継続渡しで煙に巻かれないルートがあると嬉しいのだけれど。
