Note: this assignment will have test-sweeps. Turn them in by 11:59pm on Monday.

Continuation Passing Style

For this assignment, you will implement a continuation passing style (CPS) transformation for Paret. It will translate a Paret expression into an equivalent Paret expression that uses continuation passing style.

In continuation passing style, functions never return. Instead, they are given as an extra argument a continuation (which is a function of one argument), and instead of returning they invoke the continuation with the value they want to return. Continuation passing style, and its motivation, are explained in detail in the book.

Transforming a program to use CPS is difficult. In particular, it's generally hard to tell whether you've CPSed everything or just some things. It's also hard to keep track of which functions represent functions that the user wrote vs. which represent continuations. As such, we've written a type definition (CPSExpr) that should guarantee that a program is in continuation passing style. It's important to realize, however, that a CPS transformation is fundamentally a function from programs to programs: the CPSExpr data type is just to help you do it correctly.

We have provided an interpreter for this language. You will test your CPS transformation by checking that CPSing a program doesn't change its behavior. In particular, you will test that interpreting the CPSed version of an expression e yields the same answer as interpreting e directly.

Note that CPS gives an explicit order of evaluation to all computations, so you must make sure that your transformation matches the order of the evaluator. The order is the same as in previous assignments, with subexpressions being evaluated left to right as applicable and if being short-circuiting. As before, operators and function application evaluate their all subexpressions before checking whether they are of the right type. So for example, (+ true x) would raise an err-unbound-id, not err-bad-arg-to-op.

What to Implement

You will implement two functions:

fun cps(expr :: C.Expr) -> C.CPSExpr:

fun to-expr(cps :: C.CPSExpr) -> C.Expr:

cps should perform a CPS transformation on expr (as described in the book), returning a CPSExpr. Next, to-expr should take this CPSExpr and turn it into an Expr so that the interpreter can run it. While cps will be performing a complicated program transformation, to-expr should be very simple: it is just changing from one data representation to another.

Here are some high-level notes on converting CPSed expressions into ordinary expressions in to-expr. These should all be what you would expect -- lambdas turn into lambdas, applications turn into applications, etc.:

Of course you need to do a little more work than this: the subexpressions need to be recursively converted into Exprs as well (for instance, in cps-app-atomic, func, arg, and k would need to be recursively converted into regular Exprs).

As an example of cps, one good CPS transformation of (+ 1 2) is the following:

  cps-app-cps(cps-lam("k*", cps-app-kont(k-id("k*"), a-num(1))),
      cps-app-cps(cps-lam("k*", cps-app-kont(k-id("k*"), a-num(2))),
          cps-op(op-plus, a-id("x*"), a-id("y*"), k-id("k*")))))))

This does the following:

Part of your cps transformation will need to construct expressions that use identifiers. When this happens, there is a possibility that an identifier in the input program will accidentally get bound to an identifier of the same name that was made by the transformation. An ideal cps function would generate new names (using gensym or some such). But to keep things simple, you can just assume that programs have no variables with * in them, and use identifiers with * in cps (e.g. x*, k*, arg*, ...).

How to Test

To check that a CPSed program does what it should, write a test case like

test-cps("(+ 1 2)")

This will run the program twice: once directly, and once after CPS, and check that both give the same answer.

To check that a program raises an error, instead write

eval-cps("(+ true 2)") raises-satisfies is-err-bad-arg-to-op

This will try evaluating the CPSed program, and ensure that it raises the correct error. (Note the difference between eval-cps and test-cps.)

Since your CPS transformation might be slightly different than others' (even if both are correct!), it's important not to put any test cases in your test file that checks the result of cps directly.


<expr> ::= | true
           | false
           | <num>

           | (+ <expr> <expr>)
           | (num= <expr> <expr>)
           | (if <expr> <expr> <expr>)

           | <id>
           | (fun (<id>) <expr>)
           | (<expr> <expr>)
           | (let ((<id> <expr>)) <expr>)

Abstract Syntax

For reference, here is the full definitions file (The interpreter is defined in here.)

type Env = List<EnvCell>

data Value:
  | v-num(value :: Number)
  | v-bool(value :: Boolean)
  | v-fun(param :: String, body :: Expr, env :: Env)
    with: _equals(self, other, eq):
      raise("You should not compare functions for equality in "
          + "this assignment, since a CPS'ed function body looks "
          + "so different from a regular one.")

data EnvCell:
  | env-cell(name :: String, val :: Value)

data Expr:
  | e-op(op :: Operator, left :: Expr, right :: Expr)
  | e-if(cond :: Expr, consq :: Expr, altern :: Expr)
  | e-let(name :: String, expr :: Expr, body :: Expr)
  | e-lam(param :: String, body :: Expr)
  | e-app(func :: Expr, arg :: Expr)
  | e-id(name :: String)
  | e-num(value :: Number)
  | e-bool(value :: Boolean)

data Operator:
  | op-plus
  | op-num-eq

data InterpError:
  | err-if-got-non-boolean(val :: Value)
  | err-bad-arg-to-op(op :: Operator, val :: Value)
  | err-unbound-id(name :: String)
  | err-not-a-function(val :: Value)

data CPSExpr:
  | cps-if(cond :: CPSAtomicExpr, consq :: CPSExpr, altern :: CPSExpr)
  | cps-app-atomic(func :: CPSAtomicExpr, arg :: CPSAtomicExpr, k :: Kont)
  | cps-app-kont(k :: Kont, value :: CPSAtomicExpr)
  | cps-app-cps(func :: CPSExpr, k :: Kont)
  | cps-lam(k-name :: String, expr :: CPSExpr)
  | cps-op(op :: Operator, left :: CPSAtomicExpr, right :: CPSAtomicExpr, k :: Kont)

data CPSAtomicExpr:
  | a-lam(v-name :: String, k-name :: String, body :: CPSExpr)
  | a-num(value :: Number)
  | a-bool(value :: Boolean)
  | a-id(v-name :: String)

data Kont:
  | k-lam(v-name :: String, expr :: CPSExpr)
  | k-id(k-name :: String)

The CPSExpr data type helps ensure that your expression is in CPS form:

There are places in a correctly CPSed expression that shouldn't do computations, and can only evaluate directly to values. We enforce this in the CPSExpr data type by putting CPSAtomicExprs in those positions:

Finally, there are continuations:

What to hand in

To get started, here are the stencils:

Turn in your test sweeps by Monday night:

For your final submission, please submit a zip file containing two files: "cps-code.arr" and "cps-tests.arr" that contain your code and tests. Submit them through Captain Teach: