[XANALYS][Common Lisp HyperSpec (TM)] [Previous][Up][Next]

Issue TAILP-NIL Writeup

Issue:        TAILP-NIL

References: TAILP (p275)


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)

01-Dec-88, version 4 by Pitman (minor edits per discussion)

9-Dec-88, Version 5 by Masinter (clarify EQL)

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 implementations of this definition might be:

(defun tailp (sublist list) ;Definition "A"

(do ((list list (cdr list)))

((endp list) nil)

(if (eql sublist list)

(return t))))

(defun tailp (sublist list) ;Definition "B"

(do ((list list (cdr list)))

((atom list) (eql list sublist))

(if (eql 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".

Also at issue is the question of whether dotted lists are permissible

second arguments.

Proposal (TAILP-NIL:T):

Strike any text in the definition of TAILP which suggests that a

sublist must be a cons.

Clarify that (TAILP sublist list) returns true iff (NTHCDR n list) is

sublist for some value of n, and false otherwise.

Note, however, that since the list may be dotted, so the end test

used by TAILP must be ATOM, not ENDP. That is, if (TAILP x l)

returns true, it means there was n such that (NTHCDR n list) would

return x; however, it doesn't follow that if TAILP returns false,

it is safe to go blithely NTHCDR's into the list looking for it,

since the list might be dotted and NTHCDR might hit bad data.

Note that TAILP uses EQL or equivalent to compare

sublist to list in the case where sublist is a number, etc.


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.

Some reasons for preferring an ATOM check to ENDP include:

- The name TAILP suggests tails, not sublists. Some users might

expect this distinction to mean that data more general than

proper sublists.

- Making TAILP require lists limits its usefulness. If we did

not make this choice, some users would end up having to write

their own extended TAILP which we could just as well have

provided compatibly.

- TAILP is not considered to be used frequently enough in code

that the minor loss in speed to an ATOM check is worth the

lost functionality. Indeed, expanding the scope of its

capabilities may lead to more uses for TAILP.

- Other operators (eg, APPEND) have recently been extended to

treat dotted lists in an interesting way because users have

expressed a desire for this. As such, this change is

culturally consistent.

- Some implementations already support this feature, and the

wording in CLtL is sufficiently ambiguous that some users

might think it appropriate to depend on the feature. In the

absence of compelling efficiency reasons to the contrary,

we should lean toward extending some implementations rather

than tightening others in our efforts to achieve cross-dialect



#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 T under this proposal.

#4: (TAILP 3 '(A B C))

returns NIL under this proposal.

#5: (TAILP 3 '(A B C . 3))

returns T under this proposal.

#6: (TAILP '(X Y) '(A B C . 3))

returns NIL under this proposal.

Current Practice:

Symbolics Genera is consistent with TAILP-NIL:T.

Neither Lucid nor VAX LISP currently implements TAILP-NIL:T.

VAX LISP effectively implements definition "A" from the

Problem Description above.

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.


Avoids unnecessary incompatibilities between implementations.


Slows down TAILP slightly in some implementations because ENDP is

potentially faster than ATOM.


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

It recommended an earlier proposal, TAILP-NIL:NIL, which is effectively

equivalent to Definition "A" from the Problem Description.

Pitman introduced TAILP-NIL:T as an alternative, arguing that the

definition TAILP-NIL:NIL offered no practical value to programmers

in the disputed situations, while TAILP-NIL:T was of arguable usefulness.

Pitman and van Roggen support TAILP-NIL:T.

It was suggested more than once by more than one cleanup

committee member that we remove TAILP from the language

"since almost nobody uses it".

[Starting Points][Contents][Index][Symbols][Glossary][Issues]
Copyright 1996-2001, Xanalys Inc. All rights reserved.