CS217 Day 18 Monday, May 8, 2000

Continuation-Passing Interpreters

• Our interp3-7 is deeply recursive. There are some simple base cases to eval-expression, but there are several cases where the result of one call is used in others. A very deep control context has to be built in evaluating complex expressions.

  A continuation passing style (CPS) procedure is one in which control information is passed in a "continuation" parameter, and no context has to be remembered. It's result is determined without ever having to return from a procedure call.

  We are going to rewrite eval-expression as a CPS procedure, as in 4.1, p113-132 of EOPL II. The rewriting procedure is a special case of a general procedure described in Ch 5.

  Making control explicit via continuations would enable us to add exception handling and multiple threads to our interpreter. (See 4.4, 4.5)

• We start with

  (define eval-expression
    (lambda (exp env)
      (cases expression exp
        (lit-exp (datum) datum)
        (bool-exp (bval) bval)
        (var-exp (id) (apply-env env id))
        (primapp-exp (prim rands)
  	(let ((args (eval-rands rands env)))
  	  (apply-primitive prim args)))
        (if-exp (test-exp true-exp false-exp)
  	(if (true-value? (eval-expression test-exp env))
  	    (eval-expression true-exp env)
  	    (eval-expression false-exp env)))
        (let-exp (ids exps body)
  	(let ((args (eval-rands exps env)))
  	  (eval-expression body (extend-env ids args env))))
        (letrec-exp (proc-names idss bodies letrec-body)
  	(eval-expression letrec-body
  	  (extend-env-recursively proc-names idss bodies env)))
        (proc-exp (ids body)
  	(closure ids body env))
        (app-exp (rator rands)
  	(let ((proc (eval-expression rator env))
  	      (args (eval-rands rands env)))
  	  (apply-procval proc args)))
        (varassign-exp (id rhs-exp)
  	(begin
  	  (setref!
  	    (apply-env-ref env id)
  	    (eval-expression rhs-exp env))
  	  1))
        (begin-exp (exp exps)
  	(eval-begin exp exps env))
        (else
  	(error 'eval-expression "bad exp ~s" exp)))))
  
  (define eval-begin
    (lambda (exp exps env)
      (let ((val (eval-expression exp env)))
        (if (null? exps)
  	  val
  	  (eval-begin
  	    (car exps)
  	    (cdr exps)
  	    env)))))
  
  (define eval-rands
    (lambda (rands env)
      (map (lambda (rand) (eval-rand rand env)) rands)))
  
  (define eval-rand
    (lambda (rand env)
      (eval-expression rand env)))
  

  A continuation is applied to the value of a procedure. It prescribes "what to do with" the value. Our interpreter will print the value of a program. Thus, we want to add a cont parameter to eval-expression to pass a continuation. Then

  (define run
    (lambda (string)
      (eval-program (scan&parse string))))
  
  (define eval-program
    (lambda (pgm)
      (cases program pgm
        (a-program (exp)
  	(eval-expression exp (make-init-env)
  	  (halt-cont))))))
  
  (define halt-cont
    (lambda (val)
      (begin (display "Value is: ") (write val) (newline))))
  

  The third actual parameter to eval-expression is a continuation that, in this case, prints "Value is: " is printed, and then the result.

  We will use apply-cont to apply continuations. With a procedural implementation, apply-cont would be

  (define apply-cont
    (lambda (cont val)
      (cont val)))
  

• We will use define-datatype to implement continuations using records. Then halt-cont and apply-cont can be defined by

  (define-datatype continuation continuation?
    (halt-cont))
  
  (define apply-cont
    (lambda (cont val)
      (cases continuation cont
        (halt-cont ()
  	(begin
  	  (display "Value is: ") (write val) (newline)))
        (else
  	(error 'apply-cont "bad continuation ~s" cont)))))
  

• In evaluating if-exp, we first evaluate the test expression, and depending on the result, either the true expression or the false expression.

  The continuation of evaluating the test expression, test-cont has to be constructed to do this to the result, and then to apply the given continuation. Thus,

  (define-datatype continuation continuation?
    (halt-cont)
    (test-cont
      (true-exp expression?)
      (false-exp expression?)
      (env environment?)
      (cont continuation?)))
  
  (define apply-cont
    (lambda (cont val)
      (debug 'apply-cont cont val)
      (cases continuation cont
        (halt-cont ()
  	(begin
  	  (display "Value is: ") (write val) (newline)))
        (test-cont (true-exp false-exp env cont)
  	(if (true-value? val)
  	    (eval-expression true-exp env cont)
  	    (eval-expression false-exp env cont)))
        (else
  	(error 'apply-cont "bad continuation ~s" cont)))))
  

• Continuations have to be constructed for each case where there is something new to do with the result of a call to eval-expression . The "final result" follows. Note first how the base cases and "if" case are handled.

  (define eval-expression
    (lambda (exp env cont)
      (cases expression exp
        (lit-exp (datum) (apply-cont cont datum))
        (bool-exp (bval) (apply-cont cont bval))
        (var-exp (id) (apply-cont cont (apply-env env id)))
        (primapp-exp (prim rands)
  	(eval-rands rands env
  	  (prim-args-cont prim cont)))
        (if-exp (test-exp true-exp false-exp)
  	(eval-expression test-exp env
  	  (test-cont true-exp false-exp env cont)))
        (let-exp (ids exps body)
  	(eval-rands exps env
  	  (let-exp-cont ids env body cont)))
        (letrec-exp (proc-names idss bodies letrec-body)
  	(eval-expression letrec-body
  	  (extend-env-recursively proc-names idss bodies env)
  	  cont))
        (proc-exp (ids body)
  	(apply-cont cont (closure ids body env)))
        (app-exp (rator rands)
  	(eval-expression rator env
  	  (eval-rator-cont rands env cont)))
        (varassign-exp (id rhs-exp)
  	(eval-expression rhs-exp env
  	  (varassign-exp-cont id env cont)))
        (begin-exp (exp exps)
  	(eval-expression exp env
  	  (begin-exp-cont exps env cont)))
        (else
  	(error 'eval-expression "bad exp ~s" exp)))))
  
  (define eval-rands
    (lambda (rands env cont)
      (if (null? rands)
  	(apply-cont cont '())
  	(eval-expression (car rands) env
  	  (eval-first-cont rands env cont)))))
  

• The continuations that need to be constructed and their definitions follow. A debug procedure is shown to enable displaying the args in calls of apply-cont.

  (define-datatype continuation continuation?
    (halt-cont)
    (test-cont
      (true-exp expression?)
      (false-exp expression?)
      (env environment?)
      (cont continuation?))
    (prim-args-cont
      (prim primitive?)
      (cont continuation?))
    (eval-first-cont
      (rands (list-of expression?))
      (env environment?)
      (cont continuation?))
    (eval-rest-cont
      (first expval?)
      (cont continuation?))
    (varassign-exp-cont
      (id symbol?)
      (env environment?)
      (cont continuation?))
    (let-exp-cont
      (ids (list-of symbol?))
      (env environment?)
      (body expression?)
      (cont continuation?))
    (eval-rator-cont
      (rands (list-of expression?))
      (env environment?)
      (cont continuation?))
    (app-exp-cont
      (proc procval?)
      (cont continuation?))
    (begin-exp-cont
      (exps (list-of expression?))
      (env environment?)
      (cont continuation?)))
  
  (define *debug* #f)
  
  (define debug
    (lambda args
      (if *debug*
  	(pretty-print args)
  	0)))
  
  (define apply-cont
    (lambda (cont val)
      (debug 'apply-cont cont val)
      (cases continuation cont
        (halt-cont ()
  	(begin
  	  (display "Value is: ") (write val) (newline)))
        (test-cont (true-exp false-exp env cont)
  	(if (true-value? val)
  	    (eval-expression true-exp env cont)
  	    (eval-expression false-exp env cont)))
        (prim-args-cont (prim cont)
  	(apply-cont cont (apply-primitive prim val)))
        (eval-first-cont (rands env cont)
  	(eval-rands (cdr rands) env
  	  (eval-rest-cont val cont)))
        (eval-rest-cont (first-val cont)
  	(apply-cont cont (cons first-val val)))
        (varassign-exp-cont (id env cont)
  	(begin
  	  (setref!
  	    (apply-env-ref env id)
  	    val)
  	  (apply-cont cont 1)))
        (let-exp-cont (ids env body cont)
  	(let ((new-env (extend-env ids val env)))
  	  (eval-expression body new-env cont)))
        (eval-rator-cont (rands env cont)
  	(eval-rands rands env
  	  (app-exp-cont val cont)))
        (app-exp-cont (proc cont)
  	(apply-procval proc val cont))
        (begin-exp-cont (exps env cont)
  	(if (null? exps)
  	    (apply-cont cont val)
  	    (eval-expression (car exps) env
  	      (begin-exp-cont (cdr exps) env cont))))
        (else
  	(error 'apply-cont "bad continuation ~s" cont)))))
  

• Here is the resulting code -- interp4-1cps.scm

We will next examine Scheme.java, a call-by-value interpreter in Java that parses and evaluates list syntax. We'll read and try to understand the code.

This example will be an introduction object-oriented languages (OOL). We will extend our interpreter to interpret an OOL (See Ch 6), and also extend Scheme to be an OOL, School.