cps.ml

cps.ml

type expr = Var of int | Abs of int * expr | App of expr * expr 
          | Lit of int | Add of expr * expr;;

let cnt = ref 100;;
let fresh () = let ret = !cnt in cnt := 1; ret;;

let rec cps e k = 
  match e with
  | Var x -> App (k, (Var x))
  | Abs (v, x) -> 
      let fk = fresh () in
      App (k, (Abs (v, Abs (fk, cps x (Var fk)))))
  | App (f, x) -> 
      let ff = fresh () in
      let fx = fresh () in
      cps f (Abs (ff, cps x (Abs (fx, App (App (Var ff, Var fx), k)))))
  | Lit i -> App (k, (Lit i))
  | Add (x, y) -> 
      let fx = fresh () in
      let fy = fresh () in
      cps x (Abs (fx, cps y (Abs (fy, Add (Var fx, Var fy)))));;

let rec cps_ e k = 
  match e with
  | Var x -> k (Var x)
  | Abs (v, x) -> 
      let fk = fresh () in
      k (Abs (v, Abs (fk, cps_ x (fun x_ -> App (Var fk, x)))))
  | App (f, x) ->
      let fk = fresh () in
      cps_ f (fun f_ -> cps_ x (fun x_ -> App (App (f_, x_), Abs (fk, k (Var fk)))))
  | Lit i -> k (Lit i)
  | Add (x, y) -> cps_ x (fun x -> cps_ y (fun y -> Add (x, y)));;