Kernel LISP - how low down can it go?

[Mike McDonald]

>Subject: Re: Kernel LISP - how low down can it go?
>To: lispos@math.gatech.edu
>Date: Thu, 22 May 1997 12:15:48 -0400 (EDT)
>From: BRIAN SPILSBURY <zhivago@iglou.com>
>
>> I don't think he was suggesting that you make _every_ immutable list
>> into a vector; only that some immutable lists might profit from such
>> a thing.
>
>Right
> 
>> Actually, for the most part I wouldn't advise making most immutable
>> cons cells into vectors, since one still has to worry about recursing
>> down a list with CDR's, so it would be nice if this were reasonably
>> efficient.
>
>Yeah, I wasn't thikning of a normal vector, but rather leaving out the
>cdr reference, once the list had been rearranged to be linear, with
>a special case to catch falling off the end. Then you could have cdr/car
>work normally on elements of the list.
>
>At the least for reasonable length lists this would save around
>
>#-#-#-#-#-#-#-#-| (16 references)
>| | | | | | | |
>a b c d e f g h
>
>becomes
>
>abcdefgh| (9 references)
>
>and we get a saving of almost half. A magic termination symbol may be
>necessary, but that's not a huge deal.
>
>As for speed, I suspect it will be slightly faster.
>Another advantage is that it reduces fragmentation.
>
>I haven't tested this yet, so I guess its speculative. :)
>
>Brian
>

  This already has been done and it even has a name. It's called
cdr-coding.

  Mike McDonald
  mikemac@engr.sgi.com