9 Assignment 9: Capturing Continuations

So, you’re telling us that the universe is written in continuation-passing style?

——Phil Wadler, sometime during ICFP 2004

Part I: let/cc

This part is just for you to practice using Racket’s let/cc, so you should not CPS anything.

1. Complete the following definition of last-non-zero, a function which takes a list of numbers and return the last cdr whose car is 0. In other words, when starting from the right of the list, it should be all numbers before the first 0 is reached. See the test cases below. Your solution should be naturally recursive, and should not call any member-like operation, nor should you be reversing the list.

   (define last-non-zero

   (lambda (ls)

   (let/cc k

   (letrec

   ((last-non-zero

   (lambda (ls)

   (cond

   ;; fill in lines here

   ))))

   (last-non-zero ls)))))

   > (last-non-zero '(0))
   ()
   > (last-non-zero '(1 2 3 0 4 5))
   (4 5)
   > (last-non-zero '(1 0 2 3 0 4 5))
   (4 5)
   > (last-non-zero '(1 2 3 4 5))
   (1 2 3 4 5)
   >

   Advice on this problem: first, get it to work for the base case. Then, get it to work for a list with no 0s in it. Then, get it to work for a list with one 0 in it. Then, get it to work for a list with more than one 0 in it. And you’re going to be using that continuation k somewhere in your definition.

Part II: CPS interpreter

2. Take the first step towards a low-level interpreter that does not grow the control context: CPS this interpreter.

   • Start by turning each test of value-of above into a test of value-of-cps.

     (define empty-k

     (lambda ()

     (lambda (v) v)))

     (check-equal? (value-of-cps ... (empty-env) (empty-k)) ...)

     Consider writing additional tests.

   • CPSing this interpreter includes CPSing all environments (lambda (y) ...) and closures (lambda (a) ...) so that they take an additional continuation argument. As you do this, consider renaming environments to env-cps and closures to c-cps. Also consider always using the name k^ for the continuation argument you add to environments.

     Do not apply k^ to the call to error in empty-env. This is similar to the behavior of times-cps-shortcut from Assignment 8.

   • You might consider commenting out some of your match clauses, and CPSing the interpreter a few lines at a time.

   • If you’re not sure how to CPS (let ((a (value-of e env))) ...), recall that it is equivalent to ((lambda (a) ...) (value-of e env)).

   • Racket’s let/cc may not be used in your CPSed interpreter.

Brainteaser

3. The fact that variables in the object language above are identified by de Bruijn indices rather than symbol names makes it easier to produce a low-level interpreter for it, but makes it harder to write test programs in it. It would be much easier to write test programs with variable names, defined by the following grammar:

   Expr		=		Number
   		|		Boolean
   		|		Symbol
   		|		(* Expr Expr)
   		|		(sub1 Expr)
   		|		(zero? Expr)
   		|		(λ Symbol Expr)
   		|		(Expr Expr)
   		|		(let Symbol Expr Expr)
   		|		(if Expr Expr Expr)
   		|		(catch Symbol Expr)
   		|		(throw Expr Expr)

   So, define and test a compiler that turns variable names into de Bruijn indices. This is similar to lambda-lex from Assignment 3: Your function lex should take an Expr and an accumulator (a list of symbols which starts empty) and return the corresponding DeBruijn expression. Assume that the input Expr has no free variable occurrence.

   • Note that the DeBruijn grammar uses different words in a handful of places, such as const mult zero lambda app. So your lex should contain match clauses like

     [`(* ,e1 ,e2)    `(mult ,(lex e1 acc) ,(lex e2 acc))]

     [`(zero? ,e0)    `(zero ,(lex e0 acc))]

     [`(,rator ,rand) `(app ,(lex rator acc) ,(lex rand acc))]

   • Recall that the expression `(let ,name ,rhs ,body) binds the variable name only in body, not in rhs.

     The expression `(catch ,name ,body) binds the variable name in body.

Just Dessert

By now, you probably have a pretty strong intuition as to the mechanical process by which you CPS programs. As mentioned in class, it is possible to write a program that automatically performs CPS transformations. Write a procedure that takes an expression and returns a CPSed version of that expression. You may find it exceedingly helpful to consult Danvy and Nielsen’s “A First-Order One-Pass CPS Transformation”, specifically Figure 2 on page 244 and the surrounding discussion. Take note of the four specific cases in which they treat applications.

This is a little more open-ended than most of our problems; you can get it to work on the lambda-calculus, or add more forms if you want (this will probably make it easier to test and to use it). Add a comment in your assignment to tell us how to call and to use your CPSer.