Constant time interpretation for shallow-bound variables in the presence of mixed special/local declarations

摘要

The semantics of variables in LISP are usually centered around the compiled-code environment; in many shallow-bound systems, local variables are implemented as stack-slots in the compiled environment, but are merely converted to special (or "fluid") variables by the interpreter. This paper shows a method for separating local from special bindings when interpreting, such that the time to evaluate a reference to a variable is bounded by a modestly small constant; comparison is made to methods which require a time proportional to the number of variables present in the function being interpreted. Notations: A MacLISP style is used for program examples; thus DEFUN rather than DEFINE, LET often in preference to LAMBDA, and semi-colon for noting commentary. Without loss of generality, we refer to all variable binding, whether from LET, LAMBDA, PROG, or whatever, as "lambda binding".