There are two common structures for associative maps in Lisp, A-Lists 
and P-Lists.  A-Lists are structured like so:

((key . value) (key . value) ...)

while P-Lists are structured like so:

(key value key value ...)

Both are equally efficient in terms of storage and search times.  ALists 
have a slight advantage over PLists when used as models of lambda 
bindings because popping a binding requires only one CDR operations 
whereas a PList requires two.  (Note that I am talking about PLists in 
the abstract here, without the additional constraints imposed on them by 
e.g. Common Lisp, which requires a P-List to have unique keys.)

There is a third representation of an abstract associative map, which 
I've never seen mentioned before.  But it is so obvious I can't believe 
that the idea is original with me.  For the moment I've dubbed them 
DLists.  They look like this:

((key1 key2 ... keyN) value1 value2 ... valueN)

DLists are just as efficient as ALists and PLists for all common 
operations, but they have several advantages over either ALists or 
PLists:

1.  The empty DList is not (), it's (()).  This means that you can push 
new bindings onto a DList without having to special-case NIL like you do 
with ALists or Plists.

2.  When using a DList as a model of a lexical environment, the keys and 
values are cleanly separated, so you can compile a lexical access simply 
by looking up the position of the key in the CAR of the DList, after 
which you can discard the CAR of the DList with no loss of 
functionality.  In other words, (deref dlist key) is equivalent to (nth 
(position key (car dlist)) (cdr dlist)), and (position key (car dlist)) 
is a compile-time constant.

3.  It is trivial to replace the CAR and the CDR of a DList with vectors 
(optionally adjustable vectors with fill pointers, though for the common 
use case of modeling lambda bindings this would not be necessary), in 
which case dereferencing constant keys can be done in amortized O(1) 
time.  This transformation is not possible with ALists or PLists.  Of 
course, it is possible to dereference constant keys for ALists and 
PLists in amortized O(1) time by keeping a reference to the value cell 
itself, but separating the steps so that there is a tangible 
intermediate result that is an integer offset into a value vector I 
believe has pedagogical value when teaching students how closures are 
compiled.

4.  Multiple D-Lists can share the same key list, making D-Lists more 
space efficient (by a factor asymptotically approaching 2) for the 
common use case of modeling lexical environments that get instantiated 
multiple times.

But all that is neither here nor there, because my actual question is: 
has all this been thought of before?  I can't imagine that it hasn't 
been, but I've never seen it in any Lisp text.  If there's literature on 
this, can someone point me to a reference?  Do these structures have an 
actual name?

Thanks,
rg

Ron Garret <rNOSPAMon@flownet.com> writes:

> Common Lisp [...] requires a P-List to have unique keys.

In the CL standard, the glossary entry for "property list", the
specification of GET, and the specification of GETF contradict this
notion. Is there a passage that supports it?

Zach

In article <m3ws5vb9ru.fsf@unnamed.xach.com>,
 Zach Beane <xach@xach.com> wrote:

> Ron Garret <rNOSPAMon@flownet.com> writes:
> 
> > Common Lisp [...] requires a P-List to have unique keys.
> 
> In the CL standard, the glossary entry for "property list", the
> specification of GET, and the specification of GETF contradict this
> notion. Is there a passage that supports it?
> 
> Zach

My mistake.  It's emacs lisp that has this requirement, not CL.  
(Reference: http://www.emacswiki.org/emacs/AlistVsPlist :
"In a plist, each key must be distinct.")

rg

On Jul 26, 10:39=A0am, Ron Garret <rNOSPA...@flownet.com> wrote:
>
> 4. =A0Multiple D-Lists can share the same key list

For an extreme example of where this can be taken, check out my
"dynamic tuples":

http://common-lisp.net/project/fset/

Look in file `Code/tuples.lisp'.

Not only do multiple tuples share a single key vector, there's a cute
key-reordering feature that pulls commonly-accessed keys toward the
beginning of the vector.  (The key vector and value vector are thus
not in the same order, but the key vector has indices into the value
vector.)

-- Scott

Ron Garret <rNOSPAMon@flownet.com> writes:

> 1.  The empty DList is not (), it's (()).  This means that you can push 
> new bindings onto a DList without having to special-case NIL like you do 
> with ALists or Plists.

What special case did you have in mind?

Zach

In article <m3skgjb4kg.fsf@unnamed.xach.com>,
 Zach Beane <xach@xach.com> wrote:

> Ron Garret <rNOSPAMon@flownet.com> writes:
> 
> > 1.  The empty DList is not (), it's (()).  This means that you can push 
> > new bindings onto a DList without having to special-case NIL like you do 
> > with ALists or Plists.
> 
> What special case did you have in mind?
> 
> Zach

If we want to treat associative maps as objects with state independent 
of the places where they are stored, we can do e.g. this with DLists:

(defun add-binding-to-dlist (key value dlist)
  (push key (car dlist))
  (push value (cdr dlist))
  dlist)

which works thusly:

? (setf dlist (list nil))  ; Empty DList
(NIL)
? (add-binding-to-dlist 'k1 'v1 dlist)
((K1) V1)
? dlist
((K1) V1)
? 

If we try to do the analogous thing with ALists or PLists it's not quite 
possible.  We can do e.g. this:

(defun add-binding-to-alist (key value alist)
  (let ((temp (car alist)))
    (rplaca alist (cons key value))
    (rplacd alist (cons temp (cdr alist)))
    alist))

which works as long as the list isn't empty:

? (setf alist (list '(k1 . v1)))
((K1 . V1))
? (add-binding-to-alist 'k2 'v2 alist)
((K2 . V2) (K1 . V1))
? alist
((K2 . V2) (K1 . V1))

but fails if there are no bindings:

? (setf alist nil)
NIL
? (add-binding-to-alist 'k2 'v2 alist)
> Error: value NIL is not of the expected type CONS.

In other words, all DLists are of type PAIR, even the empty DList.  All 
ALists and PLists are of type PAIR *except* the empty AList/PList, which 
is of type NULL.

rg

In article 
<19e3dc45-037b-4f25-aed6-89f09ddbcba6@d4g2000prc.googlegroups.com>,
 Scott Burson <FSet.SLB@gmail.com> wrote:

> On Jul 26, 10:39�am, Ron Garret <rNOSPA...@flownet.com> wrote:
> >
> > 4. �Multiple D-Lists can share the same key list
> 
> For an extreme example of where this can be taken, check out my
> "dynamic tuples":
> 
> http://common-lisp.net/project/fset/
> 
> Look in file `Code/tuples.lisp'.
> 
> Not only do multiple tuples share a single key vector, there's a cute
> key-reordering feature that pulls commonly-accessed keys toward the
> beginning of the vector.  (The key vector and value vector are thus
> not in the same order, but the key vector has indices into the value
> vector.)
> 
> -- Scott

Spiffy!  Thanks for the pointer.

rg

Ron Garret <rNOSPAMon@flownet.com> writes:

> In article <m3skgjb4kg.fsf@unnamed.xach.com>,
>  Zach Beane <xach@xach.com> wrote:
>
>> Ron Garret <rNOSPAMon@flownet.com> writes:
>> 
>> > 1.  The empty DList is not (), it's (()).  This means that you can push 
>> > new bindings onto a DList without having to special-case NIL like you do 
>> > with ALists or Plists.
>> 
>> What special case did you have in mind?
>> 
>> Zach
>
> If we want to treat associative maps as objects with state independent 
> of the places where they are stored, we can do e.g. this with DLists:

I suppose this "problem" of NIL makes people not use alists/plists like
that, instead non-destructively extending them with ACONS or LIST*.

Zach

On Jul 26, 7:39=A0pm, Ron Garret <rNOSPA...@flownet.com> wrote:
> [...]
> There is a third representation of an abstract associative map, which
> I've never seen mentioned before. =A0But it is so obvious I can't believe
> that the idea is original with me. =A0For the moment I've dubbed them
> DLists. =A0They look like this:
>
> ((key1 key2 ... keyN) value1 value2 ... valueN)
> [...]
> But all that is neither here nor there, because my actual question is:
> has all this been thought of before? =A0I can't imagine that it hasn't
> been, but I've never seen it in any Lisp text. =A0If there's literature o=
n
> this, can someone point me to a reference? =A0Do these structures have an
> actual name?

"Not A-lists"? See note {This ain't A-lists} in
"The Art of the Interpreter of, the Modularity Complex (Parts Zero,
One, and Two)"
( http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-453.pdf
).


Mattias

In article <m3iqhfb20d.fsf@unnamed.xach.com>,
 Zach Beane <xach@xach.com> wrote:

> Ron Garret <rNOSPAMon@flownet.com> writes:
> 
> > In article <m3skgjb4kg.fsf@unnamed.xach.com>,
> >  Zach Beane <xach@xach.com> wrote:
> >
> >> Ron Garret <rNOSPAMon@flownet.com> writes:
> >> 
> >> > 1.  The empty DList is not (), it's (()).  This means that you can push 
> >> > new bindings onto a DList without having to special-case NIL like you do 
> >> > with ALists or Plists.
> >> 
> >> What special case did you have in mind?
> >> 
> >> Zach
> >
> > If we want to treat associative maps as objects with state independent 
> > of the places where they are stored, we can do e.g. this with DLists:
> 
> I suppose this "problem"

I didn't say it was a "problem."  Please don't introduce conflict where 
none exists.

> of NIL makes people not use alists/plists like
> that, instead non-destructively extending them with ACONS or LIST*.

Sometimes, and sometimes it makes them use setf macros to effect 
mutation, which forces them to bind the objects to particular places, 
most notably (but not exclusively) in symbol-plists.  But *if* someone 
wants an associative map that they can treat as a simple mutable object 
they can't use a PList nor an AList.  But they can use a DList.  Note 
that DLists can also be extended functionally as well:

(defun dcons (key value dlist)
  (cons (cons key (car dlist)) (cons value (cdr dlist))))

? (dcons 'k1 'v1 (extend-dlist 'k2 'v2 '(())))
((K1 K2) V1 V2)

rg

Ron Garret <rNOSPAMon@flownet.com> writes:

>> > If we want to treat associative maps as objects with state independent 
>> > of the places where they are stored, we can do e.g. this with DLists:
>> 
>> I suppose this "problem"
>
> I didn't say it was a "problem."  Please don't introduce conflict where 
> none exists.

If you don't find the special casing of NIL a problem with alists and
plists compared to dlists, it's a little silly to list the absence of a
special case as an advantage of dlists.

Zach

In article <m38wibaz4a.fsf@unnamed.xach.com>,
 Zach Beane <xach@xach.com> wrote:

> Ron Garret <rNOSPAMon@flownet.com> writes:
> 
> >> > If we want to treat associative maps as objects with state independent 
> >> > of the places where they are stored, we can do e.g. this with DLists:
> >> 
> >> I suppose this "problem"
> >
> > I didn't say it was a "problem."  Please don't introduce conflict where 
> > none exists.
> 
> If you don't find the special casing of NIL a problem with alists and
> plists compared to dlists, it's a little silly to list the absence of a
> special case as an advantage of dlists.

I like blue cars.  So if I were to go shopping for a car, a blue car 
would have an advantage over a red one.  I would not say, however, that 
there is therefore a "problem" with red cars.

Analogously, some people like an object-oriented programming style.  For 
such people, DLists offer an advantage over PLists or ALists.  It does 
not follow that PLists and ALists have a "problem."

rg

Ron Garret wrote:
> For the moment I've dubbed them DLists.  They look like this:
> 
> ((key1 key2 ... keyN) value1 value2 ... valueN)

FWIW, this is similar to the parameter list to PROGV.

- Daniel

Mattias Nilsson  <mattiasn@bredband.net> wrote:
+---------------
| Garret <rNOSPA...@flownet.com> wrote:
| > There is a third representation of an abstract associative map, which
| > I've never seen mentioned before. But it is so obvious I can't believe
| > that the idea is original with me. For the moment I've dubbed them
| > DLists. They look like this:
| >
| > ((key1 key2 ... keyN) value1 value2 ... valueN)
| > [...]
| > But all that is neither here nor there, because my actual question is:
| > has all this been thought of before? I can't imagine that it hasn't
| > been, but I've never seen it in any Lisp text. If there's literature on
| > this, can someone point me to a reference? Do these structures have an
| > actual name?
| 
| "Not A-lists"? See note {This ain't A-lists} in
| "The Art of the Interpreter of, the Modularity Complex (Parts Zero,
| One, and Two)"
| ( http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-453.pdf ).
+---------------

In addition to that, SICP2 also discusses this version [not at all
surprising, given the 2nd author of AIM-453] for lexical environments
which are a list of "frames", each of which is a cons of a list of
variables and a list of values. See the functions MAKE-FRAME and
EXTEND-ENVIRONMENT in the source file "ch4-mceval.scm" from SICP2.
[Note: SICP1 didn't seem to use this method; compare with "chapter4.code".]

Queinnec also discusses this variation in L.i.S.P., Chapter 1,
Exercise 1.3, with solution code in the source file "chap1d.scm":

    (define (extend env names values)
      (cons (cons names values) env)) 

    (define (lookup id env)
      ...[~15 lines].. )

Also, in "Chapter 6: Fast interpretation" [which has lots of variations
on representations of lexical environments] he includes the option of
making the "values" side be a vector and then dropping the "names" side
entirely at runtime, using only the offsets computed at compile time.

[He also discusses "flat" environments and the need in such environments
to box lexical bindings that are shared, mutated, & escape, but that's
another story...]


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607

In article <TM6dnZ34lf7cgPDXnZ2dnUVZ_oydnZ2d@speakeasy.net>,
 rpw3@rpw3.org (Rob Warnock) wrote:

> Mattias Nilsson  <mattiasn@bredband.net> wrote:
> +---------------
> | Garret <rNOSPA...@flownet.com> wrote:
> | > There is a third representation of an abstract associative map, which
> | > I've never seen mentioned before. But it is so obvious I can't believe
> | > that the idea is original with me. For the moment I've dubbed them
> | > DLists. They look like this:
> | >
> | > ((key1 key2 ... keyN) value1 value2 ... valueN)
> | > [...]
> | > But all that is neither here nor there, because my actual question is:
> | > has all this been thought of before? I can't imagine that it hasn't
> | > been, but I've never seen it in any Lisp text. If there's literature on
> | > this, can someone point me to a reference? Do these structures have an
> | > actual name?
> | 
> | "Not A-lists"? See note {This ain't A-lists} in
> | "The Art of the Interpreter of, the Modularity Complex (Parts Zero,
> | One, and Two)"
> | ( http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-453.pdf ).
> +---------------
> 
> In addition to that, SICP2 also discusses this version [not at all
> surprising, given the 2nd author of AIM-453] for lexical environments
> which are a list of "frames", each of which is a cons of a list of
> variables and a list of values. See the functions MAKE-FRAME and
> EXTEND-ENVIRONMENT in the source file "ch4-mceval.scm" from SICP2.
> [Note: SICP1 didn't seem to use this method; compare with "chapter4.code".]
> 
> Queinnec also discusses this variation in L.i.S.P., Chapter 1,
> Exercise 1.3, with solution code in the source file "chap1d.scm":
> 
>     (define (extend env names values)
>       (cons (cons names values) env)) 
> 
>     (define (lookup id env)
>       ...[~15 lines].. )
> 
> Also, in "Chapter 6: Fast interpretation" [which has lots of variations
> on representations of lexical environments] he includes the option of
> making the "values" side be a vector and then dropping the "names" side
> entirely at runtime, using only the offsets computed at compile time.
> 
> [He also discusses "flat" environments and the need in such environments
> to box lexical bindings that are shared, mutated, & escape, but that's
> another story...]

Just what I was looking for.  Thanks!

rg

In article <rNOSPAMon-7545AD.18210326072009@news.albasani.net>,
 Ron Garret <rNOSPAMon@flownet.com> wrote:

> In article <m38wibaz4a.fsf@unnamed.xach.com>,
>  Zach Beane <xach@xach.com> wrote:
> 
> > Ron Garret <rNOSPAMon@flownet.com> writes:
> > 
> > >> > If we want to treat associative maps as objects with state independent 
> > >> > of the places where they are stored, we can do e.g. this with DLists:
> > >> 
> > >> I suppose this "problem"
> > >
> > > I didn't say it was a "problem."  Please don't introduce conflict where 
> > > none exists.
> > 
> > If you don't find the special casing of NIL a problem with alists and
> > plists compared to dlists, it's a little silly to list the absence of a
> > special case as an advantage of dlists.
> 
> I like blue cars.  So if I were to go shopping for a car, a blue car 
> would have an advantage over a red one.  I would not say, however, that 
> there is therefore a "problem" with red cars.
> 
> Analogously, some people like an object-oriented programming style.  For 
> such people, DLists offer an advantage over PLists or ALists.  It does 
> not follow that PLists and ALists have a "problem."
> 
> rg

All you've done is add a level of indirection.  It's just as easy to do 
that with alists and plists.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***

In article <barmar-68EA64.08444327072009@news.eternal-september.org>,
 Barry Margolin <barmar@alum.mit.edu> wrote:

> In article <rNOSPAMon-7545AD.18210326072009@news.albasani.net>,
>  Ron Garret <rNOSPAMon@flownet.com> wrote:
> 
> > In article <m38wibaz4a.fsf@unnamed.xach.com>,
> >  Zach Beane <xach@xach.com> wrote:
> > 
> > > Ron Garret <rNOSPAMon@flownet.com> writes:
> > > 
> > > >> > If we want to treat associative maps as objects with state 
> > > >> > independent 
> > > >> > of the places where they are stored, we can do e.g. this with 
> > > >> > DLists:
> > > >> 
> > > >> I suppose this "problem"
> > > >
> > > > I didn't say it was a "problem."  Please don't introduce conflict where 
> > > > none exists.
> > > 
> > > If you don't find the special casing of NIL a problem with alists and
> > > plists compared to dlists, it's a little silly to list the absence of a
> > > special case as an advantage of dlists.
> > 
> > I like blue cars.  So if I were to go shopping for a car, a blue car 
> > would have an advantage over a red one.  I would not say, however, that 
> > there is therefore a "problem" with red cars.
> > 
> > Analogously, some people like an object-oriented programming style.  For 
> > such people, DLists offer an advantage over PLists or ALists.  It does 
> > not follow that PLists and ALists have a "problem."
> > 
> > rg
> 
> All you've done is add a level of indirection.

I never meant to imply that DLists were a major breakthrough.  I was 
just asking if they appeared in the literature.  (They do.)

>  It's just as easy to do that with alists and plists.

That's true, but then they aren't ALists and PLists any more, they are 
some other data structure that happens to contain an AList or a PList.  
You couldn't pass one of these directly to ASSOC or GETF.

rg

On Jul 26, 1:39=A0pm, Ron Garret <rNOSPA...@flownet.com> wrote:

> But all that is neither here nor there, because my actual question is:
> has all this been thought of before? =A0I can't imagine that it hasn't
> been, but I've never seen it in any Lisp text. =A0If there's literature o=
n
> this, can someone point me to a reference? =A0Do these structures have an
> actual name?

No literature pointer for you (other than
source) but I *think* I recall that what
you call a D-list representation is sometimes
used to represent environment frames in SCM and
Guile.

-t

On Jul 27, 11:30=A0am, Ron Garret <rNOSPA...@flownet.com> wrote:

> I never meant to imply that DLists were a major breakthrough. =A0I was
> just asking if they appeared in the literature.

I think it's great!  If you hadn't had that brainstorm, then I'm sure
I would've been forever ignorant of the idea. Because I surely
wouldn't have thought of it.  And I'm pretty sure I would've just read
right past it without noting the import if I ever read SICP or came
across the AIM doc (which I do browse those sometimes, but you know,
"in one ear, out the other").

In article 
<0d8f8c2f-c47b-41e3-9141-1934132c23be@l35g2000pra.googlegroups.com>,
 fortunatus <daniel.eliason@excite.com> wrote:

> On Jul 27, 11:30�am, Ron Garret <rNOSPA...@flownet.com> wrote:
> 
> > I never meant to imply that DLists were a major breakthrough. �I was
> > just asking if they appeared in the literature.
> 
> I think it's great!  If you hadn't had that brainstorm, then I'm sure
> I would've been forever ignorant of the idea. Because I surely
> wouldn't have thought of it.  And I'm pretty sure I would've just read
> right past it without noting the import if I ever read SICP or came
> across the AIM doc (which I do browse those sometimes, but you know,
> "in one ear, out the other").

Thanks.  My interest in this is primarily pedagogical, so that's good to 
know.

rg

In article <rNOSPAMon-C519F5.08304027072009@news.albasani.net>,
 Ron Garret <rNOSPAMon@flownet.com> wrote:

> In article <barmar-68EA64.08444327072009@news.eternal-september.org>,
>  Barry Margolin <barmar@alum.mit.edu> wrote:
> 
> >  It's just as easy to do that with alists and plists.
> 
> That's true, but then they aren't ALists and PLists any more, they are 
> some other data structure that happens to contain an AList or a PList.  
> You couldn't pass one of these directly to ASSOC or GETF.

So?  You can't pass D-lists to any standard functions, either.  Either 
way you have to define new functions, so you could just as easily add 
functions that work with the wrapped plists or alists.

In fact, Maclisp did this with plists.  Originally, plists were only 
available as attributes of symbols, so they served as the indirection.  
Then they expanded it to "disembodied plists" -- if you gave GET a cons, 
it operated on the plist in its CDR (and conversely, CDR of a symbol 
would return its plist -- I assume they simply laid out both objects so 
that the same location was used for both).

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***

In article <barmar-BA3AE3.10271228072009@news.eternal-september.org>,
 Barry Margolin <barmar@alum.mit.edu> wrote:

> In article <rNOSPAMon-C519F5.08304027072009@news.albasani.net>,
>  Ron Garret <rNOSPAMon@flownet.com> wrote:
> 
> > In article <barmar-68EA64.08444327072009@news.eternal-september.org>,
> >  Barry Margolin <barmar@alum.mit.edu> wrote:
> > 
> > >  It's just as easy to do that with alists and plists.
> > 
> > That's true, but then they aren't ALists and PLists any more, they are 
> > some other data structure that happens to contain an AList or a PList.  
> > You couldn't pass one of these directly to ASSOC or GETF.
> 
> So?  You can't pass D-lists to any standard functions, either.  Either 
> way you have to define new functions, so you could just as easily add 
> functions that work with the wrapped plists or alists.

That's right.  And your point would be...?  (Keep in mind that my 
original question was: does this data structure appear in the 
literature?)

rg

In article <rNOSPAMon-9A4CD7.08004928072009@news.albasani.net>,
 Ron Garret <rNOSPAMon@flownet.com> wrote:

> In article <barmar-BA3AE3.10271228072009@news.eternal-september.org>,
>  Barry Margolin <barmar@alum.mit.edu> wrote:
> 
> > In article <rNOSPAMon-C519F5.08304027072009@news.albasani.net>,
> >  Ron Garret <rNOSPAMon@flownet.com> wrote:
> > 
> > > In article <barmar-68EA64.08444327072009@news.eternal-september.org>,
> > >  Barry Margolin <barmar@alum.mit.edu> wrote:
> > > 
> > > >  It's just as easy to do that with alists and plists.
> > > 
> > > That's true, but then they aren't ALists and PLists any more, they are 
> > > some other data structure that happens to contain an AList or a PList.  
> > > You couldn't pass one of these directly to ASSOC or GETF.
> > 
> > So?  You can't pass D-lists to any standard functions, either.  Either 
> > way you have to define new functions, so you could just as easily add 
> > functions that work with the wrapped plists or alists.
> 
> That's right.  And your point would be...?  (Keep in mind that my 
> original question was: does this data structure appear in the 
> literature?)

And I would answer that yes, the idea of adding a wrapper around a data 
structure appears in the literature very often.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***

 ZB> If you don't find the special casing of NIL a problem with alists and
 ZB> plists compared to dlists, it's a little silly to list the absence of a
 ZB> special case as an advantage of dlists.

Dlists are more flexible, as they can be extended both destructively and
non-destructively, while alists and plists can be extended only 
non-destructively.

In some cases this might be an advantage -- e.g. you started using some 
container
in a functional style, but then you need to use it in some place where such 
use is
not possible -- e.g. you need to pass it as function's parameter, for 
example. If you've
chose dlist, it wouldn't be a problem -- you can just use it destructively 
as it is,
while if your choice was alist or plist, you either need to wrap it and 
create some handling
code (some hassle...) or restructute your code to avoid destructive usage. 
So with dlist
you'll have less hassle.

Now, if dlist has advantage, that means alist and plist have disadvantages.

But it is not like alists and plists have problems --ANY design decision is 
a trade-off, it
 has both advantages and disadvantages, that's perfectly normal. 
Disadvantages become
problems only when choice was wrong and design decision cannot satisfy 
requirements.

In article <barmar-68B312.11065028072009@news.eternal-september.org>,
 Barry Margolin <barmar@alum.mit.edu> wrote:

> In article <rNOSPAMon-9A4CD7.08004928072009@news.albasani.net>,
>  Ron Garret <rNOSPAMon@flownet.com> wrote:
> 
> > In article <barmar-BA3AE3.10271228072009@news.eternal-september.org>,
> >  Barry Margolin <barmar@alum.mit.edu> wrote:
> > 
> > > In article <rNOSPAMon-C519F5.08304027072009@news.albasani.net>,
> > >  Ron Garret <rNOSPAMon@flownet.com> wrote:
> > > 
> > > > In article <barmar-68EA64.08444327072009@news.eternal-september.org>,
> > > >  Barry Margolin <barmar@alum.mit.edu> wrote:
> > > > 
> > > > >  It's just as easy to do that with alists and plists.
> > > > 
> > > > That's true, but then they aren't ALists and PLists any more, they are 
> > > > some other data structure that happens to contain an AList or a PList.  
> > > > You couldn't pass one of these directly to ASSOC or GETF.
> > > 
> > > So?  You can't pass D-lists to any standard functions, either.  Either 
> > > way you have to define new functions, so you could just as easily add 
> > > functions that work with the wrapped plists or alists.
> > 
> > That's right.  And your point would be...?  (Keep in mind that my 
> > original question was: does this data structure appear in the 
> > literature?)
> 
> And I would answer that yes, the idea of adding a wrapper around a data 
> structure appears in the literature very often.

Ah.  Well, in response to that I would say that D-Lists are not JUST a 
wrapper.  That they are a wrapper is the reason that they can be used in 
an object-oriented way without having to treat the empty collection 
specially.  But D-Lists also separate the keys from the values which 
neither ALists or PLists do, even when they are wrapped.  (That's the 
reason I called them D-Lists -- because the keys and values are 
Disconnected).  That separation provides additional benefits (which also 
appear in the literature as it turns out).

rg

In article <4a6f1626$0$300$14726298@news.sunsite.dk>,
 "Alex Mizrahi" <udodenko@users.sourceforge.net> wrote:

>  ZB> If you don't find the special casing of NIL a problem with alists and
>  ZB> plists compared to dlists, it's a little silly to list the absence of a
>  ZB> special case as an advantage of dlists.
> 
> Dlists are more flexible, as they can be extended both destructively and
> non-destructively, while alists and plists can be extended only 
> non-destructively.

That's not true.  Both ALists and PLists can be extended destructively, 
except in the case where they contain no bindings, which has to be 
handled as a special case.

rg

On Jul 26, 7:39=A0pm, Ron Garret <rNOSPA...@flownet.com> wrote:

> while P-Lists are structured like so:
>
> (key value key value ...)

Unless they're disembodied plists, in which case they're structured
like so:

 (nil key value key value ...)

These aren't CL-style plists, but they are historically important, and
still exist as a fundemental data structure in at least one
contemporary dialect (Skill).

> There is a third representation of an abstract associative map, which
> I've never seen mentioned before. =A0But it is so obvious I can't believe
> that the idea is original with me. =A0For the moment I've dubbed them
> DLists. =A0They look like this:
>
> ((key1 key2 ... keyN) value1 value2 ... valueN)
>
> DLists are just as efficient as ALists and PLists for all common
> operations, but they have several advantages over either ALists or
> PLists:
>
> 1. =A0The empty DList is not (), it's (()). =A0This means that you can pu=
sh
> new bindings onto a DList without having to special-case NIL like you do
> with ALists or Plists.

True enough for CL-style plists, but disembodied plists have this
attribute, too. Another bit you didn't mention that they both share is
object identity for the "dictionary". A related property is that dpls
give you a way to identify the meaning of the structure, by putting
something descriptive (the "class name" of the plist if you will) in
the car.

> 2. =A0When using a DList as a model of a lexical environment, the keys an=
d
> values are cleanly separated, so you can compile a lexical access simply
> by looking up the position of the key in the CAR of the DList, after
> which you can discard the CAR of the DList with no loss of
> functionality. =A0In other words, (deref dlist key) is equivalent to (nth
> (position key (car dlist)) (cdr dlist)), and (position key (car dlist))
> is a compile-time constant.

True as far as it goes, although you'd really want to compile those
references into indexes into a vector, not a list. You could make it
work with dlists, but I think it would be about as much work as using
alists.

> 3. =A0It is trivial to replace the CAR and the CDR of a DList with vector=
s
> (optionally adjustable vectors with fill pointers, though for the common
> use case of modeling lambda bindings this would not be necessary), in
> which case dereferencing constant keys can be done in amortized O(1)
> time. =A0This transformation is not possible with ALists or PLists. =A0Of
> course, it is possible to dereference constant keys for ALists and
> PLists in amortized O(1) time by keeping a reference to the value cell
> itself, but separating the steps so that there is a tangible
> intermediate result that is an integer offset into a value vector I
> believe has pedagogical value when teaching students how closures are
> compiled.

This is a nice property (although it doesn't really easily apply to
environments produced by compilers, since you want shared tails for
them).

> 4. =A0Multiple D-Lists can share the same key list, making D-Lists more
> space efficient (by a factor asymptotically approaching 2) for the
> common use case of modeling lexical environments that get instantiated
> multiple times.
>
> But all that is neither here nor there, because my actual question is:
> has all this been thought of before? =A0I can't imagine that it hasn't
> been, but I've never seen it in any Lisp text. =A0If there's literature o=
n
> this, can someone point me to a reference? =A0Do these structures have an
> actual name?

You mention down-thread that they are mentioned elsewhere. I may have
totally spaced, but did you mention where?

In article 
<38434cfe-78cd-4115-b244-1719ebf19ba3@o6g2000yqj.googlegroups.com>,
 "Thomas F. Burdick" <tburdick@gmail.com> wrote:

> > 2. �When using a DList as a model of a lexical environment, the keys and
> > values are cleanly separated, so you can compile a lexical access simply
> > by looking up the position of the key in the CAR of the DList, after
> > which you can discard the CAR of the DList with no loss of
> > functionality. �In other words, (deref dlist key) is equivalent to (nth
> > (position key (car dlist)) (cdr dlist)), and (position key (car dlist))
> > is a compile-time constant.
> 
> True as far as it goes, although you'd really want to compile those
> references into indexes into a vector, not a list. You could make it
> work with dlists, but I think it would be about as much work as using
> alists.

Not at all.  This is one the things that I think is cool about DLists.  
Transitioning from ((key ...) value ...), which is to say ((key ...) . 
(value ...)) to ((key ...) . #(value ...)) is trivial.

> > 3. �It is trivial to replace the CAR and the CDR of a DList with vectors
> > (optionally adjustable vectors with fill pointers, though for the common
> > use case of modeling lambda bindings this would not be necessary), in
> > which case dereferencing constant keys can be done in amortized O(1)
> > time. �This transformation is not possible with ALists or PLists. �Of
> > course, it is possible to dereference constant keys for ALists and
> > PLists in amortized O(1) time by keeping a reference to the value cell
> > itself, but separating the steps so that there is a tangible
> > intermediate result that is an integer offset into a value vector I
> > believe has pedagogical value when teaching students how closures are
> > compiled.
> 
> This is a nice property (although it doesn't really easily apply to
> environments produced by compilers, since you want shared tails for
> them).

You can have shared tails with DLists, though not if you do the 
list-to-vector transformation above.  In that case what I do is chain 
DLists together, so that an individual DList is a single frame in the 
call chain.  This is really what you want for closures anyway.

> > 4. �Multiple D-Lists can share the same key list, making D-Lists more
> > space efficient (by a factor asymptotically approaching 2) for the
> > common use case of modeling lexical environments that get instantiated
> > multiple times.
> >
> > But all that is neither here nor there, because my actual question is:
> > has all this been thought of before? �I can't imagine that it hasn't
> > been, but I've never seen it in any Lisp text. �If there's literature on
> > this, can someone point me to a reference? �Do these structures have an
> > actual name?
> 
> You mention down-thread that they are mentioned elsewhere. I may have
> totally spaced, but did you mention where?

Not me, it was Rob Warnock and Mattias Nilsson.

rg

On Jul 28, 10:51=A0pm, Ron Garret <rNOSPA...@flownet.com> wrote:
> In article
> <38434cfe-78cd-4115-b244-1719ebf19...@o6g2000yqj.googlegroups.com>,
> =A0"Thomas F. Burdick" <tburd...@gmail.com> wrote:
>
> > > 2. =A0When using a DList as a model of a lexical environment, the key=
s and
> > > values are cleanly separated, so you can compile a lexical access sim=
ply
> > > by looking up the position of the key in the CAR of the DList, after
> > > which you can discard the CAR of the DList with no loss of
> > > functionality. =A0In other words, (deref dlist key) is equivalent to =
(nth
> > > (position key (car dlist)) (cdr dlist)), and (position key (car dlist=
))
> > > is a compile-time constant.
>
> > True as far as it goes, although you'd really want to compile those
> > references into indexes into a vector, not a list. You could make it
> > work with dlists, but I think it would be about as much work as using
> > alists.
>
> Not at all. =A0This is one the things that I think is cool about DLists. =
=A0
> Transitioning from ((key ...) value ...), which is to say ((key ...) .
> (value ...)) to ((key ...) . #(value ...)) is trivial.

Sure, no doubt. What I meant was, if you have a situation like this:

  (let (a)
    (list (lambda (b) (setq a b) a)
          (lambda (b) (prog1 a (setq a b)))))

And you have your environments like so:

  ((b . #1=3D(a)) . (nil . #2=3D(nil)))
  ((b . #1#) . (nil . #2#))

Which would be the easy way to do things in a simple compiler, there's
no simple way to turn the binding parts of those environments into
vectors. You have to do the same work as with alists if you have
multiple frames with shared tails.

> > > 3. =A0It is trivial to replace the CAR and the CDR of a DList with ve=
ctors
> > > (optionally adjustable vectors with fill pointers, though for the com=
mon
> > > use case of modeling lambda bindings this would not be necessary), in
> > > which case dereferencing constant keys can be done in amortized O(1)
> > > time. =A0This transformation is not possible with ALists or PLists. =
=A0Of
> > > course, it is possible to dereference constant keys for ALists and
> > > PLists in amortized O(1) time by keeping a reference to the value cel=
l
> > > itself, but separating the steps so that there is a tangible
> > > intermediate result that is an integer offset into a value vector I
> > > believe has pedagogical value when teaching students how closures are
> > > compiled.
>
> > This is a nice property (although it doesn't really easily apply to
> > environments produced by compilers, since you want shared tails for
> > them).
>
> You can have shared tails with DLists, though not if you do the
> list-to-vector transformation above. =A0In that case what I do is chain
> DLists together, so that an individual DList is a single frame in the
> call chain. =A0This is really what you want for closures anyway.

Right, I think we're saying the same thing. You get shared tails or
you get easy transformation into vectors. Whereas for compiling
closures you want both.

> > > 4. =A0Multiple D-Lists can share the same key list, making D-Lists mo=
re
> > > space efficient (by a factor asymptotically approaching 2) for the
> > > common use case of modeling lexical environments that get instantiate=
d
> > > multiple times.
>
> > > But all that is neither here nor there, because my actual question is=
:
> > > has all this been thought of before? =A0I can't imagine that it hasn'=
t
> > > been, but I've never seen it in any Lisp text. =A0If there's literatu=
re on
> > > this, can someone point me to a reference? =A0Do these structures hav=
e an
> > > actual name?
>
> > You mention down-thread that they are mentioned elsewhere. I may have
> > totally spaced, but did you mention where?
>
> Not me, it was Rob Warnock and Mattias Nilsson.

Ah thanks, I somehow missed that bit of the thread (I blame Google
Groups).

By the way, another useful property of d-lists to represent
environments: if you're defining a dynamically scoped dialect, binding
your variables in the host lisp gets super-easy:

  (progv (car env) (cdr env)
    ...)

On Jul 27, 8:23 am, Ron Garret <rNOSPA...@flownet.com> wrote:

[[...]]

> If we want to treat associative maps as objects with state independent
> of the places where they are stored, we can do e.g. this with DLists:
>
> (defun add-binding-to-dlist (key value dlist)
>   (push key (car dlist))
>   (push value (cdr dlist))
>   dlist)
>
> which works thusly:
>
> ? (setf dlist (list nil))  ; Empty DList
> (NIL)
> ? (add-binding-to-dlist 'k1 'v1 dlist)
> ((K1) V1)
> ? dlist
> ((K1) V1)
> ?
>
> If we try to do the analogous thing with ALists or PLists it's not quite
> possible.  We can do e.g. this:
>
> (defun add-binding-to-alist (key value alist)
>   (let ((temp (car alist)))
>     (rplaca alist (cons key value))
>     (rplacd alist (cons temp (cdr alist)))
>     alist))
>
> which works as long as the list isn't empty:

[[...]]

> In other words, all DLists are of type PAIR, even the empty DList.  All
> ALists and PLists are of type PAIR *except* the empty AList/PList, which
> is of type NULL.
>
> rg

Actually it's not so bad with plists. By adopting the appropriate
programming style, I've typically found that you don't have to special
case nil if you do

(setf (getf my-plist key) value)

instead. This is very concise and handles the case where my-plist is
nil, just fine.

(let ((my-plist (list)))
 (setf (getf my-plist :name) "Pete")
 my-plist)
==> (:NAME "Pete")

Of course, you still have a problem with the identity of your
'object'. You cannot abstract this away with a function. Eg the
analogous counterpart to your alist example is:

(defun add-binding-to-plist (key value plist)
 (setf (getf plist key) value)
 plist)
==> add-binding-to-plist

(let ((x (list)))
 (add-binding-to-plist :name "Pete" x))
==> (:NAME "Pete")

(let ((x (list)))
 (add-binding-to-plist :name "Pete" x)
 x)
==> NIL

When x is not nil, then it's ok I guess.

(let ((x (list :age 20)))
 (add-binding-to-plist :name "Pete" x))
==> (:NAME "Pete" :AGE 20)

(let ((x (list :age 20)))
 (add-binding-to-plist :name "Pete" x)
 x)
==> (:NAME "Pete" :AGE 20)


The answer is probably to adopt a functional style, and if you really
need an abstraction like add-binding-to-plist or somesuch, make it a
macro instead?

 ZB>>> If you don't find the special casing of NIL a problem with alists and
 ZB>>> plists compared to dlists, it's a little silly to list the absence of
 ZB>>> a special case as an advantage of dlists.
 ??>>
 ??>> Dlists are more flexible, as they can be extended both destructively
 ??>> and non-destructively, while alists and plists can be extended only
 ??>> non-destructively.

 RG> That's not true.  Both ALists and PLists can be extended destructively,
 RG> except in the case where they contain no bindings, which has to be
 RG> handled as a special case.

I.e. they cannot be extended destructively in general case. 

Thomas F. Burdick <tburdick@gmail.com> wrote:
+---------------
| Ron Garret <rNOSPA...@flownet.com> wrote:
| > This is one the things that I think is cool about DLists.
| > Transitioning from ((key ...) value ...), which is to say ((key ...) .
| > (value ...)) to ((key ...) . #(value ...)) is trivial.
| 
| Sure, no doubt. What I meant was, if you have a situation like this:
| 
|   (let (a)
|     (list (lambda (b) (setq a b) a)
|           (lambda (b) (prog1 a (setq a b)))))
| 
| And you have your environments like so:
| 
|   ((b . #1=(a)) . (nil . #2=(nil)))
|   ((b . #1#) . (nil . #2#))
| 
| Which would be the easy way to do things in a simple compiler, there's
| no simple way to turn the binding parts of those environments into
| vectors. You have to do the same work as with alists if you have
| multiple frames with shared tails.
+---------------

Actually, you *can* readily turn them into vectors, by transforming
the shared lexicals into "box"es [a.k.a. "box conversion"]. That is,
your original code gets rewritten something like this:

    (defstruct box val)

    (let ((%a (make-box :val a))
      (list (lambda (b)
	      (setf (box-val %a) b)
	      (box-val %a))
            (lambda (b)
	      (prog1
		(box-val %a)
		(setf (box-val %a) b)))))

and then because %A is itself never mutated, it can be freely copied
without worrying about sharing, e.g.:

    (let ((%a (make-box :val a)))
      (list (let ((%b %a))
	      (lambda (b)
		(setf (box-val %b) b)
		(box-val %b)))
	    (let ((%c %a))
              (lambda (b)
		(prog1
		  (box-val %c)
		  (setf (box-val %c) b))))))

If this transformation is performed on all closed-over variables
which are both shared and mutated, then the closure environments
for each closure can be single unshared vectors, which can be
accessed in O(1). These are called "flat" environments, are used
in both PLT Scheme and CMU Common Lisp, and are discussed in
several places in Queinnec's "Lisp in Small Pieces".

+---------------
| > > This is a nice property (although it doesn't really easily apply to
| > > environments produced by compilers, since you want shared tails for
| > > them).
| >
| > You can have shared tails with DLists, though not if you do the
| > list-to-vector transformation above. In that case what I do is chain
| > DLists together, so that an individual DList is a single frame in the
| > call chain. This is really what you want for closures anyway.
| 
| Right, I think we're saying the same thing. You get shared tails or
| you get easy transformation into vectors. Whereas for compiling
| closures you want both.
+---------------

And you get both (and more) by adding box conversion to the mix.

+---------------
| > > > If there's literature on this, can someone point me to a reference?
| > > > Do these structures have an actual name?
| >
| > > You mention down-thread that they are mentioned elsewhere.
| > > I may have totally spaced, but did you mention where?
| >
| > Not me, it was Rob Warnock and Mattias Nilsson.
| 
| Ah thanks, I somehow missed that bit of the thread (I blame Google Groups).
+---------------

To save you some chasing, Mattias Nilsson referred to AIM-453, and
I referred to SICP2 [*not* SICP1!] and L.i.S.P. [also mentioned above].


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607

On Jul 29, 1:54=A0pm, r...@rpw3.org (Rob Warnock) wrote:
> Thomas F. Burdick <tburd...@gmail.com> wrote:
> +---------------
> | Ron Garret <rNOSPA...@flownet.com> wrote:
> | > This is one the things that I think is cool about DLists.
> | > Transitioning from ((key ...) value ...), which is to say ((key ...) =
..
> | > (value ...)) to ((key ...) . #(value ...)) is trivial.
> |
> | Sure, no doubt. What I meant was, if you have a situation like this:
> |
> | =A0 (let (a)
> | =A0 =A0 (list (lambda (b) (setq a b) a)
> | =A0 =A0 =A0 =A0 =A0 (lambda (b) (prog1 a (setq a b)))))
> |
> | And you have your environments like so:
> |
> | =A0 ((b . #1=3D(a)) . (nil . #2=3D(nil)))
> | =A0 ((b . #1#) . (nil . #2#))
> |
> | Which would be the easy way to do things in a simple compiler, there's
> | no simple way to turn the binding parts of those environments into
> | vectors. You have to do the same work as with alists if you have
> | multiple frames with shared tails.
> +---------------
>
> Actually, you *can* readily turn them into vectors, by transforming
> the shared lexicals into "box"es [a.k.a. "box conversion"]. That is,
> your original code gets rewritten something like this:

True. But what I was trying to say was that this data structure
doesn't make this any easier. To properly compile closures, there are
a few things you ant to do, including boxing shared variables and
removing references to unreferenced variables in enclosing
environments. Dlists do hint a little bit more in the right direction,
but ultimately you'll have the same amount of work to do with any of
the three representations.

> =A0 =A0 (defstruct box val)
>
> =A0 =A0 (let ((%a (make-box :val a))
> =A0 =A0 =A0 (list (lambda (b)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 (setf (box-val %a) b)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 (box-val %a))
> =A0 =A0 =A0 =A0 =A0 =A0 (lambda (b)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 (prog1
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (box-val %a)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (setf (box-val %a) b)))))
>
> and then because %A is itself never mutated, it can be freely copied
> without worrying about sharing, e.g.:
>
> =A0 =A0 (let ((%a (make-box :val a)))
> =A0 =A0 =A0 (list (let ((%b %a))
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 (lambda (b)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (setf (box-val %b) b)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (box-val %b)))
> =A0 =A0 =A0 =A0 =A0 =A0 (let ((%c %a))
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 (lambda (b)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (prog1
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (box-val %c)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 (setf (box-val %c) b))))))
>
> If this transformation is performed on all closed-over variables
> which are both shared and mutated, then the closure environments
> for each closure can be single unshared vectors, which can be
> accessed in O(1). These are called "flat" environments, are used
> in both PLT Scheme and CMU Common Lisp, and are discussed in
> several places in Queinnec's "Lisp in Small Pieces".
>
> +---------------
> | > > This is a nice property (although it doesn't really easily apply to
> | > > environments produced by compilers, since you want shared tails for
> | > > them).
> | >
> | > You can have shared tails with DLists, though not if you do the
> | > list-to-vector transformation above. In that case what I do is chain
> | > DLists together, so that an individual DList is a single frame in the
> | > call chain. This is really what you want for closures anyway.
> |
> | Right, I think we're saying the same thing. You get shared tails or
> | you get easy transformation into vectors. Whereas for compiling
> | closures you want both.
> +---------------
>
> And you get both (and more) by adding box conversion to the mix.
>
> +---------------
> | > > > If there's literature on this, can someone point me to a referenc=
e?
> | > > > Do these structures have an actual name?
> | >
> | > > You mention down-thread that they are mentioned elsewhere.
> | > > I may have totally spaced, but did you mention where?
> | >
> | > Not me, it was Rob Warnock and Mattias Nilsson.
> |
> | Ah thanks, I somehow missed that bit of the thread (I blame Google Grou=
ps).
> +---------------
>
> To save you some chasing, Mattias Nilsson referred to AIM-453, and
> I referred to SICP2 [*not* SICP1!] and L.i.S.P. [also mentioned above].
>
> -Rob
>
> -----
> Rob Warnock =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 <r...@rpw3.org>
> 627 26th Avenue =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 <URL:http://rpw3.org/>
> San Mateo, CA 94403 =A0 =A0 =A0 =A0 =A0 =A0 (650)572-2607

In article 
<71a54602-d061-4868-8e8d-584cee0ed3b7@d32g2000yqh.googlegroups.com>,
 "Thomas F. Burdick" <tburdick@gmail.com> wrote:

> On Jul 28, 10:51�pm, Ron Garret <rNOSPA...@flownet.com> wrote:
> > In article
> > <38434cfe-78cd-4115-b244-1719ebf19...@o6g2000yqj.googlegroups.com>,
> > �"Thomas F. Burdick" <tburd...@gmail.com> wrote:
> >
> > > > 2. �When using a DList as a model of a lexical environment, the keys and
> > > > values are cleanly separated, so you can compile a lexical access simply
> > > > by looking up the position of the key in the CAR of the DList, after
> > > > which you can discard the CAR of the DList with no loss of
> > > > functionality. �In other words, (deref dlist key) is equivalent to (nth
> > > > (position key (car dlist)) (cdr dlist)), and (position key (car dlist))
> > > > is a compile-time constant.
> >
> > > True as far as it goes, although you'd really want to compile those
> > > references into indexes into a vector, not a list. You could make it
> > > work with dlists, but I think it would be about as much work as using
> > > alists.
> >
> > Not at all. �This is one the things that I think is cool about DLists. �
> > Transitioning from ((key ...) value ...), which is to say ((key ...) .
> > (value ...)) to ((key ...) . #(value ...)) is trivial.
> 
> Sure, no doubt. What I meant was, if you have a situation like this:
> 
>   (let (a)
>     (list (lambda (b) (setq a b) a)
>           (lambda (b) (prog1 a (setq a b)))))
> 
> And you have your environments like so:
> 
>   ((b . #1=(a)) . (nil . #2=(nil)))
>   ((b . #1#) . (nil . #2#))
> 
> Which would be the easy way to do things in a simple compiler, there's
> no simple way to turn the binding parts of those environments into
> vectors. You have to do the same work as with alists if you have
> multiple frames with shared tails.

Ah.  What about this:

#((#(b) . #(...))) (#(a) . #(...)))

In other words, instead of trying to fram all the frames into a single 
D-List, I'd have a vector of D-Lists, one per frame.  That would let you 
share value vectors.  (Not clear if they still ought to be called 
D-Lists if their components are vectors.)

rg