[HARLEQUIN][Common Lisp HyperSpec (TM)] [Previous][Up][Next]


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.


[Starting Points][Contents][Index][Symbols][Glossary][Issues]
Copyright 1996, The Harlequin Group Limited. All Rights Reserved.