[PLT logo] Supplement to Lecture 8, Comp 311

Understanding Control

The Structure of Environments

In Algol-like languages like Pascal and Algol W, all of the environments that exist at any point during a computation can be collectively represented using a stack. This representation for evironments is particularly advantageous because the enviroment stack can be implemented as an elaboration of the control stack embedded in the architecture of a modern computer to support procedure calls.

Programs written in "advanced" languages like Scheme, ML, Jam, and LC can be restricted to accommodate this implementation method by prohibiting program-defined functions from appearing anywhere except as the right hand side of definitions and as arguments in procedure calls. Most Scheme/ML programs make only occasional use of procedures as data (closures), so some implementations (like Chez Scheme and DrScheme) still rely on a central stack and heap allocate variables that appear free in lambda expressions.

Almost all modern computers use a stack to store the return addresses of procedure calls. In addition, other context information (such as the contents of registers that may be modified by the called the procedure) is typically saved with the address address on this "control" stack. To return, the called procedure pops the pushed information off the stack, restores the saved context information (typically the contents of registers) and jumps to the specified return address. The "popping" of the stack removes the top (most recent) "frame" from the stack, restoring the stack to the form it had before the call.

Some machines also pass argument values to procedures in the stack. The argument values are pushed on the stack along with the return address and the saved context information. Another common convention is to pass arguments (assuming the number is small) in registers. The result returned by a procedure is typically returned in a register because the stack frame associated with the call is deallocated on return.

In the absence of tail-call optimization which converts procedure calls to jumps, every procedure call allocates a new stack frame. Hence a recursive procedure may allocate a large number of stack frames. The standard definition of the factorial function, for example, allocates 1001 frames to evaluate 1000!

In the course of an computation, an exceptional condition may be encountered that requires abandoning a subcomputation. If that subcomputation has a large number of associated stack frames, the "bubbling" action require to pass a special value back up the call chain is time-consuming and awkward to program. What we want is a construct that lets us label a selected stack frame as a recovery point and return a value directly to that frame (just as if the next stack frame had returned normally). The "direct return" operation deallocates all of the stack frames from the current frame back to the recovery frame; this can be done simply by changing the contents of the register serving as the stack pointer. In addition, it places the return value in the standard place (usually a register) in determined by the procedure calling conventions.

The Scheme letcc Construct

Here are some examples of the behavior of letcc: In general, when a letcc expression is evaluated, it turns its current context (as in, ``complete textual context'') into a procedural object. This procedural object is also known as a continuation object. When a continuation object is applied, it forces the evaluator to remove the current evaluation context and to re-create the context of the original letcc expression, filled with the value of its argument. Like procedures, continuation objects are first-class values, which means they can be stored in data structures or tested by predicates.

Now we understand the semantics of letcc, but how do we use it to write programs? We need to also understand its pragmatics. For instance, letcc can be used for exception handling.

Example:

Let us write a procedure, PiHelp, that computes the product of a list of digits. The data definition looks like this: 

lod ::= null | (cons [0-9] lod)
Our procedure might look like this: 
(define PiHelp
  (lambda (l)
    (cond
      ((null? l) 1)
      (else (* (car l) (PiHelp (cdr l)))))))
However, suppose it is possible that we can get an invalid digit (in the range [a-f]); if we do, we want the result of invoking PiHelp to be false. We can add the following clause within the cond statement, 
      ((bad? (car l)) (Xit #f))
where Xit is some unused identifier.

We use the following recipe for constructing such programs:

If we pass this new procedure exceptional data, we get 

    (Pi '(1 2 b))
==> (letcc Abort (PiHelp '(1 2 b) XXX))
==> (letcc Abort (* 1 (*2 (PiHelp #f))))
==> #f
as desired.

Exercises:

Modeling Simple Control Constructs

There are numerous control constructs that we can add to LC. Some of these are:

Here is the core of an interpreter that implements # and raise. This version of # takes a body and a handler, as outlined above. The handler takes one argument, which is the value ``thrown'' by raise. 

(define MEval/ec
  (lambda (M env Exit)
    (cond
      ...
      ((raise? M)
	(Exit (MEval/ec (raise-expr M) env Exit)))
      ((#? M)
	((letcc new-Exit
	   (lambda ()
	     (MEval/ec (#-body M) env
	       (lambda (raised-value)
		 (new-Exit (lambda ()
			     (MApply/ec
			       (MEval/ec (#-handler M) env Exit)
			       raised-value Exit))))))))))))
(Note that all calls to the former MEval will now have to call MEval/ec instead, passing on the Exit handler unchanged; only # installs new handlers. MApply/ec is similarly modified.)

Summary

At this point, we will conclude our study of meta-interpreters. We have thusfar covered the following:

It would be worthwhile to note in passing some of the topics that we did not cover but which could be studied with the same methodology:

Shriram Krishnamurthi / shriram@cs.rice.edu