From: David Pollen
Subject: Do Cons, List, Append, etc. Always create new boxes?
Date:
Message-ID: <pollenCrvy2t.AHE@netcom.com>
Does the Common List Standard guarentee that cons, list, append etc.
will always create new cons boxes (at the top level) or are there
any implemenatations which can and do try to use existing boxes
for memory effeciency reasons without telling the user?
······@netcom.com
From: Henry G. Baker
Subject: Re: Do Cons, List, Append, etc. Always create new boxes?
Date:
Message-ID: <hbakerCrxJ3H.1I6@netcom.com>
In article <················@netcom.com> ······@netcom.com (David Pollen) writes:
>Does the Common List Standard guarentee that cons, list, append etc.
>will always create new cons boxes (at the top level) or are there
>any implemenatations which can and do try to use existing boxes
>for memory effeciency reasons without telling the user?
The usual interpretation is that cons, list , append creates new boxes.
Routines like rplaca, rplacd, nconc, are explicitly designed to reuse
the old boxes.
Now if the implementation can figure out that the old boxes for cons,
append, etc., are going away anyway, then it can reuse them without
waiting for the GC to pick them up. For cons & append, this isn't
very important, but for 'functional arrays', this issue is absolutely
crucial to gaining decent performance. For example, the 'logical'
operations on 'bignums' are all functional in Common Lisp, but it
would be nice for 'lognot' to do its operation 'in-place' if the
compiler could prove that the old value was garbage, anyway.
I have written several papers about a dialect of Lisp called 'Linear
Lisp' in which the programmer can't tell the difference between append
and nconc, because the arguments to _every_ function are already known
to be garbage because every variable and object is 'used only once'.
Of course, the implementation immediately reuses the cells -- in some
cases without even putting them back onto the free list.
For some references:
Baker, H.G. A Linear Logic Quicksort. ACM Sigplan Not. 29,2 (Feb 1994),
13-18.
Baker, H.G. Linear Logic and Permutation Stacks. ACM Computer Arch. News
22,1 (mar 1994), 34-43.
Baker, H.G. Lively Linear Lisp. ACM Sigplan Not. 27,8 (Aug 1992, 89-98.