Issue NINTERSECTION-DESTRUCTION Writeup

Issue:        NINTERSECTION-DESTRUCTION

Document:     X3J13/91-412

Reference:    CLtL-II, p.429

              Issue REMF-DESTRUCTION-UNSPECIFIED

              Draft 10.156 (X3J13/91-103)

              Draft 12.24 (X3J13/92-102)

              Barrett's public review comment #24 (X3J13/92-2524)

Category:     CLARIFICATION

Edit History: Version 1, 22-Dec-91, Kim Barrett

              Version 2, 19-Apr-92, Kim Barrett

                (Two proposals, note confused status)

              Version 3, 20-Apr-92, Kim Barrett (KMP's comments)

              Version 4, 7-Jun-92, Kim Barrett

Status:       Confusion!  One of the proposals (REVERT or PERMIT) was passed at

              the 12/91 meeting, but there is disagrement as to which.

              Draft 12.24 (X3J13/92-102) was written assuming that REVERT was

              the passed proposal.

              Barrett now asks us to reconsider proposal PERMIT.

	      Proposal REVERT passed 11-0 on letter ballot 93-302;

              on same ballot, proposal PERMIT failed 2-6.



Problem Description:


 Issue REMF-DESTRUCTION-UNSPECIFIED permits NINTERSECTION to modify either list

 argument, contrary to the description of NINTERSECTION in CLtL, which

 explicitly states that the second argument (list2) is not destroyed.  It is

 questionable whether this change was intentional or not, especially since

 REMF-DESTRUCTION-UNSPECIFIED was categorized as a clarification rather than a

 change.  


Proposal (NINTERSECTION-DESTRUCTION:REVERT):


 Affirm the wording from CLtL, prohibiting NINTERSECTION from modifying the

 second (list2) argument.


Proposal (NINTERSECTION-DESTRUCTION:PERMIT):


 Affirm the wording from REMF-DESTRUCTION-UNSPECIFIED, permitting NINTERSECTION

 to modify either list argument.


Editorial Impact:


 For REVERT:

   None.  The 12.24 draft assumes that REVERT was accepted.


 For PERMIT:

   Small.  The two-line paragraph on p.14-51 of X3J13/92-102 describing the

   difference between NINTERSECTION and INTERSECTION would have to be changed

   slightly, specifying that both the LIST-1 and LIST-2 arguments may be

   destroyed, rather than only permitting LIST-1 to be destroyed and requiring

   that LIST-2 be preserved.


Rationale:


 For REVERT:

   The intent of REMF-DESTRUCTION-UNSPECIFIED was not to change side-effect

   behavior, but to tack down places where we had all pretty much agreed on

   side-effect behavior but never spelled it out.  This was a case where CLtL

   had spelled things out, and which was probably changed unintentionally.

   Some older programs may depend on this argument not getting bashed, and it

   would be a shame to have some implementation decide to bash it.


   Don't make an apparently unintentional incompatible change.


 For PERMIT:

   Affirm the more recent decision, which went through more than two years of

   discussion before finally being accepted.  The intent of

   REMF-DESTRUCTION-UNSPECIFIED was to permit greater implementation freedom

   in order to achieve better performance; prohibiting the destruction of one

   of the lists may have a negative performance impact.


   A ``destructive'' function that is only permitted to destroy one of it's two

   arguments (with no rationale for which argument may be destroyed and which

   may not) is confusing; this is the only case of such.


Examples:


Current Practice:


 Apple Macintosh Common Lisp 2.0 obeys REVERT.


 Symbolics Genera 8.2 (and before) obeys REVERT.


Cost to Implementors:


 None for PERMIT.


 If REVERT is adopted, implementations that have been tracking the passed

 cleanups and have taken advantage of the permission granted by

 REMF-DESTRUCTION-UNSPECIFIED in this case will have to change.  It may require

 a significant amount of work to achieve similar performance.  Implementations

 that pre-existed the acceptance of that proposal may be able to revert to an

 older source that obeyed the CLtL1 restriction.


Cost to Users:


 For REVERT, no semantic cost for users; there may be a performance cost.


 For PERMIT, an incompatible change.  In some cases it may be quite difficult

 to determine whether a call to NINTERSECTION can safely destroy the second

 argument.


Performance Impact:


 There may be a negative performance impact in choosing REVERT over PERMIT.


 The ``obvious'' implementation is to iterate over the elements of one of the

 lists and if that element appears in the other list then collect it, reusing

 storage from the first list in the collection process.  If the length of the

 first list is less than the length of the second, this algorithm is

 asymptotically as much as a factor of two slower than if the lists were

 exchanged.  Thus, by preventing such a choice of which list to destroy, REVERT

 might result in slower performance for NINTERSECTION.


Discussion:


 The status of this issue is unclear.


    Date: Wed, 22 Jan 92 13:25:51 EST

    From: kab (Kim Barrett)

    To: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>

    Subject: Re: Issue: NINTERSECTION-DESTRUCTION (Version 1)


    >     Date: Sun, 22 Dec 1991 14:48 EST

    >     From: kab@cambridge.apple.com (Kim Barrett)

    > 

    >     Does this look ok to you?

    > 

    > No! My meeting notes say:

    > 

    >  "Move to say list-2 not modified.  PASS 8-2"

    > 

    > Lest you think I mis-noted this, I certainly remember lobbying for a

    > position which said that REMF-DESTRUCTION-UNSPECIFIED had made the

    > change unintentionally, and that we should revert the wording.  Had I

    > wanted to retain the wording, I would not have raised the issue.


    Looks like we have a problem here.  My notes just say


      "NINTERSECTION-DESTRUCTION passed 8-2"


    which is not very helpful.  My memory says that we voted to affirm the

    words in the draft (as stated in the draft writeup I sent you), but

    obviously I could be mistaken.  Unfortunately, the minutes are also

    ambiguous:


      REMF-DESTRUCTION-UNSPECIFIED

      (In document 91-003b.)

      Vote: 7 - 2. Passed.


    There isn't any such thing in the specified document.  (I pointed this out

    to Jan after the last version of minutes was mailed out).


 The reference to REMF-DESTRUCTION-UNSPECIFIED in 91-003b was to the following

 message:


    Date: Tue, 16 Jul 1991 17:33-0400

    From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>

    Subject: possible issue NINTERSECTION-DESTRUCTION

    To: kab@chestnut.com

    Cc: KMP@STONY-BROOK.SCRC.Symbolics.COM, barmar@think.com, GLS@Think.COM


    [Addressed to Kim because he's been keeping a list of my little nitpicks

     and figuring out which shoudl be written up and distributed.  Other

     relevant individuals cc'd in case they have comments.]


    One of Barmar's reviews turned up the following...


    CLtL said plainly that list-2 was not destroyed by NINTERSECTION.


    REMF-DESTRUCTION-UNSPECIFIED says quite clearly that it might be, even

    though I think the intent of REMF-DESTRUCTION-UNSPECIFIED was mainly to

    clarify points left vague by CLtL, not to introduce new things that were

    possible to destroy.


    The current draft is inconsistent in that in different places, it says

    things that are consistent either with CLtL or with the cleanup issue.


    The status quo is well-defined, so if no vote is taken I will believe

    REMF-DESTRUCTION-UNSPECIFIED.   But I don't think that people realized

    they were making an incompatible change in this particular case, so I

    wonder if the issue should be raised at X3J13 for confirmation.


    As an aside, I note that CLtL2's wording also implies that this was a

    "clarification" without making it apparent that an actual change had

    occurred.