継続とは何か（１）

『Scheme 手習い』の第8章に「継続」の概念が出てきた。 ただ、説明が少なくいまいち理解できないので、Web ページを漁ってみる。

Gauche の作者 Shiro さん曰く、

文献を紐解くと、 継続とは「これから行われるであろう計算をパッケージ化したもの」とある。

「これから行われるであろう計算をパッケージ化したもの」だという。 まったく分からない…。

紫藤さんのページ を見てみる。

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

うーん、やはり分からない。

ただ、継続に関連して「関数の継続渡しスタイル」というものがあるらしい。

継続渡しスタイルとは、関数が、値を返す代わりに、計算した値をどの関数に渡すのかを明示的に指定する方法です。

少しピンときた気がする。

まずは「継続渡しスタイル」を、単純な例からひもといていくことにする。

継続渡しスタイル

はじめに、二つの数を掛け算する関数 mul と足し算する関数 add を定義してみる。

(define (mul x y)
  (* x y))
  
(define (add x y)
  (+ x y))

これらの実行は簡単。次のようにする。

(mul 3 4) ; => 12
(add 1 2) ; => 3

次に継続渡しスタイル。

継続渡しスタイルは「計算した値をどの関数に渡すのかを明示的に指定する方法」だ。 だから、計算の結果を渡す関数を引数として受け取り、計算結果はその関数に渡すようにする。

(define (mul&co x y col)
  (col (* x y)))
 
(define (add&co x y col)
  (col (+ x y)))

これで mul と add は継続渡しになった。 &co は継続渡し形式を意味し、col は結果を渡す関数である。

なんとなく、コールバック関数を渡すのに近い感覚か。

これらの関数を使って実際に計算するにはどのようにすればよいだろう。 add や mul と違って結果を渡す何らかの関数を渡さなければならない。

もし、単に値を返すだけなら、col に値を返すだけの単純な lambda を渡せばよい。

(mul&co 3 4 (lambda (n) n)) ; => 12
(add&co 1 2 (lambda (n) n)) ; => 3

これで最も単純な継続渡しスタイルが理解できた。

少し複雑な例

足し算と掛け算の両方を使った計算はどのようになるだろう。

(mul 3 (add 1 2)) ; => 9

これを継続渡しスタイルで実行すると次のようになる。

(add&co 1 2
  (lambda (x)
    (mul&co 3 x
      (lambda (n)
        n)))) ; => 9

少し複雑になった。add&co には lambda で包んだ mul&co の計算を渡している。

ステップバイステップで関数の適用をひもといていくと次のようになる。

(add&co 1 2
  (lambda (x)
    (mul&co 3 x
      (lambda (n)
        n))))
=>
((lambda (x)
  (mul&co 3 x
    (lambda (n)
      n))) (+ 1 2))
=>
((lambda (x)
  (mul&co 3 x
    (lambda (n)
      n))) 3)
=>
(mul&co 3 3
  (lambda (n)
      n))
=>
((lambda (n)
      n) (* 3 3))
=>
((lambda (n)
      n) 9)
=>
9

通常の計算スタイル（(mul 3 (add 1 2))）は内側から外側にむかって計算したが、継続渡しスタイルでは計算が外側から内側に流れていることが分かる。

さらに複雑な例

もう少し複雑な例をとるとどうなるだろう。

(mul (mul 2 3) (add 1 (add 1 2))) => 24

少し長くなるが、これを継続渡しスタイルにすると次のようになる。

(add&co 1 2
  (lambda (x)
    (add&co 1 x
      (lambda (y)
        (mul&co 2 3
          (lambda (z)
            (mul&co y z
              (lambda (n)
                n)))))))) ; => 24

関数の適用は省略するが、継続渡しスタイルでもちゃんと複雑な計算ができる。

ここで、最初の継続の説明に戻ってみる。

継続とは「これから行われるであろう計算をパッケージ化したもの」

さきほどの継続渡しスタイルをもう一度見てみると、一番外側の add&co には次の関数を渡している。

(lambda (x)
    (add&co 1 x
      (lambda (y)
        (mul&co 2 3
          (lambda (z)
            (mul&co y z
              (lambda (n)
                n)))))))

一番外側の add&co にとって、これがまさに「これから行われるであろう計算をパッケージ化したもの」なのではないだろうか。（これが継続？）

通常スタイルの場合、関数の適用は内側から外側に向かって行われるので、あとに続く計算は外側にたどり着くまで分からない。 一方、継続渡しスタイルでは最初の計算を行う時点で、その後に行われる計算が関数として渡されている。

少しだけ理解ができたかもしれない。

今日はここまで。次は継続渡しスタイルの再帰関数について書く予定。