On this page:
3.13.1 Stack Space
3.13.2 CPS Transformation
3.13.3 Stack Inspection
3.13.4 Application

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)
    ....)

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)

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:

"stackinspect.rkt":
  #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.