I am writing a Lisp interpreter and it has now become reasonably mature (191
functions, many overloaded). It is a Lisp1 and I have no real desire to
change this but I would like to implement function quoting. Is there any
straightforward way to do this? I have searched the web for "The funarg
device" but I can find only references.
I presently store the "environment" in the cells in the heap. Saved
environment is stored in stack frames as (cell, old value) pairs. The only
way that I can see to implement function quoting is to create a "closure" of
sorts which contains the function pointer and a stack marker. All calls to
such closures must take every symbol reference and scan the stack from the
marker forward looking for the oldest saved value of that variable. Most
scans will presumably fail to find a change of binding and scan right up to
the top. I can't help thinking that this will turn a fast interpreter into
a real slug.
So, is there a clever algorithm that avoids all of this or am I just being
pessimistic about the performance hit. The interpreter is currently running
a reasonably substantial test program which includes an algebraic
parser/deparser at around 3.5uS per eval including GC time on a PIII733.
Although speed is not the only consideration I would like to keep it as fast
as reasonably possible.
TIA
Andy
As an aside the interpreter, AJBLisp, is soon to be released as freely
distributable binary and source for Windows (an older Linux version also
exists.) I have released earlier versions but they were rather beta. It is
written in C++ and it is genuinely useful (I use it!) It handles 32-bit
integers, double precision floats, strings, characters, dates/times, vectors
and lists(!). The code is well commented and it might make a useful
educational tool. If you are interested, decode the following AJBLisp
encoded address and ask for a copy.
(printc "ajblisp" ··@ "abisson" (char 46) "co" (char 46) "uk")
"A J Le Couteur Bisson" <·······@thanks> wrote in message news:<···················@newsfep1-win.server.ntli.net>...
> I am writing a Lisp interpreter and it has now become reasonably mature (191
> functions, many overloaded). It is a Lisp1 and I have no real desire to
> change this but I would like to implement function quoting. Is there any
> straightforward way to do this? I have searched the web for "The funarg
> device" but I can find only references.
By function quoting you mean #'function, right? In Lisp, this means
accessing the function binding of the given symbol.
> I presently store the "environment" in the cells in the heap. Saved
> environment is stored in stack frames as (cell, old value) pairs.
Saving and restoring old values is the means to dynamic scoping. To
implement modern Lisp properly, you must also provide lexical scoping,
and closures.
The only
> way that I can see to implement function quoting is to create a "closure" of
> sorts which contains the function pointer and a stack marker.
Anything that refers to stack storage which will disappear is not a
true, first-class lexical closure.
> All calls to
> such closures must take every symbol reference and scan the stack from the
> marker forward looking for the oldest saved value of that variable.
That indicates that lexical scoping is being emulated over top of
dynamic scoping, which smells like a bad design mistake. If I
understand it right, you have a stack full of saved dynamic values,
and want to access something other than the latest one in an old stack
frame.
Real lexical closures don't have to do this kind of search, because
they are containers which encapsulate the captured bindings.
A closure's references to its captured lexical variables can be
compiled into efficient accesses. In fact lexical variables can be
subject to those same kinds of optimizations as local variables in
C-like languages. In the guts of a compiled closure, you might not
find any symbolic references at all, just machine instructions that
directly address what they want. No scanning of any kind is needed.
All functions in Lisp are really function objects. When you write
#'format, you are asking to retrieve the function object that
implements the format function. When you use DEFUN to write a
function, it captures the lexical
environment:
(let ((x 42))
(defun foo () ...))
The expression #'FOO must return the lexical closure which has
captured the variable X when the DEFUN was evaluated.
Don't worry about trying to capture dynamic bindings; this is simply
not a feature of Lisp. An exepression naming a special variable always
refers to its currently established dynamic binding.
"A J Le Couteur Bisson" <·······@thanks> writes:
> I have searched the web for "The funarg device" but I can find only
> references.
"Closure" and "upward closure" might be more rewarding.
> I presently store the "environment" in the cells in the heap. Saved
> environment is stored in stack frames as (cell, old value) pairs.
> The only way that I can see to implement function quoting is to
> create a "closure" of sorts which contains the function pointer and
> a stack marker. All calls to such closures must take every symbol
> reference and scan the stack from the marker forward looking for the
> oldest saved value of that variable.
That sounds like dynamic closures. Those are not as useful as lexical
closures, such as in Common Lisp. Nevertheless, much of what I'm
writing will apply to dynamic closures as well - I've just never
implemented such a beast.
A lexical closure only closes over the variables in the current
lexical scope. There are fewer of those, and you only need to scan
the frame that the marker points to. However, if that was another
closure frame then you have to recursively take its stack marker and
scan that frame. E.g.,
(defun addmul (a k)
#'(lambda (list)
(mapcar #'(lambda (elem) (+ (* k elem) a)) list)))
Note that the first lambda is a closure merely because it has a
closure inside it.
To make this kind of thing efficient, you'd really want to preprocess
the code.
> Most scans will presumably fail to find a change of binding and scan
> right up to the top. I can't help thinking that this will turn a
> fast interpreter into a real slug.
The thing to do is not to scan; store what the scan would compute, a
pointer into the value cell, in the closure when it is created, and
transfer it to the symbol when the closure is called. Again, this
requires examining the code when the closure is created (or in an
earlier preprocessing pass); doing it on the fly as the variable is
accessed is going to be really slow (although you can still cache the
lookups).
On the matter of upward closures and heap-allocating the value cells,
I refer you to of my earlier note about this
<http://groups.google.com/groups?ie=UTF-8&selm=ulmkru50w.fsf%40globalgraphics.com>.
If you really want to get your lexical scoping right, you'll find you
want to rename your variables &c. I'm afraid the gap between a
working Lisp interpreter and one with a correct implementation of
lexical scoping is much larger than you'd think.
--
Pekka P. Pirinen
"If you don't look after knowledge, it goes away."
- Terry Pratchett, The Carpet People
"Pekka P. Pirinen" <···············@globalgraphics.com> wrote in message
··················@globalgraphics.com...
> That sounds like dynamic closures. Those are not as useful as lexical
> closures, such as in Common Lisp. Nevertheless, much of what I'm
> writing will apply to dynamic closures as well - I've just never
> implemented such a beast.
>
Hmm. The term dynamic closures sounds appropriate but information is so
hard to
come by.
Another example where scope is problematic is in the session
below. NB. macros are just functions that don't evaluate their
arguments in my Lisp.
> (defmacro xinc (x) (set x (+ (eval x) 1)))
= xinc
> (setq a 4)
= 4
> (xinc a)
= 5
> a
= 5
> (setq x 5)
= 5
> (xinc x)
Error [5] : Numeric argument expected
Error object: x
Failed in: (+ (eval x) 1)
Backtrace
Eval : (+ (eval x) 1)
Arg1 = (x 1) ; Oops! Not that x, I meant the x bound
to 5...
Eval : (set x (+ (eval x) 1))
Arg1 = x
Eval : (xinc x)
Arg1 : x = x
Clearly I need the eval to use the scope outside of the macro. I avoid this
by by using odd symbol names for formals where it matters, like inc~x.
Thanks for the comments. I need to think about this a bit more. It may be
that a partial implementation of lexical scoping is not possible or perhaps
not in itself useful. Anyway this is all very instructive and its a useful
way
to spend my time "in between jobs" as a software engineer.
Andy.
"A J Le Couteur Bisson" <·······@thanks.com> writes:
> Hmm. The term dynamic closures sounds appropriate but information
> is so
> hard to
> come by.
In the vocabulary of Lisp, a dynamic closure is a type of closure that
will close over variables declared special. The only system I have
used that offers dynamic closures is the Lisp Machine which also has
quite a nifty set of interface to manipulate dynamic closures. Among
other things, you are empowered to externally query and mutate the
bindings it captures as well as copy the closure object wholesale (in
some rather creative ways).
Now a days, there is little a dynamic closure can offer you that would
not be cleanly and portably implementable using a lexical closure,
CLOS, or CLOS plus the FUNCALLABLE-STANDARD-CLASS metaclass as found
in the AMOP book. If you just want a copy of the dynamic environment
which you can pass around as an object, creating a new thread in a
multi-processing Lisp will get you at least that far (although a
runnable process is quite heavyweight in comparison to a closure).
Thanks for your comments. I think Kaz missed my point a little, I am not
trying to emulate CL and I am quite happy with a Lisp1. I just knew that
this elusive "funarg device" had been implemented on other Lisp1s and I
wondered how they did it. I actually like dynamic scope, or rather I ensure
that all variables used are local, formal arguments or global. I think that
this approach leads to clearer code in any language. The only place where
it is a pain is for functional arguments and if there is a simple, efficient
fix for this then I'd like to know what it is.
I haven't had time to digest Pekka's post yet but it looks very interesting
and relevant. I'll check it out later.
Got to party now...
Andy
Have a look at:
http://www.cs.utexas.edu/users/wilson/schintro/schintro_121.html
It's for scheme, but it does a pretty good job of explaining implementation
of lexical scoping.
--
Justin Johnson
"A J Le Couteur Bisson" <·····@here.com> wrote in message
·················@paris.btinternet.com...
>
> Thanks for your comments. I think Kaz missed my point a little, I am not
> trying to emulate CL and I am quite happy with a Lisp1. I just knew that
> this elusive "funarg device" had been implemented on other Lisp1s and I
> wondered how they did it. I actually like dynamic scope, or rather I
ensure
> that all variables used are local, formal arguments or global. I think
that
> this approach leads to clearer code in any language. The only place
where
> it is a pain is for functional arguments and if there is a simple,
efficient
> fix for this then I'd like to know what it is.
> I haven't had time to digest Pekka's post yet but it looks very
interesting
> and relevant. I'll check it out later.
>
> Got to party now...
> Andy
>
>