ただし、正確には、継続は関数とは違う。 継続1のあとに継続2を実行しようとしても、 関数合成のようにはならず、継続1 を実行しおわったら(継続2を実行せずに)終わってしまう。 従って、正確には、継続は、(fun v -> exit(1+2*v)) といった関数 のようなものである。ここで exit は「終わる」という意味の C言語の exit() 関数と同じつもりである(OCaml にはないので、こんな式を書いてはいけない。 仮想的なものである。)
let rec factorial_normal n =
if n = 0 then 1
else n * (factorial_normal (n - 1))
このような普通の階乗関数を「継続」を使った方式で書きかえると以下のようになる。
let rec factorial_c n k =
if n = 0 then (k 1)
else factorial_c (n - 1) (fun x -> k (n * x))
let factorial n =
factorial_c n (fun x -> x)
パラメータとして n のほかに k をとってきており、これが「継続」を表す。
k の初期値は、「何もしない関数」である fun x -> x とする。これは「残りの計算がもうない」
という事を意味する。
これではまだ何のことかわからないかもしれないが、後者を実行すると以下のようになる。
factorial 5 -> factorial_c 5 (fun x -> x) -> factorial_c 4 (fun x -> (fun x -> x) (5 * x)) -> factorial_c 3 (fun x -> ((fun x -> (fun x -> x) (5 * x)) (4 * x)) -> ...これだと見にくいので、少し整形すると、
factorial 5 -> factorial_c 5 (fun x -> x) -> factorial_c 4 (fun x -> 5 * x) -> factorial_c 3 (fun x -> 5 * 4 * x) -> ...継続を使ったスタイルでは、関数の再帰呼び出しが常にトップレベルで行われていることがわかる。 (つまり、「末尾再帰」になっているということである。ちなみに、最初の(普通の)factorial_normal関数では、
factorial_normal 5 -> 5 * (factorial_normal 4) -> 5 * (4 * (factorial_normal 3)) -> ...となり、関数呼び出しがトップレベルでなくなる。これだと、インタープリタはスタックをどんどん使ってしまう。 一方、「継続」を使った方式では、関数の再帰呼び出しはトップレベルにあるので、 (前節までのインタープリタでは、それでもスタックを使ってしまうが、 ちょっと頑張って改善すれば、) スタックを無駄に消費しない実装が可能になる。 このようなスタイルのプログラムは、「継続」を引数として渡していくスタイ ルなので、継続渡し方式 (CPS) と呼ばれる。
まずは、eval7 の実装を見てみよう。
(**************************************************************************)
(* eval7 : exp -> env -> (value -> 'a) -> 'a *)
(* 継続渡し形式のインタープリタは value を返すのではなく、(value->'a) と
* いう継続をもらって、'a型の要素を返す。ここで'aは、どんな型でもよい
*)
let rec eval7 e env cont =
match e with
| Var(x) -> cont (lookup x env)
| IntLit(n) -> cont (IntVal n)
| BoolLit(b) -> cont (BoolVal b)
| Plus(e1,e2) -> binop (+) e1 e2 env cont
| Times(e1,e2) -> binop ( * ) e1 e2 env cont
| Eq(e1,e2) ->
eval7 e1 env (fun v1 ->
eval7 e2 env (fun v2 ->
cont (BoolVal (eq_val v1 v2))))
| If(e1,e2,e3) ->
eval7 e1 env (function
| BoolVal(true) -> eval7 e2 env cont
| BoolVal(false) -> eval7 e3 env cont
| _ -> failwith "wrong value")
| Let(x,e1,e2) ->
eval7 e1 env (fun v1 ->
let env1 = ext env x v1
in eval7 e2 env1 cont)
| LetRec(f,x,e1,e2) ->
let env1 = ext env f (RecFunVal (f, x, e1, env))
in eval7 e2 env1 cont
| Fun(x,e1) -> cont (FunVal(x, e1, env))
| App(e1,e2) ->
eval7 e1 env (fun funpart ->
eval7 e2 env (fun arg ->
app funpart arg cont))
...
and
eq_val v1 v2 =
match (v1,v2) with
| (IntVal(n1),IntVal(n2)) -> n1 = n2
| (BoolVal(b1),BoolVal(b2)) -> b1 = b2
...
and (* App(e1,e2)のケースは長いので、以下の関数として独立させた *)
app funpart arg cont =
match funpart with
| FunVal(x,body,env1) ->
eval7 body (ext env1 x arg) cont
| RecFunVal(f,x,body,env1) ->
let env2 = (ext (ext env1 x arg) f funpart) in
eval7 body env2 cont
...
(* テスト *)
let ee = emptyenv ()
let initial_continuation = fun a -> a
let eval7top e = eval7 e ee initial_continuation
let _ = eval7top (IntLit 1)
let _ = eval7top (IntLit (-1))
let _ = eval7top (Plus (IntLit 1, Plus (IntLit 2, IntLit (-1))))
let _ = eval7top (Times (IntLit 1, Plus (IntLit 2, IntLit (-1))))
...
いきなり全部書いてしまったが、たとえば、
| Eq(e1,e2) ->
eval7 e1 env (fun v1 ->
eval7 e2 env (fun v2 ->
cont (BoolVal (eq_val v1 v2)))))
というところを見ると、CPS の「味」が非常によく出ているところである。
この式は、普通に段付けすると、
| Eq(e1,e2) ->
eval7 e1
env
(fun v1 -> eval7 e2
env
(fun v2 -> cont (BoolVal (eq_val v1 v2)))))
となってしまいそうなところであるが、CPS のプログラムでは、
継続の部分に関数が来る形が頻繁に出現して、
後者の段付けでは見にくいため、
上記のような独特の段付けで書くという習慣がある。
また、App の処理は場合分けになるので、独立させて別関数とした。
例外機構の実装では、インタープリタの引数として上記の「継続」のほかに、 「例外処理のための継続」という引数を加える必要があって、ちょっと煩雑なので、 call/ccの実装の概要を述べよう。
type value = ...
| ContVal of (value -> value)
eval7 本体では、
| Callcc(e1) ->
eval7 e1 env (fun funpart ->
app funpart (ContVal cont) cont)
といった形にすればよい。若干ややこしいのは、(call/cc (fun k -> e)) に
限定した処理ではなく、(call/cc e1) の形の処理を書いているからである。
これは、(1) e1 を計算する、(2) ただし、そのときの継続は、現在の継続cont ではなく
それを変形したものである、(3) 変形した継続は、
e1 の計算結果を funpart と呼ぶことにすると、funpart を
「現在の継続 cont(に ContVal をつけて、value型にしたもの)」に適用するが、
その時の継続(適用した後の処理)が cont である、
というコードである。
let rec app funpart arg cont =
match funpart with
...
| ContVal cont1 -> cont1 arg (* switch continuation *)
というように、1行追加するだけである。cont を使わずに、cont1 だけを使うのがポイントであるが、
それにしても、たった1行で済むとは驚きである。
亀山幸義