On Lisp --- 継続

継続とは，動作中に凍結したプログラムだ．すなわち計算処理の状態を含んだ一つの関数的オブジェクトだ．保存された計算処理は，それが中断された時点から再開する．プログラムの状態を保存し，後に再開できる能力は，ある種の問題解決に素晴しい威力を発揮する．例えば並列処理では，中断されたプロセスを継続で表すのが便利だ．非決定的探索問題では，継続は探索ツリーのノードを表現できる．

継続の理解は難しいかも知れない．この章ではその話題に2段階で取り組む．この章の前半では継続の組込みサポートのあるSchemeでの用例を見る．継続の振舞を説明し終わったら，後半ではCommon Lispプログラムで継続を生成するマクロの使い方を示す．第22--24章のいずれでも，ここで定義したマクロを利用する．

Schemeの継続

Common Lispでシンボルの「シンボル値」と「シンボル関数」と呼ぶものをSchemeでは区別しない． Schemeの変数は単一の値を持つが，それは関数でも何らかのオブジェクトでもよい．そのため，シャープ・クォートやfuncallはSchemeでは必要ない． Common Lispのこのコードは，

(let ((f #'(lambda (x) (1+ x))))
  (funcall f 2))

Schemeでは次のようになる．

(let ((f (lambda (x) (1+ x))))
  (f 2))

Schemeの名前空間は1つだけなので，代入するためのオペレータがそれぞれ個別に（defunとsetqのように）存在しなくてもよい．代わりにdefvarに似たdefineと， setqの代わりになるset!が存在する．グローバル変数はdefineで定義してからでないとset!で値を設定できない．

Schemeでは名前の付いた関数は普通はdefineで定義される． defvarだけでなくdefunの役割もあるのだ． Common Lispのこのコードは，

(defun foo (x) (1+ x))

Schemeでは2通りに書ける．

(define foo (lambda (x) (1+ x)))
(define (foo x) (1+ x))

Common Lispでは，関数の引数は左から右の順に評価される． Schemeでは評価順は意図的に未定義とされた．（それを忘れた人間は慌てふためいて実装者の笑いものになる．）

tとnilの代わりに，Schemeには#tと#fがある．空リスト()を真に評価する処理系もあれば偽に評価する処理系もある．

オペレータcondではdefault節，オペレータcaseではキーelseが使えるが，これらはCommon Lispのtの役割を持つ．

組込みオペレータの名前が違う．conspがpair?でnullがnull?， mapcarは（ほぼ）mapに対応する，等．普通，文脈から違いは明らかだ．

\caption{SchemeとCommon Lispの相異点．} \label{fig:SomeDifferences}

SchemeとCommon Lispの主要な相異点には，継続を明示的にサポートする点がある．この節ではSchemeで継続がどのように動作するかを示す．（\reffig{fig:SomeDifferences}にはSchemeとCommon Lispの他の相異点を列挙した．）

継続は計算処理の未来を表現する関数だ．式が評価されるときには，必ず何かがその返り値を待っている．例えば次のコードで(- x 1)が評価された時点では，

外側の/式がその値を待っており，さらに別の何かが/式の値を待っている... 等が，printの待っているトップレベルまで延々と続く．

任意の時点の継続は，1引数関数と考えられる．上の例がトップレベルに打ち込まれたとき，部分式(- x 1)が評価された時点での継続は次のように考えられる．

すなわち計算処理の残りは(- x 1)の返り値を上の関数に与えることで模倣できる．また，式(- x 1)が次の文脈の中に現われており，f1がトップレベルから呼ばれた場合は，

Schemeでは，継続は関数と同格のファーストクラス・オブジェクトだ． Schemeでは現在の継続 (current continuation) を求めると計算処理の未来を表現する1引数関数が得られる．このオブジェクトは好きなように保存できるし，保存した継続を呼び出せば，それが生成された時点で始まろうとしていた計算処理を再開する．

継続はクロージャの一般化として理解できる．クロージャとは，関数とそれが生成された時点で見えていたレキシカル変数へのポインタをまとめたものだった．継続とは，関数とそれが生成された時点で溜っているスタック全体へのポインタをまとめたものだ．継続が評価されると，現在のスタックを無視し，それが保持しているスタックのコピーに基づいて値を返す．継続がT1で生成されT2で評価された場合， T1において溜っているスタックに基づいた評価が行われる．

Schemeプログラムは組込みオペレータcall-with-current-continuation（略してcall/cc）を通じて現在の継続にアクセスできる．プログラムがcall/ccを1引数関数に対して呼び出すと，

その1引数関数には現在の継続を表現する別の関数が渡される．上でccの値をどこかに保存することで，call/ccの時点での計算処理の状態が保存できる．

上の例では，最後の要素がcall/cc式の返り値であるようなリストにappendを適用している．

call/ccはaを返すが，最初に継続をグローバル変数frozenに保存する．

frozenを呼び出すと，call/ccの時点での古い計算が再開される． frozenに渡した値は，いずれもcall/ccの返り値になる．

継続は，評価されても消費はされない．他の普通の関数と同様，繰りかえし呼ぶこともできる．

継続を他の処理の内部で呼ぶとき，古いスタックに立ち戻ることの意味がはっきり見えるようになる．

ここでは，frozenが呼ばれると結果を待っている+は無視される． frozenは，最初に生成された時点で溜っていたスタックに従い，まずlist，次にappendを通じ，トップレベルまで戻る． frozenが普通の関数呼び出しと同様に値を返していたら，上の式は+が1をリストに足し算しようとしたことでエラーになっていただろう．

継続はスタックのコピーを個別に保持するのではない．他の継続や，進行中の計算処理と変数を共有できる．次の例では，2つの継続が同じスタックを共有している．

call/cc式の値は破棄されるので，froz1やfroz2に与える引数は何でもよい．

\caption{2つのツリー} \label{fig:TwoTrees}

さて，計算処理の状態を保存できるようになった訳だが，それで何をすればよいのだろう？第21--24章は継続を使うアプリケーションに充てられている．ここでは「保存された状態」を使うプログラミングの雰囲気がよく現われる単純な例を考えよう．ツリーの集合が与えられたとき，各ツリーから要素を1つずつ取って作ったリストを，何らかの条件を満たす組合せになるまで生成しよう．

ツリーは入れ子になったリストとして表現できる． grqページではある種のツリーをリストとして表現する方法を説明した．ここでは別の方法を使い，内部ノードが（アトムの）値を持て，任意個の子を持てるようにした．この表現では，内部ノードはリストになる． Car部はノードとしての値を保持し，cdr部はそのノードの子の表現を保持する．例えば\reffig{fig:TwoTrees}の2つのツリーは次のように表現できる．

(define (dft tree)
  (cond ((null? tree) ())
        ((not (pair? tree)) (write tree))
        (else (dft (car tree))
              (dft (cdr tree)))))

(define *saved* ())

(define (dft-node tree)
  (cond ((null? tree) (restart))
        ((not (pair? tree)) tree)
        (else (call-with-current-continuation
                (lambda (cc)
                  (set! *saved*
                    (cons (lambda ()
                            (cc (dft-node (cdr tree))))
                          *saved*))
                  (dft-node (car tree)))))))

(define (restart)
  (if (null? *saved*)
      'done
      (let ((cont (car *saved*)))
        (set! *saved* (cdr *saved*))
        (cont))))

(define (dft2 tree)
  (set! *saved* ())
  (let ((node (dft-node tree)))
    (cond ((eq? node 'done) ())
          (else (write node)
                (restart)))))

\caption{継続を使ったツリーの探索．} \label{fig:TraversalUsingCont}

\reffig{fig:TraversalUsingCont}にはそのようなツリーに対して深さ優先探索を行う関数を示した．実際のプログラムでは，ノードに行き着くごとにそれに対して何かの処理をしたくなる．ここでは単に表示するだけだ．比較に用いる関数dftは，通常の深さ優先探索を行う．

関数dft-nodeの方は，ツリーの辿り方は同じだがノードを個別に扱う． dft-nodeがノードに達すると，ノードのcar部に進み， cdr部を探索するという継続を*saved*にプッシュする．

restartを呼ぶと最後に保存された継続をポップして呼び出すことで探索が再開される．

最後に保存された状態が使い果たされると，restartはdoneを返すことでそれを知らせる．

最後に，関数dft2は上で手動で行っていたことをきれいに隠蔽する．

dft2の定義には明示的な再帰も反復もないことに注意．ノードが次々と表示されるのは，restartの呼び出した継続により，必ずdft-nodeの同じcond節にまで戻るからだ．

この種のプログラムは鉱脈のように働く． dft-nodeを呼び出すことで最初の穴を掘る．返り値がdoneでない限り，dft-nodeの呼び出しに続くコードはrestartを呼び，それが再びスタックに制御を送る．（訳注: このあたりは曖昧な表現が多くて意味不明）この経過はまで返り値が鉱脈は空であると知らせるまで継続する．その値を表示する代わりに，dft2は#fを返す．継続による探索は，プログラムに関する新たな考え方を表現している．適切なコードをスタックに入れ，繰りかえしそこに戻ることで結果を手にするのだ．

dft2のように一度に一つのツリーしか扱わないなら，この手法にこだわる理由はない． dft-nodeの利点は同時に複数の処理を進行させられることだ． 2つのツリーに対し，深さ優先探索で要素の直積を得たいとしよう．

普通の手法を使うと， 2つのツリーにおける位置を保存する段階を明示的に踏む必要がある．継続を使うと，2つの実行中の探索の状態は自動的に扱われる．このような単純な例では，ツリー中の位置を保存することは大して難しくない．ツリーは不変なデータ構造だから，ツリー内の「自分の場所」を把握する方法は少なくとも何かある．継続がすばらしいのは，対応する不変なデータ構造がない場合ですら，任意の計算処理の途中で容易に進み具合を保存できる点だ．計算処理の状態は，再開したいものが有限個である限り，有限個である必要すらない．

第24章で見るように，それらの考慮の両方がPrologの実装で重要だと分かる． Prologプログラムではプログラムが結果を生成する上での「探索ツリー」は実際のデータ構造ではなく，暗黙のものである．それらツリーはしばしば無限の大きさを持つが，その場合，あるツリー全体の探索を，別のツリーの探索の前に行うことは期待できない．どうにかして「場所」を保存する他に選択肢はないのだ．

継続渡しマクロ

Common Lispはcall/ccを提供しないが，少々の労力でSchemeと同じことができるようになる．この節では，マクロを使ってCommon Lispプログラムで継続を実現する方法を示す． Schemeの継続は2種類のものを提供してくれた．

レキシカル・スコープを持つLispでは，クロージャで第1の機能が得られる．実はクロージャを使って計算処理の状態も変数束縛に格納すれば第2の機能も得られることが分かる．

\reffig{fig:ContPassMacro}のマクロを使うと，継続を保存しつつ関数を呼び出せる．これらのマクロはCommon Lispで関数を定義したり呼び出したり，値を返すための組込みオペレータの代わりになる．

継続を利用したい関数（もしくは継続を利用する関数を呼びたい関数）は defunでなく=defunを使って定義する． =defunの構文はdefunと同じだが，機能は微妙に異なる．単に関数を定義するだけでなく，=defunは関数を定義し，その関数の呼び出しに展開されるマクロを定義する．（そのマクロは，関数が自分自身を呼び出す場合に備えて最初に定義しなければならない．）関数の本体は=defunに渡されたものになるが，引数リストには*cont*が追加される．マクロの展開形では，定義された関数は*cont*を他の引数と一緒に受け取る．よって次の関数定義は，

add1を呼ぶとき実際に呼ばれるのは関数でなくマクロだ．マクロは関数呼び出しに展開される \footnote{=defunにはインターンされた名前が意図的に使われるが，それはトレースできるようにするためだ．トレースが必要でないと分かっていれば，名前にgensymを使うのが安全だろう．} が，引数*cont*を1つ余計に受け取っている．

よって=defunで定義されたオペレータの呼び出しの際には，その時点での*cont*の値が必ず渡される．

(setq *cont* #'identity)

(defmacro =lambda (parms &body body)
   `#'(lambda (*cont* ,@parms) ,@body))

(defmacro =defun (name parms &body body)
   (let ((f (intern (concatenate 'string
                                          "=" (symbol-name name)))))
       `(progn
            (defmacro ,name ,parms
               `(,',f *cont* ,,@parms))
            (defun ,f (*cont* ,@parms) ,@body))))

(defmacro =bind (parms expr &body body)
   `(let ((*cont* #'(lambda ,parms ,@body))) ,expr))

(defmacro =values (&rest retvals)
   `(funcall *cont* ,@retvals))

(defmacro =funcall (fn &rest args)
   `(funcall ,fn *cont* ,@args))

(defmacro =apply (fn &rest args)
   `(apply ,fn *cont* ,@args))

\caption{継続渡しマクロ．} \label{fig:ContPassMacro}

*cont* は何のためにあるのか？それは現在の継続に束縛される． =valuesの定義を読むとその継続の使い方が分かる． =defunで定義された任意の関数は=valuesを使って制御を戻すか，, それを行う別の関数を呼ばなければいけない． =valuesの構文はCommon Lispの組込みオペレータvaluesと同じだ．多値を返すには，=bindに同じ数の仮引数を与えておく．しかしトップレベルに多値を返すことはできない．

仮引数*cont*は，=defunで定義された関数に，返り値に対して何を行うかを伝える． =valuesがマクロ展開されると*cont*を捕捉するようになり，それによって関数から戻ることをシミュレートする．次の式は，

トップレベルでは*cont*の値はidentityだ．これは渡された値をそのまま返す関数だ．トップレベルから(add1 2)を呼ぶと，それは等価な次のコードに展開される．

*cont* の参照はこの場合グローバルな束縛を持つ． =values式は等価な次の式に展開される．

add1などの関数では， we go through all this trouble just to simulate what Lisp function call and return do anyway:

大事なのは，今や私達は独自に制御できる関数呼び出しと戻りreturnを手にしており，他のこともその気になればできるということだ．

継続の効果は，*cont*を通じて利用する． *cont* はグローバルな値を持ってはいるが，グローバルな値そのものが使われることはまずない． *cont* はほとんど常に=valuesや=defunで定義されたマクロに捕捉される仮引数だ．例えばadd1の内部では*cont*は仮引数でグローバル変数ではない．この区別が重要なのは，これらのマクロは*cont*がローカル変数だからこそ機能するからだ．だからこそ*cont*に初期値を与えるためにdefvarでなくsetqを使っている． defvarではスペシャル変数を定義することになってしまう．

\reffig{fig:ContPassMacro}の3番目のマクロ=bindは， multiple-value-bindと同様の用途を想定している．引数には仮引数のリスト，式，実行部本体となるコードを取る．仮引数は渡された式の返り値に束縛され，その下で本体コードが評価される． =defunで定義された関数の呼び出し後に付加的な式が評価されなければいけないときにはこのマクロを使わなければいけない．

=bindの展開形は新変数*cont*を作っていることに注意． bazの本体は次のようにマクロ展開される．

*cont*の新しい値は=bind式の本体になるので， *cont*にfuncallを適用することでmessageから「戻る」ときには，結果は「コード本体を評価すること」になる．しかし（ここが大事なのだが）=bindの本体内では次のようになっており，

=bazに引数として渡された*cont*が見えるままなので，コード本体が=valuesを評価する番になると，元の呼出側関数に戻ることができる．クロージャは互いに縫い合わされている: *cont*の個々の束縛は*cont*の以前の束縛を含むクロージャで，グローバルな値に戻ってゆくまでの連鎖を形成する．

この例ではgへの参照を含むクロージャを作っているが， gそのものもfへの参照を含むクロージャである．これと似たクロージャの連鎖が，xezページのネットワーク・コンパイラによって生成される．

残りのマクロ=applyと=funcallは=lambdaで定義された関数と共に使う． =defunで定義された「関数」は実際はマクロなので， applyやfuncallの引数に使えないことに注意．この問題の解決策はldtページで触れたトリックに似ている．つまり呼び出しを別の=lambdaの内部にくるんでしまう．

(=defun foo (x)
        (=bind (y) (bar x)
               (format t "Ho ")
               (=bind (z) (baz x)
                      (format t "Hum.")
                      (=values x y z))))

\caption{継続渡しマクロに付随する制限．} \label{fig:RestrictionsContPassMacros}

\reffig{fig:RestrictionsContPassMacros}には継続渡しマクロによって生じる制限をまとめた．継続を保存しないし，継続を保存する関数を呼び出しもしない関数は，これらのマクロを使う必要はない．例えばlistなどの組込み関数は除かれる．

(defun dft (tree)
  (cond ((null tree) nil)
        ((atom tree) (princ tree))
        (t (dft (car tree))
           (dft (cdr tree)))))

(setq *saved* nil)

(=defun dft-node (tree)
        (cond ((null tree) (restart))
              ((atom tree) (=values tree))
              (t (push #'(lambda () (dft-node (cdr tree)))
                       *saved*)
                 (dft-node (car tree)))))

(=defun restart ()
        (if *saved*
            (funcall (pop *saved*))
            (=values 'done)))

(=defun dft2 (tree)
        (setq *saved* nil)
        (=bind (node) (dft-node tree)
               (cond ((eq node 'done) (=values nil))
                     (t (princ node)
                        (restart)))))

\caption{継続渡しマクロを使ったツリーの探索．} \label{fig:TreeTraversalUsingContPassMacros}

\reffig{fig:TreeTraversalUsingContPassMacros}は， \reffig{fig:ContPassMacro}のSchemeコードをCommon Lispに直したものを含み，継続渡しマクロをSchemeの継続の代わりに使っている．同じ例のツリーに対してdft2は全く同様に動作する．

複数の探索の状態を保存するのもSchemeと同様に機能するが，例は少し長くなる．

レキシカル・クロージャの連鎖をつなぎ合わせることで， Common Lispプログラムでも独自の継続を作ることができる．うまいことに， \reffig{fig:ContPassMacro}の込み入ったマクロによってクロージャはつなぎ合わされており，ユーザは実現過程を想像する必要はなく，きれいな側面だけを見ていればよい．

第21--24章はいずれもある意味で継続に依存している．これらの章では，継続がすさまじい力の抽象化であることを示す．継続は，特にあるプログラミング言語上のマクロとして実装された場合には，最高に速いとは言えない．しかしそれらを利用して行える抽象化により，ある種のプログラムははるかに速く書けるようになり，そのような速度のプログラムも重宝する場合というものはある．

Code-WalkersとCPS変換

前節で説明したマクロは妥協の産物だ．継続の力が得られるが，それはプログラムを特定の形で書いたときに限られる． \reffig{fig:RestrictionsContPassMacros}のルール4によれば，必ず次のようにしなければならず，

本物のcall/ccはプログラマにそのような制限を課すことはない． call/ccは任意の時点で任意の形のプログラムの継続を取り出せる． call/ccの力の全てを実現するオペレータを実装することもできるが，それにはさらに手間がかかるだろう．この節ではその方法の概要を示す．

Lispプログラムは「継続渡しスタイル」という形に変換できる．完全にCPS変換を施したプログラムは読めたものではないが，部分的に変換されたコードを読むことでその過程のエッセンスを掴むことはできる．次の関数はリストを逆転させるものだが，

継続渡しスタイルでは，関数には引数（ここではk）が余分に増える．その値は継続になる．継続は，その関数の現在の値を使って何をすべきかを表現するクロージャだ．再帰の最初の段階では継続は恒等関数だ．何をすべきかと言えば，関数は現在の値をそのまま返せばよい．再帰の第2段階では，継続は次と等価だ．

つまり，何をするべきかと言えば，リストのcar部を現在の値に付加して返すということだ．

CPS変換を覚えればcall/ccを書くのは簡単だ． CPS変換を経たプログラムでは，全体に対する現在の継続が常に存在し， call/ccはその引数として何らかの関数を呼び出す単純なマクロとして実装できる．

CPS変換には，code-walker, すなわちプログラムのソースコードを表現するツリーを探索するプログラムが必要になる． Common Lispに対するcode-walkerを書くのはひどい骨折りだ．使えるものになるには，code-walkerは単に式を探索するだけでは済まず，．その式の意味もかなり理解できなければならない．例えば，code-walkerはシンボルだけを考えていれば済むものではない．シンボルが表現するのは，いくつか挙げると，シンボル自身，関数，変数，ブロック名，goのためのタグなどだ． Code-walkerは文脈からシンボルの種類を判別し，それに従って動作しなければならない．

Code-walkerを書くのはこの本の範囲を超えるので，この章で説明したマクロは実用的な代理品に過ぎない．この章のマクロは継続を構築する仕事をユーザと分担して行う．ユーザがCPSに十分近いプログラムを書けば，残りはマクロがやってくれる．第4の規則は本当はそういうことだ． =bindの後に続く処理がその本体内にあれば， *cont*の値と=bindの本体内のコードの間で，プログラムは現在の継続を作るための十分な情報を得ることができる．

マクロ=bindはこのスタイルのプログラミングを自然に思わせる意図を持って書かれた．実際には継続渡しマクロの課す制限は我慢の範囲内だろう．