5-3. 継続渡し方式

発展課題の1つとして、継続渡し方式(Continuation Passing Style)の処理系を作成する。

継続 (Continuation)

継続とは、「残りの計算」をあらわすものである。たとえば、1+(2 * (3 - 1)) の中の (3-1) を計算している瞬間の「残りの計算」は、「1+(2 * v)」である。ただし、「今計算している式の値」を v とした。つまり、継続の意味は、(fun v -> (1+2*v)) といった関数ととらえると都合がよい。

ただし、正確には、継続は関数とは違う。継続1のあとに継続2を実行しようとしても、関数合成のようにはならず、継続1 を実行しおわったら(継続2を実行せずに)終わってしまう。従って、正確には、継続は、(fun v -> exit(1+2*v)) といった関数のようなものである。ここで exit は「終わる」という意味の C言語の exit() 関数と同じつもりである(OCaml にはないので、こんな式を書いてはいけない。仮想的なものである。)

このような「継続」を使って、インタープリタをここに載せてしまうので、見てみてほしい。このプログラムがどう動いているかを自力で理解すると、関数プログラミングの神髄がわかるであろう。

(**************************************************************************)
(* 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
	     | _  -> raise 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 ->
	else false
    | (ListVal(_),ListVal(_)) -> false
  ...

(* テスト *)

let ee = emptyenv () 
let initial_continuation = fun a -> a
let eval7top e = eval7 e ee initinal_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))))
...

トップ, 前へ, 次へ.

亀山幸義