Outline of the Specializer

A specification of the specializer for the full language treated in this paper is bound to be bulky. Therefore, we confine the specification to a simple but illustrative subset which excludes multi-argument and variadic functions. It is a continuation-based specializer [4,23] which makes the treatment of call/cc explicit.

In Fig. 14 we define the specializer that maps a two-level expression, an environment, and a specialization continuation to a specialization value. On the right side of the definition we use a call-by-value lambda with the McCarthy conditional and some other extensions. The specializer has an implicit constant argument --the current source program--that is accessed in the interpretation of procedure calls as : the body expression of procedure P. The auxiliary functions and map constants and operators to their denotations. is the built-in eval function, mk-constant maps a specialization-time constant to a run-time constant. The different mk- functions all receive Variable and Code arguments and produce Code. The exception is which builds a closure where the environment is equal to restricted to the free variables of (lambda (V) E). The use of on the right sides denotes the generation of a fresh variable.

Some further functions are involved with the memoization mechanism. First, there is a global cache which is accessed by where and is a vector of static values. It associates the pair with a procedure name which is either a fresh name--if the pair was not in the cache--or the name assigned to the pair in a previous cache lookup. The function adds a new function to the residual program, which is also kept in a global variable. The remaining functions project-static, project-dynamic, and clone-dynamic extract the static and dynamic parts from partially static specialization-time values. They are explained elsewhere [21,31]. These functions only work on abstractions represented by closures.