Issue REMF-DESTRUCTION-UNSPECIFIED Writeup

Status: v6 accepted by X3J13 with amendments to fix typos (see v7) on 16-1 vote

Issue:        REMF-DESTRUCTION-UNSPECIFIED

References:   (SETF (GET ...) ...), REMPROP, (SETF (GETF ...) ...),

	      REMF (pp165-167); NREVERSE (p248); DELETE, DELETE-IF,

	      DELETE-DUPLICATES, NSUBSTITUTE, NSUBSTITUTE-IF (pp254-256); 

	      NCONC, NRECONC (p269); NUNION, NINTERSECTION,

	      NSET-EXCLUSIVE-OR (pp276-279).

Category:     CLARIFICATION/CHANGE

Edit history: 11-Feb-87, Version 1 by Dave Andre (DLA@Symbolics.COM)

	      29-Oct-87, Version 2 by Pitman (flesh out proposals)

	      28-Nov-88, Version 3 by Pitman (revised presentation)

	      29-Nov-88, Version 4 by Pitman (slight editing per DLA)

	      15-Mar-89, Version 5 by Margolin (amendments discussed in

			 Hawaii, removed -NOT functions)

	      17-Mar-89, Version 6 by Margolin (make NSUBSTITUTE* less vague)

	      05-Apr-89, Version 7 by Pitman (typos corrected per X3J13)


Problem Description:


 Currently, the exact nature of the side-effect performed by list

 modification routines is not specified.


 Either the specific modifications allowed should be specified so that

 programmers can rely on them and implementors can avoid accidentally

 causing problems by introducing well-meaning optimizations, or else

 the documentation should explicitly state that the effects are

 unspecified so that programmers will not depend on them and 

 implementors will feel comfortable about doing interesting optimizations.


Proposal (REMF-DESTRUCTION-UNSPECIFIED:X3J13-MAR-89):


 Clarify that the way in which the destructive behavior of the

 operators below is achieved is explicitly vague in a number of ways,

 in order to provide individual implementations the necessary

 flexibility to do useful optimizations.


 (SETF (GETF place indicator) value)

  is permitted to either SETF place or to SETF any part, CAR or

  CDR, of the top-level list structure held by that place.


 (REMF place indicator)

  is permitted to either SETF place or to SETF any part, CAR or

  CDR, of the top-level list structure held by that place.


 (SETF (GET symbol indicator) value)

  is constrained to behave exactly the same as

  (SETF (GETF (SYMBOL-PLIST symbol) indicator) value).


 (REMPROP symbol indicator)

  is constrained to behave exactly the same as

  (REMF (SYMBOL-PLIST symbol) indicator).


 (NREVERSE sequence)

  when sequence is a list, is permitted to SETF any part, CAR or

   CDR, of the top-level list structure in that sequence.

  when sequence is an array is permitted to re-order the elements

   of the given sequence in order to produce the resulting array.


 (DELETE object sequence ...)

  when sequence is a list, is permitted to SETF any part, CAR or

   CDR, of the top-level list structure held in that sequence.

  when sequence is an array is permitted to change the dimensions

   of the array and to slide its elements into new positions without

   permuting them to produce the resulting array.

  

 (DELETE-IF test sequence ...)

  is constrained to behave exactly like

  (DELETE NIL sequence

	  :TEST #'(LAMBDA (IGNORE ITEM) (FUNCALL test ITEM))

	  ...).


 (DELETE-DUPLICATES sequence ...)

  when sequence is a list, is permitted to SETF any part, CAR or

   CDR, of the top-level list structure held in that sequence.

  when sequence is an array is permitted to change the dimensions

   of the array and to slide its elements into new positions without

   permuting them to produce the resulting array.


 (NRECONC list tail)

  is constrained to have side-effect behavior equivalent to:

  (NCONC (NREVERSE list) tail).


 (NUNION list1 list2 ...)

 (NINTERSECTION list1 list2 ...)

 (NSET-EXCLUSIVE-OR list1 list2 ...)

  is permitted to SETF any part, CAR or CDR, of the top-level of

  any of the given lists.


  Note, however, that since this side-effect is not required,

  these functions should still not be used in for-effect-only

  positions in portable code.


 (NCONC . lists)

  is defined using the following recursive relationship:


    (NCONC) => NIL

    (NCONC NIL . args) == (NCONC . args)

    (NCONC arg) => arg

    (NCONC arg1 arg2) has the side effect of (RPLACD (LAST arg1) arg2),

		      and returns arg1 

    (NCONC arg1 arg2 . args) == (NCONC (NCONC arg1 arg2) . args)


  [If a previous cleanup issue prohibited NIL as a non-last argument

   then ignore the (NCONC NIL . args) case.]


 (NSUBSTITUTE new-object old-object sequence ...)

 (NSUBSTITUTE-IF new-object test sequence ...)

  is required to SETF any CAR (if SEQUENCE is a list) or AREF (if it's

  a vector) of SEQUENCE which is required to be replaced with

  NEW-OBJECT.  If SEQUENCE is a list, none of the CDRs of the

  top-level list may be modified.  These functions, therefore, may be

  used in for-effect-only positions in code (some may find this

  stylistically distasteful, though).


 Note: The above clarifications are not intended as complete functional

 descriptions. They are intended to augment (rather than to replace)

 other descriptions already in effect.


Test Cases:


 For GETF...


    (SETQ FOO (LIST 'A 'B 'C 'D 'E 'F))    ==> (A B C D E F)

    (SETQ BAR (CDDR FOO))                  ==> (C D E F)

    (REMF FOO 'C)

    BAR				           ==> ??


    In Symbolics Common Lisp, BAR holds (C D E F).

    CLtL allows other interpretations. eg, BAR might hold

    (C), (NIL), (C NIL) or (C D).

    Under this proposal, any of these interpretations (and others as well)

    would still be valid


 For DELETE...


    (SETQ FOO (LIST 'A 'B 'C))   ==> (A B C)

    (SETQ BAR (CDR FOO))         ==> (B C)

    (SETQ FOO (DELETE 'B FOO))   ==> (A C)

    BAR                          ==> ??

    (EQ (CDR FOO) (CAR BAR))     ==> ??


    In Symbolics Common Lisp, these last two expressions return ((C)) and T.

    Under this proposal, either of these interpretations (and others

    as well) would be valid.


 For NCONC...


    (SETQ FOO (LIST 'A 'B 'C 'D 'E)

	  BAR (LIST 'F 'G 'H 'I 'J)

	  BAZ (LIST 'K 'L 'M)) => (K L M)

    (SETQ FOO (NCONC FOO BAR BAZ)) => (A B C D E F G H I J K L M)

    FOO => (A B C D E F G H I J K L M)

    BAR => (F G H I J K L M)

    BAZ => (K L M)


    (SETQ FOO (LIST 'A 'B 'C 'D 'E)

	  BAR (LIST 'F 'G 'H 'I 'J)

	  BAZ (LIST 'K 'L 'M)) => (K L M)

    (SETQ FOO (NCONC NIL FOO BAR NIL BAZ)) => (A B C D E F G H I J K L M) 

    FOO => (A B C D E F G H I J K L M)

    BAR => (F G H I J K L M)

    BAZ => (K L M)



Rationale:


 Implementations already vary widely on their implementation techniques

 for these functions. This effectively clarifies the status quo, making

 it more clear to programmers what they may rely upon in portable code.


 In the case of NCONC, however, the precise definition is useful because

 it is what users expect, it is how NCONC has been defined for many

 years, and it is how current implementations generally work.  It may

 not always be the most efficient way (e.g. it may result in invisible

 pointers in CDR-coded implementations), but callers of NCONC probably

 use it specifically for its precise side effects.


 In the case of NSUBSTITUTE, this seems like the only reasonable

 implementation mechanism, and there doesn't seem to be a reason not to

 guarantee it.


Current Practice:


 All valid implementations are believed to comply with the vague

 definitions.  Symbolics Genera 7.2 and Sun Common Lisp 2.1.3 appear to

 conform to the NCONC spec.


Cost to Implementors:


 None. This is probably the status quo for most implementors.  If there

 are any implementations that don't implement NCONC and NSUBSTITUTE as

 above (which I doubt) they will have to be changed.


Cost to Users:


 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 already 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

 above-mentioned functions.


 There is, however, no automatic technique for making this check for

 programs already in error. Bugs due to unexpected side-effects are in

 general among the hardest to reckon with.


Cost of Non-Adoption:


 Programmers may naively believe there is only one possible or reasonable

 implementation of these functions. Some implementors may shy away from

 reasonable optimizations out of a paranoid belief that deviating from 

 some vague, unspoken rules will lead to programmer unrest. Making these

 things explicitly vague clarifies the implementor's rights in a way that

 permits numerous useful optimizations.


Benefits: 


 Users would be discouraged from taking advantage of subtle details

 of these destructive operations because such details would be explicitly

 not guaranteed to be portable.


 Implementations can improve performance of many of the above-mentioned

 functions when they are not under the constraint to implement them

 in a highly constrained fashion. For example, in Symbolics systems,

 DELETE of a cdr-coded list could use the implementation primitive

 %CHANGE-LIST-TO-CONS rather than RPLACD to avoid creating forwarding

 pointers.


 Garbage collection effectiveness can also be improved. For example,

 all of the destructive operations which remove objects (eg, REMF)

 could remove CAR pointers to removed objects which are more volatile

 than the list itself, assisting the garbage collector and thereby

 improving memory usage and paging performance.


 Tightening the definition of NCONC and NSUBSTITUTE permits users to

 predict their programs' behavior more precisely.


Non-Benefits:


 Users who inadvertently depend on side-effect behavior may be rudely

 surprised when moving between implementations.


 Compatibility with older Lisp dialects is diminished.


 Implementors have less flexibility in implementing NCONC efficiently.

 This is true of NSUBSTITUTE, but this is less likely to cause problems.


Performance Impact:


 Metering in Symbolics test  systems have shown that there are substantial

 performance gains to be had by allowing implementations flexibility in

 these areas.


 In the case of NCONC, this implementation flexibility, and hence

 potential performance improvements, is sacrificed.


 If anyone ever invents CAR-coding, the required implementation of

 NSUBSTITUTE could be a performance hindrance.


Aesthetics:


 Most of these 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.


 NCONC is a "less abstract" function than the rest of the functions

 described above.  It is usually used precisely because of the way it

 interacts with list implementation.  Similarly for NSUBSTITUTE.


Discussion:


 Andre's original version of this proposal pushed for explicitly vague

 descriptions of these functions' side-effect behavior.  He believes

 that if users want more predictability from these functions, they

 should write private variants that implement whatever predictability

 they require. 


 Pitman originally opposed this position because he weighed portability

 a higher concern. Since the original discussion, however, his views on

 how to resolve this priority have been refined, and he now believes

 that leaving things vague is appropriate. As such, he now supports what

 is effectively Andre's original proposal.


 Pitman and Andre supported version 4.  [I don't know how they feel

 about v6 -- Barmar].


 Moon supports version 6.