Assignment 7: Continuations and Representation Independence

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.

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))))])))

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))])]
      [(eq? (car ls) '?) (cdr ls)]
      [else (cons (car ls) (rember*1 (cdr ls)))])))

CPS your interpreter. After CPSing, create two copies of your interpreter that are representation-independent with respect to continuations, using procedural representation for one copy, and data-structural representation for the other.

You will also need to implement the helpers for environments and procedures, using a representation of your choice. Feel free to share the environment and procedure helpers among all the interpreters. Do not CPS these helpers.

In all, you should implement three interpreters. Name your interpreters as follows:

Scheme's call/cc may not be used in any of your interpreters.

The code for value-of-cps-fn and value-of-cps-ds will be identical, except that they will call different sets of continuation helpers. When you define empty continuation constructors for value-of-cps-fn and value-of-cps-ds, name them empty-k-fn and empty-k-ds, respectively. This will make it possible for us to test and grade your code.

After your interpreter has been CPSed and you're ready to move on to the next phase of the assignment, you may want to make use of this method for making continuations representation-independent. (There are many valid ways to make continuations representation-independent, and it's up to you whether to use this technique or not.)

Start with this interpreter:

(define value-of
  (lambda (expr env)
    (pmatch expr
      [,n (guard (or (number? n) (boolean? n))) n]
      [(+ ,x1 ,x2) (+ (value-of x1 env) (value-of x2 env))]
      [(* ,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))]
      [(letcc ,k-id ,body) (call/cc (lambda (k)
                                      (value-of body (extend-env k-id k env))))]
      [(abort-with ,v-exp ,k-exp) ((value-of k-exp env) (value-of v-exp env))]
      [(abort-case ,v-exp ,k1-exp ,k2-exp) (let ((v (value-of v-exp env)))
      		   	  	  	     (cond
					       ((zero? v) ((value-of k1-exp env) v))
                                               (else ((value-of k2-exp env) v))))]
      [,x (guard (symbol? x)) (apply-env env x)]
      [(lambda (,id) ,body) (closure id body env)]
      [(,rator ,rand) (apply-closure (value-of rator env) (value-of rand env))])))

Here are a few test programs that work with every version of the interpreter. Remember to test your interpreter after each step in the transformation!

You will also be adding an abort form, which should run the following test cases in all 3 versions of your interpreter. Its takes a single expression, and it should abort to top level with the value of that expression.

(load "test.scm")
 
(define fact-5
  '((lambda (f)
      ((f f) 5))
    (lambda (f)
      (lambda (n)
        (if (zero? n)
            1
            (* n ((f f) (sub1 n))))))))
 
(define letcc-fun
  '(* 3 (letcc q (* 2 (abort-with 4 q)))))
 
(define abort-case-fun1
  '(+ 5 (letcc q (+ 3 (letcc p (+ 2 (abort-case 0 q p)))))))
 
(define abort-case-fun2
  '(+ 5 (letcc q (+ 3 (letcc p (+ 2 (abort-case 1 q p)))))))
 
(test "fact-5"
  (value-of-cps fact-5 (empty-env) (empty-k))
  120)
 
(test "letcc"
  (value-of-cps letcc-fun (empty-env) (empty-k))
  12)		
 
(test "abort-case-fun1"
  (value-of-cps abort-case-fun1 (empty-env) (empty-k))
   5)
 
(test "abort-case-fun2"
  (value-of-cps abort-case-fun2 (empty-env) (empty-k))
   9)
 
(test "fact-5-fn"
  (value-of-cps-fn fact-5 (empty-env) (empty-k-fn))
  120)
 
(test "letcc-fn"
  (value-of-cps-fn letcc-fun (empty-env) (empty-k-fn))
  12)
 
(test "abort-case-fun1-fn"
  (value-of-cps-fn abort-case-fun1 (empty-env) (empty-k-fn))
   5)
 
(test "abort-case-fun2-fn"
  (value-of-cps-fn abort-case-fun2 (empty-env) (empty-k-fn))
   9)
 
(test "fact-5-ds"
  (value-of-cps-ds fact-5 (empty-env) (empty-k-ds))
  120)
 
(test "letcc-ds"
  (value-of-cps-ds letcc-fun (empty-env) (empty-k-ds))
  12)
 
(test "abort-case-fun1-ds"
  (value-of-cps-ds abort-case-fun1 (empty-env) (empty-k-ds))
   5)
 
(test "abort-case-fun2-ds"
  (value-of-cps-ds abort-case-fun2 (empty-env) (empty-k-ds))
   9)

(define abort-fun
  '(* 3 (letcc q (* 6 (abort (+ 1 3))))))
 
(test "abort"
  (value-of-cps abort-fun (empty-env) (empty-k))
  4)
 
(test "abort-fn"
  (value-of-cps-fn abort-fun (empty-env) (empty-k-fn))
  4)
 
(test "abort-ds"
  (value-of-cps-ds abort-fun (empty-env) (empty-k-ds))
  4)

Place all of your code in a file named a7.scm 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$ $) (take$ (sub1 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$.

EDIT: Corrected mistake in sample cases.

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