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 /






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]:
  • An input file in ITests contains a single Toy expression.

  • An output file is the cps (continuation-passing style) version of the input Toy.

Recall JSON: Simplicity and Complexity.