2.13 Continuations
Complete this assignment with Team Two.
You must submit this in an archive named "wcont.zip".
2.13.1 Stack Space
You must submit this in a file named "whynostack.pdf".
Any program that consumes some amount of stack, when converted to CPS and run, suddenly consumes no stack space at all. Why?
2.13.2 CPS Transformation
You must submit this in a file named "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) (listof x) receiver -> doesn't |
| (define (filter/k f l k) |
| ....) |
| (define (less-than-three x) |
| (< x 3)) |
| (filter less-than-three |
| (cons 1 (cons 4 empty))) ; this evaluates to (list 1) |
2.13.3 Stack Inspection
You must submit this in a file named "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:
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.
| 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:
| #lang planet plai/plai |
| (define-type KCFAE |
| [num (n number?)] |
| [add (lhs KCFAE?) (rhs KCFAE?)] |
| [id (name symbol?)] |
| [if0 (test KCFAE?) (truth KCFAE?) (falsity KCFAE?)] |
| [fun (param symbol?) (body KCFAE?)] |
| [app (fun-expr KCFAE?) (arg-expr KCFAE?)] |
| [bless (body KCFAE?)] |
| [check]) |
| (define-type KCFAE-Value |
| [numV (n number?)] |
| [closureV (p procedure?)] |
| [contV (c procedure?)]) |
| (define-type DefrdSub |
| [mtSub] |
| [aSub (name symbol?) (value KCFAE-Value?) (ds DefrdSub?)]) |
| ; lookup : symbol DefrdSub -> KCFAE-Value |
| (define (lookup name ds) |
| (type-case |
| DefrdSub ds |
| [mtSub () (error 'lookup "no binding for identifier")] |
| [aSub (bound-name bound-value rest-ds) |
| (if (symbol=? bound-name name) |
| bound-value |
| (lookup name rest-ds))])) |
| ; num+ : KCFAE-Value KCFAE-Value -> KCFAE-Value |
| (define (num+ x y) |
| (numV (+ (type-case |
| KCFAE-Value x |
| [numV (n) n] |
| [else (error 'num+ "addition of a non-number")]) |
| (type-case |
| KCFAE-Value y |
| [numV (n) n] |
| [else (error 'num+ "addition of a non-number")])))) |
| ; num-zero? : KCFAE-Value -> boolean |
| (define (num-zero? n) |
| (type-case |
| KCFAE-Value n |
| [numV (n) (= n 0)] |
| [else |
| (error 'num-zero? "argument must be a number")])) |
| ; interp : KCFAE Env receiver -> (doesn't) |
| (define (interp expr env k) |
| (type-case |
| KCFAE expr |
| [num (n) (k (numV n))] |
| [add (l r) (interp l env |
| (lambda (lv) |
| (interp r env |
| (lambda (rv) |
| (k (num+ lv rv))))))] |
| [if0 (test truth falsity) |
| (interp test env |
| (lambda (tv) |
| (if (num-zero? tv) |
| (interp truth env k) |
| (interp falsity env k))))] |
| [id (v) (k (lookup v env))] |
| [fun (param body) |
| (k (closureV |
| (lambda (arg-val dyn-k) |
| (interp body (aSub param arg-val env) dyn-k))))] |
| [app (fun-expr arg-expr) |
| (interp |
| fun-expr env |
| (lambda (fun-val) |
| (interp |
| arg-expr env |
| (lambda (arg-val) |
| (type-case |
| KCFAE-Value fun-val |
| [closureV (c) (c arg-val k)] |
| [contV (c) (c arg-val)] |
| [else |
| (error 'interp "not an applicable value")])))))] |
| [else (error 'interp "incomplete interp!")])) |
| ; test-interp : KCFAE -> KCFAE-Value |
| (define (test-interp expr) |
| (let/cc k (interp expr (mtSub) k))) |
| (test (test-interp (add (num 3) (num 4))) (numV 7)) |
2.13.4 Application
You must submit this in a file named "wcont-app.pdf".
In 850 words or less, describe if and how your knowledge of continuations and CPS will help you in your future programming practice. Good answers might discuss how this concept can be applied in interesting programming environments or how knowledge of its subtleties clarifies or improves existing practices, techniques, tools, etc.