Appendix 3. 継続についてもう少し

以下の文章は、以前継続について書いたものです。皆様の継続の理解に役立てば幸いです。

1. はじめに

Scheme の継続は大変強力だそうです。ただ、理解するのは大変難しく、実は紫藤もよくは理解していません。ここでは備忘録を兼ねて継続について詳しく説明しようと思います。

Scheme は言語体系は小さいのですが、それによってほとんどのプログラミング技法が表現できるように設計されています。他の言語に見られるような便利な機能は無いのですが、その分アルゴリズムを直接記述できるので主に教育用言語として使われています。有名な計算機プログラムの構造と解釈に記載されているプログラムは Scheme を用いて書かれています。なお、実用的には全く用いられないということは無く、 Practical Scheme に事例があります。

継続を除いて、Scheme 言語そのものを理解することは簡単で、 LISP 経験者なら半日で習得できると思います。独習 Scheme 三週間は Scheme の分かりやすい入門サイトです。紫藤もここで勉強しました。なお、入門書として Little Schemer も評判が良いようです。また、継続についての詳しい説明は何でも継続にあります。継続について悩んだ人は紫藤のほかにかなりいるみたいで、 google で検索するとたくさんヒットします。

このページのほとんどは上に挙げたページのパクリです。ただ、trace を使って継続をイメージするというアイデア（というほどのものではありませんが）はなぜか載っていませんでした。ちなみに、実装によっては trace が無い！こともあります。紫藤は trace が付いている Chez Scheme を使いました。

2. 継続の説明

継続は”トップレベルに戻るためにある時点からやる必要のある計算”のことです。継続は、計算プロセスに普遍的に存在していますが、ほとんどのプログラミング言語や OS では明示的に扱われることは無く、利用者が意識することはほとんどありません。そのため、ピンとこない方も多いと思います（実は私もその一人です）が、次の様なごく普通の計算でも継続は存在します。

>(* (+ 1 2) (- 10 5))       ............. (1)

(1) の計算で、(+ 1 2) の評価が終わった段階でしなければならない計算は、(+ 1 2) を [ ] で置き換えて表すと、
(* [ ] (- 10 5))
です。また、"2" の評価が終わった段階では、
(* (+ 1 [ ]) (- 10 5))
となります。 Scheme ではこういった"途中の計算" を call-with-current-continuation （略して call/cc) というオペレータを使って取り出すことが出来ます。

継続は、

大域脱出
（通常のループまたは再帰では処理しづらいデータ構造の）再帰的処理

をあらわすのに使われています。

3. call/cc の書式

call/cc の書式は以下の通りです。

(call/cc (lambda (cc) [cc を用いて何かをする。]))

ここで、cc はcall/cc が呼ばれた時点での計算の進行状況です。この値を保存しておくことによって将来の任意の時点で計算を再開させることが出来ます。例えば、上の (1) の場合、

(define *save* ())
(* (+ 1 (call/cc (lambda(cc) (set! *save* cc) 2))) (- 10 5))

として、 cc を *save* に保存すると、(* (+ 1 [ ]) (- 10 5)) （つまり、(lambda(x) (* (+ 1 x) (- 10 5)))　のようなもの）が、 *save* に保存されます。これ以降 *save* を使って計算が出来ます。

(*save* 2) => 15
(*save* 10) => 55

継続は、トップレベルに戻るためにしなければならない計算ですから、トップレベル以外で呼ばれたときは、その文脈を無視します。以下の例では 0 で割るという計算を無視しています。（これが、単なる関数と違うところです）

(*save* 5) => 30
(/ (*save* 5) 0) => 30

4. call/cc を用いた脱出

継続は文脈を無視してトップレベルに戻るので、大域脱出に使うことが出来ます。例えば、リストの要素の乗算をしたい場合、0 があったら、即座に計算を打ち切ることが出来ます。（この例は継続を説明するためにしばしば用いられます。）

(define ls*
  (lambda (ls)
    (call/cc
     (lambda (cc)
       (if (null? ls)
           1
         (let ((x (car ls)))
           (if (= 0 x)
               (cc 0)                           ;(2)-a
             (* x (ls* (cdr ls))))))))))        ;....................(2)

(2)-a で cc に 0 を渡しています。cc は call/cc が呼ばれたところまで、途中の文脈を無視して一気に脱出するので、ls* が呼ばれたところに即座に 0 が返ります。

ls* がトップレベル以外から呼ばれても動作します。例えば、

(define ls0 '(0 1 2 3 4 5))
(+ 100 (ls* ls0)) => 100

上の例では、cc の値は (+ 100 [ ]) となるので、ls* が関数として働いて、(ls* ls0) が 0 を返したと思って差し支えありません。関数全体を call/cc で包むという手法は、内部で call/cc を使う関数が、その呼び出し元へ値を返すために必要です。（重要）つまり、call/cc を使っている関数を普通の関数のように振舞わせたければ、全体を call/cc で囲む必要があるということです。

5. 階乗の計算

階乗の計算は、継続がソースコード上の構造ではなく、本当に計算の進行状況に関する情報を保持している例として用いられます。

(define *save* ())
(define fact
  (lambda (x)
    (if (= x 1)
        (call/cc
         (lambda (cc)
           (set! *save* cc)
           1))
      (* x (fact (- x 1))))))  ;........................................(3)

例えば、(fact 3)の場合、(* 3 (* 2 [ ])) が cc の値となります。

(fact 3) => 6
(*save* 1) => 6
(*save* 2) => 12

trace をして stack の様子を見てみると分かりやすいと思います。

> (fact 3)
|(fact 3)
| (fact 2)
| |(fact 1)
| |1      ; ここで、これ以降の計算を *save* に保持
| 2       ; (* 2 [ ])
|6        ; (* 3 (* 2 [ ]))
6

6. 継続を用いたツリーのトラバース

独習 Scheme 三週間にあるツリーのトラバース関数 (tree-traverser) を説明します。この関数は呼ばれるたびにツリー構造の葉を１つずつ前から順番に返す関数を返します。
使用例：

(define tr '((1 2) (3 (4 5))))
(define p (tree-traverser tr))
(p) => 1
(p) => 2
(p) => 3
(p) => 4
(p) => 5
(p) => ()  ; 最後に () を返す。

この関数の定義は以下の通りです。基本的には独習 Scheme 三週間にある tree->generator と同じですが（実は全く同じですが）、若干単純化しています。また、継続を表すシンポルに return, continue などの馴染みの単語を使うことで、コードを読みやすくしています。継続は直感的に分かりにくいので、分かりやすい単語を使うことで敷居が低くなることを期待しています。

01:     (define (make-traverser tree)
02:       (let ((return ()))                                                        ; 1
03:         (letrec ((continue                                                      ; 2
04:     	      (lambda ()
05:     		(let loop ((tree tree))                                     ; 3
06:     		  (cond                                                     ; 4
07:     		   ((null? tree) 'skip)                                     ; 5
08:     		   ((pair? tree) (loop (car tree)) (loop (cdr tree)))       ; 6
09:     		   (else                                                    ; 7
10:     		    (call/cc (lambda (lap-to-go)                            ; 8
11:     			       (set! continue (lambda () (lap-to-go 'restart)))    ; 9
12:     			       (return tree))))))                      ;10
13:     		(return ()))))                                         ;11
14:             (lambda ()                                                     ;12
15:               (call/cc (lambda (where-to-go)                               ;13
16:                          (set! return where-to-go)                         ;14
17:                          (continue)))))))

上のコードの説明：

脚注	説明
1.	局所変数 return を宣言。
2.	continue を letrec を使って宣言。 continue は現状での先頭の葉を返して、その時点での計算経過を次の continue にセットして停止する手続き。 letrec は let と同様に局所変数を宣言し、かつ 9. のように宣言ブロック内で宣言したシンボルを参照することが出来る。
3.	名前つき let を使って rec を宣言。名前つき let は Common LISP の labels にほぼ相当する。
4.	cond を使って処理を振り分ける。
5.	空リストの時は何もしない。
6.	リストのときはその car と cdr に対して rec を再帰的に適用。
7.	葉のときは、
8.	call/cc を呼び出して、途中経過 so-far を取得し、
9.	so-far を（次に呼び出す）continue にセットする。 so-far は、もともとの continue の定義に、その時点での変数、ネストの深さ etc が入ったもの。つまり、[ ] を使って表すと、 (lambda () (let rec ((tree tree0)) (cond ((null? tree) ()) ((pair? tree) (rec (car tree)) (rec (cdr tree))) (else [ ] (return ())))) が、入っていると想像できる。so-far が呼ばれた時点で (car tree) が葉の時の処理が終わったので、次は (rec (cdr tree)) が開始される。[ ] の処理が終わったところから計算が開始されるので、 [ ] は埋めなくてもいい。つまり、継続に引数を与えなくてもそのまま手続きとして計算が再開される。
10.	そして見つかった葉を呼び出し元に返す。(return tree) は call/cc の内側にある必要がある。もし、外側にあると次の計算が始まらない。
11.	全ての葉を調べつくしたら空リストを返す。
12.	make-traverser が返す traverse 関数。
13.	まず最初に call/cc を呼び出して、
14.	返す場所を return にセットする。see section 4。
15.	しかる後に continue を呼び出す。

make-traverser で作られた関数の動作は、通常の traverse 関数を書いて、それのトレースから推測できます。trace の * 印の所で計算がストップし、残りの計算は continue に保持されます。
通常の traverse 関数：

(define tree-traverse
  (lambda (tree)
    (cond
     ((null? tree) `_)
     ((pair? tree) (tree-traverse (car tree)) (tree-traverse (cdr tree)))
     (else
      (write tree)))))

tree が '((1 2) 3) のときの trace。

> (tree-traverse '((1 2) 3))
|(tree-traverse ((1 2) 3))
| (tree-traverse (1 2))
| |(tree-traverse 1)           
1| |#< void>               ; *
| (tree-traverse (2))
| |(tree-traverse 2)           
2| |< void>                ; *
| (tree-traverse ())
| _
|(tree-traverse (3))
| (tree-traverse 3)            
3| #< void>                ; *
|(tree-traverse ())
|_
_

7. おわりに

継続は、コードに現れない計算状態を保持したオブジェクトなので、自分が何をやっているのか視覚的にイメージするのが困難です。このような時、通常の動作をする関数を書き、そのトレースから継続の値を推測することによって継続がどのように働くかが視覚的に理解できるようになると思います。

Scheme は囲碁のような言語で、ルールは非常に単純ですが（つまり、言語自体の習得は半日ですみますが、）うまくやれるようになるには熟練が必要だと思います。特に、継続の理解は難しく、何でも継続で言われているように禅問答になります。継続はあまりに突飛なアイデアなので、理解するとはどういうことか？という哲学的な思索を我々に強います。

継続は理解するものではなく、慣れるものなのかもしれません。
例えば、

自転車が転ばない理由を理解しなくても自転車に乗れるように。子供のころ自転車がなぜ転ばないのかを理解しようとしてなかなか自転車に乗れなかった様に。
足し算の数学的意味についてほとんど知らなくても足し算が出来るように。また、計算機内部で足し算がどのようなビット処理によって実現されているかを全く考えずにプログラムが書けるように。我々が足し算を簡単に出来るのはそれについて理解しているからではなく小学校のころからやらされたのでただ慣れているだけのように。

などと、取り留めの無いことを書きましたが、結論としては
継続は習うより慣れろ
でしょう。つまり、”理解するとは慣れることである”となります。