pcg@cs.aber.ac.uk (Piercarlo Grandi) (05/02/90)
In article <23025@uflorida.cis.ufl.EDU> smr@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: pcg%cs.aber.ac.uk@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk
bvrotney@ADS.COM (Bill Vrotney) (05/04/90)
In article <PCG.90May2124043@odin.cs.aber.ac.uk> pcg@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: pcg@cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.lang.lisp Date: 2 May 90 11:40:43 GMT References: <23025@uflorida.cis.ufl.EDU> Sender: pcg@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 21 In article <23025@uflorida.cis.ufl.EDU> smr@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
pirinen@cc.helsinki.fi (05/07/90)
In article <23025@uflorida.cis.ufl.EDU>, smr@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 pirinen@csc.fi, pirinen@finfun.bitnet Hietalahdenkatu 2 B SF-00180 HELSINKI phone: +358 0 605604 FINLAND fax: +358 0 603639 University of Helsinki pirinen@cc.helsinki.fi, pirinen@finuh.bitnet