第二回
「末尾呼び出し(tail call)と継続渡し形式(Continuation Passing Style)」

継続とは何ぞということをなんとなくでもいいので把握しておきましょう！
というのが今回の内容です。

（継続の話に入る前に、まずは末尾呼び出しの話をします。）

階乗を求める関数 fac は次のように書けます。

let rec fac n =
    if n = 0 then 1 else n * fac (n - 1)

これを実行、例えば fac 3 等とすると、

    fac 3
-> 3 * fac 2
-> 3 * (2 * fac 1)
-> 3 * (2 * (1 * fac 0))
-> 3 * (2 * (1 * 1))
-> 3 * (2 * 1)
-> 3 * 2
-> 6

といった感じで計算が進みます。
このプログラムは再帰の度にスタックを使っています。
つまり、fac 3 をやっている中で fac 2 を呼び出すとき、
「fac 2 の答えが求まった後には 3 * [] をやる」ということを
スタックを使って覚えているわけです。

これを、スタックを使わないように書き換えることができます。
次のように、アキュムレータを使います。

let rec fac n answer =
    if n = 0 then answer else fac (n - 1) (n * answer)

これを実行、例えば fac 3 1 等とすると、
（この例の場合、answer には必ず初期値 1 を入れて呼び出すことに注意。）

    fac 3 1
-> fac 2 3
-> fac 1 6
-> fac 0 6
-> 6

といった感じで計算が進みます。

このように、関数を呼び出した後に覚えておかなくてはならない
作業がないような関数呼び出しのことを「末尾呼び出し(tail call)」
と言います。再帰呼び出しが末尾呼び出しになっている場合、
それを末尾再帰(tail recursion)と呼びます。

=======================================================
問題（相談、質問可）

1. m の n 乗を求める関数 power を書け。
2. それを末尾呼び出しの形で書け。
3. フィボナッチ数を求める関数 fib を書け。
4. それを末尾呼び出しの形で書け。

フィボナッチ数は

fib(0) = 0
fib(1) = 1
fib(n) = fib (n-1) + fib (n-2)    (n>=2)

で定義される。
=======================================================

末尾再帰にするメリットは、スタックに覚えておかなくてはならないような
情報がないのでスタックが不要になることに加え、コンパイラが
プログラムを関数呼び出しとしてではなくループとしてコンパイル
するので高速になるということです。

また、自由に計算を中断できるということもあげられます。
例えば、階乗のプログラムを末尾呼び出しで書いておけば、
fac 1 6 まできたところで一時中断して、別のことをしてから、
後でまた計算を再会する……といったことが簡単にできます。
システムのスタックを使っていたら、計算の中断/再開に伴って
システムのスタックも退避/復活しなくてはなりません。

ここで、上の末尾再帰の例で階乗の計算はどのように行われているか
少し見直してみましょう。
末尾再帰に変換する前は
    3 * (2 * (1 * 1))
のようにかけ算をしていましたが、末尾再帰に変換したものでは
    1 * (2 * (3 * 1))
のようにかけ算が行われます。
変換後は、かけ算をする順序が変わってしまっています。
かけ算では順序が変わってもそう問題は起こりませんが、
順序が変わると困る場合もあります。
例として、リスト中の正の要素のみを取り出す関数 positive を考えます。

let rec positive lst = match lst with
    [] -> []
  | first :: rest -> if first > 0 then first :: positive rest
                        else positive rest

これを（無理矢理）アキュムレータを使って書こうとすると、

let rec positive lst answer = match lst with
    [] -> []
  | first :: rest -> if first > 0 then positive rest (answer @ [first])
                        else positive rest answer

となります。
処理の順番が変わってしまったために、変換前だったら::を使えばよかったところが
@ (List.append と同じ。リストの最後にくっつける。)になってしまっています。
リストの最後にくっつけるには、リストの長さに比例した時間がかかるので、
（小さなプログラムでは気にならないかもしれませんが、）ちょっと避けたい事態です。

処理の順序を変えることなく末尾呼び出しの形にプログラムを書き換えるには、
アキュムレータを使うのではなく、次のようにします。

let rec positive lst cont = match lst with
    [] -> cont []
  | first :: rest ->
      if first > 0
      then positive rest (fun result -> cont (first :: result))
      else positive rest cont

ここで cont は「継続(continuation)」と呼ばれます。
直観的には、「その計算が終わったあとにする仕事」を表します。
上の関数を次のように呼び出したとすると、以下のように実行されていきます。
（ここで、id とは恒等関数で、具体的には fun lst -> lst とします。）

    positive [1; -2; 4; 3] id
-> positive [-2; 4; 3] (fun result -> id (1 :: result))
-> positive [4; 3] (fun result -> id (1 :: result))
-> positive [3] (fun result -> (fun result -> id (1 :: result)) (4 :: result))
= positive [3] (fun result -> id (1 :: 4 :: result))
-> positive [] (fun result -> (fun result -> id (1 :: 4 :: result)) (3 :: result))
= positive [] (fun result -> id (1 :: 4 :: 3 :: result))
-> (fun result -> id (1 :: 4 :: 3 :: result)) []
-> id (1 :: 4 :: 3 :: [])
-> 1 :: 4 :: 3 :: []
= [1; 4; 3]

最初の positive [1; -2; 4; 3] id は
「[1; -2; 4; 3] の positive を計算し、その結果を id に渡す」
と読みます。id は恒等関数なので、
実際には [1; -2; 4; 3] の positive を求める事になります。

このように継続を渡すことで全ての関数呼び出しを末尾呼び出しの形で書いた
プログラムのことを継続渡し形式(CPS : Continuation Passing Style)で
書かれたプログラムと呼びます。これと対比して、CPS でない通常のプログラム
のことを直接形式 direct style と言ったりもします。

ちなみに、上の実行例で = で結ばれているところは、わかりやすくするため
に簡略化しましたが、call-by-value の実行では実際には簡略化されません。

別の例として、CPS で書かれた fac もあげておきます。

let rec fac n cont =
    if n = 0 then cont 1 else fac (n - 1) (fun x -> cont (n * x))

=======================================================
問題

1. fac 4 id の実行例を書き下して、確かにアキュムレータを使わない fac
と同じ順番でかけ算をしていながら、すべて末尾呼び出しで階乗が求まること
を確認せよ。
2. power を CPS で書け。
3. fib を CPS で書け。（ちょっと難。）
=======================================================