Continuations

Problem 1

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

As a corollary, does conversion to CPS reduce the overall memory footprint of the program?


Problem 2

CPS the following Racket 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 convert the following to use filter/k.

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

Problem 3

Java's native security model employs a mechanism called stack inspection (look it up if you aren't familiar with it). What is the interaction between stack inspection and CPS? That is, if we were to CPS a program, would this affect its security behavior?

If not, why not?

If so, how, and what would you suggest doing to recover security assuming the CPS conversion was necessary?


Problem 4

We have seen in quiz that Python's generators do not permit any abstraction over yielding, whereas Racket's do. Assuming this was intentional, why might Python have made such a design decision?


Handin

Turn in four files:

  1. whynostack.txt, which contains your solution to Problem 1.
  2. filterk.rkt, which contains your solution to Problem 2.
  3. stackinspect.txt, which contains your solution to Problem 3.
  4. generator.txt, which contains your solution to Problem 4.
From the directory containing your solutions, execute
/course/cs173/bin/cs173handin cont-writ