Advanced Methods in Programming Languages (201-2-4411-01)
Notes Week 7 - Michael Elhadad
previous class main page next class

Interpreters and Reflection

Meta-language Continuations

We have started with a recursive environment interpreter and applied the following transformations:
  1. Transform to CPS style using procedural continuations
  2. Transform procedural continuations into a record-based implementation of continuations
  3. Registerization: remove parameter passing in the CPS interpreter
We have then obtained an interpreter for a recursive language which is iterative and has made explicit the handling of a recursive stack in the form of a continuation parameter. This interpreter can be easily implemented in an assembler-like language when considering that a function definition is like a label and function invocation (with no parameters and no need for "return" because we work in CPS style) is equivalent to a jump to a label.

The continuation parameter when implemented as a record-based datastructure, takes the form of a stack: all the various sub-types of the continuation datatype have a "next continuation" field, which can be interpreted as a pointer to the rest of the stack. In all invocations of continuation constructors, the current continuation is passed as the "next continuation" field -- which means that new continuations are always obtained by "pushing" an activation frame on top of the current continuation.

Correspondingly, in the code for apply-cont, the interpreter functions are invoked with the field "next continuation" of the current continuation -- which means that invoking a continuation corresponds to a "pop" of an activation frame from the current continuation stack.

In the current version of the interpreter, the signature of the eval-exp function is the following:

(define eval-exp 
  (lambda (exp env cont) ...))
We now apply an operation known as reflection which will make available, in the object language, the objects which we manipulate in the meta-language when running the interpreter.

The two objects we consider are:

  1. The current environment: by providing access to the current environment to the object language - as a new expressed value type, we give the programmer in the object language the ability to query the state of variables using variable names.
  2. The current continuation: by giving access to the current continuation to the programmer, we open new capabilities to model "non-local" control structures, such as exception handling, multi-threading or co-routines.
Reflection in general gives the programmer the possibility to extend the object language with "compiler-like" functionality: code generation, code inspection, runtime inspection, debugging.

Reflection on the Current Environment

To give access to the current environment in the object language, we must do the following:
  1. Extend the expressed value domain: ExpVal = Number + String + Closure + Env
  2. Introduce a new syntactic form (or a primitive) which returns the current environment as an expressed value and to manipulate environments:
         <exp> ::= (current-env)
         
         ;; New primitives:
         (apply-env env string)      --> ExpVal
         (update-env env string val) --> 1
         
  3. Add a new computation rule to evaluate the current-env expression and extend the apply-prim procedure to implement the apply-env and update-env primitives.
The following program shows how this feature can be used in an object language:
;; Program in L9
(let ((a 1) (b 2))
  (let ((e (current-env)))
    (let ((a 3)
          (p (proc (e s) (apply-env e s))))
      (+ (p e "a")
         (p (current-env) "a")))))
This is implemented in the following interpreter which is a variation of the CPS interpreter studied last week:
;; CPS interpreter - record-based continuations
;; with reflection on environments.

(define-datatype program program?
  (pgm (body expression?)))

;; Define an expressed value to wrap meta-language continuations
(define-datatype object-env object-env?
  (the-env (env env?)))

(define eval-program
  (lambda (p)
    (cases program p
      (pgm (body)
        (eval-exp body (empty-env) (halt-cont))))))

(define eval-exp
  (lambda (exp env cont)
    (cases expression exp
      (lit-exp (datum) (apply-cont cont datum))
      (var-exp (id) (apply-cont cont (apply-env env id)))
      (proc-exp (ids body) (apply-cont cont (closure ids body env)))
      (if-exp (test-exp then-exp else-exp)
        (eval-exp test-exp env
          (test-cont then-exp else-exp env cont)))
      (primapp-exp (prim rands)
        (eval-rands rands env
          (prim-args-cont prim cont)))
      (app-exp (rator rands)
        (eval-exp rator env
          (proc-cont rands env cont)))
      (let-exp (ids rands body)
        (eval-rands rands env
          (args-cont body ids env cont)))
      (varassign-exp (id rhs-exp)
        (eval-exp rhs-exp env
          (rhs-val-cont env id cont)))
      (current-env ()
        (apply-cont cont (object-env env)))
      )))

(define apply-primitive
  (lambda (prim args)
    (case prim
      ((+) (+ (car args) (cadr args)))
      ((-) (- (car args) (cadr args)))
      ((*) (* (car args) (cadr args)))
      ((/) (/ (car args) (cadr args)))
      ((apply-env) 
        (cases object-env (car args)
          (the-env (env) (apply-env env (string->symbol (cadr args)))))
      ((update-env)
        (cases object-env (car args)
          (the-env (env) 
            (setref! (apply-env-ref env (string->symbol (cadr args)))))))))

Reflection on the Current Continuation

To obtain the current continuation in the object language, we adopt the same strategy. We then obtain the following behavior:
((proc (k) (+ (* 2 (k 1)) 3)) (current-cont)) --> 1

(* 2 ((proc (k) (+ 1 (k 3))) (current-cont))) --> 6

(let ((i 10) (sum 0) (k 0))
  (begin
    (set! k (current-cont))
    (if i 
        (begin (set! sum (+ sum i)) (set! i (- i 1)) (k 0))  ;; This is like a loop
        sum)))
--> 55

(let ((i 0) (p (current-cont)))
  (begin (set! i (+ i 1)) (p i)))
--> Error: attempting to apply 1 to 2
This functionality is available in Scheme (considered here as an object language, not as our meta-language), with a slightly different design. The primitive is a special form called call-with-current-continuation, often written call/cc. call/cc has the following syntax:
;; invoke the procedure with the current continuation as a parameter
(call/cc (lambda (k) ...))  

;; Invoke a continuation with v as a parameter
(k v)
Consider the following Scheme expressions:
;; Define a global variable
% (define toplevel '*)

;; Bind the global toplevel to the toplevel continuation
;; in the read-eval-print loop of the Scheme interpreter
% (call/cc (lambda (k) (set! toplevel k)))

;; Use the toplevel continuation
% (+ (toplevel 1) 2)
1

;; Toplevel ignores the current environment
% (+ (* 2 (toplevel 3)) 4)
3

A possible usage of this feature would be to write a sort of debugger. Consider the following design:

;; break: stop the current computation and return to the toplevel
;; Remember in the resume continuation how to return to the stopped
;; computation.
(define resume '*)

(define break
  (lambda (v)
    (call/cc (lambda (k)
      (begin (set! resume k)
             (display "Break: ")
             (toplevel v))))))

;; Usage:
% (+ (break 1) (break 2))
Break: 1

% (resume 5) ;; compute (+ 5 (break 2))
Break: 2

% (resume 6) ;; compute (+ 5 6)
11        

If we want to write a really useful debugger, we also need the possibility to break, go back to the context in which the computation was stopped, inspect the environment in this context, and then resume the computation (possibly after having changed the value of some variables in the environment). Assuming we extend Scheme with reflection on the environment as discussed above, this can be achieved by the following design:
;; Define a global resume
(define resume '*)

;; inspect the current environment
;; Special purpose read-eval-print loop
;; with 3 command:
;; v var: view a variable value in the current env
;; s var val: set a variable value
;; r: resume (exit the break mode and continue the computation
(define inspect-current-env
  (lambda (e)
    (begin
      (display "Break: enter a command (v var), (s var val), (r val): ")
      (let ((c (read)))
        (case (car c)
          ((v) (display (apply-env e (cadr c))))
          ((s) (display (update-env e (cadr c) (caddr c))))
          ((r) (resume (cadr c)))))
      (newline)
      (inspect-current-env e))))
      
;; break is more complex: it also returns to the context where it occurred...
(define break
  (lambda ()
    (let ((e (current-env)))           ;; remember the current environment with no modifs.
      (call/cc (lambda (k)
        (begin (set! resume k)         ;; remember the current continuation
               (k                      ;; return to the current context where break occurred
                 (call/cc (lambda (k2) ;; and run an evaluation loop in this context
                   (inspect-current-env e))))))))))

This method is quite close to how actual debuggers work at the machine level: break is implemented by an "interrupt" instruction, which is caught by the debugger code. The debugger runs its own interpreter loop, and then resume continues where the break stopped. The "remember current environment" operation is performed as a store of the current "top of stack" register.

The implementation of current-cont is to be done in assignment 4.

Exception Handling

In general, continuations allow us to modify the control context. Exceptions are a "well-defined" and restricted way to use non current continuation in the object language.

To support exceptions in the object language, we add two syntactic forms:

  <exp> ::= try <exp> handle <exp> (try-exp (body-exp handler-exp))
         | raise <exp>            (raise-exp (exp))
Try-exp first evaluates the handler which should return a procedure of one argument. It installs this handler as an exception handler, and then evaluates the body. If the body returns normally, the value of the whole try expression is that of the body, and the exception handler is removed.

If a raise expression is evaluated, the expression of the raise is evaluated, and this value is sent to the most-recently installed exception handler. The exception handler can either return a value, which becomes the value of corresponding try expression, or it can propagate the exception by raising another exception. In this case, the next exception handler in the chain will be activated.

Consider the standard example of the list-index procedure, which receives as parameters a list and an element and should return -1 if the element is not a member of the list, or the index of the first occurrence of the element in the list otherwise.

letrec index (n, l) = if null?(l) then -1
                      else if equal?(n, car(l))
                           then 0
                           else let p = (index n cdr(l))
                                in if equal?(p, -1)
                                   then -1
                                   else +(1, p)
  in index(1, list(2, 3, 4))
This code has a complex logic because the "special" value of -1 must be tested at all the levels of the recursion. We can avoid this by raising an exception when the list becomes empty:
let index = proc(n, l)
  letrec loop(l) = if null?(l)
                   then raise(-1)
                   else if equal?(n, car(l))
                        then 0
                        else +(1, (loop cdr(l)))
    in try (loop l) handle proc (x) x
  in index(1, list(2, 3, 4))
To implement exception-handling, we add 2 new continuation constructors:
  (handler-cont (body exp?)
                (env environment?)
                (cont continuation?))
  (try-cont (handler expval?)
            (cont continuation?))
And we add to eval-exp the following evaluation rule for try:
  (try-exp (body-exp handler-exp)
    (eval-exp handler-exp env
      (handler-cont body-exp env cont)))
To the specification of continuations, we add the equation:
(apply-cont (handler-cont body-exp env cont) handler-val) ===
  (if (procval? handler-val)
    (eval-exp body-exp env
      (try-cont handler-val cont))
    (error "Handler is not a procedure"))
When the body of the try is evaluated, and the body returns normally, the value should be passed to the "current continuation". This means:
(apply-cont (try-cont handler cont) val) ===
  (apply-cont cont val)
If an exception is raised, then we need to search through the continuation stack to find the most recent handler. The handler must be found in the topmost try-cont continuation.
;; In eval-exp
(raise-exp (exp)
  (eval-exp exp env (raise-cont cont)))
And in the continuation specification, we add:
(apply-cont (raise-cont cont) val) ===
  (find-handler val cont)


(define find-handler
  ;; Unwind the exception stack until a handler is found
  (lambda (val cont)
    (cases continuation cont
      ;; Found a handler: activate it
      ;; Pass the value of the handler as the value of the try.
      (try-cont (handler cont)
        (apply-procval handler (list val) cont))
      ;; End of stack: no handler found
      (halt-cont ()
        (error "Uncaught exception"))
      ;; All other cases: link to next continuation in stack
      (test-cont (true-exp false-exp env cont)
        (find-handler val cont))
      (prim-args-cont (prim cont)
        (find-handler val cont))
      ...)))        
Find-handler searches for a handler by doing a linear search through the continuation stack. To avoid this linear search, an alternative design is to use two continuations in eval-exp -- one for "normal" values, and one for exceptions.
Last modified Apr 9, 2003 Michael Elhadad