Schemeの継続とcall/cc

前置き

継続(continuation)についてのメモです。継続と聞くと大域脱出(longjmp)を連想してしまう私には、The Little Schemerに出てくるmultirember&coの"co"がcontinuationの略だと言われても、ピンと来ませんでした。しかし本来、継続は「後続の処理」のような意味なので、別にジャンプを伴う必要はないんですね。

下記のサイトが参考になりました。

本文

継続渡しスタイル(CPS: Continuation Passing Style)

API関数の引数で別の関数を渡しておいて、後でコールバックしてもらうなんてのは、別に珍しくないと思いますが、実はこれがCPSです。例えばAJAXでは、GETリクエスト送信のAPI関数に無名関数を渡して、レスポンス受信後に呼んでもらいます。ここで渡す無名関数には、HTTP通信の後続の処理(つまり継続)を実装しておきます。

もっとシンプルな例として、加算と乗算をCPSで書くと、こんな感じです。

gosh> (define +_cps (lambda (a b co) (co (+ a b))))
|+_cps|
gosh> (define *_cps (lambda (a b co) (co (* a b))))
*_cps

どちらも、第3引数で継続を受け取り、それを和(あるいは積)に適用します。これらを使って、(1+2)*5+1を計算するには以下のように書きます。

gosh> (+_cps 1 2 (lambda (x) (*_cps x 5 (lambda (y) (+_cps y 1 (lambda (z) z))))))
16

The Little Schemerのmultirember&coは、これを応用したもと言えるでしょう。

cc(current-continuation)

Schemeには、call-with-current-continuation(省略形はcall/cc)という関数があります。直訳すると「その時点の継続と共に(この関数を)呼べ」でしょうか。より関数型っぽく言えば、「その時点の継続に(この関数を)適用しろ」です。いずれにしろ、call/ccの引数は関数で、その関数の引数はその時点の継続です。でも、「その時点の継続(current-continuation)」って何でしょうか?

先ほどの、(1+2)*5+1を例にしてみましょう。もうCPSのことは忘れて下さい。

gosh> (+ (* (+ 1 2) 5) 1)
16

このとき、Schemeは、以下の順で評価しているはずです。

  1. 1と2に+を適用
  2. その結果と5に*を適用
  3. その結果と1に+を適用

この手順の任意の時点で、それより後ろの処理のことをcurrent-continuationと呼びます。例えば、手順1の時点でのccは、手順2と手順3です。

では、手順1のところでcall/ccを呼んでみましょう。

(+ (* (call/cc ???) 5) 1)

???の部分は……。call/ccの引数には、ccを引数に取る関数を指定する必要があります。例えば、下記のような関数です。

gosh> (define foo (lambda (cc) (cc (+ 1 2))))
foo

では、もう一度。

gosh> (+ (* (call/cc foo) 5) 1)
16

fooは、1と2の和に仮引数ccを適用する関数です。その関数にcall/ccを適用しました。手順1のところでcall/ccを適用したので、その時点の継続は手順2と手順3です。つまりfooの実引数は手順2と手順3です。1と2の和に、手順2と手順3を適用するので、結局、(1+2)*5+1を計算するのと同じことですね。

call/ccの性質

ここで、もう少しcall/ccの性質を掘り下げてみます。まず、call/ccの引数に渡す関数はその場で呼ばれるという点に注意しましょう。なので、下記の2つは同じことです。このことを理解しておくと、call/ccを使った複雑なコードを読むのが少し楽になると思います。

gosh> (+ (* (+ 1 2) 5) 1)
16
gosh> (+ (* (call/cc (lambda (cc) (+ 1 2))) 5) 1)
16

上記のコードでは、無名関数は引数ccを使ってないので、call/ccを使う意味がありません。ccを何かに適用してこそのcall/ccです。無名関数の中でccを適用すれば、どんなにネストの深いところからでも、call/cc適用の所までジャンプしてきます(具体的な例は次節で示します)。

また、ccをグローバル変数に退避しておいて、後から適用することも可能です。

gosh> (define k '())
k
gosh> (+ (* (call/cc (lambda (cc) (set! k cc) (+ 1 2))) 5) 1)
16

どこでkを適用しようと、call/ccした時点にジャンプして後続の処理を行います。ここでの後続の処理とは、「5を掛けて1を足す」です。

gosh> (k 3)
16
gosh> (+ (* (+ 3 4) (k 8)) 10)
41

上記の最後のコードでは、3+4の結果と掛けたり、10を足すといった処理を捨てて、8*5+1の結果が表示されています。もし、8にkを適用する時点のccを別のグローバル変数に退避しておけば、捨てたはずの処理に戻ってくることも可能です(これも具体例は次節で)。

call/ccの応用

call/ccの応用例として、大域脱出と生成器を示します。前述のサイトに載っているものと同じコードです。

大域脱出

数値リストに含まれる全ての数値の積を計算するとき、リストに0が含まれていたら、その時点で答えは0に決まります。残りの乗算はスキップして0を返したいですね。これは、以下のように書けます。

(define list-product
  (lambda (lis)
    (call/cc
      (lambda (exit)
        (let recur ((l lis))
          (if (null? l) 1
              (if (= (car l) 0) (exit 0)
                  (* (car l) (recur (cdr l))))))))))

exitがccです。0にexitを適用することにより、call/ccの直後(つまりlist-productの出口)へジャンプします。

gosh> (list-product '(3 2 1))
6
gosh> (list-product '(9 8 0 7 6 5))
0

生成器

生成器(generator)は、何かの値を生成しつづける関数です(無限に続くとは限りませんが)。例えば、呼ぶたびにフィボナッチ数列の数を1つ返すとか、乱数を返すとかですね。あるいは、Namihei、Fune、Masuo、…と、サザエさん一家の名前を順に返すとか。

下記のコードは生成器を作る関数です。この関数に任意のツリーを渡すと、そのツリーの葉(leaf)を生成する生成器を返します。

(define mk-leaf-generator
  (lambda (tree)
    (let ((gen-to-client '()))
      (letrec ((client-to-gen
               (lambda (x)                            ;;gen
                  (let loop ((tree tree))
                    (cond
                     ((null? tree) 'skip)                       ;;①
                     ((pair? tree) (loop (car tree))            ;;②
                      (loop (cdr tree)))
                     (else (call/cc (lambda (cc)                ;;③
                                      (set! client-to-gen cc)   ;;☆
                                      (gen-to-client tree)))))) ;;★
                  (gen-to-client '()))))                        ;;★
        (lambda ()                                    ;;client
          (call/cc (lambda (cc)
                     (set! gen-to-client cc)
                     (client-to-gen 'start))))))))

使い方は、以下のような感じです。

gosh> (define leaf-generator (mk-leaf-generator '(a (b c) d (e (f g)))))
leaf-generator
gosh> (leaf-generator)
a
gosh> (leaf-generator)
b
gosh> (leaf-generator)
c
gosh> (leaf-generator)
d
gosh> (leaf-generator)
e
gosh> (leaf-generator)
f
gosh> (leaf-generator)
g
gosh> (leaf-generator)
()

mk-leaf-generatorが作る生成器は、大きく分けて2つの無名関数(無名ですが仮にgenとclientと呼びます)で構成されています。ユーザが呼ぶのがclientで、実際に値(leaf)を生成するのがgenです。そして、相互にジャンプし合えるように、グローバル変数(gen-to-clientとclient-to-gen)にccを退避します。genは引数xを取りますが使いません。

generator

このような構成をとることにより、genは、値を生成することに専念できます。実際のところ、genの仕事は以下の3つです。

  1. treeを走査(traverse)する
  2. 葉を見つけたら、(その時点のccを退避したうえで)その葉をclientに通知する
  3. 走査が終わったら、空リストをclientに通知する

ここで、「clientに通知する」というのは、gen-to-clientを呼んでいる箇所(★印の箇所)のことです。

genの構造を図示すると、こんな感じです。

gen

  • まずloopがあり、木を走査しながら、condで3分岐する
  • 木が空なら走査終わりで、loopを抜ける(①)
  • 木が枝ならcar部とcdr部について再帰(②)
  • 木が葉なら、(ccを退避したうえで)それをclientへ通知(③)
  • loopから抜けた場合、もう走査終了なので、()をclientへ通知

一方、clientは、ただ単に(ccを退避したうえで)client-to-genを呼ぶだけです。client-to-genの初期値にはletrecによりgenがセットされていますが、その後は☆印の箇所でccがセットされます。よって、leaf-generator(つまりclient)を2回目に呼ぶときは、genの途中(③のcall/ccの箇所)へジャンプすることになります。

genは決して終わりません。上記の例の場合、ツリー走査の最後の方でtreeが(g)になり、cond分岐の②で(car tree)がg、(cdr tree)が()になります。car部の処理でgをgen-to-clientする直前にccを退避しますが、これが最後のcc退避です。この時点の「後続の処理」は、「else節の評価(car側のloopの最後)が終わり、cdr側のloopの最後を評価し(その結果は'skip)、let loopが終わって、gen-to-clientを呼んでclientへ()を通知する」ことです。もうclient-to-genは変更されないので、これ以降は、何度leaf-generatorを呼んでも、この「後続の処理」が行われるので、clientには()が通知されます。

最後に、シンプルな木 '(a (b c))を例に、genが木を走査する様子を図示します。

tree

丸数字はcondの分岐経路を示し、四角はclientへの通知を示しています。再帰する(つまりloopの周回数が変わる)箇所で色を変えています。②に分岐する箇所では、car部とcdr部に対する再帰を(同じ色で)左右に並べました。client-to-genが最後に更新されるのは、cを通知するときです。よって、それ以降は何度leaf-generatorを呼んでも、ここへ戻ってきて、()が通知されます。

Last modified:2013/04/21 10:50:46
Keyword(s):
References:[FP: 関数型プログラミング]
This page is frozen.