Issue: TAILP-NIL (version 3)

[vanroggen%aitg.DEC@decwrl.dec.com]

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
                18-Oct-88, version 3 by van Roggen (just one proposal)
 
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: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.  VAX LISP implements
  TAILP-NIL:NIL.
 
Cost to Implementors:
 
  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:
 
  Avoids unnecessary incompatibilities between implementations.
 
Discussion:
 
  This issue was first raised in ">GLS>clarifications.text" of 12/06/85.
  It recommended TAILP-NIL:NIL.