Issue: TAILP-NIL (Version 2)

• To: CL-Cleanup@SAIL.Stanford.EDU
• Subject: Issue: TAILP-NIL (Version 2)
• From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>
• Date: Tue, 13 Sep 88 18:40 EDT

```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.

```