Haskell で callCC 関数 - 「継続渡しスタイル」をつなげた計算を途中で破棄する

1. Haskell で callCC の定義を考える

これまで Haskell による「継続渡しスタイル」の計算と、その計算を「つなげる」関数について見てきた。

今回は、「継続渡しスタイル」をつなげた計算の流れをコントロールする関数である

callCC

について考える。

a. callCC 関数の大雑把なイメージ

はじめに、定義したい関数の大雑把なイメージをしておく。

前回までの復習

「継続渡しスタイル」の計算では、関数が「目的とする結果」を単純に返さない。関数が「目的とする結果」を得るために必要な引数に加え、「目的とする結果を与える関数」を引数に与えることにより、「目的とする結果」の利用先を指定する。

「継続渡しスタイル」の関数に、「目的とする結果」を得るために必要な引数を与えたときの関数の型は、

(a –> r) –> r

型変数 a が「目的とする結果」。関数 a –> r は「目的とする結果を与える関数」。

型が複雑なので、この型に対して別名を付けておく。

type Cont r a = (a -> r) -> r

先回、このような型の計算を「つなげる」 comb 関数を定義した。型のみ示す。

comb :: Cont r a -> (a -> Cont r b) -> Cont r b

comb 関数は、「継続渡しスタイル」の計算を「つなげた」結果、再び「継続渡しスタイル」の計算になるように定義した。そのため、同じ comb 関数を使い、「継続渡しスタイル」の計算を次々につなげていくことができる。

callCC の動作イメージ

今回、定義したい callCC 関数は、計算の流れを分岐させることを目的とする。「つながっている計算」における「任意の時点の計算結果」を、別の計算へとつなげる。

b. モナドについて考えない

callCC 関数は Control.Monad.Cont.Class に定義されている。

Continuation モナドによると、

MonadCont クラスは callCC 関数を提供します．この関数は，Continuation モナド用の脱出継続機構を提供するものです．脱出継続は現在の計算を中断し，即座に値を返します．これにより，Error モナドでの throwError および catchError に類似した効果が得られます．

callCC の定義は、以下のように示されている。

callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

ここではモナドについて考えず、「継続渡しスタイル」の計算をつなげ、「つなげた計算を途中で脱出する」という観点から、callCC がなぜこのように定義されているかについて考える。

2. Scheme における call/cc の動作を確認する

予め Scheme における call/cc について確認しておく。

Scheme では、計算の「任意の時点における継続」を取り出すことができる。継続を取り出すための手続きは

Call-with-current-continuation

略して、

call/cc

と呼ばれる。

Scheme の特徴的は、計算を「継続渡しスタイル」で記述しなくても、call/cc により通常の計算式に対して、任意の時点で継続を取り出せること。

Scheme 入門 16. 継続には、一般的な「継続渡しスタイル」の計算と比較しながら、「Scheme の継続」と call/cc について、次のように述べられている。

継続はクロージャの連鎖です。

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

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

a. call/cc を使わない計算式

例えば、次の簡単な計算を元にして、call/cc の動作を確認する。

(display
 (- (* (+ 1 2) 3) 4))   ;=> 5

Scheme は「内側の括弧から外側へ」と評価がされる。そのため、上記の式は次の順序で計算が進む。

1 + 2 => 3
3 * 3 => 9
9 – 4 => 5

それぞれの演算子に対応した「計算方法」と「結果」があり、結果が「後続の計算」に与えられる、と見なせる。

b. 「継続」を呼び出さない場合

先ほど述べたように、Scheme では「継続渡しスタイル」で計算を記述しなくても、任意の時点における「継続」を call/cc で取り出すことができる。

例えば、上記の計算に対して、次のように call/cc を呼び出し、「継続」を取り出すことができる。

(display
 (- (call/cc
     (lambda (exit)
       (* (+ 1 2) 3)))
    4))   ;=> 5

この call/cc 手続きにより取り出された「継続」は、

「ある値から 4 を引いた結果を表示する」

こと。Scheme の call/cc 手続きは、「継続」が call/cc に与えるラムダ式の「引数」に与えられる。（ここでは引数 exit ）

上記の計算の場合、ラムダ式本体で「継続」 exit の呼び出しを行なっていない。このとき、ラムダ式本体を評価した結果が返される。計算は先ほどと同じように、次の順序で行われる。

1 + 2 => 3
3 * 3 => 9
9 – 4 => 5

call/cc により継続を取り出したが、継続を全く活用していない。

c. 「継続」を呼び出す場合

次に、継続を call/cc に与えたラムダ式本体で呼び出す場合の動作を確認する。

(display
 (- (call/cc
     (lambda (exit)
       (* 
        (exit (+ 1 2)) 
        3)))
    4))   ;=> -1

先ほどと違い、「 1 と 2 を足した結果」から、「 4 を引いた結果が表示」された。

注目する点は、call/cc に与えたラムダ式本体にある「 3 をかける計算」が行われなかったこと。継続 exit を呼び出すことにより、計算が途中でキャンセルされ、実行位置がジャンプしたように見える。

計算は次の順序で行われる。

1 + 2 => 3
3 – 4 => –1

先ほどの計算と比べると、

1 + 2 => 3
~~3 * 3 => 9~~ ← この式の実行がキャンセルされた
3 – 4 => –1

d. call/cc のまとめ

call/cc 手続きの呼び出しをまとめると、call/cc の評価結果を次のように見なせることが分かる。

call/cc に与えるラムダ式の本体において、

「継続」が呼び出されない場合、ラムダ式本体が通常通り評価され、その結果が call/cc を呼び出した結果となる。そのため、call/cc 手続きの呼び出しがあってもなくても計算結果は同じ。
「継続」が呼び出される場合、継続に与える値が call/cc を評価した結果となる。

3. Haskell で callCC を定義する

Scheme の call/cc 手続きを参考にして、Haskell で同じような関数を定義したい。

繰り返すが、Scheme では通常の計算に対して、call/cc により「任意の時点における継続」を取り出すことができる。「継続渡しスタイル」の計算を明示的に記述し、継続を扱う必要はない。

Haskell では、通常の計算に対して、継続を取り出す関数は用意されていない。そのため、Scheme のように継続を扱うためには、「継続渡しスタイル」の計算において考えなければならない。

Scheme の call/cc 手続きに相当する関数を Haskell で定義するには、「継続渡しスタイル」の計算の「つなげ方」をコントロールすることにより実現する。

a. callCC に与える引数について

Scheme の call/cc に相当する関数を、Haskell で callCC 関数として定義する過程を考える。

最初に call/cc 手続きに与えるラムダ式に注目する。先ほどの Scheme の例（「継続」を呼び出す場合）を再掲。

(display
 (- (call/cc
     (lambda (exit)
       (* 
        (exit (+ 1 2)) 
        3)))
    4))   ;=> -1

ここで、以下の点について確認しておく。

call/cc に与える引数は「関数」である。
その関数は「一つの引数（ここでは exit ）」をとる。
引数 exit には call/cc を呼び出した時点の「継続」が与えれる。
「継続」は、値を一つとる関数である。

4. 「継続」を適用しない場合

次に、Scheme で call/cc 手続きに与えるラムダ式本体で、「継続を呼び出さない」場合を参考にしながら、Haksell の callCC の定義を考えていく。

(display
 (- (call/cc
     (lambda (exit)
       (* (+ 1 2) 3)))
    4))   ;=> 5

まずは、この関数と同じ内容の計算を Haskell で定義してみる。

a. Haskell で継続渡しスタイルの計算

先ほど述べたように、Scheme では継続渡しスタイルで call/cc 手続きを考えなくても良い。しかし、Haskellでは「継続渡しスタイル」で考えなければならない。

予め、「継続渡しスタイル」にする関数と、「継続渡しスタイル」を「つなげる」関数が、以下のように定義されているとする。

ret x = \k -> k x
comb m n = \k -> m (\x -> n x k)

cf. 「継続渡しスタイル」の計算をつなげる関数

また、上記の関数を元に、継続渡しスタイルの「足し算・かけ算・引き算」が用意されているとする。

add_cps x y = ret $ x + y
mul_cps x y = ret $ x * y
sub_cps x y = ret $ x - y

b. callCC 関数を適用した場合を想像する

そして、callCC 関数を次のように使うと想定する。

main = print $ ((callCC $ \exit ->
                 add_cps 1 2 `comb` \x ->
                 mul_cps x 3) `comb` \y ->
                sub_cps y 4) id

最初に callCC 関数に与えられる「無名関数」に注目。

\exit –> …

これより、callCC 関数に与える引数 f を想定できる。

callCC f =

この「無名関数」の引数 exit が callCC 関数を適用した後の「継続」を導く。

exit 関数を適当な値に適用すると、
callCC 関数を適用した後の「継続」に値を与え、
exit 関数以降の計算はキャンセルされる。

という仕組みを考えていく。

c. callCC の定義

上記の「無名関数」の引数は１つ ( exit ) なので、次のような形で定義できる。

callCC f = f ◯

ここでは ◯ の中身について、とりあえず考慮しない。

繰り返すが、 Haskell では「継続渡しスタイル」の計算の「つながり」に対して callCC 関数の定義する。

もし、callCC 関数を適用した結果、「継続渡しスタイル」の型が返されるなら、その結果に対して更に計算をつなげることができる。つまり、callCC 関数を適用した結果、「継続渡しスタイル」が返されると都合が良い。よって、次のように定義する。

callCC f = \k -> f ◯

問題は「継続」である引数 k を、何に対して適用するのか？それとも、何に対して与えるのか？ということ。

ここでもし、

 f ◯

の結果が「継続渡しスタイル」として返されることが保証されるなら、callCC 関数の引数 k を

 f ◯

によって生成された「継続渡しスタイル」の計算に与えることにより、callCC 関数の後にくる計算へとつなげることができる。

callCC f = \k -> f ◯ k

上記の計算では、引数 exit を callCC 関数の中で適用していない。そのため、◯ の型がどのようなものであっても、最終的な結果に影響を与えない。

d. 具体例で確認する

ここまで定義で、具体的な式を定義で置き換え、動作を確認する。

(callCC $ \exit -> add_cps 1 2 `comb` \x -> mul_cps x 3)
=> \k -> (\exit -> add_cps 1 2 `comb` \x -> mul_cps x 3) ◯ k
=> \k -> (add_cps 1 2 `comb` \x -> mul_cps x 3) k
=> \k -> (\k -> k 9) k
=> \k –> k 9

f ◯ の結果が「継続渡しスタイル」であれば、exit 関数を適用しない場合、◯ の中身は何でも良いことが分かる。

そのため、◯ に相当する式としてどのような値を与えても、この場合、計算に影響を与えない。例えば、◯ の代わりに undefeined を与えても答えを求めることができる。

callCC f = \k -> f undefined k

5. 「継続」を適用する場合

次に、Scheme で call/cc 手続きに与えるラムダ式本体において、「継続を呼び出す」例を参考にしながら、callCC 関数の定義を考えていく。

先ほどの Scheme の例を再掲する。

(display
 (- (call/cc
     (lambda (exit)
       (* 
        (exit (+ 1 2)) 
        3)))
    4))   ;=> -1

これを Haskell で「継続渡しスタイル」にして書きなおすと、以下のようになる。

main = print $ ((callCC $ \exit ->
                 add_cps 1 2 `comb` \x ->
                 exit x      `comb` \y ->
                 mul_cps y 3) `comb` \z ->
                sub_cps z 4) id

今回は、callCC 関数に与える無名関数の引数である exit を、callCC 関数に与えた無名関数の中で適用している。そのため、先ほどの callCC 関数の定義では思うような結果は得られない。

callCC f = \k -> f undefined k

とりあえず undefined として、保留していた部分を考えなければならない。

a. exit 関数の役割

ところで、この undefined は、callCC 関数を適用した場合、exit 関数に与えられる。

exit 関数の役割は、exit 関数を値に適用したら、

その値が callCC 関数の「後に続く計算」（継続）に与えられること。 … 【条件A】
exit 関数を適用した「後に続く計算」を破棄すること。 … 【条件B】

【条件A】より、callCC 関数の「後に続く計算」を表す引数 k に「値を渡す」関数を想定できる。

callCC f = \k –> f (\x –> k x) k

しかし、この定義ではコンパイルエラーとなる。なぜなら、【条件B】が満たされていないため。

b. 後続の「継続」を破棄する

では、どのような定義にすれば、【条件B】を満たすことができるのだろう？

もう一度、「継続渡しスタイル」について、簡単な例で考えてみる。

main = print $ (add_cps 1 2 `comb` \x ->
                mul_cps x 3) id  -- 9

ここでは、２つの「継続渡しスタイル」の計算をつなげている。この２つの計算の間に、次のような「継続渡しスタイル」の計算を挿入してみる。

main = print $ (add_cps 1 2 `comb` \x ->
                (\k -> k x) `comb` \y ->
                mul_cps x 3) id  -- 9

新たに挿入した「継続渡しスタイル」の計算は、全体の計算に影響を与えない。

これに対して、「継続」に値を与えないように式を変更すると、結果として挿入した「継続渡しスタイル」の x の値が返される。なぜなら、後続する計算に中間結果を与えないため。

main = print $ (add_cps 1 2 `comb` \x ->
                (\k -> x)   `comb` \y ->
                mul_cps x 3) id  -- 3

変数 k は使われないので、ワイルドカードで良い。

main = print $ (add_cps 1 2 `comb` \x ->
                (\_ -> x)   `comb` \y ->
                mul_cps x 3) id  -- 3

確認のため、この式を定義で置き換えてみる。

add_cps 1 2 `comb` \x -> (\_ -> x) `comb` \y -> mul_cps x 3
=> (\_ -> 3) `comb` \y -> mul_cps x 3
=> \k -> (\_ -> 3) (\x -> (\y -> mul_cps x 3) x k)
=> \k -> 3

「継続」に値を与えないことにより、後続の計算が破棄されたのが分かる。

次に、上記の式を exit 関数を与える test 関数として定義しなおしてみる。

test exit = (add_cps 1 2 `comb` \x ->
             exit x      `comb` \y ->
             mul_cps x 3) id

先ほどと同じように、途中で「継続」を破棄するためには、test 関数に次の無名関数を与えれば良い。

main = print $ test (\x -> \_ -> x)

callCC の定義に戻る。先ほどコンパイルエラーとなったのは、下記の式だった。

callCC f = \k –> f (\x –> k x) k

これを「後続する継続を破棄するときに与えた無名関数」を真似て、次のように変更する。

callCC f = \k –> f (\x –> \_ –> k x) k

これにより、先ほど挙げた【条件B】を満たすことができる。

確認のため、callCC を使った式を定義で置き換えてみる。

(callCC $ \exit -> add_cps 1 2 `comb` \x -> exit x `comb` \y -> mul_cps y 3) 
=> \k -> (\exit -> add_cps 1 2 `comb` \x -> exit x `comb` \y -> mul_cps y 3) (\x -> \_ -> k x) k
=> \k -> (\exit -> exit 3 `comb` \y -> mul_cps y 3) (\x -> \_ -> k x) k
=> \k -> ((\x -> \_ -> k x) 3 `comb` \y -> mul_cps y 3) k
=> \k -> ((\_ -> k 3) `comb` \y -> mul_cps y 3) k
=> \k -> (\k' -> (\_ -> k 3) (\x -> (\y -> mul_cps y 3) x k')) k
=> \k -> (\k' -> (k 3)) k
=> \k -> k 3

これで、callCC 関数の定義における「無名関数」の意味が理解できた。

しかし、自分の頭では直感的に理解できないなぁ。。

すぐに忘れる脳みそのためのメモ

2013年4月27日土曜日