@kyanny's blog

My thoughts, my life. Views/opinions are my own.

継続を学ぶ #0

http://practical-scheme.net/docs/cont-j.html を読む。一回通して読んでみた時点での自分の理解をまとめておく。たぶん、不十分な上に間違っていると思う。なので、継続に詳しくない方はこの記事の内容を信じないでください。継続に詳しい方からのツッコミは歓迎しますが、正解を教えてもらっても理解できないかもしれません・・・。

「継続」とは何か

「継続」とは、プログラムのある部分より後ろの部分のことを指す。

func foo {
    do something1; # (A)
    # ------------------
    do something2; # (B)
}


上の擬似コードでは、「(B) は (A) の継続である」という。

「末尾再帰」とは何か

継続の説明の中で末尾再帰の話が出てきた。末尾再帰が何なのかを一応理解しておかないと、継続の説明が理解できない気がしたのでこれも整理しておく。

「末尾再帰」とは、再帰関数（関数定義の中で、自分自身を呼び出している関数）のうち、関数のブロックの中で一番最後に実行される部分が再帰である（自分自身を呼び出しているコードである）もののことである。

func rec (x) {
    if (x < 0) {
        return x;
    }
    else {
        return rec(x - 1);
    }
}

上の、見るからに何の意味もない擬似コードで、 x >= 0 のときは rec(x - 1) がこの関数 rec の中で最後に実行される部分なので、これは末尾再帰している。実行例を展開して順を追って見ていくと、こんな風になるはずだ。

rec(3);

# 一ステップずつ展開してみる
# step1 rec(3) を実行する
func rec (3) {
    if (3 < 0) { # 3 < 0 は成り立たないので return 3; は実行されない
        return 3;
    }
    else {
        return rec(3 - 1); # rec(2) を実行する
    }
}
# step2 rec(2) を実行する
func rec (2) {
    if (2 < 0) { # 2 < 0 は成り立たないので return 2; は実行されない
        return 2;
    }
    else {
        return rec(2 - 1); # rec(1) を実行する
    }
}
# step3 rec(1) を実行する
func rec (1) {
    if (1 < 0) { # 1 < 0 は成り立たないので return 1; は実行されない
        return 1;
    }
    else {
        return rec(1 - 1); # rec(0) を実行する
    }
}
# step4 rec(0) を実行する
func rec (0) {
    if (0 < 0) { # 0 < 0 は成り立たないので return 0; は実行されない
        return 0;
    }
    else {
        return rec(0 - 1); # rec(-1) を実行する
    }
}
# step5 rec(-1) を実行する
func rec (-1) {
    if (-1 < 0) { # -1 < 0 は成り立つので、 return -1; が実行される
        return -1;
    }
    else {
        return rec(-1 - 1); # ここはもう実行されない
    }
}
# step6 rec(-1) の結果を rec(0) に戻す
func rec (0) {
    if (0 < 0) { # さっき実行済みなので無視
        return 0;
    }
    else {
        return -1; # rec(-1) が -1 に置き換わる
    }
}
# step7 rec(0) の結果を rec(1) に戻す
func rec (1) {
    if (1 < 0) { # さっき実行済みなので無視
        return 1;
    }
    else {
        return -1; # rec(0) が -1 に置き換わる
    }
}
# step8 rec(1) の結果を rec(2) に戻す
func rec (2) {
    if (2 < 0) { # さっき実行済みなので無視
        return 2;
    }
    else {
        return -1; # rec(1) が -1 に置き換わる
    }
}
# step9 rec(2) の結果を rec(3) に戻す
func rec (3) {
    if (3 < 0) { # さっき実行済みなので無視
        return 3;
    }
    else {
        return -1; # rec(2) が -1 に置き換わる
    }
}
# step10 トップレベルの rec(3); に戻る
-1; # rec(3) の戻り値は -1

rec(n) を、 n を 1 ずつ減らしながら順に実行していって一番深いステップまでいった後は、 rec(n-1) は rec(n-2) の戻り値をそのまま rec(n) に返している。こういうのを、一番最後（末尾）に再帰呼び出しが来るから末尾再帰という。

で、末尾再帰というやつは、 Scheme のインタプリタだかコンパイラだか処理系だか（そういうものを正確になんと呼べばいいのか知らない）が、内部的に最適化をしてくれて、とても早いプログラムになるらしい。

「継続」と「末尾再帰」を組み合わせる

へたくそな擬似コードで整理できる気がしないので、 http://practical-scheme.net/docs/cont-j.html の例を拝借して、自分なりの言葉と、プラス参考文献を引用して説明してみる。

まずコード例。

; ふつうの再帰関数 leaf-count
(define (leaf-count tree)
  (if (pair? tree)
      (+ (leaf-count (car tree))
         (leaf-count (cdr tree)))
      1))

; 継続 + 末尾再帰な leaf-count/cps
(define (leaf-count/cps tree cont)
  (if (pair? tree)
      (leaf-count/cps (car tree)      
        (lambda (n)
          (leaf-count/cps (cdr tree)
            (lambda (m) (cont (+ n m))))))
      (cont 1)))

leaf-count は引数 tree をとり、 tree がリストならば (+ (leaf-count (car tree) (leaf-count (cdr tree))) を呼ぶ。 car とか cdr とかはあまり深く考えずに、 (+ (leaf-count ...) (leaf-count ...)) という形に注目すると、この関数は自分自身を呼び出しているので再帰関数であるが、 (leaf-count ...) の返り値をそのまま返していない。 (+ ...) で囲われているので、 (leaf-count ...) の再帰呼び出しが 100 回あった場合、 100 回目の再帰呼び出しの返り値を使って 99 回目の (+ ...) を実行し、次に 99 回目の再帰呼び出しの結果（さっき実行した (+ ...) の値）を使って 98 回目の (+ ...) を実行し・・・という風に動作する。再帰呼び出しをして値を返されたあと、ワンクッションおいて別の計算をしてから return するわけだ。これは末尾再帰ではない。

末尾再帰ではない再帰関数である leaf-count を末尾再帰に変形するために継続を利用する。（たぶん継続はこのためだけに存在するものではないが、ここではそういう使い方しか考えない）。

Paul Graham の On Lisp では、継続をこんな風に説明している。

(/ (- x 1) 2)

という式があるとして、 (/ ...) という外側の式は (- x 1) という内側の式が評価されるのを待っている。 (- x 1) が計算されて値を返さないと、 (/ ...) という式を計算できないからだ（(- x 1) の値が何になるか、(- x 1) を計算してみるまでわからないため）。

ここで、「(- x 1) が評価されたが、しかしまだ (/ ...) の式は評価されていない、その時点での (/ ...) 式を表す関数」を、以下のように書くことができる。

(lambda (val) (/ val 2)) ; ただし、この無名関数の引数 val は (- x 1) を評価した値とする

これまたステップを区切って、分解してみていくことにする。

; まず (/ (- x 1) 2) に名前を付ける
(define (foo x)
  (/ (- x 1) 2))

; トップレベルの呼び出し
(foo 5)

; step1 展開して変数 x を置き換える
(define (foo 5)
  (/ (- 5 1) 2))

; step2 本体だけを取り出す
(/ (- 5 1) 2)

; (A)

; step3 内側の式 (- 5 1) だけを評価する
(/ 4 2)

; (B)

; step4 外側の式 (/ 4 2) を評価する
2

; step5 トップレベルに値を返す
(foo 5)
; => 2

ここで、 (B) の時点では、次に (/ 4 2) を計算するわけだが、ここで「(- x 1) が評価されたが、しかしまだ (/ ...) の式は評価されていない、その時点での (/ ...) 式を表す関数」に値を当てはめると、こうなる。

(lambda (4) (/ 4 2))

この関数の本体は (/ 4 2) で、 (B) 時点で次に計算される式 (/ 4 2) と同じである。つまり (B) 時点での式 (/ 4 2) は、上の (lambda (4) (/ 4 2)) のような無名関数をかいてそれを実行する式と等価である。

ここで、継続の定義に戻ると、この分解図において「(B) は (A) の継続」なのだった。つまり (A) の継続は、

(lambda (4) (/ 4 2))

であり、これを一般化、というかステップ分解する前の関数 foo に対して当てはめると、関数 foo において、 (- x 1) が実行される前の時点を A' とし、 (- x 1) が実行された後の時点を B' とすると、 A' の継続 B' は、

(lambda (x)
  (lambda ((- x 1)) (/ (- x 1) 2)))

こんな風になるんじゃないだろうか。

今回はここまで

さらっとメモるくらいのつもりで書き始めたのに、気づいたらずいぶん長くなってしまった。一時間以上かかったかも。しかも最後のほうは自分で書いててかなり怪しい気がしている。なんとなーく、書き終えられる程度には自分の中で理屈が通っているような気がするのだけど。明日読み返したらとんでもない思い違いに気づいたりして。


参考ページ
http://practical-scheme.net/docs/cont-j.html

参考文献

On Lisp

On Lisp