Issue: APPEND-FIASCO (Version 2)

[Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>]

Issue:        APPEND-FIASCO
Forum:	      Cleanup
References:   APPEND (p268), NCONC (p269), Backquote (pp349-351),
	      issue APPEND-DOTTED, issue APPEND-ATOM,
	      issue BACKQUOTE-COMMA-ATSIGN-DOT-COMMA
Category:     CLARIFICATION/CHANGE
Edit history: 11-Jan-89, Version 1 by Pitman (internal review at Symbolics)
	      12-Jan-89, Version 2 by Pitman (merge comments)	
Status:	      For Internal Discussion
Subsumes:     issue APPEND-DOTTED (already adopted by X3J13),
	      issue APPEND-ATOM,
	      issue BACKQUOTE-COMMA-ATSIGN-DOT-COMMA

Problem Description:

  Issue APPEND-DOTTED sought to clarify a vague part of the language
  in a useful and interesting way (which was already current practice
  in several implementations).

  Unfortunately, that clarification had unanticipated consequences
  which give us reason to reconsider the decision:

    - (APPEND "FOO" "BAR") is one example of a degenerate 
      case of APPEND not treated explicitly by the APPEND-DOTTED
      proposal. Issue APPEND-ATOM was raised to deal with this.
      The proposal suggested that this either signal an error or
      return "BAR".

    - The fact that `(FOO ,@X) might not return the same as
      `(FOO .,X), if X were a dotted list, is another example.
      Issue BACKQUOTE-COMMA-ATSIGN-DOT-COMMA was raised to deal
      with this. There was disagreement about how to resolve the
      problem.

Proposal (APPEND-FIASCO:DOTTED-IS-ERROR):

  Revert the approval of issue APPEND-DOTTED:REPLACE.

  Since its problem described in APPEND-DOTTED is also reverted, solve the
  it anew in the following different way:

  1. Define that the effects of passing a dotted list to APPEND or
     NCONC are undefined.

  2. Define that the effects of passing a non-null atom to APPEND
     or NCONC are undefined.

  3. Clarify that it is an error for the form following a ",@" or a ",."
     to return an atom or a dotted list.

     3a. Clarify that since it is permissible for the form following a
	 normal "," to return an atom or dotted list, there are logically
	 no restrictions on the return value of the form following ".,".
	 As such, ".," may be useful in some cases involving atoms or
	 dotted lists where ",@" is undefined.

  4. Clarify that although (COPY-LIST x) and (APPEND x '()) agree for
     all valid arguments X, COPY-LIST is defined on some values that APPEND
     isn't. As such, the two are not equivalent in intent and no relation
     should be made between them.

  5. Observe that the above rules have these implications:

     5a. Due to 1 and 2: Valid uses of APPEND and NCONC can never return
	 dotted lists.

     5b. Due to 3: For all valid uses of ",@" before the last element of
         a list, using ".," instead will produce structurally equivalent
	 code.

     5c. Due to 3: For all valid uses of ",." before the last element of
         a list, using ".," instead will produce structurally equivalent
         code [although there may be differences in the side-effect 
	 behavior].

     5d. Due to 3: For all valid uses of ",@", using ",." instead will
         produce structurally equivalent code [although there may be
         differences in the side-effect behavior].

Test Case:

  1.1  (APPEND '(A . B) '(C)) is undefined.

       It might return (A C), APPEND might signal an error, memory might
       be corrupted, etc.

  1.2  (APPEND '(A) '(B . C)) is undefined.

       It might return (A B . C), APPEND might signal an error, memory
       might be corrupted, etc.

  2.1  (APPEND 'A '(B)) is undefined.

       It might return (B), APPEND might signal an error, memory
       might be corrupted, etc.

  2.2  (APPEND '(A) 'B) is undefined.

       It might return (A . B), APPEND might signal an error, memory
       might be corrupted, etc.

  2.3  (APPEND "A" "B") is undefined.

       It might return "B", it might return "AB", APPEND might signal
       an error, memory might be corrupted, etc.

  3.1  `(A ,@'(B . C)) is undefined.

       It might return (A B . C), the operator into which ",@" expands 
       might signal an error, memory might be corrupted, etc.

  3.2  `(A ,@'B) is undefined.

       It might return (A . B), the operator into which ",@" expands 
       might signal an error, memory might be corrupted, etc.

  3a.1 `(A .,'(B . C)) must return (A B . C).

  3a.2 `(A .,'B) must return (A . B).

Rationale:

  This addresses the problems originally raised in APPEND-DOTTED.

  However, unlike APPEND-DOTTED, the solution suggested is to tighten
  existing definitions rather than loosening them. Such an approach is
  far less likely to lead to internal inconsistencies.

  Keeping people from confusing (APPEND x '()) with (COPY-LIST x) is
  a good idea anyway, since we might someday want to loosen the
  restrictions on what arguments APPEND copies so that it doesn't
  bother to copy an argument when all subsequent arguments are ().

Current Practice:

  All valid implementations are presumably compatible with this,
  whether they have switched to the APPEND-DOTTED behavior or not.

  [Source for the following information is the writeup for 
   APPEND-DOTTED (Version 5), approved by X3J13:]

  Symbolics Lisp, Vaxlisp, and Lucid Lisp appear to implement 
  APPEND-DOTTED:REPLACE (at least in the interpreter). Franz's
  Allegro Common Lisp also conforms to that proposal except in
  the case of (NCONC (LIST) 17) => 17, where it returns NIL instead
  of 17.

  Kyoto Common Lisp signals an error when using APPEND or NCONC on
  a dotted list.

  Xerox Common Lisp signals an error on APPEND of a dotted list but
  permits NCONC on a dotted list.

Cost to Implementors:

  None. This change is upward compatible.

Cost to Users:

  Technically none. Unless this change causes an implementation to
  change, no user code would be forced to change. Any user code which
  does have to change was certainly not portable to begin with.

Cost of Non-Adoption:

  Some people might resist the full set of changes needed to make
  APPEND-DOTTED consistent throughout the language. The aesthetic
  cost of having things be inconsistent in the language are probably
  higher than the pragmatic costs of portability problems having some
  implementations extending APPEND and NCONC in ways that are barriers
  to portability.

  We already have evidence (issues BACKQUOTE-COMMA-ATSIGN-DOT-COMMA
  and APPEND-ATOM) that APPEND-DOTTED had consequences which were
  unforseen. One risk of going forward is that other issues like them
  will arise only after using this language, too late to be corrected
  by the standard.

Benefits:

  Implementations which do not extend APPEND and NCONC can make useful
  optimizations in high speed/low safety code based on the knowledge that
  they always return proper lists.

Aesthetics:

  This proposal improves linguistic aesthetics, possibly at some expense to
  portability [since implementations will probably differ on how they treat
  the part of the contract of APPEND and NCONC which has been made vague].

Discussion:

  Pitman originally wrote and supported APPEND-DOTTED based on observations
  of current practice, but now believes that the price of pursuing that
  approach may have been too high.

  Michael Greenwald, Kent Pitman, Glenn Burke, and David Moon read version
  1 of this proposal. The level of support or opposition varied, centered
  around ambivalence with no strikingly strong positions in favor or against.
  In spite of lack of agreement on this particular proposal, there was general
  agreement that the whole situation with APPEND was getting pretty weird
  and that we should at least be willing to consider alternatives in attempt
  to reach a closure on these complicated issues.

  Glenn Burke was the most skeptical. He doesn't like to view NCONC as a
  destructive form of APPEND. He likes to think of it as a way of achieving
  (RPLACD (LAST x) y). He doesn't care if it's inconsistent with APPEND.
  He's mostly just worried about existing code breaking, and about loss of
  functionality. This proposal was therefore not his preference, but he
  didn't absolutely condemn it either.

  Moon observes that in issue REMF-DESTRUCTION-UNSPECIFIED, many people
  have expressed concern that the precise side-effect of NCONC should be 
  more well-defined than that of other destructive operators because it
  has a lot of history and a lot of code depending on it. The bottom line
  here was that extending the arguments (per APPEND-DOTTED) does not risk
  breaking code, while restricting the arguments (per this proposal) does.

  Some (not necessarily exclusive) alternatives are:

   - decide that APPEND-DOTTED was right and continue with APPEND-ATOM
     and BACKQUOTE-COMMA-ATSIGN-DOT-COMMA for consistency.

   - back up pre-APPEND-DOTTED days and write a proposal reaffirming
     the status quo, simply making disagreements and/or boundary cases
     explicit.

   - write a DOTTED-SHOULD-SIGNAL variant of the above proposal,
     requiring implementations to signal an error at least in the
     highest safety setting [though perhaps not for the last
     argument; see next option]. Such a variant would implicitly
     define implementations which extend APPEND and NCONC to handle
     dotted lists to be non-conforming.

   - a variant which weakened the restriction on argument type so
     that only the last argument to APPEND and NCONC could be dotted,
     but no other argument could be. This makes practical sense since
     it's highly unlikely that any implementation will want to actually
     verify that particular argument. [However, doing so might lose the
     useful optimizations that could be done by knowing that the
     results of NCONC and APPEND are always proper lists. In the long
     run such optimizations might be of considerable value. Among other
     things, this change to APPEND-DOTTED seems to have begun a trend
     toward using ATOM rather than ENDP to end-check lists. While it
     makes the language more powerful, it may also make it slower.
     On the other hand, this second order problem would be lessened if
     there were a PROPER-LIST type so that you could declare the inputs
     to APPEND and NCONC to be proper lists, and the type of the output
     could be inferred by compilers.]

  A consequence of this proposal is that the optimization
    (NCONC X NIL) => X
  becomes legitimate for implementations that disallow dotted lists as
  arguments to NCONC.