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:
whynostack.txt
, which contains your solution to Problem 1.filterk.rkt
, which contains your solution to Problem 2.stackinspect.txt
, which contains your solution to Problem 3.generator.txt
, which contains your solution to Problem 4.
/course/cs173/bin/cs173handin cont-writ