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:
    ...
end

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

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.:

cps-app-atomic(func, arg, k) becomes (func(arg))(k)
cps-app-kont(k, val) becomes k(val)
cps-app-cps(func, k) becomes func(k)
cps-op(op, left, right, k) becomes k(op(left, right))
a-lam(v, k, body) becomes lam(v): lam(k): body

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-lam("k*",
  cps-app-cps(cps-lam("k*", cps-app-kont(k-id("k*"), a-num(1))),
    k-lam("x*",
      cps-app-cps(cps-lam("k*", cps-app-kont(k-id("k*"), a-num(2))),
        k-lam("y*",
          cps-op(op-plus, a-id("x*"), a-id("y*"), k-id("k*")))))))

This does the following:

The outer cps-lam("k*", ...) is the result of CPS, which is a function that takes the continuation k* as an argument.
Line 2 (cps-app-cps(... a-num(1) ...)) just calls the function starting on line 3 with the argument 1. (Note that the function here, cps-lam("k*", cps-app-kont(k-id("k*"), a-num(1))), is the result of CPSing the program 1.)
Line 3 (k-lam("x*",) begins a function that says what to do with the first argument to +; in this case x* will be 1.
Line 4 (cps-app-cps(... a-num(2) ...)) calls the function after it with the argument 2.
Line 5 (k-lam(y*,) begins a function that says what to do with y*; in this case 2.
Line 6 (the last line) says to perform plus on x* and y*, and pass the result to k*, where k* is the continuation passed in on line 1.

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.

Grammar

<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.")
    end
end

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

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)
end

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

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)
end

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)
end

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)
end

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

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

cps-if represents a conditional (just like e-if).
cps-app-atomic is for applying a CPS'ed user function. Source language functions take one argument, but after being CPS'ed they take two: the original argument arg, plus the continuation k to call when it wants to "return".
Typically, at the end of a CPS'ed expression, you'll want to pass the result to the continuation. This is what cps-app-kont is for: value is an expression that holds the result, and k is a continuation to pass it to.
Sometimes you'll need to apply a CPS'ed expression to a continuation. This is what cps-app-cps is for: func is the result of CPSing some expression, and k is the continuation to pass it.
cps-lam constructs a function that takes a continuation as an argument. CPSing an expression should always produce a cps-lam.
cps-op takes a continuation as a third argument, so for instance (+ 1 2 k) would add one to two and pass the result to the continuation k. (Though note that the parser won't accept (+ 1 2 k) because it parses regular Exprs, not CPSExprs.)

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:

a-lam represents a user function. When the user wrote it, it took one argument v-name, but now it takes two: its original argument v-name, plus k-name, which will get bound to a continuation.
a-id is for an identifier that is bound to a value.
a-num and a-bool are simply values.

Finally, there are continuations:

k-lam represents a continuation. v-name is the name of the value it takes, and expr says what it does with it.
k-id is an identifier bound to a continuation (e.g. from cps-lam).

What to hand in

To get started, here are the stencils:

Turn in your test sweeps by Monday night:

https://www.captain-teach.org/brown-cs173/assignments/

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:

https://www.captain-teach.org/brown-cs173/assignments/