CPS Conversion by Specialising an Interpreter

A program is in continuation passing style (CPS) if every function takes a continuation as a parameter, and as its last action calls its continuation, passing it the function's `result'. A continuation is a kind of abstract return address, and represents all the rest of the computation after the function call.

The following lambda-calculus interpreter is written in CPS (except for the auxiliary function for look-ups in the environment).

module CPS where

data E = Con Int | Var String | Ap E E | Lam String E
data V = Num Int | Fun (V -> (V->V) -> V)

eval e env k =
  case e of
    Con n -> k (Num n)
    Var s -> k (look s env)
    Ap e1 e2 -> eval e1 env (\f-> eval e2 env (\x->
                  case f of
		    Fun g -> g x k))
    Lam x e1 -> k (Fun (\v k'->eval e1 ((x,v):env) k'))

look x env =
  case env of
    nv:env' ->
      case nv of
        (n,v) -> if x==n then v else look x env'

As you can see, eval calls its continuation k to `return' the values of constants and variables, evaluates applications by evaluating the function with a continuation that evaluates the argument, and evaluates lambda-expressions to a function which also expects a continuation at the point of call. Since eval itself is written in CPS, all specialisations of eval will also be in CPS.

Any lambda-expression can be transformed into continuation passing style, using a method known as CPS conversion. The object of this exercise is to implement CPS conversion as specialisation of the interpreter above.

Modify the interpreter to make the expression argument of eval static, and the environment argument partially static, as in the previous exercise.
Modify the interpreter further to unfold calls of eval and look.
The result of applying CPS conversion to \x->x x, for example, should be \v k'->v v k'. Try converting this term by specialising your interpreter -- do you obtain this result? If not, can you modify your interpreter to do so?

Last modified: Sun Sep 21 13:31:16 MEST 1997