[Sorry for the tardy followup...]

Some time ago, felix <felix@anu.ie> wrote:
+---------------
| Which leads to another question of mine: the environment-representation-issue
| (a-lists - too slow; full display-closures - much translation-overhead for
| an interpreter; chained environment vectors - somewhere in between).
+---------------

First, you really, *REALLY* need to buy/read Queinnec's "Lisp In Small
Pieces", despite the cost. It's very well worth it for anyone seriously
into implementation. He covers all these issues in detail.

But the flippant answer is, "it depends", mainly (as you suggest) on
the ratio of closure-creation to closure-calling in the applications that
you're trying to tune the compilation process for. In my own (toy/learning)
implementation, I'm planning on trying both full closures & chained vectors,
to see which one "wins" for the applications *I'm* interested in (mainly
general text-bashing & cgi-bin scripting).

By the way, Queinnec also mentions yet another option, somewhat in between
those two. I forget what he calls it, but I think of them as "partial-" or
or "binary-search" displays. The idea is that the nominal env. structure
is linked vectors, but at every power-of-two (or some other convenient
interval, such a Fibbonacci numbers) increase in environment depth you
add a level-jumping display link. So that if a given environment is, say,
19 deep, it'd have the local lexical variables in it plus a display link
for the next level up, the 2nd level up, the 4th, the 8th, and the 16th
levels up. Thus it'd be a vector with "#lexicals"+5 elements in it. That
way, access to a given lexically-bound variable never needs to chase more
than (ceiling (log2 (- current-depth target-depth -1))) pointers per access.

[I'm not sure that closure creation is any *faster* with this scheme than
with full displays (which after all, only requires a simple block copy from
the level above), but it certainly saves space if you have a lot of deep
nesting.]


-Rob

-----
Rob Warnock, 41L-955		rpw3@sgi.com
Applied Networking		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		PP-ASEL-IA
Mountain View, CA  94043