Dead end in LISP implementation
Wolfgang von Hansen
Moin, Moin!
Though this is the first paragraph of my posting, I wrote it as the last
one. To my own surprise a simple question with a long explanation of the
situation yielded a rather longish essay. If you are in a hurry, skip down
to the last paragraph (above the footnotes! ;-) which contains a summary
and the actual cry for help. To all others: Keep an eye on your coffee
while reading -- it might be ice-cold afterwards. :-)
First an introductory part to let you understand my problem better:
Currently I implement a LISP interpreter. Its primary purpose is the joy
of programming it and using it later -- so it's going to be more a toy
interpreter than a professional heavy duty system. The primary goal of the
implementation is simplicity and elegance. I try to get away with a minimal
set of hardcoded LISP functions and define the rest in LISP itself. [1]
Modern Lisp dialects, especially Common Lisp, are rather complex systems.
Because of that I started out with a rather old definition [2] for the first
version and want to improve it later on to meet more recent demands. Keep
this in mind if my technical terms sound somewhat old-fashioned to you. :-)
Oh, one more thing: Though ancient LISP implementations almost always
featured an EVALQUOTE interpreter with an external syntax different to the
internal syntax, I try to do it with an EVAL interpreter and an interface
that conforms with modern Lisps. [3]
My problems started with the idea to do as much as possible in LISP itself.
There exist some "special forms" which have an indefinite number of
arguments. Now LISP 1.5's LAMBDA expression only allows a fixed number of
arguments in its "varlist". Because of this, one is unable to define such
special forms in LISP. To get around this dilemma, and inspired by Scheme,
I extended the LAMBDA construct to additionally accept a single identifier
instead of the varlist. All the arguments to such a function were evaluated
and put on a list which then was passed to the function. With this
definition I was able to define LIST as
(DEFINE LIST (LAMBDA L L))
Beautiful, isn't it? After the extension I defined an awful lot of functions
which were impossible before. Unfortunately I missed one thing: Special
forms not only have an indefinite number of arguments, also the way the
arguments are to be evaluated could be different to normal function calls.
Namely the predicates AND and OR evaluate their arguments from left to right
until the result, T or NIL, is determined and do _not_ evaluate the rest of
the argument list. Because of possible side effects, my implementation was
incorrect since it first evaluated all arguments and then went through the
resulting list to get the final result.
After much thinking I found a way out (but would steer deeper into the mud
at the same time). I redefined the new LAMBDA contruct; now the arguments
are no longer evaluated before they are put on the list -- or, defined in a
different way, QUOTEs were put around each argument before evaluation. (The
other LAMBDA construct with the fixed number of arguments still evaluates
the arguments during lambda conversion as usual.) Furthermore I added an
EVAL function which was now needed for explicit evaluation. After adding
calls to EVAL to all my special forms everything worked fine again and
things _really_ looked promising. Now I could even define the most basic
QUOTE in LISP terms -- it looks exactly like the definition of LIST above
and simply doesn't apply the new EVAL to its argument.
But then I suddenly discovered a major flaw in my design which even
violates the basic idea of lambda calculus: The combination of my new
LAMBDA construct with explicit calls to EVAL yielded something one might
christen "delayed evaluation". Pure LISP depends heavily on recursion,
especially mine which yet lacks the sequential PROG. As a result, the
evaluation sometimes is delayed until the program control reaches some
deeper nested functions.
Now, recursive functions are always(?) implemented by using a stack where
all the variables are put on. Variables of inner scopes hide the variables
of outer scopes (something we call local and global variables). With delayed
evaluation the problem arises when nested functions use the same variable
names. Through a function call a variable named X is put a level deeper
without evaluating it in the correct context. If the inner function tries
to evaluate that X its true contents may be hidden by another, local
variable X. Unfortunately, and this is why I said that the flaw violates the
lambda calculus, changing the name of the lambda variables shouldn't change
the return value of the function. You could simply name all the variables
in your Lisp system A; if you need a second one, it would be B and so on.
My current interpreter is very likely to choke on that. :-(
This is the point I am stuck at now. I need the extended notation for LAMBDA
to cope with functions with an indefinite number of arguments. This extended
LAMBDA must not evaluate its arguments because the special forms decide on
that themselves, using EVAL. This causes a delayed evaluation which might
confuse the interpreter when local variable names collide in nested function
calls. I am now in dire need of a good idea to get out of this dead end!
Is my general concept wrong or am I just missing some minor point?
[1] At the current stage there are 16 basic and about 60 derived
functions -- though not all of them are necessary -- including
a complete set for integer arithmetics.
[2] It's Clark Weissman's LISP 1.5 Primer, first published in 1967.
[3] Does the lot of you know the difference?
Gruß
Wolfgang
--
(_(__)_) Privat: w...@geodesy.inka.de //
~oo~ Uni: vha...@ipf.bau-verm.uni-karlsruhe.de \X/
(..)
Rob Warnock
Wolfgang von Hansen <w...@geodesy.inka.de> wrote:
+---------------
| But then I suddenly discovered a major flaw in my design...
| "delayed evaluation"... until the program control reaches some
| deeper nested functions.
|
| Now, recursive functions are always(?) implemented by using a stack where
+---------------
Without reading your essay in fine detail (sorry!), it sounds like you're
having trouble with "dynamic" versus "lexical" scope. Modern Lisps such
as Common Lisp and Scheme use lexical scoping of lambda-bound variables,
and their approach to your "delayed evaluation" problem is that lambdas
are "closed" over their environments, that is, carry around their lexical
environment with them. This is (a little) more expensive at lambda creation
time, but (usually) cheaper at function call time (besides being closer
to the lambda calculus).
I *strongly* suggest reading a book such as "Lisp in Small Pieces", by
Christian Queinnec [Cambridge University Press] (originally in French,
as "Les Languages Lisp" [InterEditions]). See:
ftp://ftp.inria.fr/INRIA/Projects/icsla/WWW/LiSP.html
This will expose you to a great variety of interpreter (and compiler)
strategies and alternatives.
Another useful book for a Lisp implementor is "Essentials of Programming
Languages" by Friedman, Wand, and Haynes.
-Rob
-----
Rob Warnock, 7L-551 rp...@sgi.com http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673 [New area code!]
2011 N. Shoreline Blvd. FAX: 650-933-4392
Mountain View, CA 94043 PP-ASEL-IA
Wolfgang von Hansen
Moin, Moin!
Rob Warnock <rp...@rigden.engr.sgi.com> schreibt über `Re: Dead end in LISP
implementation':
> Wolfgang von Hansen <w...@geodesy.inka.de> wrote:
> +---------------
> | But then I suddenly discovered a major flaw in my design...
> | "delayed evaluation"... until the program control reaches some
> | deeper nested functions.
> |
> | [...]
>
> [...] it sounds like you're
> having trouble with "dynamic" versus "lexical" scope.
Thanks for the answer! Though I'm not sure if I really unterstood "lexical
scoping", it seems to be rather difficult to implement. However, I was able
to solve the problem in a different way. After some more RTFM -- which I
actually should have done before bothering you :-( -- I found the
description of MACRO. It allows you to manipulate an expression before it is
evaluated. With that tool I am now able to transform the rebellious AND into
a sequence of CONDs which preserves the correct order of evaluation. :-)
After adding MACRO I dumped that evil EVAL. I tried to define it with other
LISP means afterwards but haven't succeeded yet. Is it possible at all to
explicitly evaluate something in LISP without EVAL or similar available?
Erik Naggum
* Wolfgang von Hansen
| After adding MACRO I dumped that evil EVAL.
I think part of your problem is considering EVAL evil. it has its uses.
| I tried to define it with other LISP means afterwards but haven't
| succeeded yet. Is it possible at all to explicitly evaluate something in
| LISP without EVAL or similar available?
one of the earlier exercises in some Lisp courses is writing a simple
EVAL that handles function calls, variable references and some special
forms. it is not particularly hard.
#:Erik
--
God grant me serenity to accept the code I cannot change,
courage to change the code I can, and wisdom to know the difference.
Joerg Hoehle
Wolfgang von Hansen (w...@geodesy.inka.de) wrote:
: Currently I implement a LISP interpreter. Its primary purpose is the joy
: of programming it and using it later -- so it's going to be more a toy
: After much thinking I found a way out (but would steer deeper into the mud
: at the same time). I redefined the new LAMBDA contruct; now the arguments
: are no longer evaluated before they are put on the list -- or, defined in a
: different way, QUOTEs were put around each argument before evaluation. (The
: other LAMBDA construct with the fixed number of arguments still evaluates
: the arguments during lambda conversion as usual.) Furthermore I added an
You shouldn't do this. You need two different constructs: one called
LAMBDA, with both fixed and Scheme like &rest arguments that are
evaluated, as you had defined previously, and another one which you
may call FLAMBDA or whatever, which does not evaluate (and probably
also not add quotes), with all arguments in a list.
A better approach to an explicit EVAL in your code is the way modern
macros work (use MLAMBDA for them): the result they produce is a Lisp
form which is then evaluated by your interpreter, you don't have to
write EVAL explicitly in your macro code. But you then still need a
few special forms such as either either COND or IF, so that all macros
can be reduced to either normal functions or COND or LAMBDA. Even LET
can be written in terms of LAMBDA.
Somebody else already answered your delayed evaluation resp. dynamic
binding problem. Dynamic binding was preferred for performance (?)
reasons in old systems, Emacs still uses this, but Common Lisp and
Scheme use lexical scope, which requires closures.
Regards,
Jo"rg Ho"hle.
Joerg....@gmd.de http://zeus.gmd.de/~hoehle/amiga-clisp.html
Donald Fisk
Wolfgang von Hansen wrote:
> Thanks for the answer! Though I'm not sure if I really unterstood "lexical
> scoping", it seems to be rather difficult to implement. However, I was able
> to solve the problem in a different way. After some more RTFM -- which I
> actually should have done before bothering you :-( -- I found the
> description of MACRO. It allows you to manipulate an expression before it is
> evaluated. With that tool I am now able to transform the rebellious AND into
> a sequence of CONDs which preserves the correct order of evaluation. :-)
>
> After adding MACRO I dumped that evil EVAL. I tried to define it with other
> LISP means afterwards but haven't succeeded yet. Is it possible at all to
> explicitly evaluate something in LISP without EVAL or similar available?
I thought the standard way of doing this is to implement both eval(expr,
env)
and apply(fun, args, env). Everything goes through eval initially.
Ordinary
functions (fixed number of args, all evaluated) are dispatched to
apply. Others,
such as COND, LIST and SETQ, are dispatched to their own evaluator
functions
(evcond, evlis and evsetq). Macros cannot be written as ordinary
lambdas, as
they most be recognized as distinct by eval, otherwise they would be
dispatched
(incorrectly) to apply. You will also need eval and apply anyway, as
these
are functions available to the user, though their semantics is slightly
different
in both cases from the internal version.
You can evaluate AND using evand, which you can implement to stop
evaluating
when it reaches its last argument or NIL. Alternatively, as you say,
you can
macroexpand it into nested CONDs. The same applies to its numeric
analogues,
e.g. +. evand, etc. is obviously more efficient, but if you want as
much as
possible implemented in Lisp you can implement it as a macro, and wait
until
you write a compiler to get efficiency.
Most of this information (except how eval handles macros) is covered in
The
Anatomy of Lisp by Allen (now out of print). My copy is falling to
pieces.
> Wolfgang
--
Le Hibou
"What the ... This is Lambic! Where's my culture of amoebic
dysentery?"
-- Gary Larson
Wolfgang von Hansen
Moin, Moin!
Joerg Hoehle <hoe...@zeus.gmd.de> schreibt über `Re: Dead end in LISP
implementation':
> Wolfgang von Hansen (w...@geodesy.inka.de) wrote:
> [...]
> : I redefined the new LAMBDA contruct; now the arguments
> : are no longer evaluated before they are put on the list -- or, defined in
> a
> : different way, QUOTEs were put around each argument before evaluation.
>
> You shouldn't do this. [...]
OK, as mentioned in another posting I have already replaced it by MACRO...
> A better approach to an explicit EVAL in your code is the way modern
> macros work (use MLAMBDA for them): the result they produce is a Lisp
> form which is then evaluated by your interpreter, you don't have to
> write EVAL explicitly in your macro code.
...which seems to be exactly the same as what you suggest here. :-)
> But you then still need a
> few special forms such as either either COND or IF, so that all macros
> can be reduced to either normal functions or COND or LAMBDA.
Yes. But first of all I try to implement derived functions with LAMBDA
whenever possible because they're evaluated faster and are easier to write
as my MACROs rearrange their argument with CONS, CAR and CDR which really
is a pain. And secondly there needs to be an interface to the internals
of the computer which requires a few built-in functions (in my system
currently ten without the support for arithmetics and 14 with it).
> Dynamic binding was preferred for performance (?)
> reasons in old systems
Oh well, _you_ call it dynamic binding. To me it is simply preserving
variables during recursion by putting them on a stack. :-) The idea of LISP
was an A-list where the elements were inserted and removed at the beginning
and bindings were retrieved by ASSOC. Of course performance may be a reason
for dynamic binding, but it also is a simple approach to solve the problem.
Wolfgang von Hansen
Moin, Moin!
Erik Naggum <cle...@naggum.no> schreibt über `Re: Problem solved (was: Dead end
in LISP implementation)':
> * Wolfgang von Hansen
> | After adding MACRO I dumped that evil EVAL.
>
> I think part of your problem is considering EVAL evil. it has its uses.
I had my problems with it (have a look at my original posting). But it does
not mean there's no EVAL on my system. It simply is invisible to the user.
> | I tried to define it with other LISP means afterwards but haven't
> | succeeded yet. Is it possible at all to explicitly evaluate something in
> | LISP without EVAL or similar available?
>
> one of the earlier exercises in some Lisp courses is writing a simple
> EVAL that handles function calls, variable references and some special
> forms. it is not particularly hard.
I agree, but that's not what I actally meant. You can define LISP in terms
of LISP itself, but that requires a working implementation and with that
at hand you don't need that extra level of abstraction. What seek is a
definition of EVAL that behaves as if it were an internal function. Here's
an example:
> (DEFINE A (QUOTE (PLUS 2 3)))
A
> A
(PLUS 2 3)
> (EVAL A)
5
See what I mean? EVAL triggers one more level of evaluation. Or put in a
different way: QUOTE is used to protect its argument from evaluation and
EVAL reverses this effect.
Currently it seems impossible to me to write that function in LISP. All my
attempts resulted in an identity function.
Rob Warnock
|
| scoping", it seems to be rather difficult to implement.
Lexical scoping per se is actually easy, it what most of the non-Lispy
languages do, too (e.g., Pascal, and in the degenerate case, C & C++).
Allowing procedure definitions inside procedures (which C *doesn't*)
is a bit harder; you need what Pascal calls a "display". And then providing
"lexical closures with dynamic extent" (Scheme or Common Lisp lambdas)
is harder still.
You're really going to need to read up at least a little bit on lexically-
scoped Lisps (e.g., Common Lisp or Scheme). Again I would suggest perhaps
Rob Warnock
| > reasons in old systems
|
| Oh well, _you_ call it dynamic binding. To me it is simply preserving
| variables during recursion by putting them on a stack. :-) The idea of LISP
| was an A-list where the elements were inserted and removed at the beginning
| and bindings were retrieved by ASSOC. Of course performance may be a reason
| for dynamic binding, but it also is a simple approach to solve the problem.
Actually, lexical scope gives *better* performance for access to variables,
since you can [if you do things right] compute the offsets back into the
environments at *compile* time -- you never need to search an A-list to
find the value of a variable. (An implementation may *choose* to search
the environment, but by using a little extra storage at closure-creation
time for a "display", it need not. A double index can be made to suffice.)
A dynamic A-list is ndeed simple to implement, but *understanding* programs
written with dynamic scope can be horribly complex! On the other hand, with
lexical scope, you can look at the static printed source text of a program
and *know* which binding is associated with each variable reference.