219 lines
12 KiB
HTML
219 lines
12 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 NINTERSECTION-DESTRUCTION 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/iss246_w.htm">
|
|
<LINK REL=UP HREF="../Issues/iss247_m.htm">
|
|
<LINK REL=NEXT HREF="../Issues/iss249_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/iss246_w.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Previous]" SRC="../Graphics/Prev.gif" ALIGN=Bottom></A><A REL=UP HREF="../Issues/iss247_m.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Up]" SRC="../Graphics/Up.gif" ALIGN=Bottom></A><A REL=NEXT HREF="../Issues/iss249_w.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Next]" SRC="../Graphics/Next.gif" ALIGN=Bottom></A></H1>
|
|
|
|
<HR>
|
|
|
|
|
|
|
|
<H2>Issue NINTERSECTION-DESTRUCTION Writeup</H2>
|
|
|
|
<PRE><B>Issue:</B> <A HREF="iss247_m.htm">NINTERSECTION-DESTRUCTION</A><P>
|
|
Document: X3J13/91-412<P>
|
|
Reference: CLtL-II, p.429<P>
|
|
Issue <A HREF="iss293.htm">REMF-DESTRUCTION-UNSPECIFIED</A><P>
|
|
Draft 10.156 (X3J13/91-103)<P>
|
|
Draft 12.24 (X3J13/92-102)<P>
|
|
Barrett's public review comment #24 (X3J13/92-2524)<P>
|
|
<B>Category:</B> CLARIFICATION<P>
|
|
<B>Edit History:</B> Version 1, 22-Dec-91, Kim Barrett<P>
|
|
Version 2, 19-Apr-92, Kim Barrett<P>
|
|
(Two proposals, note confused status)<P>
|
|
Version 3, 20-Apr-92, Kim Barrett (KMP's comments)<P>
|
|
Version 4, 7-Jun-92, Kim Barrett<P>
|
|
<B>Status:</B> Confusion! One of the proposals (REVERT or PERMIT) was passed at<P>
|
|
the 12/91 meeting, but there is disagrement as to which.<P>
|
|
Draft 12.24 (X3J13/92-102) was written assuming that REVERT was<P>
|
|
the passed proposal.<P>
|
|
Barrett now asks us to reconsider proposal PERMIT.<P>
|
|
Proposal REVERT passed 11-0 on letter ballot 93-302;<P>
|
|
on same ballot, proposal PERMIT failed 2-6.<P>
|
|
<P>
|
|
<P>
|
|
<B>Problem Description:<P>
|
|
</B><P>
|
|
Issue <A HREF="iss293.htm">REMF-DESTRUCTION-UNSPECIFIED</A> permits <A REL=DEFINITION HREF="../Body/f_isec_.htm#nintersection"><B>NINTERSECTION</B></A> to modify either list<P>
|
|
argument, contrary to the description of <A REL=DEFINITION HREF="../Body/f_isec_.htm#nintersection"><B>NINTERSECTION</B></A> in CLtL, which<P>
|
|
explicitly states that the second argument (list2) is not destroyed. It is<P>
|
|
questionable whether this change was intentional or not, especially since<P>
|
|
<A HREF="iss293.htm">REMF-DESTRUCTION-UNSPECIFIED</A> was categorized as a clarification rather than a<P>
|
|
change. <P>
|
|
<P>
|
|
<B>Proposal (NINTERSECTION-DESTRUCTION:REVERT):<P>
|
|
</B><P>
|
|
Affirm the wording from CLtL, prohibiting <A REL=DEFINITION HREF="../Body/f_isec_.htm#nintersection"><B>NINTERSECTION</B></A> from modifying the<P>
|
|
second (list2) argument.<P>
|
|
<P>
|
|
<B>Proposal (NINTERSECTION-DESTRUCTION:PERMIT):<P>
|
|
</B><P>
|
|
Affirm the wording from <A HREF="iss293.htm">REMF-DESTRUCTION-UNSPECIFIED</A>, permitting <A REL=DEFINITION HREF="../Body/f_isec_.htm#nintersection"><B>NINTERSECTION</B></A><P>
|
|
to modify either list argument.<P>
|
|
<P>
|
|
<B>Editorial Impact:<P>
|
|
</B><P>
|
|
For REVERT:<P>
|
|
None. The 12.24 draft assumes that REVERT was accepted.<P>
|
|
<P>
|
|
For PERMIT:<P>
|
|
Small. The two-line paragraph on p.14-51 of X3J13/92-102 describing the<P>
|
|
difference between <A REL=DEFINITION HREF="../Body/f_isec_.htm#nintersection"><B>NINTERSECTION</B></A> and <A REL=DEFINITION HREF="../Body/f_isec_.htm#intersection"><B>INTERSECTION</B></A> would have to be changed<P>
|
|
slightly, specifying that both the LIST-1 and LIST-2 arguments may be<P>
|
|
destroyed, rather than only permitting LIST-1 to be destroyed and requiring<P>
|
|
that LIST-2 be preserved.<P>
|
|
<P>
|
|
<B>Rationale:<P>
|
|
</B><P>
|
|
For REVERT:<P>
|
|
The intent of <A HREF="iss293.htm">REMF-DESTRUCTION-UNSPECIFIED</A> was not to change side-effect<P>
|
|
behavior, but to tack down places where we had all pretty much agreed on<P>
|
|
side-effect behavior but never spelled it out. This was a case where CLtL<P>
|
|
had spelled things out, and which was probably changed unintentionally.<P>
|
|
Some older programs may depend on this argument not getting bashed, and it<P>
|
|
would be a shame to have some implementation decide to bash it.<P>
|
|
<P>
|
|
Don't make an apparently unintentional incompatible change.<P>
|
|
<P>
|
|
For PERMIT:<P>
|
|
Affirm the more recent decision, which went through more than two years of<P>
|
|
discussion before finally being accepted. The intent of<P>
|
|
<A HREF="iss293.htm">REMF-DESTRUCTION-UNSPECIFIED</A> was to permit greater implementation freedom<P>
|
|
in order to achieve better performance; prohibiting the destruction of one<P>
|
|
of the lists may have a negative performance impact.<P>
|
|
<P>
|
|
A ``destructive'' function that is only permitted to destroy one of it's two<P>
|
|
arguments (with no rationale for which argument may be destroyed and which<P>
|
|
may not) is confusing; this is the only case of such.<P>
|
|
<P>
|
|
<B>Examples:<P>
|
|
</B><P>
|
|
<B>Current Practice:<P>
|
|
</B><P>
|
|
Apple Macintosh Common Lisp 2.0 obeys REVERT.<P>
|
|
<P>
|
|
Symbolics Genera 8.2 (and before) obeys REVERT.<P>
|
|
<P>
|
|
<B>Cost to Implementors:<P>
|
|
</B><P>
|
|
None for PERMIT.<P>
|
|
<P>
|
|
If REVERT is adopted, implementations that have been tracking the passed<P>
|
|
cleanups and have taken advantage of the permission granted by<P>
|
|
<A HREF="iss293.htm">REMF-DESTRUCTION-UNSPECIFIED</A> in this case will have to change. It may <A REL=DEFINITION HREF="../Body/f_provid.htm#require"><B>require</B></A><P>
|
|
a significant amount of work to achieve similar performance. Implementations<P>
|
|
that pre-existed the acceptance of that proposal may be able to revert to an<P>
|
|
older source that obeyed the CLtL1 restriction.<P>
|
|
<P>
|
|
<B>Cost to Users:<P>
|
|
</B><P>
|
|
For REVERT, no semantic cost for users; there may be a performance cost.<P>
|
|
<P>
|
|
For PERMIT, an incompatible change. In some cases it may be quite difficult<P>
|
|
to determine whether a call to <A REL=DEFINITION HREF="../Body/f_isec_.htm#nintersection"><B>NINTERSECTION</B></A> can safely destroy the second<P>
|
|
argument.<P>
|
|
<P>
|
|
<B>Performance Impact:<P>
|
|
</B><P>
|
|
There may be a negative performance impact in choosing REVERT over PERMIT.<P>
|
|
<P>
|
|
The ``obvious'' implementation is to iterate over the elements of one of the<P>
|
|
lists and if that element appears in the other list then collect it, reusing<P>
|
|
storage from the first list in the collection process. If the length of the<P>
|
|
first list is less than the length of the second, this algorithm is<P>
|
|
asymptotically as much as a factor of two slower than if the lists were<P>
|
|
exchanged. Thus, by preventing such a choice of which list to destroy, REVERT<P>
|
|
might result in slower performance for <A REL=DEFINITION HREF="../Body/f_isec_.htm#nintersection"><B>NINTERSECTION</B></A>.<P>
|
|
<P>
|
|
<B>Discussion:<P>
|
|
</B><P>
|
|
The status of this issue is unclear.<P>
|
|
<P>
|
|
Date: Wed, 22 Jan 92 13:25:51 EST<P>
|
|
From: kab (Kim Barrett)<P>
|
|
To: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM><P>
|
|
Subject: Re: Issue: <A HREF="iss247_m.htm">NINTERSECTION-DESTRUCTION</A> (Version 1)<P>
|
|
<P>
|
|
> Date: Sun, 22 Dec 1991 14:48 EST<P>
|
|
> From: kab@cambridge.apple.com (Kim Barrett)<P>
|
|
> <P>
|
|
> Does this look ok to you?<P>
|
|
> <P>
|
|
> No! My meeting notes say:<P>
|
|
> <P>
|
|
> "Move to say list-2 not modified. PASS 8-2"<P>
|
|
> <P>
|
|
> Lest you think I mis-noted this, I certainly remember lobbying for a<P>
|
|
> position which said that <A HREF="iss293.htm">REMF-DESTRUCTION-UNSPECIFIED</A> had made the<P>
|
|
> change unintentionally, and that we should revert the wording. Had I<P>
|
|
> wanted to retain the wording, I would not have raised the issue.<P>
|
|
<P>
|
|
Looks like we have a problem here. My notes just say<P>
|
|
<P>
|
|
"NINTERSECTION-DESTRUCTION passed 8-2"<P>
|
|
<P>
|
|
which is not very helpful. My memory says that we voted to affirm the<P>
|
|
words in the draft (as stated in the draft writeup I sent you), but<P>
|
|
obviously I could be mistaken. Unfortunately, the minutes are also<P>
|
|
ambiguous:<P>
|
|
<P>
|
|
<A HREF="iss293.htm">REMF-DESTRUCTION-UNSPECIFIED</A><P>
|
|
(In document 91-003b.)<P>
|
|
Vote: 7 - 2. Passed.<P>
|
|
<P>
|
|
There isn't any such thing in the specified document. (I pointed this out<P>
|
|
to Jan after the last version of minutes was mailed out).<P>
|
|
<P>
|
|
The reference to <A HREF="iss293.htm">REMF-DESTRUCTION-UNSPECIFIED</A> in 91-003b was to the following<P>
|
|
message:<P>
|
|
<P>
|
|
Date: Tue, 16 Jul 1991 17:33-0400<P>
|
|
From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM><P>
|
|
Subject: possible issue <A HREF="iss247_m.htm">NINTERSECTION-DESTRUCTION</A><P>
|
|
To: kab@chestnut.com<P>
|
|
Cc: KMP@STONY-BROOK.SCRC.Symbolics.COM, barmar@think.com, GLS@Think.COM<P>
|
|
<P>
|
|
[Addressed to Kim because he's been keeping a list of my little nitpicks<P>
|
|
and figuring out which shoudl be written up and distributed. Other<P>
|
|
relevant individuals cc'd in case they have comments.]<P>
|
|
<P>
|
|
One of Barmar's reviews turned up the following...<P>
|
|
<P>
|
|
CLtL said plainly that list-2 was not destroyed by <A REL=DEFINITION HREF="../Body/f_isec_.htm#nintersection"><B>NINTERSECTION</B></A>.<P>
|
|
<P>
|
|
<A HREF="iss293.htm">REMF-DESTRUCTION-UNSPECIFIED</A> says quite clearly that it might be, even<P>
|
|
though I think the intent of <A HREF="iss293.htm">REMF-DESTRUCTION-UNSPECIFIED</A> was mainly to<P>
|
|
clarify points left vague by CLtL, not to introduce new things that were<P>
|
|
possible to destroy.<P>
|
|
<P>
|
|
The current draft is inconsistent in that in different places, it says<P>
|
|
things that are consistent either with CLtL or with the cleanup issue.<P>
|
|
<P>
|
|
The status quo is well-defined, so if no vote is taken I will believe<P>
|
|
<A HREF="iss293.htm">REMF-DESTRUCTION-UNSPECIFIED</A>. But I don't think that people realized<P>
|
|
they were making an incompatible change in this particular case, so I<P>
|
|
wonder if the issue should be raised at X3J13 for confirmation.<P>
|
|
<P>
|
|
As an aside, I note that CLtL2's wording also implies that this was a<P>
|
|
"clarification" without making it apparent that an actual change had<P>
|
|
occurred.<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>
|