I'm working on a (small, now) Lisp interpreter for the MC68000
series, and I've got a few questions (help!):
I'm using these as references: CLtL, Winston & Horn's "Lisp" (two
latest editions), Abelson & Sussmans' "Structure and Interpretation of
Computer Programs", Gabriel's "Performance and Evaluation of Lisp
Systems", AAAI87 Tutorial "Advanced Common Lisp", and (sheepishly)
SYS:SYS;EVAL.LISP on my favorite Symbolics.
There are a lot of examples of interpreters, and they all
point out the differences between dynamic and lexical scoping, and
show how to implement each. However, they all represent environments
as lists, which I can't see as being feasible (efficient) for anything
but a lisp machine (because of all that consing), so I've been trying
to come up with some scheme (oops) for representing closures on the
stack. I drown myself in hairy ideas. The best so far is modeled
after what I've gleaned from the LispM code, that of "stack" lexical
closures and "general" lexical closures, and evacuating things off the
stack when necessary...
I suppose one possibility would be consing env-lists on the
stack...
- and what are rib-lists? (mentioned in the Adv. CL tutorial briefly)
Can someone point me towards help on this? Source code, books,
papers, people to pester, whatever...
Many thanks,
Sam Rushing
p.s.: If it's any good, it'll be FREE.
--
(not (not (not (not (not ... )))))
-------------------------------------------------------------------------------
···@beach.cis.ufl.edu ·······@titan.ksc.nasa.gov
From: Jim O'Dell
Subject: Re: Efficient Implementation of Lexical Scoping
Date:
Message-ID: <56461@bu.edu.bu.edu>
Well, I don't know about ultimate efficiency, but I have produced
a version of Franz Lisp for the Macintosh. It is a very faithful implementation
of the Unix version and runs quite speedily.
The unique things about this implementation, versus other Lisp
implementations are:
1) Complete source code availability.
For the about the price of other Lisps you can have complete source
code for the impterpreter, compiler and libraries.
Franz doesn't have full lixical binding, but there is an implementation
closures that is supported both by the interpreter and the compiler.
The libraries include an implemtation of flavors, format and loop.
2) An extremely small initial image.
The rawlisp image on the Mac is aboput 200K.
3) Because you own the source code you can customize to your hearts
desire. You can also study a complete lisp implementation to see
exactly how lisp works.
4) This implementation of Franz runs DOE-MACSYMA in 4 MB on a Mac.
Further inquiries to ···@fpr.com
In article <·····@uflorida.cis.ufl.EDU> ···@beach.cis.ufl.edu (Samual
Rushing) writes:
I'm working on a (small, now) Lisp interpreter for the MC68000
series, and I've got a few questions (help!):
I'm using these as references: CLtL, Winston & Horn's "Lisp" (two
latest editions), Abelson & Sussmans' "Structure and Interpretation of
Computer Programs", Gabriel's "Performance and Evaluation of Lisp
Systems", AAAI87 Tutorial "Advanced Common Lisp", and (sheepishly)
SYS:SYS;EVAL.LISP on my favorite Symbolics.
You miss out the best one: Allen's "Anatomy of Lisp".
As to implementatations of scoping, the one vital reference is the CACM
article (around 1975) by Baker on rerooting.
--
Piercarlo "Peter" Grandi | ARPA: ·················@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: ···@cs.aber.ac.uk
From: Bill Vrotney
Subject: Re: Efficient Implementation of Lexical Scoping
Date:
Message-ID: <=*5#JH$@ads.com>
In article <················@odin.cs.aber.ac.uk> ···@cs.aber.ac.uk (Piercarlo Grandi) writes:
Path: ads.com!apple!usc!cs.utexas.edu!uunet!mcsun!ukc!dcl-cs!aber-cs!odin!pcg
From: ···@cs.aber.ac.uk (Piercarlo Grandi)
Newsgroups: comp.lang.lisp
Date: 2 May 90 11:40:43 GMT
References: <·····@uflorida.cis.ufl.EDU>
Sender: ···@aber-cs.UUCP
Organization: Coleg Prifysgol Cymru
Lines: 21
In article <·····@uflorida.cis.ufl.EDU> ···@beach.cis.ufl.edu (Samual
Rushing) writes:
I'm working on a (small, now) Lisp interpreter for the MC68000
series, and I've got a few questions (help!):
I'm using these as references: CLtL, Winston & Horn's "Lisp" (two
latest editions), Abelson & Sussmans' "Structure and Interpretation of
Computer Programs", Gabriel's "Performance and Evaluation of Lisp
Systems", AAAI87 Tutorial "Advanced Common Lisp", and (sheepishly)
SYS:SYS;EVAL.LISP on my favorite Symbolics.
You miss out the best one: Allen's "Anatomy of Lisp".
As to implementatations of scoping, the one vital reference is the CACM
article (around 1975) by Baker on rerooting.
I believe he is referring to an article called "Shallow Binding in
Lisp 1.5" CACM Jul-1978 p565 which talks about rerooting.
--
Bill Vrotney
In article <·····@uflorida.cis.ufl.EDU>, ···@beach.cis.ufl.edu (Samual Rushing) writes:
> series, and I've got a few questions (help!):
> ...
> There are a lot of examples of interpreters, and they all
> point out the differences between dynamic and lexical scoping, and
> show how to implement each. However, they all represent environments
> as lists, which I can't see as being feasible (efficient) for anything
> but a lisp machine (because of all that consing), so I've been trying
> to come up with some scheme (oops) for representing closures on the
> stack. I drown myself in hairy ideas. The best so far is modeled
> after what I've gleaned from the LispM code, that of "stack" lexical
> closures and "general" lexical closures, and evacuating things off the
> stack when necessary...
I'll describe a nice, efficient way of doing lexical scoping. This is
what we at Intellitech are actually using in our Entity Common Lisp
product. I'm afraid company policy prevents me from giving you the code
itself. >-|
The scoping rules are enforced by preprocessing the code before
evaluation, renaming all lexical entities to names that are unique to the
scope. The preprocessing is done whenever the evaluator is called by user
code. For example,
#'(lambda (x)
(block square (return-from square (* x x))))
would become
#'(processed-lambda (#1=#:x)
(block #2=#:square (return-from #2# (* #1# #1#))))
Here the new name is the result of (make-symbol (string <old name>)),
which is nice for debugging. You could have special kinds of data objects
for lexical variables, blocks, etc., but this buys a small saving of space
at the expense of a more complicated interpreter -- not worth it IMO.
Lexical variables are then handled like special variables, i.e. shallow-
binding the value cell.
Closed-over lexical entities are bound to the right value by the closure
calling mechanism. Variables that are modified need an additional
complication: the value cell points to an external value cell (EVC) that
holds the actual value, the EVCs are stored in the closures, and the
calling mechanism binds the variable symbols to the EVCs. (Zetalisp used
this for its dynamic closures, so you might have some relevant code on
your Symbolics.)
The external value cell mechanism requires a modification to the variable
value fetch and set routines (Symbolics did it in hardware...), but it's
worth it, since variable accesses now only require one or two pointer
dereferences plus the test for the presence of an EVC.
There is no heap allocation except when creating closures, and that
doesn't have to be done often, since with renaming, lexical entities only
have to be closed over when referenced in a manner that that cannot be
guaranteed to be in the dynamic scope of the correct binding.
Pekka P. Pirinen
Director, R&D
IntelliTech oy ·······@csc.fi, ·······@finfun.bitnet
Hietalahdenkatu 2 B
SF-00180 HELSINKI phone: +358 0 605604
FINLAND fax: +358 0 603639
University of Helsinki ·······@cc.helsinki.fi, ·······@finuh.bitnet