Note: this assignment will have test-sweeps. Turn them in by 11:59pm on Monday.
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
e yields the same answer as interpreting
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
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
to-expr should take this
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
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
cps-op(op, left, right, k)becomes
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,
k would need to be recursively
converted into regular Exprs).
As an example of
cps, one good CPS transformation of
(+ 1 2) is the
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:
cps-lam("k*", ...)is the result of CPS, which is a function that takes the continuation
k*as an argument.
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
k-lam("x*",) begins a function that says what to do with the first argument to
+; in this case
cps-app-cps(... a-num(2) ...)) calls the function after it with the argument
k-lam(y*,) begins a function that says what to do with
y*; in this case
y*, and pass the result to
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
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
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
<expr> ::= | true | false | <num> | (+ <expr> <expr>) | (num= <expr> <expr>) | (if <expr> <expr> <expr>) | <id> | (fun (<id>) <expr>) | (<expr> <expr>) | (let ((<id> <expr>)) <expr>)
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-ifrepresents a conditional (just like
cps-app-atomicis 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
kto call when it wants to "return".
valueis an expression that holds the result, and
kis a continuation to pass it to.
funcis the result of CPSing some expression, and
kis the continuation to pass it.
cps-lamconstructs a function that takes a continuation as an argument. CPSing an expression should always produce a
cps-optakes 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
CPSExpr data type by putting
CPSAtomicExprs in those positions:
a-lamrepresents a user function. When the user wrote it, it took one argument
v-name, but now it takes two: its original argument
k-name, which will get bound to a continuation.
a-idis for an identifier that is bound to a value.
a-boolare simply values.
Finally, there are continuations:
k-lamrepresents a continuation.
v-nameis the name of the value it takes, and
exprsays what it does with it.
k-idis an identifier bound to a continuation (e.g. from
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: