6-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 にはないので、こんな式を書いてはいけない。 仮想的なものである。)

継続渡し方式 (Continuation Passing Style)

このような「継続」の考え方を使うとどういう良いことがあるだろうか。 まずは例題である。
  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) と呼ばれる。

継続渡し方式のインタープリタ

前節のインタープリタを、継続渡し方式(CPS)に書き換えよう。 前節のインタープリタ eval6 は exp -> env -> value という型を持っていたが、 今度は継続をあらわす引数が1つ増える。つまり、 CPSインタープリタを eval7 と呼ぶと、 eval7 は exp -> env -> cont -> answer という型を持つ。 ここで cont は継続の型、answer は最終的な答の型である。 これらの具体的な型は、考えるとややこしいのであるが、 とりあえずは cont = value -> value, answer = value と思うのがよい。 (実装上は、これより一般的な型となっている。)

まずは、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 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))))
...
いきなり全部書いてしまったが、たとえば、
    | 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 の処理は場合分けになるので、独立させて別関数とした。

例外や継続を扱うプリミティブの処理

ところで、なぜ、インタープリタを CPS に直したのだろうか。 いくつかの利点があるが、ここでは、例外機構(exception) や第一級継続機構 (call/ccなど)の実装に応用してみよう。 (ちなみに、春学期の「プログラム言語論」の授業で使った MiniC や MiniMLの 処理系は CPS インタープリタで実装されている。MiniC言語には例外機構はないが、 C言語の関数における return文は exception のような動作をするため、それが必要だったのである。)

例外機構の実装では、インタープリタの引数として上記の「継続」のほかに、 「例外処理のための継続」という引数を加える必要があって、ちょっと煩雑なので、 call/ccの実装の概要を述べよう。

発展課題 6-3.

以下のどれか1つでも解ければ発展課題として認める。


トップ, 前へ, 次へ.

亀山幸義