継続について考える第二弾。
前回の記事では、足し算と掛け算という単純な例を用いて継続について考えた。
今回は再帰での継続渡しスタイルについて考えて、継続についてさらに理解を深めたい。
累乗を計算する
再帰を用いて 1 から n までの累乗を計算する関数は次のようになる。
(define (fact n) (cond [(= n 1) 1] [else (* n (fact (- n 1)))]))
n=1 の時は 1 を返し、それ以外の時は、n に n - 1 までの累乗を掛け算する。
実行すると次のとおり。
(fact 6) ; => 720
ここまではいつも通りの計算だ。
継続渡しスタイル
累乗の計算を継続渡しスタイルにするとどうなるだろう。
まずは n=1 の時を考える。 1 の累乗は 1 なので、これを関数 col に与えてやればよい。
(define (fact&co n col) (cond [(= n 1) (col 1)] [else ...TODO...]))
次は n が 1 より大きい時だ。
簡単なところから一歩ずつ考えていこう。
継続スタイルでは col に計算の結果を与えてやる必要があった。 だから、col に対しては n の累乗の結果を与えてやればよい。 x を n-1 までの累乗とすれば、n の累乗は (* n x) だから、col にはそれを与えることにする。
(col (* n x)) ; => ただし、x は n-1 までの累乗
こうすれば継続スタイルの約束を守れる。 問題は x すなわち n-1 までの累乗はどうやって得られるかという点だ。
n-1 の累乗を再帰的に fact&co を使って定義する。 fact&co はそれ自体が累乗を計算して col に計算結果が渡ってくるのだから、次のように計算すればよい。
(fact&co (- n 1) (lambda (x) x)) ; => x は n-1 までの累乗の値が入る
上の lambda の中の x を使えば n-1 までの累乗の値が取得できる。 これを、さきほどのパーツを合わせれば n が 1 より大きいときの計算が得られる。
(fact&co (- n 1) (lambda (x) (col (* n x)))) ; => n の 累乗を計算して、col に与えている
これで else のケースもそろったので fact&co は次のように定義できる。
(define (fact&co n col) (cond [(= n 1) (col 1)] [else (fact&co (- n 1) (lambda (x) (col (* n x)))) ]))
実行は次のとおり。
(fact&co 6 (lambda (x) x)) ; => 720
展開してみる
理解を深めるため n=3 として、fact と fact&co の関数適用を展開してみる。
fact は展開すると次のようになる。
(fact 3) => (* 3 (fact 2)) => (* 3 (* 2 (fact 1))) => (* 3 (* 2 1))
これは簡単。 ちなみにどの時点でも評価可能で、どの時点の評価も 6 になる。
fact&co は展開すると次のようになる。
(fact&co 3 (lambda (x) x)) => (fact&co 2 (lambda (a) ((lambda (x) x) (* 3 a)))) => (fact&co 1 (lambda (b) ((lambda (a) ((lambda (x) x) (* 3 a))) (* 2 b)))) => ((lambda (b) ((lambda (a) ((lambda (x) x) (* 3 a))) (* 2 b))) 1)
少し複雑だが、順を追って見てみる。
- (fact&co 3 ... ) は、(fact&co 2 ... ) の結果の a に対して 3 をかけたものを col に渡す。
- (fact&co 2 ... ) は、(fact&co 1 ... ) の結果の b に対して 2 をかけたものを col に渡す。
- (fact&co 1 ... ) は、1 を col に渡す。
末尾再帰
こうやって眺めると、その関数の計算が終わったあとにやるべき計算をクロージャにして col に渡していることが分かる。 例えば (fact&co 2 col) には「計算結果に 3 をかけて (lambda (x) x) に渡す」というクロージャを渡している。 これはやはり「これから行われるであろう計算をパッケージ化したもの」だ。
もう一つ気づいたのは、継続スタイルでは関数が末尾再帰になってる。 本来(?)の末尾再帰だと即値で計算した結果を引数に渡してるイメージだけど、継続スタイルではやるべき計算がクロージャとして col に渡されていく。
通常の再帰では「2 までの累乗の結果に 3 をかける」という計算は、関数呼び出しのスタックにつまれて保存されている。
(* 3 (fact 2)) ; → 3 をかけるという計算 (* 3 []) はスタックに積まれて保存
一方、継続渡しスタイルではスタックには積まれずクロージャとして計算を保存している。
(fact&co 2 (lambda (a) ((lambda (x) x) (* 3 a)))) ; => 3 をかける計算はクロージャに保存されている
また、通常の呼び出しでは見えづらい「3 をかける計算」が継続渡しスタイルでは明示的な計算((* 3 a))になっている。
少し継続がつかめてきた。 次回はさらに複雑な再帰の継続渡しスタイルについて見ていく予定。