I'm trying to make a LISP interpreter in Delphi and I have some questions
about how lisp handles variables' scopes and when to bind which to what
within functions...
For example
(defun foo (x) (eval x))
(setq x 3)
(foo '(+ x 2))
returns various results in different implementations I've found; it
generates a stack-overflow error in some (by repeatedly evaluating x to
(eval x)) but evaluates (correctly, I hope) to (5 (+ X 2)) in others. Can
someone explain how the variable binding can be implemented?
"Tyler Durden" <·········@hotmail.com> writes:
> (defun foo (x) (eval x))
> (setq x 3)
> (foo '(+ x 2))
>
> returns various results in different implementations I've found; it
> generates a stack-overflow error in some (by repeatedly evaluating x to
> (eval x)) but evaluates (correctly, I hope) to (5 (+ X 2)) in
> others.
Yes, 5 is correct in Common Lisp. The Xs in FOO are local to FOO
("lexical"), and the other two default to the global binding
("special"). See Lamkins' _Succesful Lisp_, chapter 8,
<URL:http://psg.com/~dlamkins/left/sl/html/chapter08.html> for an
introduction, and the HyperSpec, chapter 3, for the full details
(particularly 3.1.4). A lot of the older Lisps (like elisp) don't
have lexical variables, just dynamic (what CL calls "special"), so the
other behaviour is quite respectable as well.
> Can someone explain how the variable binding can be implemented?
The easiest way is using environment objects: variable access does a
lookup in an association list of names and values. LETs (and LAMBDAs)
just push new pairs on the list. This is called "deep binding" in
Lisp lore. To implement lexical bindings, you need two environments:
one for the lexicals and one for the specials. Capture the lexical
env when a function object is created, #'(LAMBDA ...), and restore it
when the resulting function is called. LETs with SPECIAL declarations
complicate things a bit, if you implement them.
The other popular way is "shallow binding": the value is stored in a
slot ("the value cell") of the symbol that is the name. LETs replace
the value and store the old value on a stack, so that it can be
restored at exit (this can be fiddly with non-local exits like THROW).
To implement lexical bindings, you preprocess the code to rename the
lexical variables (uninterned symbols of the same name are a good
bet). This is faster, but harder to implement. Furthermore, to
implement closures, you have to add more cleverness to save and
restore the closed-over variables -- I'll spare you the details,
because you don't want to go there, unless you're really serious about
a fast interpreter (in the LWW interpreter, there's about 1000 lines
of preprocessing code).
Hybrid solutions and various optimizations are possible, but it's easy
to get this wrong -- be careful. Multithreading and compilation make
things more complicated. You can find more info about those by
searching this newsgroup on Deja.
--
Pekka P. Pirinen
Adaptive Memory Management Group, Harlequin Limited/Xanalys Inc.
"If you don't look after knowledge, it goes away."
- Terry Pratchett, The Carpet People