継続とcall/cc

継続とは、一言で言うと「その後にやる苓の仕事」である。

たとえば、(+ 3 (* 1 2))を入力すると Scheme はまず+を評価する。

この時点での継続は、「3を評価し、(* 1 2)を評価した後、その結果を+に適用する」である。

+を評価したら、Scheme は次に 3を評価し、* を評価する。

*を評価する時点での継続は「1を評価し、2を評価し、その結果に3を加えて返す」となる。

このように Scheme の式の評価中には常にその時点での継続というものを考えることができる。

この継続を評価の途中で登録しておく命令がcall/ccである。

ただし、処理系によっては下の宣言が必要なものもある。

(define call/cc call-with-current-continuation)

たとえば、下のような式の中で、式 (* 1 2)を評価する時点での継続を登録するには、式をさらに下のように変更する。

(+ 3 (* 1 2))
(+ 3 (call/cc (lambda (cont) (* 1 2))))

(* 1 2)の内部では変数contを使うことができる。contは一引数関数で、たとえば下のように使うことができる。

(+ 3 (call/cc (lambda (cont) (* (cont 1) 2))))

この contは (* 1 2)の実行時の継続を聞く。すなわち、「結果に3を加えて返す」である。

これを関数として内部で使うと、その引数に与えたものの本来の継続を忘れ、contを継続として適用する。

つまり、*を評価したあと、(cont 1)を評価しようとするが、ここで1を「結果に3を加えて返す」に適用し、式全体の結果を求める。

> (+ 3 (call/cc (lambda (cont) (* (cont 1) 2))))
4

継続の効果的な使い方の一つが、例外処理である。たとえば、下の関数を考える。

これは数値のリストを受け取って、その積を求める関数である。

(define (multiply-list1 lst)
  (define (multiply lst2)
    (cond ((null? lst2) 1)
          (else (* (car lst2) (multiply (cdr lst2))))))
  (multiply lst))
> (multiply-list1 '(1 2 3 4))
24

しかし、リスト中に一つでも0があれば、結果は必ず0なので残りを見る必要もないし、0が出てくるまでの掛け算をする必要もない。

そこでcall/ccを使って次のように書き換える。

(define (multiply-list2 lst)
  (call/cc (lambda (cont) ; 抜ける先を cont にとっておいて
    (define (multiply lst2)
      (cond ((null? lst2) 1)
            ((= 0 (car lst2)) (cont 0)) ; 0 だったら、いきなり0を返す
            (else (* (car lst2) (multiply (cdr lst2))))))
    (trace multiply) ; trace で観察
    (multiply lst))))

確かに、0が出てきた時点で計算を中断している。

> (multiply-list2 '(1 2 0 3 4))
| > (#<procedure #x1B6772> '(1 2 0 3 4))
| | > (#<procedure #x1B6772> '(2 0 3 4))
| | | > (#<procedure #x1B6772> '(0 3 4))
0
>

一覧 前へ 次へ