Issue DOTTED-LIST-ARGUMENTS Writeup

Forum:		Public Review

Issue:		DOTTED-LIST-ARGUMENTS

References:	Loosemore's public review comment #10 (X3J13/92-1310)

                Pitman's public review comments #37, #38, #39

		  (X3J13/92-2737, -2738, -2739)

		Issue APPEND-DOTTED (retracted)

		Issue APPEND-FIASCO (withdrawn)

		Issue APPEND-ATOM (withdrawn)

		Issue REMF-DESTRUCTION-UNSPECIFIED (passed)

		Issue LAST-N (passed)

Category:	CLARIFICATION, CHANGE

Edit history:	23 Dec 1992, Version 1 by Loosemore

		04 Feb 1993, Version 2 by Loosemore (comments from Barmar)

Status:		Proposal CLARIFY passed (6+3)-2 on letter ballot 93-302.



Problem description:


  The next-to-last paragraph on page 14-2 (in draft 12.24) says that

  functions that take list arguments should be prepared to signal an

  error if they receive dotted list arguments, except as explicitly

  stated otherwise.  But many of the descriptions of the functions in

  chapter 14 do not explicitly state otherwise, where they clearly ought

  to.  (In some cases, the "correct" behavior is implied by notes or

  examples, which are not binding parts of the standard.)  For example,

  surely the committee did not intend to make primitive accessors such

  as CAR and CDR fail on dotted lists!


  Similarly, there are exceptions missing for the rule stated in the

  last paragraph on page 14-2 (the consequences are undefined if

  a circular list is passed).  

  

  For the functions which operate on trees, there is a further problem.

  Some of the arguments are described as "objects", and others are

  described as "lists", which I think is incorrect -- an atomic tree

  argument should also be OK for functions such as SUBST and SUBLIS.

  The dotted-list prohibition should clearly not apply to the tree

  functions.  But since tree functions recursively descend both the 

  car and cdr chains of a cons, there should be a prohibition against

  circular tree structure in the arguments to these functions, not

  just circular list structure.


  Finally, there is confusion about whether atoms may be considered

  degenerate dotted lists in some contexts.



Proposal (DOTTED-LIST-ARGUMENTS:CLARIFY):


  (1) Add to page 14-2 a third paragraph:


      Except as explicitly stated otherwise, for any standardized

      function that is required to be a tree, the consequences are

      undefined if that tree is circular.


  (2) Clarify that association lists, property lists, and lists

      that are treated as sequences must be proper lists.


  (3) Change the glossary definitions of "dotted list" and "list" to

      clarify that atoms are not considered dotted lists.


  (4) Clarify the nature of list arguments to the functions in chapter

      14, as follows:



      CAR, CDR and friends:  the argument "x" is permitted to be dotted

        or circular.


        Rationale:  These are primitive accessors.



      COPY-TREE:  the argument "object" is a tree (not an object).

      SUBLIS, NSUBLIS: the "tree" argument is a tree (not a list).

      SUBST and friends: the "tree" argument is a tree (not a list).

      TREE-EQUAL:  the arguments "object1" and "object2" are trees

        (not objects).


        Rationale:  This makes all the tree functions consistent.



      COPY-LIST: the argument "list" may be dotted but not circular.


        Rationale:  This is what CLtL said.



      LIST-LENGTH: the argument "list" may be circular but not dotted.


        Rationale:  It's supposed to detect and return NIL for 

        circular lists.



      POP:  the "place" argument is permitted to evaluate to a dotted or

        circular list.

      PUSH:  the "place" argument may evaluate to any object (not just 

        a list).


        Rationale:  This follows from the equivalences given in the notes.



      FIRST and friends: the argument "list" may be dotted or circular.


        Rationale:  These functions are commonly implemented as chains

        of CAR and CDR operations.



      NTH: the argument "list" may be dotted or circular.  Note that

        the references to the length of the argument list in the

        description are incorrect, since this concept doesn't make

        sense for dotted lists.  The right thing to do is simply to 

        define (NTH n list) = (CAR (NTHCDR n list)).


        Rationale:  The notes for FIRST and friends say that

        (FIFTH x) == (NTH 4 x).  This also makes NTH and NTHCDR

        consistent.



      ENDP: the argument "list" may be dotted or circular.


        Rationale:  This function only cares whether the argument is

        NIL/a cons/something else.



      NCONC: the last "list" argument may be any object.  The remaining 

        "lists" may be dotted but not circular.


        Rationale:  This follows from the equivalence in the description

        (from issue REMF-DESTRUCTION-UNSPECIFIED).



      NRECONC: the argument "list1" must be a proper list.

        The argument "list2" can be any object (not just a list).

        (The example showing "list1" as a dotted list is incorrect.)


        Rationale:  This follows from the equivalence in the side effects

        section, which was added by issue REMF-DESTRUCTION-UNSPECIFIED.  

        (NREVERSE is a sequence function.)



      APPEND: the last "list" argument may be any object.

        The remaining "lists" must be proper lists.


        Rationale:  Allowing any object as the last argument came from

        CLtL.  The inconsistency of the remaining arguments compared to 

        NCONC was a deliberate decision by X3J13 (issues APPEND-DOTTED, etc).

        


      REVAPPEND: the argument "list1" must be a proper list.

        The argument "list2" can be any object (not just a list).

        (The example showing "list1" as a dotted list is incorrect.)


        Rationale:  This follows from the equivalence in the notes section.

        (REVERSE is a sequence function.)



      BUTLAST, NBUTLAST:  the argument "list" may be dotted but not 

        circular.   (The functions should complement LAST by counting 

        conses, not elements.)


        Rationale:  An obvious identity is

        (BUTLAST list n) == (LDIFF list (LAST list n))

        The intent of issue LAST-N was clearly to make LAST and BUTLAST

        complementary.



      LAST:  the argument "list" may be dotted but not circular.


        Rationale:  This follows from the definition in the notes section.



      LDIFF, TAILP: the "list" argument may be dotted.  The "sublist"

        argument may be any object (not just a list).  Both arguments may

        be circular lists only if (TAILP sub-list list) is true.


        Rationale:  This is already stated for TAILP and the two functions

        are clearly related.



      NTHCDR: the "list" argument may be dotted or circular.


        Rationale:  The examples show use on a dotted list, and the 

        function will clearly still terminate if passed a circular list.



      REST:  the "list" argument is permitted to be dotted or circular.


        Rationale:  compatibility with CDR and FIRST.



      MEMBER and friends:  the "list" argument must be a proper list.

      INTERSECTION, NINTERSECTION: the "list-1" and "list-2" arguments

        must be proper lists.

      ADJOIN:  the "list" argument must be a proper list.

      PUSHNEW:  the "place" argument must evaluate to a proper list.

      SET-DIFFERENCE, NSET-DIFFERENCE:  the "list-1" and "list-2" 

        arguments must be proper lists.

      SET-EXCLUSIVE-OR, NSET-EXCLUSIVE-OR:  the "list-1" and "list-2" 

        arguments must be proper lists.

      SUBSETP:  the "list1" and "list2" arguments must be proper lists.

      UNION, NUNION:  the "list1" and "list2" arguments must be proper lists.


        Rationale:  This makes all the functions that operate on lists as

        sets consistent.  



      MAPC and friends:  the "list" arguments must be proper lists.


        Rationale:  The description makes clear that the lists are treated

        as sequences.

      


Current practice:


  Loosemore thinks the only item that is likely to cause compatibility

  problems is explicitly requiring BUTLAST to work on dotted lists:

  currently at least CMU CL and AKCL signal an error, but it works

  in Lucid.



Cost to implementors:


  This proposal should probably make it easier for implementors to do

  the right thing.  Given the previous addition of the requirement that

  implementations "should be prepared to signal" errors about dotted lists

  and tighter restrictions about signalling TYPE-ERRORs for incorrect

  arguments, all implementors probably need to reexamine the definitions

  of these functions for conformance anyway.



Cost to users:


  There may be a few currently working programs that will stop working.



Aesthetics:


  This whole problem is messy to deal with.



Editorial impact:


  Substantial, but it needs to be done to correct obvious errors.



Discussion:


  Loosemore notes that there are a few more functions which could 

  reasonably be defined to work on atoms as degenerate dotted lists

  (notably, TAILP and LDIFF) but that current practice is to signal

  an error, so the proposal does not include these.