260 lines
16 KiB
HTML
260 lines
16 KiB
HTML
<!-- Common Lisp HyperSpec (TM), version 7.0 generated by Kent M. Pitman on Mon, 11-Apr-2005 2:31am EDT -->
|
|
<HTML>
|
|
<HEAD>
|
|
<TITLE>CLHS: Issue REST-LIST-ALLOCATION Writeup</TITLE>
|
|
<LINK HREF="../Data/clhs.css" REL="stylesheet" TYPE="text/css" />
|
|
<META HTTP-EQUIV="Author" CONTENT="Kent M. Pitman">
|
|
<META HTTP-EQUIV="Organization" CONTENT="LispWorks Ltd.">
|
|
<LINK REL=TOP HREF="../Front/index.htm">
|
|
<LINK REL=COPYRIGHT HREF="../Front/Help.htm#Legal">
|
|
<LINK REL=DISCLAIMER HREF="../Front/Help.htm#Disclaimer">
|
|
<LINK REL=PREV HREF="../Issues/iss296_w.htm">
|
|
<LINK REL=UP HREF="../Issues/iss297.htm">
|
|
<LINK REL=NEXT HREF="../Issues/iss298_w.htm">
|
|
</HEAD>
|
|
<BODY>
|
|
<H1><A REV=MADE HREF="http://www.lispworks.com/"><IMG WIDTH=80 HEIGHT=65 ALT="[LISPWORKS]" SRC="../Graphics/LWSmall.gif" ALIGN=Bottom></A><A REL=TOP HREF="../Front/index.htm"><IMG WIDTH=237 HEIGHT=65 ALT="[Common Lisp HyperSpec (TM)]" SRC="../Graphics/CLHS_Sm.gif" ALIGN=Bottom></A> <A REL=PREV HREF="../Issues/iss296_w.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Previous]" SRC="../Graphics/Prev.gif" ALIGN=Bottom></A><A REL=UP HREF="../Issues/iss297.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Up]" SRC="../Graphics/Up.gif" ALIGN=Bottom></A><A REL=NEXT HREF="../Issues/iss298_w.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Next]" SRC="../Graphics/Next.gif" ALIGN=Bottom></A></H1>
|
|
|
|
<HR>
|
|
|
|
|
|
|
|
<H2>Issue REST-LIST-ALLOCATION Writeup</H2>
|
|
|
|
<PRE><B>Forum:</B> Cleanup<P>
|
|
<B>Issue:</B> <A HREF="iss297.htm">REST-LIST-ALLOCATION</A><P>
|
|
<P>
|
|
<B>References:</B> CLtL pp 107-108 (<A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A>)<P>
|
|
<P>
|
|
Related issues: <A REL=DEFINITION HREF="../Body/d_dynami.htm#dynamic-extent"><B>DYNAMIC-EXTENT</B></A><P>
|
|
<P>
|
|
<B>Category:</B> CLARIFICATION<P>
|
|
<P>
|
|
<B>Edit history:</B> 8-Dec-88, Version 1 by Masinter<P>
|
|
9-Dec-88, Version 2 by Clinger (add rationale, more discussion)<P>
|
|
12-Dec-88, Version 3 by Clinger (delete bogus examples)<P>
|
|
<P>
|
|
<B>Problem description:<P>
|
|
</B><P>
|
|
In the special case of calling a function with an <A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> list via <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A>,<P>
|
|
Common Lisp fails to specify whether a new copy of the list is freshly<P>
|
|
allocated. For example, given<P>
|
|
<P>
|
|
(<A REL=DEFINITION HREF="../Body/m_defpar.htm#defvar"><B>DEFVAR</B></A> *MY-LIST* '(A B C))<P>
|
|
<P>
|
|
(<A REL=DEFINITION HREF="../Body/m_defun.htm#defun"><B>DEFUN</B></A> FOO (<A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> X) (<A REL=DEFINITION HREF="../Body/f_eq.htm#eq"><B>EQ</B></A> X *MY-LIST*))<P>
|
|
<P>
|
|
does <P>
|
|
(<A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A> #'FOO *MY-LIST*)<P>
|
|
return T?<P>
|
|
<P>
|
|
This issue is different from the question of the extent of "rest lists" in<P>
|
|
the case when they *are* newly allocated which is indefinite; the issue<P>
|
|
<A REL=DEFINITION HREF="../Body/d_dynami.htm#dynamic-extent"><B>DYNAMIC-EXTENT</B></A> also contains some proposals about extent.<P>
|
|
<P>
|
|
<P>
|
|
<B>Proposal (REST-LIST-ALLOCATION:NEWLY-ALLOCATED): <P>
|
|
</B><P>
|
|
Specify that <A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> lists are newly allocated in the case when the function<P>
|
|
is called via <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A>.<P>
|
|
<P>
|
|
<B>Proposal (REST-LIST-ALLOCATION:MAY-SHARE): <P>
|
|
</B><P>
|
|
Specify that the value of an <A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> parameter is permitted, but not required,<P>
|
|
to share (top-level) <A REL=DEFINITION HREF="../Body/f_docume.htm#structure"><B>structure</B></A> with the last argument to <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A>.<P>
|
|
<P>
|
|
Proposal (REST-LIST-ALLOCATION:MUST-SHARE)<P>
|
|
<P>
|
|
Specify that the value of an <A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> parameter is required<P>
|
|
to share (top-level) <A REL=DEFINITION HREF="../Body/f_docume.htm#structure"><B>structure</B></A> with the last argument to <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A>.<P>
|
|
<P>
|
|
>> this needs better spec about how the args match << <P>
|
|
<P>
|
|
<B>Examples:<P>
|
|
</B><P>
|
|
(<A REL=DEFINITION HREF="../Body/m_defpar.htm#defvar"><B>DEFVAR</B></A> *MY-LIST* '(A B C))<P>
|
|
<P>
|
|
(<A REL=DEFINITION HREF="../Body/m_defun.htm#defun"><B>DEFUN</B></A> FOO (<A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> X) (<A REL=DEFINITION HREF="../Body/f_eq.htm#eq"><B>EQ</B></A> X *MY-LIST*))<P>
|
|
<P>
|
|
(<A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A> #'FOO *MY-LIST*) => T ;on Symbolics systems and probably<P>
|
|
; many stock hardware implementations<P>
|
|
<P>
|
|
This implies that<P>
|
|
<P>
|
|
(<A REL=DEFINITION HREF="../Body/m_defun.htm#defun"><B>DEFUN</B></A> BAR (<A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> X) (<A REL=DEFINITION HREF="../Body/f_rplaca.htm#rplaca"><B>RPLACA</B></A> X 'D))<P>
|
|
<P>
|
|
(<A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A> #'BAR *MY-LIST*)<P>
|
|
<P>
|
|
*MY-LIST* => (D B C) ;on Symbolics systems and probably many stock<P>
|
|
; hardware implementations<P>
|
|
<P>
|
|
Another example: which of the following have the same semantics?<P>
|
|
<P>
|
|
(<A REL=DEFINITION HREF="../Body/s_setq.htm#setq"><B>setq</B></A> x '(1 2 3))<P>
|
|
<P>
|
|
[1] (apply #'foo 1 2 3 <A REL=DEFINITION HREF="../Body/a_nil.htm#nil"><B>NIL</B></A>)<P>
|
|
[2] (apply #'foo 1 2 (<A REL=DEFINITION HREF="../Body/f_car_c.htm#cddr"><B>cddr</B></A> x))<P>
|
|
[3] (apply #'foo 1 (<A REL=DEFINITION HREF="../Body/f_car_c.htm#cdr"><B>cdr</B></A> x))<P>
|
|
[4] (apply #'foo x)<P>
|
|
[5] (<A REL=DEFINITION HREF="../Body/f_funcal.htm#funcall"><B>funcall</B></A> #'foo 1 2 3)<P>
|
|
<P>
|
|
Under REST-LIST-ALLOCATION:NEWLY-ALLOCATED:<P>
|
|
[1]-[5] are equivalent.<P>
|
|
Under REST-LIST-ALLOCATION:MAY-SHARE:<P>
|
|
Any answer to the question is correct for some conceivable implementation.<P>
|
|
Abstracting over implementations, this means that [1]-[5] are pairwise<P>
|
|
non-equivalent.<P>
|
|
Under REST-LIST-ALLOCATION:MUST-SHARE:<P>
|
|
[1]-[4] are pairwise non-equivalent in all implementations. This proposal<P>
|
|
leaves open the question of whether [1] is equivalent to [5].<P>
|
|
<P>
|
|
And finally:<P>
|
|
<P>
|
|
Should (<A REL=DEFINITION HREF="../Body/m_defun.htm#defun"><B>defun</B></A> foo (&rest x) ...)<P>
|
|
<P>
|
|
behave (aside from efficiency) as if it were defined:<P>
|
|
<P>
|
|
(<A REL=DEFINITION HREF="../Body/m_defun.htm#defun"><B>defun</B></A> foo (<A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&rest</B></A> G0047) ;Gensym really<P>
|
|
(<A REL=DEFINITION HREF="../Body/s_let_l.htm#let"><B>let</B></A> ((x (<A REL=DEFINITION HREF="../Body/f_cp_lis.htm#copy-list"><B>copy-list</B></A> G0047)))<P>
|
|
...))<P>
|
|
<P>
|
|
<P>
|
|
<B>Rationale:<P>
|
|
</B><P>
|
|
The semantics of <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A> is unclear. In consequence it is impossible<P>
|
|
to write portable code that relies on <A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> arguments sharing <A REL=DEFINITION HREF="../Body/f_docume.htm#structure"><B>structure</B></A><P>
|
|
with the last argument to <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A>. Portable code can rely on <A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> arguments<P>
|
|
*not* sharing <A REL=DEFINITION HREF="../Body/f_docume.htm#structure"><B>structure</B></A> with the last argument to <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A>, but only by<P>
|
|
performing an explicit <A REL=DEFINITION HREF="../Body/f_cp_lis.htm#copy-list"><B>COPY-LIST</B></A> on all <A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> arguments; this is redundant<P>
|
|
and inefficient in implementations where <A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> arguments are newly<P>
|
|
allocated anyway.<P>
|
|
<P>
|
|
<B>Current practice:<P>
|
|
</B><P>
|
|
Some implementations always share. Some implementations never share.<P>
|
|
A few may share interpreted and not share compiled, or vice versa.<P>
|
|
<P>
|
|
<B>Cost to Implementors:<P>
|
|
</B><P>
|
|
None for MAY-SHARE, since that is the status quo. Both of the other<P>
|
|
proposals entail a significant cost for some implementations.<P>
|
|
If MUST-SHARE is adopted, then implementations that don't share <A REL=DEFINITION HREF="../Body/f_docume.htm#structure"><B>structure</B></A><P>
|
|
may be nearly impossible to convert. If NEWLY-ALLOCATED is adopted, then<P>
|
|
implementations that do share will have to insert a call to <A REL=DEFINITION HREF="../Body/f_cp_lis.htm#copy-list"><B>COPY-LIST</B></A><P>
|
|
inside either <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A> or <A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> list handling, which will slow things down<P>
|
|
and may be difficult as well.<P>
|
|
<P>
|
|
<B>Cost to Users:<P>
|
|
</B><P>
|
|
No matter what, somebody gets hurt. MAY-SHARE means you have to<P>
|
|
write awkward and inefficient code if you care. (This is already<P>
|
|
the case for portable code.) MUST-SHARE means you have to add<P>
|
|
explicit calls to <A REL=DEFINITION HREF="../Body/f_cp_lis.htm#copy-list"><B>COPY-LIST</B></A> to code that assumes the contrary.<P>
|
|
NEWLY-ALLOCATED means you have to rewrite code that assumes sharing.<P>
|
|
<P>
|
|
<B>Cost of non-adoption:<P>
|
|
</B><P>
|
|
Great confusion over the issue. A certain amount of awkwardness and<P>
|
|
inefficiency would remain inevitable if you want to write portable code.<P>
|
|
<P>
|
|
<B>Performance impact:<P>
|
|
</B><P>
|
|
MUST-SHARE costs least in consing, but might slow down function call <P>
|
|
for some implementations. MAY-SHARE lets implementations pick, has<P>
|
|
least impact. NEWLY-ALLOCATED requires consing in cases where it<P>
|
|
didn't before.<P>
|
|
<P>
|
|
<B>Benefits:<P>
|
|
</B><P>
|
|
Less confusion. Improved portability.<P>
|
|
<P>
|
|
<B>Esthetics:<P>
|
|
</B><P>
|
|
Differing, strongly held opinions.<P>
|
|
<P>
|
|
<B>Discussion:<P>
|
|
</B><P>
|
|
The Revised3 Report on Scheme specifies that the equivalent of a<P>
|
|
<A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> argument must be a newly allocated list, to avoid precisely this<P>
|
|
problem.<P>
|
|
<P>
|
|
The argument for MUST-SHARE is that copying is inefficient, so<P>
|
|
<A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> should never cause copying of a list passed to it from <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A>.<P>
|
|
Functions that desire a new copy can just call <A REL=DEFINITION HREF="../Body/f_cp_lis.htm#copy-list"><B>COPY-LIST</B></A>.<P>
|
|
<P>
|
|
Two arguments for MAY-SHARE are:<P>
|
|
<P>
|
|
1. In no other place does Common Lisp automatically unshare <A REL=DEFINITION HREF="../Body/f_docume.htm#structure"><B>structure</B></A>,<P>
|
|
except when the user is explicitly modifying the <A REL=DEFINITION HREF="../Body/f_docume.htm#structure"><B>structure</B></A> (as in <A REL=DEFINITION HREF="../Body/f_rm_rm.htm#remove"><B>REMOVE</B></A>).<P>
|
|
Making <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A> automatically unshare would be a semantic wart.<P>
|
|
<P>
|
|
2. If <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A> copies its last argument, recursive programs that receive an<P>
|
|
<A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> argument and pass it to <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A> become inefficient. A linear time<P>
|
|
algorithm can change to a quadratic time algorithm. While the efficiency<P>
|
|
could be regained through compiler flow analysis in many cases, it's<P>
|
|
better not to put the inefficiency into the language in the first place.<P>
|
|
<P>
|
|
The <A REL=DEFINITION HREF="../Body/d_dynami.htm#dynamic-extent"><B>DYNAMIC-EXTENT</B></A> proposal would allow <A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> lists<P>
|
|
that were "newly allocated" to have dynamic extent if they were<P>
|
|
to be passed down via <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A>. This puts the burden in the<P>
|
|
right place.<P>
|
|
<P>
|
|
Two (closely related) arguments for NEWLY-ALLOCATED:<P>
|
|
<P>
|
|
1. The programmer's model of function calling is simpler: functions<P>
|
|
take arguments, and any two calls that pass the same arguments to the<P>
|
|
same function are equivalent. The MAY-SHARE and MUST-SHARE proposals<P>
|
|
<A REL=DEFINITION HREF="../Body/f_provid.htm#require"><B>require</B></A> a model in which functions generally take their arguments in<P>
|
|
the form of a list, and the extent to which that list shares <A REL=DEFINITION HREF="../Body/f_docume.htm#structure"><B>structure</B></A><P>
|
|
with other lists in the system becomes an important part of the<P>
|
|
semantics of a function call.<P>
|
|
<P>
|
|
2. It's not only smashing a &rest argument that's a problem, it's<P>
|
|
smashing any list that has been given as the last argument to <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A> as<P>
|
|
well. Consider the following in an implementation that doesn't copy<P>
|
|
the last argument to <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A> when it is passed as a &rest argument:<P>
|
|
<P>
|
|
> (<A REL=DEFINITION HREF="../Body/m_defpar.htm#defvar"><B>defvar</B></A> *message*)<P>
|
|
*MESSAGE*<P>
|
|
> (<A REL=DEFINITION HREF="../Body/m_defun.htm#defun"><B>defun</B></A> set-message (&rest mess)<P>
|
|
(<A REL=DEFINITION HREF="../Body/s_setq.htm#setq"><B>setq</B></A> *message* mess))<P>
|
|
SET-MESSAGE<P>
|
|
> (let ((winner (list 'a 'winner)))<P>
|
|
(<A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>apply</B></A> #'set-message winner)<P>
|
|
(<A REL=DEFINITION HREF="../Body/a_setf.htm#setf"><B>setf</B></A> (<A REL=DEFINITION HREF="../Body/f_car_c.htm#cdr"><B>cdr</B></A> winner) (<A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A> 'loser))<P>
|
|
winner)<P>
|
|
(A LOSER)<P>
|
|
<P>
|
|
Is *message* (A WINNER) or (A LOSER)? (It might be<P>
|
|
(#<DTP-LOCATIVE 76123756> #<DTP-ODD-PC 12313453> ...)<P>
|
|
but that's a different problem.) This suggests that once a list has<P>
|
|
been given as the last argument to <A REL=DEFINITION HREF="../Body/f_apply.htm#apply"><B>APPLY</B></A> it is no longer OK to modify<P>
|
|
it.<P>
|
|
<P>
|
|
Gail Zacharias talked about the common idiom of simply doing a <A REL=DEFINITION HREF="../Body/f_cp_lis.htm#copy-list"><B>COPY-LIST</B></A><P>
|
|
on every &rest argument, to insure some normalcy. Her reasoning seems<P>
|
|
to bolster the case for those who claim that the current CL semantics<P>
|
|
(MAY-SHARE) are deficient:<P>
|
|
<P>
|
|
Subject: <A REL=DEFINITION HREF="../Body/03_da.htm#AMrest"><B>&REST</B></A> Lists<P>
|
|
Date: 24 Mar 88 12:23:15 EST (Thu)<P>
|
|
From: gz@spt.entity.com (Gail Zacharias)<P>
|
|
. . . <P>
|
|
If Common Lisp doesn't <A REL=DEFINITION HREF="../Body/f_provid.htm#require"><B>require</B></A> unshared &rest lists, then I think<P>
|
|
it must <A REL=DEFINITION HREF="../Body/f_provid.htm#provide"><B>provide</B></A> a declarative version of this idiom so the <A REL=DEFINITION HREF="../Body/f_cp_lis.htm#copy-list"><B>COPY-LIST</B></A> can<P>
|
|
be portably avoided when it's redundant. Seems to me that the fact that<P>
|
|
this is a common case where users find a need for conditionalization<P>
|
|
indicates a real deficiency in Common Lisp's specification.<P>
|
|
. . . <P>
|
|
<P>
|
|
So we have a responsibility to resolve the very thorny issue<P>
|
|
of <A HREF="iss297.htm">REST-LIST-ALLOCATION</A>.<P>
|
|
<P>
|
|
</PRE>
|
|
<HR>
|
|
|
|
<A REL=NAVIGATOR HREF="../Front/StartPts.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Starting Points]" SRC="../Graphics/StartPts.gif" ALIGN=Bottom></A><A REL=TOC HREF="../Front/Contents.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Contents]" SRC="../Graphics/Contents.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Master.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Index]" SRC="../Graphics/Index.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Symbol.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Symbols]" SRC="../Graphics/Symbols.gif" ALIGN=Bottom></A><A REL=GLOSSARY HREF="../Body/26_a.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Glossary]" SRC="../Graphics/Glossary.gif" ALIGN=Bottom></A><A HREF="../Front/X3J13Iss.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Issues]" SRC="../Graphics/Issues.gif" ALIGN=Bottom></A><BR>
|
|
|
|
<A REL=COPYRIGHT HREF="../Front/Help.htm#Legal"><I>Copyright 1996-2005, LispWorks Ltd. All rights reserved.</I></A><P>
|
|
</BODY>
|
|
</HTML>
|