7.7.0.3
9 — CPS
Due Friday, 20 March, Tuesday 24 March 2020, 6am
The purpose of this homework problem is to understand the mechanics
of control aka continuation conversions.
Delivery Deliver your solutions in a folder called 9 in your
github repo:
|
9 / |
xcps |
Other/ |
ITests/ |
[0-4]-in.json |
[0-4]-out.json |
A name ending in / is a folder, and indentation means “contained in the
closest folder listed above the current name.”
Programming Task
Toy is a new name for our old language from
5 — Simple Mutable Objects. It covers
variables, numeric literals, declarations, functions, function calls, and
decisions:
An Toy is one of: |
- a Var |
- an Int |
- a JSON array of the shape [TDecl,...,TDecl,Toy] |
all variables declared in one TDecl sequence are pairwise distinct |
- a JSON array of the shape ["fun*",VarList,Toy] |
all variables in one VarList sequence are pairwise distinct |
- a JSON array of the shape ["call",Toy,Toy,...,Toy] |
- a JSON array of the shape ["if-0",Toy,Toy,Toy] |
|
An TDecl is |
- a JSON array of the shape ["let", Var, "=", Int] |
- a JSON array of the shape ["let", Var, "=", ["fun*", VarList, Toy]] |
Nothing else is a
Toy. Note the absence of infix expressions; just
use explicit calls instead.
Toy does not permit the redefinition of primitives.
Step 0 Repair your parser from 5 — Simple Mutable Objects in case it failed test
cases in the past.
Step 1 Design the program alpha-equal, which consumes two
Toy expressions, converts them into static-distance form, and
then compares them these two static-distance forms for equality. You may wish to start from the
static-distance function of 2 — Static Distance, Simple Interpretation, which covers most of Toy.
Hint The existing static-distance functionality
retains the variable names of declared variables and function parameters.
You want to replace these names with a single constant name. Thus, if you
are in Java and you chose to represent variables with strings, you may wish
to replace all variable declarations and function parameters with
"_" in your abstract syntax representation. The static-distance
function should retain only names that are defined in the prelude or names
that are neither declared nor parameters.---Once you have terms in static
distance form, your unit tests can simply check whether they are
identical. Here is an example from unit test suite:
| (check α=? |
| (cps "x") |
| [fun ["k"] [cal "k" ["x"]]] |
| "variable case") |
The α=? function converts each of the two expressions into static
distance form and then ensures that they are the same. That way I don't
have to worry which k the cps function uses.
Step 2 Design the program cps, which consumes a Toy
expression and produces a Toy expression in continuation-passing
style that, if it were evaluated, would evaluate all sub-expressions in the
same order as the given one.
Remember that continuation-passing style means all function calls
must be in tail position.
Unlike the language in class, Toy has functions
that take many arguments. Pass the continuation argument as the first
one. Do not curry your functions.
Hint The cps conversion of primitive operations deserves special
attention. First, make sure
cps can distinguish ordinary identifiers
from prim-op identifiers. Second, transform prim-ops such as
"+" to
cps
Toy expression
["fun", ["k" "x" "y"], |
["call", "k", |
["call", "+", "x", "y"]]] |
Step 3 Design the program unparse, which consumes a Toy
expression and produces its JSON rendering.
Testing Task Write the test harness xcps for your cps programs.
Create five tests for xcps. Place them in ITests/. A test consists
of two files: N-in.json and N-out.json for N in [0 .. 4]:
Recall JSON: Simplicity and Complexity.