Continuations (Written)

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 the names of the members of your group by 5 pm on Wednesday, 10/17/07 (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 on Wednesday 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.

Please remember to follow the style and testing guidelines outlined in the syllabus.

Problem 1

Submit your solution as whynostack.txt

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

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)
    [(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)

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

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:

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.

UPDATE: bind/cc has been removed from the template code. You do not need to handle it for this assignment.

Collaboration and Submission

This is a collaborative assignment.

One team-member should handin the assignment. From the directory containing your answers, execute:

/course/cs173/bin/cs173handin writcont

Include a README file containing the names of the members of the group.