193 lines
14 KiB
HTML
193 lines
14 KiB
HTML
<!-- Common Lisp HyperSpec (TM), version 7.0 generated by Kent M. Pitman on Mon, 11-Apr-2005 2:31am EDT -->
|
|
<HTML>
|
|
<HEAD>
|
|
<TITLE>CLHS: Issue TAILP-NIL Writeup</TITLE>
|
|
<LINK HREF="../Data/clhs.css" REL="stylesheet" TYPE="text/css" />
|
|
<META HTTP-EQUIV="Author" CONTENT="Kent M. Pitman">
|
|
<META HTTP-EQUIV="Organization" CONTENT="LispWorks Ltd.">
|
|
<LINK REL=TOP HREF="../Front/index.htm">
|
|
<LINK REL=COPYRIGHT HREF="../Front/Help.htm#Legal">
|
|
<LINK REL=DISCLAIMER HREF="../Front/Help.htm#Disclaimer">
|
|
<LINK REL=PREV HREF="../Issues/iss343_w.htm">
|
|
<LINK REL=UP HREF="../Issues/iss344.htm">
|
|
<LINK REL=NEXT HREF="../Issues/iss345_w.htm">
|
|
</HEAD>
|
|
<BODY>
|
|
<H1><A REV=MADE HREF="http://www.lispworks.com/"><IMG WIDTH=80 HEIGHT=65 ALT="[LISPWORKS]" SRC="../Graphics/LWSmall.gif" ALIGN=Bottom></A><A REL=TOP HREF="../Front/index.htm"><IMG WIDTH=237 HEIGHT=65 ALT="[Common Lisp HyperSpec (TM)]" SRC="../Graphics/CLHS_Sm.gif" ALIGN=Bottom></A> <A REL=PREV HREF="../Issues/iss343_w.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Previous]" SRC="../Graphics/Prev.gif" ALIGN=Bottom></A><A REL=UP HREF="../Issues/iss344.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Up]" SRC="../Graphics/Up.gif" ALIGN=Bottom></A><A REL=NEXT HREF="../Issues/iss345_w.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Next]" SRC="../Graphics/Next.gif" ALIGN=Bottom></A></H1>
|
|
|
|
<HR>
|
|
|
|
|
|
|
|
<H2>Issue TAILP-NIL Writeup</H2>
|
|
|
|
<PRE><B>Issue:</B> <A HREF="iss344.htm">TAILP-NIL</A><P>
|
|
<B>References:</B> <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> (p275)<P>
|
|
<B>Category:</B> CLARIFICATION/CHANGE<P>
|
|
<B>Edit History:</B> 13-Sep-88, version 1 by Walter van Roggen,<P>
|
|
13-Sep-88, version 2 by Pitman<P>
|
|
18-Oct-88, version 3 by van Roggen (just one proposal)<P>
|
|
01-Dec-88, version 4 by Pitman (minor edits per discussion)<P>
|
|
9-Dec-88, Version 5 by Masinter (clarify <A REL=DEFINITION HREF="../Body/a_eql.htm#eql"><B>EQL</B></A>)<P>
|
|
<P>
|
|
<B>Problem Description:<P>
|
|
</B> <P>
|
|
CLtL (p275) specifies <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> as:<P>
|
|
<P>
|
|
<A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> sublist list [Function]<P>
|
|
<P>
|
|
This predicate is true if SUBLIST is a sublist of <A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>LIST</B></A> (i.e.,<P>
|
|
one of the conses that makes up <A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>LIST</B></A>); otherwise, it is false.<P>
|
|
Another way to look at this is that <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> is true if<P>
|
|
(<A REL=DEFINITION HREF="../Body/f_nthcdr.htm#nthcdr"><B>NTHCDR</B></A> n list) is SUBLIST, for some value of N. See <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#ldiff"><B>LDIFF</B></A>.<P>
|
|
<P>
|
|
Two implementations of this definition might be:<P>
|
|
<P>
|
|
(<A REL=DEFINITION HREF="../Body/m_defun.htm#defun"><B>defun</B></A> <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>tailp</B></A> (sublist <A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A>) ;Definition "A"<P>
|
|
(<A REL=DEFINITION HREF="../Body/m_do_do.htm#do"><B>do</B></A> ((<A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A> <A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A> (<A REL=DEFINITION HREF="../Body/f_car_c.htm#cdr"><B>cdr</B></A> <A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A>)))<P>
|
|
((<A REL=DEFINITION HREF="../Body/f_endp.htm#endp"><B>endp</B></A> <A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A>) <A REL=DEFINITION HREF="../Body/a_nil.htm#nil"><B>nil</B></A>)<P>
|
|
(<A REL=DEFINITION HREF="../Body/s_if.htm#if"><B>if</B></A> (<A REL=DEFINITION HREF="../Body/a_eql.htm#eql"><B>eql</B></A> sublist <A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A>)<P>
|
|
(<A REL=DEFINITION HREF="../Body/m_return.htm#return"><B>return</B></A> t))))<P>
|
|
<P>
|
|
(<A REL=DEFINITION HREF="../Body/m_defun.htm#defun"><B>defun</B></A> <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>tailp</B></A> (sublist <A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A>) ;Definition "B"<P>
|
|
(<A REL=DEFINITION HREF="../Body/m_do_do.htm#do"><B>do</B></A> ((<A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A> <A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A> (<A REL=DEFINITION HREF="../Body/f_car_c.htm#cdr"><B>cdr</B></A> <A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A>)))<P>
|
|
((<A REL=DEFINITION HREF="../Body/a_atom.htm#atom"><B>atom</B></A> <A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A>) (<A REL=DEFINITION HREF="../Body/a_eql.htm#eql"><B>eql</B></A> <A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A> sublist))<P>
|
|
(<A REL=DEFINITION HREF="../Body/s_if.htm#if"><B>if</B></A> (<A REL=DEFINITION HREF="../Body/a_eql.htm#eql"><B>eql</B></A> sublist <A REL=DEFINITION HREF="../Body/a_list.htm#list"><B>list</B></A>)<P>
|
|
(<A REL=DEFINITION HREF="../Body/m_return.htm#return"><B>return</B></A> t))))<P>
|
|
<P>
|
|
They differ only in their treatment of the atomic case.<P>
|
|
<P>
|
|
At issue is the fact that () is a list, and hence some would<P>
|
|
argue that it is a sublist of all other lists. On the other hand,<P>
|
|
the definition of <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> seems to imply that being a cons is a<P>
|
|
necessary precondition of being a "sublist".<P>
|
|
<P>
|
|
Also at issue is the question of whether dotted lists are permissible<P>
|
|
second arguments.<P>
|
|
<P>
|
|
<B>Proposal (TAILP-NIL:T):<P>
|
|
</B> <P>
|
|
Strike any text in the definition of <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> which suggests that a<P>
|
|
sublist must be a cons.<P>
|
|
<P>
|
|
Clarify that (<A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> sublist list) returns true iff (<A REL=DEFINITION HREF="../Body/f_nthcdr.htm#nthcdr"><B>NTHCDR</B></A> n list) is<P>
|
|
sublist for some value of n, and false otherwise.<P>
|
|
<P>
|
|
Note, however, that since the list may be dotted, so the end test<P>
|
|
used by <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> must be <A REL=DEFINITION HREF="../Body/a_atom.htm#atom"><B>ATOM</B></A>, not <A REL=DEFINITION HREF="../Body/f_endp.htm#endp"><B>ENDP</B></A>. That is, if (<A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> x l)<P>
|
|
returns true, it means there was n such that (<A REL=DEFINITION HREF="../Body/f_nthcdr.htm#nthcdr"><B>NTHCDR</B></A> n list) would<P>
|
|
return x; however, it doesn't follow that if <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> returns false,<P>
|
|
it is safe to go blithely <A REL=DEFINITION HREF="../Body/f_nthcdr.htm#nthcdr"><B>NTHCDR</B></A>'s into the list looking for it, <P>
|
|
since the list might be dotted and <A REL=DEFINITION HREF="../Body/f_nthcdr.htm#nthcdr"><B>NTHCDR</B></A> might hit bad data.<P>
|
|
<P>
|
|
Note that <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> uses <A REL=DEFINITION HREF="../Body/a_eql.htm#eql"><B>EQL</B></A> or equivalent to compare<P>
|
|
sublist to list in the case where sublist is a number, etc.<P>
|
|
<P>
|
|
<B>Rationale:<P>
|
|
</B> <P>
|
|
This is more consistent with the definition of <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#ldiff"><B>LDIFF</B></A>, which<P>
|
|
gives a useful meaning to arbitrary atomic SUBLIST arguments.<P>
|
|
<P>
|
|
This gives a more elegant definition of SUBLIST, allowing it to<P>
|
|
refer to any list -- including the empty list -- which is a<P>
|
|
part of another list.<P>
|
|
<P>
|
|
Some reasons for preferring an <A REL=DEFINITION HREF="../Body/a_atom.htm#atom"><B>ATOM</B></A> check to <A REL=DEFINITION HREF="../Body/f_endp.htm#endp"><B>ENDP</B></A> include:<P>
|
|
- The name <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> suggests tails, not sublists. Some users might<P>
|
|
expect this distinction to mean that data more general than<P>
|
|
proper sublists.<P>
|
|
- Making <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> <A REL=DEFINITION HREF="../Body/f_provid.htm#require"><B>require</B></A> lists limits its usefulness. If we did<P>
|
|
not make this choice, some users would end up having to write<P>
|
|
their own extended <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> which we could just as well have<P>
|
|
provided compatibly.<P>
|
|
- <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> is not considered to be used frequently enough in code<P>
|
|
that the minor loss in speed to an <A REL=DEFINITION HREF="../Body/a_atom.htm#atom"><B>ATOM</B></A> check is worth the<P>
|
|
lost functionality. Indeed, expanding the scope of its <P>
|
|
capabilities may lead to more uses for <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A>.<P>
|
|
- Other operators (eg, <A REL=DEFINITION HREF="../Body/f_append.htm#append"><B>APPEND</B></A>) have recently been extended to<P>
|
|
treat dotted lists in an interesting way because users have<P>
|
|
expressed a desire for this. As such, this change is <P>
|
|
culturally consistent.<P>
|
|
- Some implementations already support this feature, and the <P>
|
|
wording in CLtL is sufficiently ambiguous that some users<P>
|
|
might think it appropriate to depend on the feature. In the<P>
|
|
absence of compelling efficiency reasons to the contrary,<P>
|
|
we should lean toward extending some implementations rather<P>
|
|
than tightening others in our efforts to achieve cross-dialect<P>
|
|
consistency.<P>
|
|
<P>
|
|
<B>Examples:<P>
|
|
</B> <P>
|
|
#1: (<A REL=DEFINITION HREF="../Body/s_let_l.htm#let"><B>LET</B></A> ((X '(B C))) (<A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> X (<A REL=DEFINITION HREF="../Body/a_cons.htm#cons"><B>CONS</B></A> 'A X)))<P>
|
|
should return T in all implementations.<P>
|
|
<P>
|
|
#2: (<A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> '(X Y) '(A B C))<P>
|
|
should return <A REL=DEFINITION HREF="../Body/a_nil.htm#nil"><B>NIL</B></A> in all implementations.<P>
|
|
<P>
|
|
#3: (<A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> '() '(A B C))<P>
|
|
returns T under this proposal.<P>
|
|
<P>
|
|
#4: (<A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> 3 '(A B C))<P>
|
|
returns <A REL=DEFINITION HREF="../Body/a_nil.htm#nil"><B>NIL</B></A> under this proposal.<P>
|
|
<P>
|
|
#5: (<A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> 3 '(A B C . 3))<P>
|
|
returns T under this proposal.<P>
|
|
<P>
|
|
#6: (<A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> '(X Y) '(A B C . 3))<P>
|
|
returns <A REL=DEFINITION HREF="../Body/a_nil.htm#nil"><B>NIL</B></A> under this proposal.<P>
|
|
<P>
|
|
<B>Current Practice:<P>
|
|
</B> <P>
|
|
Symbolics Genera is consistent with <A HREF="iss344.htm">TAILP-NIL:T</A>.<P>
|
|
<P>
|
|
Neither Lucid nor VAX LISP currently implements <A HREF="iss344.htm">TAILP-NIL:T</A>.<P>
|
|
<P>
|
|
VAX LISP effectively implements definition "A" from the <P>
|
|
Problem Description above.<P>
|
|
<P>
|
|
<B>Cost to Implementors:<P>
|
|
</B> <P>
|
|
An implementation of <A HREF="iss344.htm">TAILP-NIL:T</A> is given as Definition "B" in the<P>
|
|
problem description.<P>
|
|
<P>
|
|
Some implementations might have compiler optimizers for these definitions<P>
|
|
as well, so a slight amount of additional effort might be required.<P>
|
|
<P>
|
|
<B>Cost to Users:<P>
|
|
</B> <P>
|
|
Given that current practice varies widely on the disputed case,<P>
|
|
this is unlikely to have a practical effect on existing portable code.<P>
|
|
<P>
|
|
<B>Benefits:<P>
|
|
</B> <P>
|
|
Avoids unnecessary incompatibilities between implementations.<P>
|
|
<P>
|
|
<B>Non-Benefits:<P>
|
|
</B><P>
|
|
Slows down <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> slightly in some implementations because <A REL=DEFINITION HREF="../Body/f_endp.htm#endp"><B>ENDP</B></A> is<P>
|
|
potentially faster than <A REL=DEFINITION HREF="../Body/a_atom.htm#atom"><B>ATOM</B></A>.<P>
|
|
<P>
|
|
<B>Discussion:<P>
|
|
</B> <P>
|
|
This issue was first raised in ">GLS>clarifications.text" of 12/06/85.<P>
|
|
It recommended an earlier proposal, TAILP-NIL:NIL, which is effectively<P>
|
|
equivalent to Definition "A" from the Problem Description.<P>
|
|
<P>
|
|
Pitman introduced <A HREF="iss344.htm">TAILP-NIL:T</A> as an alternative, arguing that the<P>
|
|
definition TAILP-NIL:NIL offered no practical value to programmers<P>
|
|
in the disputed situations, while <A HREF="iss344.htm">TAILP-NIL:T</A> was of arguable usefulness.<P>
|
|
<P>
|
|
Pitman and van Roggen support <A HREF="iss344.htm">TAILP-NIL:T</A>.<P>
|
|
<P>
|
|
It was suggested more than once by more than one cleanup <P>
|
|
committee member that we remove <A REL=DEFINITION HREF="../Body/f_ldiffc.htm#tailp"><B>TAILP</B></A> from the language<P>
|
|
"since almost nobody uses it". <P>
|
|
<P>
|
|
</PRE>
|
|
<HR>
|
|
|
|
<A REL=NAVIGATOR HREF="../Front/StartPts.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Starting Points]" SRC="../Graphics/StartPts.gif" ALIGN=Bottom></A><A REL=TOC HREF="../Front/Contents.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Contents]" SRC="../Graphics/Contents.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Master.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Index]" SRC="../Graphics/Index.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Symbol.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Symbols]" SRC="../Graphics/Symbols.gif" ALIGN=Bottom></A><A REL=GLOSSARY HREF="../Body/26_a.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Glossary]" SRC="../Graphics/Glossary.gif" ALIGN=Bottom></A><A HREF="../Front/X3J13Iss.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Issues]" SRC="../Graphics/Issues.gif" ALIGN=Bottom></A><BR>
|
|
|
|
<A REL=COPYRIGHT HREF="../Front/Help.htm#Legal"><I>Copyright 1996-2005, LispWorks Ltd. All rights reserved.</I></A><P>
|
|
</BODY>
|
|
</HTML>
|