Form new groups of two for this assignment. We will not accept this assignment from people working individually or with a partner from the previous assignments. Email me the names of the members of your group by 5 pm five days after the "out" date for this assignment (only one member needs to send this email). If you cannot find a partner, send us an email by the same deadline and you will be assigned a partner. In order to avoid being assigned a random partner, we suggest staying after class that day to find a partner in person. Missing the email deadline will lower your grade for this assignment by 10% per day late.

Each problem is clearly marked with a filename below. For each file that you submit that has the wrong name, you will lose 5% on the final grade.

Continuations (Written)

Problem 1

Submit your solution as whynostack.pdf

Any program that consumes some amount of stack, when converted to CPS and run, suddenly consumes no stack space at all. Why?

Problem 2

Submit your solution as filterk.ss

CPS the following Scheme function. You don’t need to CPS primitives such as empty?, first, rest, cons, cons? and <. You may also assume that the function argument to both of the functions is in CPS. Name the result filter/k as shown below.

;; filter: (x -> bool) (listof x) -> (listof x)
(define (filter f l)
  (cond
    [(empty? l) empty]
    [else (cond
            [(f (first l)) (cons (first l)
                                 (filter f (rest l)))]
            [else (filter f (rest l))])]))

;; filter/k: (x receiver -> doesn't return) (listof x) receiver -> doesn't return
(define (filter/k f l k)
  'fill-me-in)

Now change the following expressions to use filter/k. 

(define (less-than-three x)
   (< x 3))
(filter less-than-three
        (cons 1 (cons 4 empty))) ;; this evaluates to (list 1)

Problem 3

Submit your solution as stackinspect.ss

The Java security model uses a primitive called stack inspection. Let us implement a simple version of this. Assume the language had two new primitives: 

<E> ::= ...
    | {bless <E>}
    | {check}

The bless primitive creates a blessed stack frame for the duration of evaluating its sub-expression. The check primitive traverses the run-time stack; if it finds a blessed frame it evaluates to 0 (so you can, for instance, use it inside sums without affecting the outcome), otherwise it terminates the program's execution.

Extend the CPSed interpreter presented in the text in Figure 20.2 with these two new language constructs. For your convenience, here is a file to start with: stackinspect.ss

Note: Java lacks tail-call optimization ostensibly because this hurts the ability to implement stack inspection. In fact, this claim is entirely false. But we're stuck with the result of this decision, making the JVM a poor target for other language compilers. Unfortunately, .NET has also adopted this mistake, as the paper explains.