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

As you proceed with this assignment, you may find the following resources helpful.

- Notes on making continuations representation-independent methodically.

- We provide a test suite a7-student-tests for Part 2; to test Part 1 you should modify the calls provided in this assignment to be invocations of your CPSed implementations.

1. Define and test a procedure `binary-to-decimal-cps`

that is a CPSed version of the following `binary-to-decimal`

procedure:

(define binary-to-decimal (lambda (n) (cond [(null? n) 0] [else (+ (car n) (* 2 (binary-to-decimal (cdr n))))])))

`binary-to-decimal`

uses little-endian binary numbers; you should consider binary sequences with one or more trailing `0`

s to be ill-formed binary numbers (bad data). Here are a few sample calls to make the meaning clear.

> (binary-to-decimal '()) 0 > (binary-to-decimal '(1)) 1 > (binary-to-decimal '(0 1)) 2 > (binary-to-decimal '(1 1 0 1)) 11

2. Define and test a procedure `rember*1-cps`

that is a CPSed version of the following `rember*1`

procedure, which removes the first `?`

in the arbitrarily nested list `ls`

:

(define rember*1 (lambda (ls) (cond [(null? ls) '()] [(pair? (car ls)) (cond [(equal? (car ls) (rember*1 (car ls))) (cons (car ls) (rember*1 (cdr ls)))] [else (cons (rember*1 (car ls)) (cdr ls))])] [(eqv? (car ls) '?) (cdr ls)] [else (cons (car ls) (rember*1 (cdr ls)))])))

This part of the assignment will be completed in several stages. You should do each of these steps in a separate file. Turn in a file containing the last step, and call it a7.rkt. But it is **imperative** that you keep each of the previous steps. We will ask to see them at some point in the future.

You should begin with the interpreter below. The interpreter below uses a slightly different language than the interpreters we have written before. Also, instead of Racket's `match`

, we are using `union-case`

. The function `union-case`

takes an element of a union, a union, which is a collection of patterns for special forms, and then a line for each pattern in the union. You can treat it like you would `match`

. To begin with, you can download the a7-0 and parenthec files. Leave `parenthec`

in the same directory as your a7 files.

#lang racket (require "parenthec.rkt") (define-union exp (const expr) (mult x1 x2) (sub1 x) (zero x) (if test conseq alt) (capture body) (return k-exp v-exp) (let e body) (var expr) (lambda body) (app rator rand)) (define value-of (lambda (expr env) (union-case expr exp [(const expr) expr] [(mult x1 x2) (* (value-of x1 env) (value-of x2 env))] [(sub1 x) (sub1 (value-of x env))] [(zero x) (zero? (value-of x env))] [(if test conseq alt) (if (value-of test env) (value-of conseq env) (value-of alt env))] [(capture body) (call/cc (lambda (k) (value-of body (lambda (y) (if (zero? y) k (env (sub1 y)))))))] [(return k-exp v-exp) ((value-of k-exp env) (value-of v-exp env))] [(let e body) (let ((a (value-of e env))) (value-of body (lambda (y) (if (zero? y) a (env (sub1 y))))))] [(var expr) (env expr)] [(lambda body) (lambda (a) (value-of body (lambda (y) (if (zero? y) a (env (sub1 y))))))] [(app rator rand) ((value-of rator env) (value-of rand env))]))) (value-of (exp_app (exp_lambda (exp_var 0)) (exp_const 5)) (lambda (y) (error 'value-of "unbound identifier")))

The a7-0 file contains the `expr`

union, `value-of`

and test program, so you can see how to invoke it. It's not essential that you keep this test program in subsequent files. When you write your own test programs, you will probably prefer not to write them directly in the language of this interpreter. We provide the file parse.rkt, which contains a function `parse`

that will convert normal Scheme-like syntax of our usual interpreter into the language we are using on this assignment. For example,

> (require "parse.rkt") > (parse '((lambda (a b c) (* a c)) 5 6 7)) '(exp_app (exp_app (exp_app (exp_lambda (exp_lambda (exp_lambda (exp_mult (exp_var 2) (exp_var 0))))) (exp_const 5)) (exp_const 6)) (exp_const 7))

Use this to generate tests for your program. Notice that the output is curried for you. Note also that our parser produces quoted output, but your `value-of`

will not take quoted expressions as input.

- CPS this interpreter. Call it
`value-of-cps`

. Use the “let trick” to eliminate the let binding when you CPS the`let`

line. You might consider always using`k^`

as the additional continuation variable to your extended 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 6. Scheme's`call/cc`

**may not**be used in your CPSed interpreter. - Define
`apply-env`

,`apply-closure`

, and`apply-k`

, and add all the calls to those functions. Notice your`apply-closure`

and`apply-env`

now take three arguments. - Define
`extend-env`

and replace all 3 of your explicitly higher-order representations of environments with calls to`extend-env`

. - Add a
`^`

to each of the formal parameters of`extend-env`

(not the inner function, mind you). Ensure that the inner functions in both`extend-env`

and`empty-env`

use the same formal parameters as the second argument to`apply-env`

(here, typically`y`

and`k^`

). - Replace your higher-order function representation of environments with a tagged-list data structure representation. Consider first ensuring that the last two formal parameters to
`apply-env`

(`y`

and`k`

) are the same as the formal parameters to the inner functions in`extend-env`

and`apply-env`

. Remember, if you add`(else (env y k))`

as the last line of your`match`

expression, you can test each transformation one at a time. - If you used it, remove the
`(else (env y k))`

as the last line of your`match`

expression in`apply-env`

. - Define
`closure`

and replace your explicitly higher-order representation of a closure with a call to`closure`

. - Replace your higher-order function representation of closures with a tagged-list data structure representation. Consider first ensuring that the last two formal parameters to
`apply-closure`

(`a`

and`k`

) are the same as the formal parameters to the inner function in`closure`

. - Define constructors for your continuations, and replace your explicitly higher-order function continuations with calls to these constructors. For nested continuations, you should consider working from the inside out. Remember, you can test each constructor replacement one at a time.
- Add a
`^`

to each of the formal parameters of your continuation helpers, and change the body to match (that is, do an alpha substitution). Then, ensure that the inner function in each of your continuation helpers uses the same formal parameter as the second argument to`apply-k`

(typically,`v`

). - Replace your higher-order function representations of continuations with a tagged-list data structure representation. Remember, if you add
`(else (k v))`

as the last line of your match, you can test each transformation one at a time. If you're good, you can do almost all of this step with a keyboard macro. - Remove the
`(else (k v))`

line to ensure that you've properly removed all higher-order function representations of continuations.

**Place your final version in a file named a7.rkt and submit it via Oncourse.**

For the brainteaser this week, you'll get to learn about `streams`

, a data-structure
that enables us to process infinite lists of items. Its a lazily-evaluated, memoized
(also termed *delayed*) list.

To play around, we'll first need to implement a few tools.

(define-syntax cons$ (syntax-rules () ((cons$ x y) (cons x (delay y))))) (define car$ car) (define cdr$ (lambda ($) (force (cdr $))))

We'll get back to those helpers. For now, its enough that they're tweaked `cons`

, `car`

, and `cdr`

.
The first question to ask is: how do you build an infinite list? The only reasonable answer is: one item at a time, as needed.
Here, we're going to define an infinite stream of ones.

(define inf-1s (cons$ 1 inf-1s))

It looks like that can't possibly work. We're definining the stream in terms of itself. That's a circular definition. But, in fact, that's precisely what we're after. We're defining a list that has a 1 in front and whose cdr - well, whatever that thing is, it has a 1 in the front of it. And thus its 1s all the way down.

So we can build a procedure `take$`

(define take$ (lambda (n $) (cond ((zero? n) '()) (else (cons (car$ $) (let ((n- (sub1 n))) (cond ((zero? n-) '()) (else (take$ n- (cdr$ $))))))))))

that pulls n items from the stream, and returns them in a list (the $ stands for $tream, by the way).

> (take$ 5 inf-1s) (1 1 1 1 1) > (take$ 10 inf-1s) (1 1 1 1 1 1 1 1 1 1)

So how is this all working? There's nothing to `car$`

. That's just `car`

with fancy window-dressing. `cons$`

is the first macro definition we've looked at in class. But there's nothing much to it, either. You can think of it as performing a textual transformation – every time we see something of the form (`cons$`

`<thing1>`

`<thing2>`

), that code is actually transformed as (`cons`

`<thing1>`

(`delay`

`<thing2>`

)) Importantly, `<thing2>`

isn't evaluated in the process. But do take note of the `delay`

form, and the `force`

form in `cdr$`

. As we've already seen, there are times in which we might like to evaluate an expression only once, and thereafter just return that already computed value. And we might like to hold off on doing that evaluation, instead of doing it right away. `delay`

does both of those – it creates a *promise*, of which `force`

can then force the evaluation. From there on out, every time we force that promise, we get the same value.

> (define worst-random (delay (random 4))) > (force worst-random) 2 > (force worst-random) 2 > (force worst-random) 2

So, to put it all together, we define `inf-1s`

to be a pair whose `car`

is 1 and whose `cdr`

is a promise. When we finally get around to evaluating that promise, we find that its value is in fact `inf-1s`

– that is, a pair whose `car`

is 1 and whose `cdr`

is a promise.

Hopefully that all makes sense. Your task this week is to implement the tribonacci stream. Its the sequence from the exam: 0 is the first tribonacci number, 1 is the second, 1 is the third, and the values thereafter are each the sum of the three previous values in the sequence. Call it `trib$`

.

> (car$ trib$) 0 > (car$ (cdr$ trib$)) 1 > (take$ 7 trib$) (0 1 1 2 4 7 13)

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.