16. 継続

1. 初めに

今回は Scheme の特徴的なデータ型である継続について説明します。このデータ型は他のプログラミング言語には無いので理解するのは易しくないかもしれません。とりあえず、感じをつかんでいただければ結構です。

この文書では、まず一般的な継続について説明し、それから Scheme の継続について説明します。多くの解説書ではまず Scheme の継続について説明してから、継続渡しスタイルについて説明していますが、先に継続渡しスタイルについて説明したほうが、なぜ Scheme に継続というデータ型があるのかがわかりやすいと思います。

2. 継続とは

継続とはトップレベルに戻ってくるまでにしなければならない計算です。

実は、継続は計算過程において普遍的に存在しますが、明示的に扱われることが少ないため、なじみのない概念になっています。例えば、[example 1] を見てみると、 (+ 1 2) を評価した後にしなければならない計算（すなわち継続）は 3 を掛ける { (* 3 []) } となります。

[example 1]

(* 3 (+ 1 2))

3. 継続渡しスタイル

3.1. 簡単な継続渡しスタイル

継続渡しスタイルとは、関数が、値を返す代わりに、計算した値をどの関数に渡すのかを明示的に指定する方法です。継続渡しで書いた足し算と掛け算は [code 1] のように書けます。 k は引き続いて実行する関数です。

[code 1]

(define (return x)
  x)

(define (k+ a b k)
  (k (+ a b)))

(define (k* a b k)
  (k (* a b)))

[code 1] の関数を使って [example 1] と同じことをやると以下のようになります。

[example 2]

(k+ 1 2 (lambda (x) (k* x 3 return)))

通常の式 [example 1] の外側にあったものが、 CPS [example 2] では内側にきているのがわかります。 [example 2] で、k+ は (+ 1 2) を評価した結果を (lambda (x) (k* x 3 return)) に引渡し、k* は (* (+ 1 2) 3) の結果を return に引き渡しています。

継続渡しスタイル (continuation passing style) は略して CPS と呼ばれることがあります。

3.2. 再帰関数の継続渡しスタイル

再帰関数も継続渡しスタイルで書くことができます。まず、階乗の計算を継続渡しスタイルで書いてみます。

[code 2]

;;; normal factorial
(define (fact n)
  (if (= n 1) 
      1
      (* n (fact (- n 1)))))

;;; CPS factorial
(define (kfact n k)
  (if (= n 1) 
      (k 1)
      (kfact (- n 1) (lambda (x) (k (* n x))))))

上の [code 2] の fact が通常の書き方、 kfact が継続渡しスタイルです。 4 の階乗に 3 を足すという計算は [example 3] の様になります。

[example 3]

;;; normal
(+ 3 (fact 4))

;;; CPS
(kfact 4 (lambda (x) (k+ x 3 return)))

また、数のリストの積を計算する関数は [code 3] の様になります。継続渡しスタイルでは 0 を掛けたとき即座に抜け出せるように初めの引渡し先を break という局所変数に保存しておきます。

[code 3]

;;; normal
(define (product ls)
  (let loop ((ls ls) (acc 1))
    (cond
     ((null? ls) acc)
     ((zero? (car ls)) 0)
     (else (loop (cdr ls) (* (car ls) acc))))))

;;; CPS
(define (kproduct ls k)
  (let ((break k))
    (let loop ((ls ls) (k k))
      (cond
       ((null? ls) (k 1))
       ((zero? (car ls)) (break 0))
       (else (loop (cdr ls) (lambda (x) (k (* (car ls) x)))))))))

'(2 4 7) の積に 100 を足す計算は [example 4] の様になります。

[example 4]

;;; normal
(+ 100 (product '(2 4 7)))

;;; CPS
(kproduct '(2 4 7) (lambda (x) (k+ x 100 return)))

さて、このような簡単な例では継続渡しスタイルのありがたみはわかりませんが、評価の内容によって処理を振り分けたいときは通常の記法より簡潔になることがあります。そのため、継続渡しスタイルは自然言語解析、論理プログラムなどに良く用いられます。

処理を振り分ける簡単な例として例外処理を挙げておきます。以下の例は、kproduct を改良して、数値以外のものが混じっているとそれを表示するプログラムです。

[code 4]

       
(define (non-number-value-error x)
  (display "Value error: ")
  (display  x)
  (display " is not number.")
  (newline)
  'error)


(define (kproduct ls k k-value-error)
  (let ((break k))
    (let loop ((ls ls) (k k))
      (cond
       ((null? ls) (k 1))
       ((not (number? (car ls))) (k-value-error (car ls)))
       ((zero? (car ls)) (break 0))
       (else (loop (cdr ls) (lambda (x) (k (* (car ls) x)))))))))

[example 5]

;;; valid
> (kproduct '(2 4 7) 
	  (lambda (x) (k+ x 100 return)) 
	  non-number-value-error)
156

;;; invalid
> (kproduct '(2 4 7 hoge) 
	  (lambda (x) (k+ x 100 return)) 
	  non-number-value-error)
Value error: hoge is not number.
error

4. Scheme の継続

以上の説明で継続がどんなものか大体わかったと思います。継続は、

全ての計算に存在し、
関数型言語であれば、継続渡しスタイルで継続を明示的に取り扱うことができます。

また、上記の例を見てもわかるように継続はクロージャの連鎖です。

しかし、継続渡しスタイルでプログラムを読み書きするのはわずらわしいので、通常の書き方のプログラムで継続を扱えると便利です。

そこで、Scheme では継続はファーストクラスオブジェクト（つまり普通の変数）として実装されており、 call-with-current-continuation という関数を使って任意の時点での継続を取り出すことができます。また、取り出した継続は好きなだけ再利用することができます。

call-with-current-continuation の省略形 call/cc も R⁶RS および、ほとんどの実装で用意されています。タイプが楽なので、多くの場合 call/cc の方が用いられます。

call-with-current-continuation (call/cc) は 1 引数の関数で引数に現在の継続を引数とする関数をとります。以下に使い方の例を示します。

(* 3 (call/cc (lambda (k) (+ 1 2)))) ⇒ 9          ; [ 1 ]
(* 3 (call/cc (lambda (k)  (+ 1 (k 2))))) ⇒ 6     ; [ 2 ]

[ 1 ] では継続が呼ばれていないので普通の式と同じです。一方、[ 2 ] では継続 k が呼ばれて、それに 2 が与えられます。そうすると、途中の計算は飛ばして、call/cc の外側に 2 が返ります。つまり、k は 1 引数の関数で、この場合は
(lambda (x) (* 3 x))
と等価です。つまり、k には call/cc の外側からトップレベルに戻るまでの道順が保存されています。

k は他のデータと同様に保存しておいて、後で何度でも使うことができます。

(define cc)
(* 3 (call/cc (lambda (k)
                 (set! cc k)
                 (+ 1 2))))

継続はトップレベルに戻るまでの道順ですから、どこかの式の中に置かれたとき、途中の式を無視して、保存された手続きに従ってトップレベルまで戻ってきます。

(+ 100 (cc 3)) ⇒ 9 
(+ 100 (cc 10)) ⇒ 30

4.1. call/cc を使った大域脱出

一番わかりやすい使い方は継続を使った大域脱出でしょう。 [code 5] は木（ネストしたリスト）の中に obj があれば #t を返し、無ければ #f を返す関数です。 obj が見つかると、一番外側に一気に脱出します。

[code 5]

(define (find-leaf obj tree)
  (call/cc
   (lambda (cc)
     (letrec ((iter
	       (lambda (tree)
		 (cond
		  ((null?  tree) #f)
		  ((pair? tree)
		   (iter (car tree))
		   (iter (cdr tree)))
		  (else
		   (if (eqv? obj tree)
		       (cc obj)))))))
       (iter tree)))))

[example 6]

(find-leaf 7 '(1 (2 3) 4 (5 (6 7))))
⇒ 7

(find-leaf 8 '(1 (2 3) 4 (5 (6 7))))
⇒ #f

また、大域脱出用の構文 block を定義すると [code 6] のようになります。

[code 6]

(define-syntax block
  (syntax-rules ()
    ((_ tag e1 ...)
     (call-with-current-continuation
      (lambda (tag)
	e1 ...)))))

以下の様に使います。

[expample 7]

(block break
   (map (lambda (x)
           (if (positive? x)
	       (sqrt x)
	       (break x)))
	'(1 2 3)))
⇒ (1 1.4142135623730951 1.7320508075688772)

(block break
   (map (lambda (x)
           (if (positive? x)
	       (sqrt x)
	       (break x)))
	'(1 -2 3)))
⇒ -2

4.2. generator

独習 Scheme 三週間にあるツリーの葉を呼ばれるたびに１枚ずつ返す関数を説明します。この関数を使うとツリーの比較が容易になります。

使用例：

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

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

[code 7]

001:   (define (leaf-generator tree)
002:     (let ((return '()))                                                       ; 1
003:       (letrec ((continue                                                      ; 2
004:                 (lambda (x)
005:                   (let loop ((tree tree))                                     ; 3
006:                     (cond                                                     ; 4
007:                      ((null? tree) 'skip)                                     ; 5
008:                      ((pair? tree) (loop (car tree)) (loop (cdr tree)))       ; 6
009:                      (else                                                    ; 7
010:                       (call/cc (lambda (lap-to-go)                            ; 8
011:                                  (set! continue lap-to-go)                    ; 9
012:                                  (return tree))))))                           ;10
013:                   (return '()))))                                             ;11
014:               (lambda ()                                                      ;12
015:                 (call/cc (lambda (where-to-go)                                ;13
016:                            (set! return where-to-go)                          ;14
017:                            (continue 'start)))))))

上のコードの説明：

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

leaf-generator で作られた関数の動作は、通常の 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 '())
|_
_

4.3. コルーチン

継続は、これから行う計算を覚えているので、継続を利用すると複数のタスクを並列して行わせる、いわゆるコルーチンを書くことができます。 [code 7] は数字とアルファベットを交互に表示するプログラムです。 5--22 行目までは待ち行列を実装しています。 (enqueue! queue obj) で obj を待ち行列 queue の最後に追加し、 (dequeue! queue) で、queue から先頭の要素を取り除き、先頭の要素を返します。 Scheme での待ち行列の実装については http://www-ui.is.s.u-tokyo.ac.jp/~hara2001/scheme/material/4/4.mtd.column.html を見てください。

コルーチンの実装は 26--38 行です。

process-queue: プロセスの待ち行列です。
(coroutine thunk): thunk を process-queue の末尾に加えます。
(start): process-queue の先頭の要素を取り出して実行します。
(pause): 現在の継続を process-queue の末尾に追加し、process-queue の先頭の要素を実行します。この関数によって、制御が他のコルーチンに移ります。

42--61 行目は使用例です。数字を表示するルーチンとアルファベットを表示するルーチンが交互に呼び出しあい、[example 8] のような結果を得ます。 process-queue に優先度をつけると優先度の高いプロセスから実行することができます。興味のある人は試してみてください。

[code 8]

001:   (require rnrs/control-6)
002:   
003:   
004:   ;;; this imprementation of queue is MzScheme specific.
005:   (define (make-queue)
006:     (mcons '() '()))
007:   
008:   (define (enqueue! queue obj)
009:     (let ((lobj (mcons obj '())))
010:       (if (null? (mcar queue))
011:   	(begin
012:   	  (set-mcar! queue lobj)
013:   	  (set-mcdr! queue lobj))
014:   	(begin
015:   	  (set-mcdr! (mcdr queue) lobj)
016:   	  (set-mcdr! queue lobj)))
017:       (mcar queue)))
018:   
019:   (define (dequeue! queue)
020:     (let ((obj (mcar (mcar queue))))
021:       (set-mcar! queue (mcdr (mcar queue)))
022:       obj))
023:   
024:   
025:   ;;; coroutine   
026:   (define process-queue (make-queue))
027:   
028:   (define (coroutine thunk)
029:     (enqueue! process-queue thunk))
030:   
031:   (define (start)
032:      ((dequeue! process-queue)))
033:      
034:   (define (pause)
035:     (call/cc
036:      (lambda (k)
037:        (coroutine (lambda () (k #f)))
038:        (start))))
039:   
040:   
041:   ;;; example
042:   (coroutine (lambda ()
043:   	     (let loop ((i 0)) 
044:   	       (when (< i 10)
045:                    (display (+ 1 i)) 
046:                    (display " ") 
047:                    (pause) 
048:                    (loop (+ 1 i))))))
049:   		   
050:   (coroutine (lambda ()
051:   	     (let loop ((i 0)) 
052:   	       (when (< i 10)
053:   		     (display (integer->char (+ i 97)))
054:   		     (display " ")
055:   		     (pause) 
056:                    (loop (+ 1 i))))))
057:   
058:   (start)
059:   (newline)

[example 8]

> (load/cd "callcc.scm")
1 a 2 b 3 c 4 d 5 e 6 f 7 g 8 h 9 i 10 j

5. 終わりに

以上で継続の使い方の説明を終わります。よくわからなくても気にしないでください。だんだんわかるようになります。

次回は遅延評価について説明します。