Issue: REMF-DESTRUCTURING-UNSPECIFIED (Version 1)

[Masinter.pa@Xerox.COM]

Status: I cannot find any discussion on this topic. 

Issue:     REMF-DESTRUCTION-UNSPECIFIED
References: GET (SETF), REMPROP, GETF (SETF), REMF, pp. 165-167.
	   NREVERSE, p. 248.
	   DELETE, DELETE-IF, DELETE-IF-NOT, DELETE-DUPLICATES,
	   NSUBSTITUTE, NSUBSTITUTE-IF, NSUBSTITUTE-IF-NOT, pp. 254-256.
	   NCONC, NRECONC, p. 269.
	   NBUTLAST, p. 271.
	   NSUBST, NSUBST-IF, NSUBST-IF-NOT, p. 274.
	   NUNION, NINTERSECTION, NSET-EXCLUSIVE-OR, p. 276-279.

Edit history:	Version 1 by DLA@SCRC-STONY-BROOK.SCRC.Symbolics.COM


Problem Description:

Currently, the exact nature of the list modification
performed by REMF and REMPROP is not specified.  Conversation on the
Common-Lisp mailing list has made it clear that this situation is not
good.  The list modification allowed should either be specified, or
explicitly documented as unspecified and up to the individual
implementation.  If the list modification is specified, then programmers
can rely on the specification.  If it is unspecified, then implementors
can take advantage of that to make their implementation more efficient.

This argument can be made for most of the destructive functions
specified above, and possibly others, so they are included as
references.

Category:  clarification

Proposal:  REMF-DESTRUCTION-UNSPECIFIED:DONT-SPECIFY

I propose that CLtL's documentation on each of the above functions
include a statement such as the following:  "This function performs a
modification to the top-level [list] structure of its argument(s). 
Different implementations may choose different modifications of the list
structure, as long as the function otherwise fulfills its contract.  It
is an error to rely on the list destruction being performed in any
particular way.  Any references to the list structure of the argument(s)
other than the value(s) returned are therefore undefined after the function
returns."

Rationale:  

Benefits: 

Implementations can improve performance of
many of the referenced functions when they are not under the constraint
to implement them in a specified fashion or "in the most logical
fashion".  For example, on the Symbolics 3600, DELETE of a cdr-coded
list could use the implementation primitive %CHANGE-LIST-TO-CONS rather
than RPLACD to avoid creating forwarding pointers.  As another example,
all of the destructive operations which remove objects could remove CAR
pointers to removed objects which are more volatile than the list
itself, assisting the garbage collector.

Most of the referenced functions implement abstract operations, for
example REMPROP implements an abstract operation on a "property list".
Proper language design should not encourage people to delve below the
level of abstraction into the nitty gritty.

Aesthetics: 

This change would not affect programs coded with "good programming
practice".  That is, only programs which rely on currently undocumented
features would be in any danger of breaking.  In fact, those programs
are currently in such danger, and this change to the documentation would
just publicize it.  The clarification would ENCOURAGE good programming
practice by warning people to only obey the published contract of the
referenced functions.

Current practice:

Symbolics Common Lisp already implements some of the functions in a
non-obvious fashion.  For example, in Symbolics Common Lisp:

    (setq foo (list 'a 'b 'c))   ==> (a b c)
    (setq bar (cdr foo))         ==> (b c)
    (setq foo (delete 'b foo))   ==> (a c)
    bar                          ==> ((c)) ; most people would guess (b c).
    (eq (cdr foo) (car bar))     ==> t

Cost of adopting change: 
There is no cost of adopting this change to developers.
------------------------------------------------------------
Alternative proposal:  REMF-DESTRUCTION-UNSPECIFIED:DO-SPECIFY

Some or all of the functions could be documented to
perform the list destruction in a specified manner.

Rationale and Advantages:  (1) The "additional features" may be more
useful to some programmers.  (2) Programmers may expect the functions to
do the "expected" destructive operation.  (3) Compatibility with other
dialects.  For example, it may be easier to port a Zetalisp program to
Common-Lisp if REMPROP returns a sublist pointer as defined in Zetalisp.

If this alternative is pursued, then many implementations may be forced
to incompatibly change what their functions do.  This may break existing
programs and may cause the implementation to have poorer performance.