Issue: TAILP-NIL (Version 2)

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

I just can't buy into this. I think it's a big mistake to require a
sublist to be a CONS. It teaches people to confuse the notion of CONS
with the notion of LIST. The latter may include NIL. I have added
another option which I can support.

-----
Issue:		TAILP-NIL
References:	TAILP (p275)
Category:	CLARIFICATION/CHANGE
Edit History:	13-Sep-88, version 1 by Walter van Roggen,
		13-Sep-88, version 2 by Pitman

Problem Description:

  CLtL (p275) specifies TAILP as:

    TAILP sublist list				[Function]

    This predicate is true if SUBLIST is a sublist of LIST (i.e.,
    one of the conses that makes up LIST); otherwise, it is false.
    Another way to look at this is that TAILP is true if
    (NTHCDR n list) is SUBLIST, for some value of N. See LDIFF.

  Two common implementations of this definition are:

   (defun tailp (sublist list)			;Definition "A"
     (do ((list list (cdr list)))
	 ((endp list) nil)
       (if (eq sublist list)
	   (return t))))

   (defun tailp (sublist list)			;Definition "B"
     (do ((list list (cdr list)))
	 ((atom list) (eq list sublist))
       (if (eq sublist list)
	   (return t))))

  They differ only in their treatment of the atomic case.

  At issue is the fact that () is a list, and hence some would
  argue that it is a sublist of all other lists. On the other hand,
  the definition of TAILP seems to imply that being a cons is a
  necessary precondition of being a "sublist".

Proposal (TAILP-NIL:NIL):

  Clarify that the sublist argument to TAILP must be a list
  and that (TAILP NIL X) returns NIL for all lists X.

  Qualify the description in CLtL by saying that (TAILP sublist list)
  is true if SUBLIST is a cons and (NTHCDR n list) is SUBLIST for
  some value of N, and is false otherwise.

  Rationale:

   This is the status quo in a number of implementations.

Proposal (TAILP-NIL:T):

  Strike any text in the definition of TAILP which suggests that a
  sublist must be a cons.

  Clarify that (TAILP any-atom list) returns T iff (NTHCDR n list) is
  SUBLIST for some value of N, and false otherwise.

  Rationale:

   This is more consistent with the definition of LDIFF, which
   gives a useful meaning to arbitrary atomic SUBLIST arguments.

   This gives a more elegant definition of SUBLIST, allowing it to
   refer to any list -- including the empty list -- which is a
   part of another list.

Test Cases:

 #1: (LET ((X '(B C))) (TAILP X (CONS 'A X)))
     should return T in all implementations.

 #2: (TAILP '(X Y) '(A B C))
     should return NIL in all implementations.

 #3: (TAILP '() '(A B C))
     returns NIL under proposal TAILP-NIL:NIL
     returns T   under proposal TAILP-NIL:T

 #4: (TAILP 3 '(A B C))
     is an error under proposal TAILP-NIL:NIL
     returns NIL under proposal TAILP-NIL:T

 #5: (TAILP 3 '(A B C . 3))
     is an error under proposal TAILP-NIL:NIL
     returns T under proposal TAILP-NIL:T

 #6: (TAILP '(X Y) '(A B C . 3))
     is an error under proposal TAILP-NIL:NIL
     returns NIL under proposal TAILP-NIL:T

Current Practice:

  Symbolics Genera is consistent with TAILP-NIL:T.

  [Walter alleges TAILP-NIL:NIL is what all implementations already
   do, but since Genera is not in conformance, KMP regards that
   hypothesis as suspect. We need real data points, folks.]

Cost to Implementors:

  An implementation of TAILP-NIL:NIL is given as Definition "A" in the
  problem description.

  An implementation of TAILP-NIL:T is given as Definition "B" in the
  problem description.

  Some implementations might have compiler optimizers for these definitions
  as well, so a slight amount of additional effort might be required.

Cost to Users:

  Given that current practice varies widely on the disputed case,
  this is unlikely to have a practical effect on existing portable code.

Benefits:

  Either description makes the language more precise.

  [Pitman believes that] TAILP-NIL:T is more consistent with the behavior
  of TAILP and more consistent with what he thinks should be the 
  definition of a sublist.

Discussion:

  This issue was first raised in ">GLS>clarifications.text" of 12/06/85.

  Pitman supports TAILP-NIL:T.