3.13 Continuations
Complete this assignment with Team Two.
You must submit this in an archive named "wcont.zip". This archive must contain a folder named "wcont". This folder must contain all the files specified below. You must attach "wcont.zip" to an email whose subject is "BYU - Fall 2010 - CS 330 - wcont" and whose message body contains the name of everyone on your team (each on a separate line.) You must send this email to jay@cs.byu.edu before 5pm (Provo time) on 11/2. Ensure that what you are satisfied with what you submit, because only your chronologically first submission will be graded. Ensure that you follow these instructions exactly, since submissions that do not meet these requirements (i.e. do not have the correct format) will receive no credit, despite the time and energy you put into the assignment. Please see Turn In Policy for more information.
3.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?
3.13.2 CPS Transformation
You must submit this in a file named "filterk.rkt".
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) (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) |
3.13.3 Stack Inspection
You must submit this in a file named "stackinspect.rkt".
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 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)) |
3.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.