[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Lexical scoping in LISP

There is an interesting technical question connected with the religious
debate over Franz vs. T:  does lexical scoping force slow
interpretation?  My biggest complaint about T (and presumably Common
LISP) is that interpretation is significantly slower than it is
dynamically scoped LISPs like Franz.  The explanation for
this difference is that in a conventional shallow binding implementation
of lexical LISP, updating and restoring the shallow binding table on
a function call requires about twice the computation (on the average) as it
does in its dynamically scoped counterpart.  On an intuitive level, the
source of the extra cost is that the set of variables accessible
in the calling environment but not in the called environment
(e.g., local variables in the calling environment) must be removed
from the shallow binding table; otherwise an occurrence of a free
variable with the same name in the called function will be incorrectly

The most attractive solution to this problem that I have been able
to devise is to modify the abstract syntax of the language
(a heresy in the eyes of most LISPers) so that variables 
with same name declared at different lexical levels are represented
by distinct atoms.  Hence, the name X declared at level 1 is not EQ
to the name X declared at level 2.  The most obvious way to implement
this constraint is to concatenate the lexical level of a variable onto
its name to form the name of the atom representing the variable.
Given this modification to the abstract syntax for Lexical LISP,
the semantics of lexical and dynamic scoping are identical (assuming that
all function data objects are closures -- the appropriate convention 
in a lexically scoped language).  Hence, the same shallow binding 
implementation of function calls used in conventional LISP works 
for Lexical LISP as well.

Although modifying the abstract syntax of LISP is incompatible with the
goals of the Common LISP effort (where the proponents of lexical
scoping will presumably have to accept slow interpretation), it does not 
appear to conflict with the objectives of new (incompatible) LISP 
dialects like T.

Corky Cartwright