Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

(endp lst) or (null lst)

632 views
Skip to first unread message

Chris Gehlker

unread,
Jan 3, 2003, 11:37:29 PM1/3/03
to
Comes Stephen Slade to say that the canonical way to test for the end of
proper list lst is (endp lst) rather than (null lst). The HyperSpec seems to
agree. And yet I have the impression that almost no one uses endp.

To me, endp seems to express intent *slightly* better than null when setting
delineating the stop condition for a recursion. What do you all think?

-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----

Kenny Tilton

unread,
Jan 4, 2003, 1:02:44 AM1/4/03
to

Chris Gehlker wrote:
> Comes Stephen Slade to say that the canonical way to test for the end of
> proper list lst is (endp lst) rather than (null lst). The HyperSpec seems to
> agree. And yet I have the impression that almost no one uses endp.
>
> To me, endp seems to express intent *slightly* better than null when setting
> delineating the stop condition for a recursion. What do you all think?

I do not like feel-good aliases for car, cdr, null, etc. I think a Lisp
progreammer needs to be fluent in thinking about cons cells, and
syntactic sugar like first, rest, and (something I never heard of in six
years of Lisping) endp.

--

kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Cells let us walk, talk, think, make love and realize
the bath water is cold." -- Lorraine Lee Cudmore

Gabe Garza

unread,
Jan 4, 2003, 2:25:30 AM1/4/03
to
Kenny Tilton <kti...@nyc.rr.com> writes:

> I do not like feel-good aliases for car, cdr, null, etc. I think a
> Lisp progreammer needs to be fluent in thinking about cons cells, and
> syntactic sugar like first, rest, and (something I never heard of in
> six years of Lisping) endp.

Do you similiarly avoid NOT?

I'd argue that one of the things that makes Common Lisp good is the
presence functions like ENDP, NOT, and NULL. It not only provides
powerful and elegant basic representations (e.g., the many faces of
NIL, s-expressions, etc.) it also provides the tools to build clean
abstractions on top of them--it gives power, and expects the
programmer to respect it by providing clean abstractions that use it.

Personally, if I see NOT, I think "testing for true or false" not
"testing for a list with zero items". Similarly, if I see

(let ((foo '()))
...)

I think "FOO is going to be a list in the body of the let," whereas if
it were bound NIL, I'd probably think it was being used as a boolean
and if it wasn't explicitly bound at all I'd think it would be set to
an object somewhere in the body of the LET. It's not hard finding
other examples where thin layer of syntactic sugar glazes a trivial
expression using a more primitive construct.

I'll admit I don't touch FIRST and REST. Maybe having to type the two
extra characters is enough to push me into a life of hypocrisy. ;)

Gabe Garza

Alain Picard

unread,
Jan 4, 2003, 2:47:26 AM1/4/03
to
Kenny Tilton <kti...@nyc.rr.com> writes:

> I do not like feel-good aliases for car, cdr, null, etc. I think a
> Lisp progreammer needs to be fluent in thinking about cons cells, and
> syntactic sugar like first, rest, and (something I never heard of in
> six years of Lisping) endp.

I personally like FIRST, REST, and ENDP, and do not think of them as
syntactic sugar. I think of them as expressing intent;
(car foo) ; The foo is probably something returned from an a-list
; or some structure built on cons cells

(first foo) ; foo is a list.

Similarly for CDR, and ENDP.

Erik Naggum

unread,
Jan 4, 2003, 4:45:17 AM1/4/03
to
* Chris Gehlker <geh...@fastq.com>

| Comes Stephen Slade to say that the canonical way to test for the
| end of proper list lst is (endp lst) rather than (null lst). The
| HyperSpec seems to agree. And yet I have the impression that
| almost no one uses endp.

Almost nobody uses dotted lists to begin with, so why should they
think of using `endp´?

Give a function that traverses a list naïvely and tests with `null´
a dotted lists and it will most probably stumble on the `cdr´ that
gets a non-cons argument at the end of the list. In all likelihood
the program will enter the debugger or terminate ungracefully.

A much more robust way is not to test for the end of the list at
all, but to test for a cons cell that would require more traversal.

Take the infinitely silly Scheme-like example of computing `length´
with a maximum of gratuitous overhead:

(defun length (list)
(if (cons list)
(1+ (length (cdr list)))
0))

compared to the seemingly very similar:

(defun length (list)
(if (null list)
0
(1+ (length (cdr list)))))

The cdr chain of a proper list is certainly terminated by an atom
that is `nil´, but unless you explicitly attach significance to the
specific atom that is the cdr of the last cons, should you care so
much as to signal an error if it is not the canonical `nil´ or are
you no worse off if you simply ignore it? It is sloppy to pass
anything non-`nil´ to `cdr´; careful programming demands that you
know that you pass `cdr´ a cons cell.

--
Erik Naggum, Oslo, Norway

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.

Tim Bradshaw

unread,
Jan 4, 2003, 5:34:27 AM1/4/03
to
* Kenny Tilton wrote:

> I do not like feel-good aliases for car, cdr, null, etc. I think a
> Lisp progreammer needs to be fluent in thinking about cons cells, and
> syntactic sugar like first, rest, and (something I never heard of in
> six years of Lisping) endp.


I do not like feel-good languages like assembler, fortran, C etc. I
think a progreammer needs to be fluent in thinking about bits and
toggling in hex, and syntactic sugar like, assembler, fortran, and
(something I never heard of in six years of toggling in hex) lisp.

--tim

Oleg

unread,
Jan 4, 2003, 7:25:28 AM1/4/03
to
Tim Bradshaw wrote:

I do not like the feel-good aliases that a hex editor provides. I think a
real programmer needs to be fluent in thinking about bits and should write
his code as ones and zeros.

Oleg

Chris Gehlker

unread,
Jan 4, 2003, 8:16:51 AM1/4/03
to
On 1/3/03 11:02 PM, in article 3E167A3F...@nyc.rr.com, "Kenny Tilton"
<kti...@nyc.rr.com> wrote:

>
>
> Chris Gehlker wrote:
>> Comes Stephen Slade to say that the canonical way to test for the end of
>> proper list lst is (endp lst) rather than (null lst). The HyperSpec seems to
>> agree. And yet I have the impression that almost no one uses endp.
>>
>> To me, endp seems to express intent *slightly* better than null when setting
>> delineating the stop condition for a recursion. What do you all think?
>
> I do not like feel-good aliases for car, cdr, null, etc. I think a Lisp
> progreammer needs to be fluent in thinking about cons cells, and
> syntactic sugar like first, rest, and (something I never heard of in six
> years of Lisping) endp.

Hmmm... Someone in a different thread said that he uses first, rest, null
and friends, when dealing with simple one level proper lists and car, cdr,
not etc. when dealing with trees. This made a lot of sense to me because it
abstracts away the details of how a simple list is put together when they
don't matter while exposing them in the case of trees where they might.

From this point of view, 'null' is already syntactic sugar.

But if endp is so obscure that you never heard of it, that is a pretty good
argument for avoiding it even if it is 'sweet'.

Steven M. Haflich

unread,
Jan 4, 2003, 10:27:50 AM1/4/03
to
Chris Gehlker wrote:
> Comes Stephen Slade to say that the canonical way to test for the end of
> proper list lst is (endp lst) rather than (null lst). The HyperSpec seems to
> agree. And yet I have the impression that almost no one uses endp.
>
> To me, endp seems to express intent *slightly* better than null when setting
> delineating the stop condition for a recursion. What do you all think?

[I'm purposely ignoring the postings that have already appeared
on this thread because they have, as usual, immediately strayed
from the subject and are just now about to descend into
personal insults.]

IMO, ENDP is a language feature like many others with a
confused specification. That specification points in two
different directions regarding its intended manner of use,
and so it is no surprise that many programmers don't use it.

Let's review the semantics of NULL and ENDP.

NULL is defined over all lisp objects, returning T for NIL
and NIL for anything else.

ENDP is defined to return _true_ for NIL, _false_ for a
CONS or NIL, and is undefined for any ATOM other than NIL.
However, in _safe_ code ENDP must signal TYPE-ERROR if
given

I'll ignore the slight difference in specification of the
returned value (generalized boolean vs. T/NIL) as being
unimportant in typical usage. The significant difference,
then, is only the behavior on a non-NIL atom.

The confusion is that one can interpret the difference in
specification of these two functions in two different
directions. ENDP _might_ in principle be a more efficient
function in optimized code some implementations because
a code generator could exploit the unspecified behavior for
certain arguments to generate faster code. (However, it is
objectively unlikely that this freedom could be exploited
usefully in modern implementations.) But on the other hand,
in _safe_ code ENDP seems intended to aid debugging; it
guarantees earlier detection of an unintended dotted list,
that is, immediately at the iteration step of a loop rather
than later when the dotted cell is used.

It is -- I hope most would agree -- a really bad idea to
write code that _depends_ on the TYPE-ERROR being signalled
because implementations have historically been sloppy about
signalling conditions of the required class, and because it
can be hard to guarantee the conditions under which code is
compiled, and mostly because the non-local organization of
such code needless makes it harder to read and understand.
So I would lean to the intention of ENDP facilitating
debugging, and this might be a good reason for using it.

In current ACL, for example, ENDP _always_ does the extra
testing required in _safe_ code, and is therefore a less
efficient function than NOT. (We could `fix' this with a
compiler macro, but apparently ENDP is so little used in
speed-critical code that it has never been an issue.) The
implementation appears to think that the error-detection
behavior of ENDP is important to its intended use, and
therefore preserves it even at high SPEED. I haven't
checked other implementations.

The problem with the ANS specification is that it provides no
guidance whether ENDP is intended primarily as a _faster_
alternative to NOT, or as a _slower_ but _more_ _debuggable_
alternative to NOT. Until one decides the intended usage,
once cannot decide which function is better to use.

No doubt one could argue that since this fine point was
apparently not established definitively by programming practice
at the time the ANS was drafted, is best left to marketplace
competition. Perhaps so, but leaving things up to the
marketplace is the same as leaving them unspecified.

Chris Gehlker

unread,
Jan 4, 2003, 11:15:09 AM1/4/03
to
On 1/4/03 2:45 AM, in article 32506623...@naggum.no, "Erik Naggum"
<er...@naggum.no> wrote:

Either I'm very confused or the examples are in the wrong order (or both).
It seems more efficient to to simply test with consp and avoid examining the
terminal cons.

Kenny Tilton

unread,
Jan 4, 2003, 11:14:37 AM1/4/03
to

Gabe Garza wrote:
> Kenny Tilton <kti...@nyc.rr.com> writes:
>
>
>>I do not like feel-good aliases for car, cdr, null, etc. I think a
>>Lisp progreammer needs to be fluent in thinking about cons cells, and
>>syntactic sugar like first, rest, and (something I never heard of in
>>six years of Lisping) endp.
>
>
> Do you similiarly avoid NOT?

It has always given me the willies, but I now think it makes code more
readable when one is testing a boolean.

Chris Gehlker

unread,
Jan 4, 2003, 11:20:34 AM1/4/03
to
On 1/4/03 8:27 AM, in article 3E16FD70...@alum.mit.edu, "Steven M.
Haflich" <smh_no_s...@alum.mit.edu> wrote:

> In current ACL, for example, ENDP _always_ does the extra
> testing required in _safe_ code, and is therefore a less
> efficient function than NOT. (We could `fix' this with a
> compiler macro, but apparently ENDP is so little used in
> speed-critical code that it has never been an issue.) The
> implementation appears to think that the error-detection
> behavior of ENDP is important to its intended use, and
> therefore preserves it even at high SPEED. I haven't
> checked other implementations.

I checked MCL, openMCL and Clisp. They behaved like ACL. So it seems that
several vendors do agree that the point of endp is to validate that one does
have a proper list.

Very good post, Steven. It clarified the difference for me.

Erik Naggum

unread,
Jan 4, 2003, 7:50:42 PM1/4/03
to
* Oleg <oleg_i...@myrealbox.com>

| I do not like the feel-good aliases that a hex editor provides. I
| think a real programmer needs to be fluent in thinking about bits
| and should write his code as ones and zeros.

I have been trying to understand your puzzling messages of late, but
I find myself stumped. On the one hand, you appear to be an ESL
speaker with zero appreciation for anything but the most concrete,
plain meaning of the words, no ability to detect humor, no ability
to understand any relationships or contrasts that are intended to
impart something other than their most obvious meaning, generally no
appreciation for the English language and human communication.

And then you produce the above.

Considering your track record as a humorless twit with no ability to
read deeper meaning into your own or anyone else's words, and who
has even attacked people viciously and rudely because /you/ fail to
grasp their message, I believe the most likely reading of the above
paragraph from you is that you mean it literally, but this marks you
as a stunningly stupid person, in my view disgustingly retarded.
Now, such an interpretation usually gives rise to the interpretation
that it is /not/ meant literally, but you do not appear to have the
non-literal-meaning module loaded, so the question becomes one of
deciding whether your ability to read the real meaning in other
people's messages is in any way related to your ability to say what
you do not actually mean, as in advanced literary tools like irony,
sarcasm, etc. If I were inclined to be generous to you, which I am
really not considering your behavior towards me, I would simply
believe that you were so stupid that you only understand your own
humor, and that the above is actually an attempt on your part to be
funny, which only failed. Instead, I think of you as someone who
not only laughs at his own jokes even while others try to move away,
but who lambasts people who make good jokes that make others laugh
because you do not get it and are so stupid that you think you are
the butt of all the jokes you do not get. Maybe you have been,
maybe you are, for all I care, but using a public forum for your
personal problems is not really a good idea if you want people to
laugh /less/ at you. If someone shouts over a crowd "are there any
morons in the house", taking personal offense at it is not smart.

You know, "Oleg", I think humor is a good personality indicator.
The problem is that different personalities tend not to understand
each other's humor very well, or at all. I have this theory that
there are "humor strata", and that people who are not communicating
in the same humor statum would tend to take offense at what other
people think are funny. But one quality appears to be common
regardless of stratrum: The willingness to accept that something
that would be too stupid or too ridiculous were it interpreted
literally, might in fact be told in jest. I think you lack this
willingness, and should consequently not depend upon others to have
it towards you when you see so much hostility and negativity where
there is none. In brief, you see only your own hostility in others.

See a man with a degree and ask him to repair you, "Oleg".

Erik Naggum

unread,
Jan 4, 2003, 8:05:03 PM1/4/03
to
* Chris Gehlker <geh...@fastq.com>

| Either I'm very confused or the examples are in the wrong order (or
| both).

Which order did you expect the examples to be in?

| It seems more efficient to simply test with consp and avoid
| examining the terminal cons.

I thought that was exactly what I said.

Now I am puzzled. Did you /only/ look at (the order of) the
examples?

Steven M. Haflich

unread,
Jan 4, 2003, 9:10:56 PM1/4/03
to
Chris Gehlker wrote:
> It seems more efficient to to simply test with consp and avoid examining the
> terminal cons.

If your meaning of "more efficient" is that of runtime code efficiency,
SFAIK your statement is in fact not correct for any of the current
implementations that compile to native code. In particular, NULL is
generally implemented as a hardware EQ test against NIL, which is
generally stored in a register or else somewhere with fast access. The
CONSP test, on the other hand, typically requires testing tag bits for a
particular value, and on some hardware platforms that requires more than
a simple EQ test. Sometimes it is important to understand this sort
of stuff when optimizing inner loops, although usually it is quite
unimportant.

The implications for execution efficiency would have been quite
different fifteen years ago Lisp Machine hardware, and might also be
quite different today on some interpreted or byte-coded implementations.
And the answer might be different again fifteen years from now...

Of course, if your meaning of "more efficient" pertained to programmer
and debugging efficiency, the implications might be different in other
ways. Almost always, programmer and debugging efficiency is more
important than runtime efficiency.

Chris Gehlker

unread,
Jan 5, 2003, 12:00:46 AM1/5/03
to
On 1/4/03 6:05 PM, in article 32507175...@naggum.no, "Erik Naggum"
<er...@naggum.no> wrote:

> * Chris Gehlker <geh...@fastq.com>
> | Either I'm very confused or the examples are in the wrong order (or
> | both).
>
> Which order did you expect the examples to be in?
>
> | It seems more efficient to simply test with consp and avoid
> | examining the terminal cons.
>
> I thought that was exactly what I said.

That *is* what you said, as least as I understood it. Now consider:

> Take the infinitely silly Scheme-like example of computing `length´
> with a maximum of gratuitous overhead:
>
> (defun length (list)
> (if (cons list)
> (1+ (length (cdr list)))
> 0))
>
> compared to the seemingly very similar:
>
> (defun length (list)
> (if (null list)
> 0
> (1+ (length (cdr list)))))

I assume that "cons" is just a typo for "consp". So the solution that we
both prefer is labeled "the infinitely silly Scheme-like example"? That is
the source of my confusion.

Kaz Kylheku

unread,
Jan 5, 2003, 12:03:09 AM1/5/03
to
Chris Gehlker <geh...@fastq.com> wrote in message news:<BA3BB319.25505%geh...@fastq.com>...

> Comes Stephen Slade to say that the canonical way to test for the end of
> proper list lst is (endp lst) rather than (null lst). The HyperSpec seems to
> agree. And yet I have the impression that almost no one uses endp.
>
> To me, endp seems to express intent *slightly* better than null when setting
> delineating the stop condition for a recursion. What do you all think?

ENDP expresses the intent better---to someone who knows squat about
Lisp.

If you just invented the list data structure, and were not sure about
its representation details, you might abstract the iteration
primitives, including the termination test, so that you could later
change the implementation. This is how lists are done in some other
languages, in particular lists that function purely as containers,
rather than as structurally-flexible data representations. E.g. in C++
you have:

for (iterator = list.begin(); iterator != list.end(); iterator++)
...

As it is, Lisp lists are terminated by the NIL atom, and it has been
that way forever, so trying to abstract that buys you nothing.

The error check also buys you nothing, because if the list ends with
an atom other than NIL, your code will fail trying to apply CAR or CDR
to it moments later.

ENDP might give you a more descriptive error message, that is all.

Chris Gehlker

unread,
Jan 5, 2003, 1:35:43 AM1/5/03
to
On 1/4/03 7:10 PM, in article 3E1793E8...@alum.mit.edu, "Steven M.
Haflich" <smh_no_s...@alum.mit.edu> wrote:

> Chris Gehlker wrote:
>> It seems more efficient to to simply test with consp and avoid examining the
>> terminal cons.
>
> If your meaning of "more efficient" is that of runtime code efficiency,
> SFAIK your statement is in fact not correct for any of the current
> implementations that compile to native code. In particular, NULL is
> generally implemented as a hardware EQ test against NIL, which is
> generally stored in a register or else somewhere with fast access. The
> CONSP test, on the other hand, typically requires testing tag bits for a
> particular value, and on some hardware platforms that requires more than
> a simple EQ test. Sometimes it is important to understand this sort
> of stuff when optimizing inner loops, although usually it is quite
> unimportant.

I was assuming something like this:

We are comparing an approach that goes something like:

(defun list-walker (x)
(if (consp x)
(list-walker (cdr x))
(do-something)))

with:

(defun list-walker (x)
(if (null x)
(do-something)
(list-walker (cdr x))))

I made the following assumptions:

If x is a nil pointer, (consp x) will return nil and (null x) will return t
based on some register colored x. If x is non-nil, (consp x) will fetch the
object at x and determine whether it is an atom or a cons cell. If it is a
cons cell, its car and cdr will be loaded into registers so that on the next
iteration x will available on chip.

Turning to the second approach, the program will first test if x is a nil
pointer. Assuming it's not, it will have to fetch the object pointed to by x
to continue.

I'm not sure this little story is correct but it seems likely. If it is
approximately correct, then explicitly testing for nil is redundant. If
consp can somehow tell whether an object is a cons without fetching it, the
the first version is even better because it avoids an expensive memory
access.

Chris Gehlker

unread,
Jan 5, 2003, 1:57:51 AM1/5/03
to
On 1/4/03 10:03 PM, in article
cf333042.03010...@posting.google.com, "Kaz Kylheku"
<k...@ashi.footprints.net> wrote:

> Chris Gehlker <geh...@fastq.com> wrote in message
> news:<BA3BB319.25505%geh...@fastq.com>...
>> Comes Stephen Slade to say that the canonical way to test for the end of
>> proper list lst is (endp lst) rather than (null lst). The HyperSpec seems to
>> agree. And yet I have the impression that almost no one uses endp.
>>
>> To me, endp seems to express intent *slightly* better than null when setting
>> delineating the stop condition for a recursion. What do you all think?
>
> ENDP expresses the intent better---to someone who knows squat about
> Lisp.

[snip]

That isn't what I meant. I simply meant that there might be other reasons
for testing whether a list happened to empty than as the termination
condition of a recursion.

> As it is, Lisp lists are terminated by the NIL atom, and it has been
> that way forever, so trying to abstract that buys you nothing.

Only proper lists are terminated by a nil atom. Surely the point of endp is
that it alerts the programmer when something that he expected would always
be a proper list turns out to be something else.


>
> The error check also buys you nothing, because if the list ends with
> an atom other than NIL, your code will fail trying to apply CAR or CDR
> to it moments later.
>
> ENDP might give you a more descriptive error message, that is all.

That doesn't seem like anything to sneeze at.

Erik Naggum

unread,
Jan 5, 2003, 2:12:27 AM1/5/03
to
* Chris Gehlker <geh...@fastq.com>

| I assume that "cons" is just a typo for "consp".

Yes, sorry about that.

| So the solution that we both prefer is labeled "the infinitely
| silly Scheme-like example"? That is the source of my confusion.

Ah. The idea of computing the length of a list with recursion is
very Scheme-like and very silly, and you should not do this, but it
is useful in an example. Note that both examples are identical in
this respect and it can therefore not be the point of the examples.
The point of the examples is therefore where they differ.

Chris Gehlker

unread,
Jan 5, 2003, 2:20:41 AM1/5/03
to
On 1/5/03 12:12 AM, in article 32507395...@naggum.no, "Erik Naggum"
<er...@naggum.no> wrote:

> * Chris Gehlker <geh...@fastq.com>
> | I assume that "cons" is just a typo for "consp".
>
> Yes, sorry about that.
>
> | So the solution that we both prefer is labeled "the infinitely
> | silly Scheme-like example"? That is the source of my confusion.
>
> Ah. The idea of computing the length of a list with recursion is
> very Scheme-like and very silly, and you should not do this, but it
> is useful in an example. Note that both examples are identical in
> this respect and it can therefore not be the point of the examples.
> The point of the examples is therefore where they differ.

That does clarify it. I understand now. Thanks.

Tim Bradshaw

unread,
Jan 5, 2003, 8:36:23 AM1/5/03
to
* oleg inconnu wrote:

> I do not like the feel-good aliases that a hex editor provides. I think a
> real programmer needs to be fluent in thinking about bits and should write
> his code as ones and zeros.

Editor? Real men program with switches, patch cables and soldering
irons.

--tim

Tim Daly, Jr.

unread,
Jan 6, 2003, 2:15:46 PM1/6/03
to
Alain Picard <apicard+die...@optushome.com.au> writes:

> I personally like FIRST, REST, and ENDP, and do not think of them as
> syntactic sugar. I think of them as expressing intent;
> (car foo) ; The foo is probably something returned from an a-list
> ; or some structure built on cons cells
>
> (first foo) ; foo is a list.
>
> Similarly for CDR, and ENDP.

I think it's a bit like the words "road" and "street" in English.
You're welcome to assign different shades of meaning to them, if
you're that sort (programmers usually are), but you cannot expect
others to concur. The actual semantics are identical. [1]

On a different note, as spiffy as using FIRST, SECOND, ..., REST for
ordinary lists, and CAR and CDR for other structures may be, CDDDR is
always going to be nicer than (REST (REST (REST ...))) . Of course,
if you find yourself taking the CDDDR a lot, it's probably time to
name whatever it is you're _actually_ trying to get at (i.e. introduce
an accessor).

It's great to work with such a rich language, is it not?

-Tim

1. This is not to say that "on the road again" and "on the street
again" mean the same thing...

Joe Marshall

unread,
Jan 6, 2003, 2:50:56 PM1/6/03
to
"Steven M. Haflich" <smh_no_s...@alum.mit.edu> writes:

> Chris Gehlker wrote:
> > It seems more efficient to to simply test with consp and avoid examining the
> > terminal cons.
>
> If your meaning of "more efficient" is that of runtime code efficiency,
> SFAIK your statement is in fact not correct for any of the current
> implementations that compile to native code. In particular, NULL is
> generally implemented as a hardware EQ test against NIL, which is
> generally stored in a register or else somewhere with fast access.
> The CONSP test, on the other hand, typically requires testing tag bits
> for a particular value, and on some hardware platforms that requires
> more than a simple EQ test. Sometimes it is important to understand
> this sort of stuff when optimizing inner loops, although usually it is
> quite unimportant.

It also depends on the safety settings. Just because the object isn't
EQ to NIL doesn't mean that it is a CONS. So code written like this:

(if (consp x)
(f (car x))
...)

The compiler is justified in not inserting a type-check before calling
CAR, but in code like this:

(if (null x)
...
(f (car x)))

The compiler would have to check that X is a CONS (unless safety was
rather low).

I suppose a `sufficiently smart' compiler could rewrite the second
example as:

(cond ((consp x) (f (car x)))
((null x) ...)
(t (error ....)))

Thus making it almost equivalent to the first.

Joe Marshall

unread,
Jan 6, 2003, 2:53:38 PM1/6/03
to
Oleg <oleg_i...@myrealbox.com> writes:

I do not like the feel-good abstraction that a written representation
of bits provides. I think a real programmer needs to be fluent in
thinking about electric fields, current flows, and Maxwell's
equations.

sv0f

unread,
Jan 6, 2003, 4:34:48 PM1/6/03
to
In article <wk8yxyw...@tenkan.org>, t...@tenkan.org (Tim Daly, Jr.) wrote:

>On a different note, as spiffy as using FIRST, SECOND, ..., REST for
>ordinary lists, and CAR and CDR for other structures may be, CDDDR is
>always going to be nicer than (REST (REST (REST ...))) . Of course,
>if you find yourself taking the CDDDR a lot, it's probably time to
>name whatever it is you're _actually_ trying to get at (i.e. introduce
>an accessor).

Just today I found myself writing (nthcdr 5 <list>) with little
or no shame at all.

Steven M. Haflich

unread,
Jan 6, 2003, 9:25:12 PM1/6/03
to
Joe Marshall wrote:

> "Steven M. Haflich" <smh_no_s...@alum.mit.edu> writes:

> (if (consp x)
> (f (car x))
> ...)
>
> The compiler is justified in not inserting a type-check before calling
> CAR, but in code like this:
>
> (if (null x)
> ...
> (f (car x)))
>
> The compiler would have to check that X is a CONS (unless safety was
> rather low).

car, cdr, and their compounds and cousins are required to signal
error on a non-list argument only in _safe_ code, where safe code
is defined as code compiled with safety 3.

When I commented on "more efficient" I presumed the concern was
efficiency of optimized code, or at least, normally-compiled code
that was not compiled expressly for enhanced debugging.

Hmmm, does the ANS imply anywhere abuot the safety of the
interpreter? (I don't have time to research this right now --
maybe later.) One could assume that eval _might_ compile the
given form inside a lambda, and that would inherit the current
synamic optimize settings, but offhand I can't think of anything
that would require this model, nor that eval executes as if
safe.

Gabe Garza

unread,
Jan 6, 2003, 10:07:40 PM1/6/03
to
"Steven M. Haflich" <smh_no_s...@alum.mit.edu> writes:

> Hmmm, does the ANS imply anywhere abuot the safety of the
> interpreter? (I don't have time to research this right now --
> maybe later.)

It never requires an interpreter--it's possible to implement EVAL with
the compiler, which is what several major implementations do: MCL,
Corman Lisp, SBCL, and possibly others. It specifies everything
in terms of evaluation, and specifies that all forms of evaluation
might be implemented in the same basic way.

Gabe Garza

Kent M Pitman

unread,
Jan 6, 2003, 11:11:12 PM1/6/03
to
"Steven M. Haflich" <smh_no_s...@alum.mit.edu> writes:

> Hmmm, does the ANS imply anywhere abuot the safety of the
> interpreter?

The ANS does not mention interpreters. They are not even required.

> One could assume that eval _might_ compile the
> given form inside a lambda, and that would inherit the current
> synamic optimize settings, but offhand I can't think of anything
> that would require this model, nor that eval executes as if
> safe.

There is a notion of minimal compilation. There is no corresponding
model of minimal interpretation.

To underscore (i.e., you surely know this but others reading on might not),
the presence of the EVAL function does not imply an interpreter. EVAL might
be implemented as:

(defun eval (form)
(funcall (compile nil `(lambda () ,form))))

- - - - -

Random datapoint, btw: I never use ENDP. I'm used to using NULL (or
sometimes NOT) from days long before CL. I never got use to ENDP.
It's not a matter of religion with me--I don't know that I have a
strong opinion on this either way, really. Probably if I thought more
on it I would use ENDP rather than NULL... I'd probably use it more
if it had a better name... like, for example, NULL. History
notwithstanding, I probably don't think NOT and NULL should be
identical in meaning. NOT plainly should be a universal function; that
is, (NOT 'FOO) => NIL. But NULL should presumably have as its domain
the type LIST, and as such should probably feel free to err on
non-list arguments.... One of those issues like EQ and EQL where I
think we should have just renamed EQL to EQ and omitted EQ. We should
have renamed ENDP to NULL and flushed the old NULL... Ah well, too much
spilled milk under the bridge at this point... ;)

Steven M. Haflich

unread,
Jan 7, 2003, 3:43:43 AM1/7/03
to
Kent M Pitman wrote:

>>Hmmm, does the ANS imply anywhere abuot the safety of the
>>interpreter?
>
> The ANS does not mention interpreters. They are not even required.

...


> To underscore (i.e., you surely know this but others reading on might not),
> the presence of the EVAL function does not imply an interpreter. EVAL might
> be implemented as:
>
> (defun eval (form)
> (funcall (compile nil `(lambda () ,form))))

Sorry, you and Gabe missed the point of my question entirely. Everyone
knows by now that eval could be implemented trivially by the compiler, as
above. And if implemented that way, the safeness of the evaluated form
would inherit from the dynamic state of the optimize qualities, which are
the same as the globally-proclaimed qualities.

But there is no _requirement_ that eval be implemented that way. For
example, an implementation might quite-reasonably wrap the form in a local
binding of the optimize qualities so that the lambda is compiled with
safety 3. Indeed, this is what a naive developer expects from an
interpreter, whether or not an interpreter actually exists... You
could have defined eval this way:

(defun eval (form)
(funcall (compile nil `(lambda ()

(locally (declare (optimize safety))
,form)))))

My question can be restated simply: Does the ANS impose any _requirement_
on the safety of forms executed by eval?

I can't think of any such requirement, but as I wrote earlier, I haven't
yet taken the time to consider the question carefully wrt the ANS.

Christophe Rhodes

unread,
Jan 7, 2003, 4:40:28 AM1/7/03
to
"Steven M. Haflich" <smh_no_s...@alum.mit.edu> writes:

> Kent M Pitman wrote:
>
> > To underscore (i.e., you surely know this but others reading on might not),
> > the presence of the EVAL function does not imply an interpreter. EVAL might
> > be implemented as:
> > (defun eval (form)
> > (funcall (compile nil `(lambda () ,form))))
>

> [...] You could have defined eval this way:


>
> (defun eval (form)
> (funcall (compile nil `(lambda ()
> (locally (declare (optimize safety))
> ,form)))))
>
> My question can be restated simply: Does the ANS impose any _requirement_
> on the safety of forms executed by eval?

Difficult one. EVAL is defined to evaluate in the current dynamic
environment, which, if it includes the global environment, includes
information about proclamations, so the optimize qualities are
available to it. I would imagine that it would inherit the global
optimize qualities, not any lexical ones, though, so in:
(declaim (optimize safety))
(locally
(declare (optimize (safety 0)))
(eval '(endp 1)))
I think the (ENDP 1) is "safe code", but with the declarations
reversed it wouldn't be. But this is only one interpretation, and I
haven't found any clear-cut requirement. As a datapoint, SBCL (an
effectively compiler-only implementation, at least for the time being)
errs on the side of caution and does much as Steven suggests,
overriding the current OPTIMIZE qualities inside EVAL.

A side note is that, in fact, I don't think EVAL is quite that trivial
to implement: consider
(eval '(progn (defmacro foo (x) `(+ ,x 1)) (foo 2)))

I think people would be unhappy if this were to cause an undefined
function error; and, while getting PROGN right isn't so hard, the
other special forms that preserve toplevelness (MACROLET,
SYMBOL-MACROLET, LOCALLY and EVAL-WHEN) require a fair amount of work
(which can mostly be shared by the compiler, of course). Again, as a
data point, SBCL's compiler-based implementation of EVAL comes to
about 100 lines of code, and I would imagine that other compiler-only
implementations will be of a similar size.

Cheers,

Christophe
--
http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge)

Tim Bradshaw

unread,
Jan 7, 2003, 5:34:01 AM1/7/03
to
* Tim Daly, wrote:

> I think it's a bit like the words "road" and "street" in English.
> You're welcome to assign different shades of meaning to them, if
> you're that sort (programmers usually are), but you cannot expect
> others to concur. The actual semantics are identical. [1]

I'm not sure if anyone has pointed this out yet, but for NULL and ENDP
the semantics are *not* identical in a very important way: ENDP
signals an error if its argument is not a list (so: is not an (or cons
null): it doesn't check proper-listness, obviously). This means that
algorithms which expect a proper list, and cdr down it using ENDP will
signal an error if the list is in fact dotted - since endp will be
called on a non-cons, non-null object - rather than blundering on into
something which is not a cons.

--tim

Tim Bradshaw

unread,
Jan 7, 2003, 5:36:40 AM1/7/03
to
* Joe Marshall wrote:

> I do not like the feel-good abstraction that a written representation
> of bits provides. I think a real programmer needs to be fluent in
> thinking about electric fields, current flows, and Maxwell's
> equations.

Well, of course. All good programmers are failed physicists, everyone
knows that, surely?

--tim

Kent M Pitman

unread,
Jan 7, 2003, 10:41:32 AM1/7/03
to
"Steven M. Haflich" <smh_no_s...@alum.mit.edu> writes:

> But there is no _requirement_ that eval be implemented that way. For
> example, an implementation might quite-reasonably wrap the form in a local
> binding of the optimize qualities so that the lambda is compiled with
> safety 3. Indeed, this is what a naive developer expects from an
> interpreter, whether or not an interpreter actually exists... You
> could have defined eval this way:
>
> (defun eval (form)
> (funcall (compile nil `(lambda ()
> (locally (declare (optimize safety))
> ,form)))))

Yes, I agree with this.

> My question can be restated simply: Does the ANS impose any _requirement_
> on the safety of forms executed by eval?

Nope. Don't remember any such thing.

To my knowledge, any implementation is free to start at low or high safety.
Common sense suggests relatively high safety, to be cranked down by the user,
but I remember no requirement even of that, since we wanted specialized
implementations to be able to deviate freely.

The only safety requirement is that if you manually crank safety up, the
implementation must support it (or, I suppose, signal an error saying it
can't do that). There is no permission given to ignore an explicit request
for safety from user code and the incumbent safeguards that offers; but there
is no requirement that any unmarked code be processed with such safety.



> I can't think of any such requirement, but as I wrote earlier, I haven't
> yet taken the time to consider the question carefully wrt the ANS.

Yeah, my memory is flakey sometimes but I certainly don't remember
putting in any such thing..

Kent M Pitman

unread,
Jan 7, 2003, 10:51:39 AM1/7/03
to
Christophe Rhodes <cs...@cam.ac.uk> writes:

> Difficult one. EVAL is defined to evaluate in the current dynamic
> environment, which, if it includes the global environment, includes
> information about proclamations, so the optimize qualities are
> available to it. I would imagine that it would inherit the global

> optimize qualities, not any lexical ones, though, so [...]

An interesting argument. I wouldn't be too unhappy if this was how
things worked, but I somehow doubt that all implementations have taken
this interpretation. If you find a deviating implementation, you might
try this argument on them and see what you get back...

> A side note is that, in fact, I don't think EVAL is quite that trivial
> to implement: consider
> (eval '(progn (defmacro foo (x) `(+ ,x 1)) (foo 2)))

Hmm.



> I think people would be unhappy if this were to cause an undefined
> function error; and, while getting PROGN right isn't so hard, the
> other special forms that preserve toplevelness (MACROLET,
> SYMBOL-MACROLET, LOCALLY and EVAL-WHEN) require a fair amount of work
> (which can mostly be shared by the compiler, of course). Again, as a
> data point, SBCL's compiler-based implementation of EVAL comes to
> about 100 lines of code, and I would imagine that other compiler-only
> implementations will be of a similar size.

Yes.

Joe Marshall

unread,
Jan 7, 2003, 4:21:39 PM1/7/03
to
Kent M Pitman <pit...@world.std.com> writes:

> Random datapoint, btw: I never use ENDP. I'm used to using NULL (or
> sometimes NOT) from days long before CL. I never got use to ENDP.

I don't use ENDP either. Every time I see it, I have to stop and
think what the difference is between ENDP and NULL. Since
communicating with other programmers is at least as important as
communicating with the computer, I tend to use NULL (and CAR and CDR
over FIRST and REST) because I expect experienced lisp hackers will be
less surprised by it.

Damien Kick

unread,
Jan 10, 2003, 5:17:01 PM1/10/03
to
"Steven M. Haflich" <smh_no_s...@alum.mit.edu> writes:

> Chris Gehlker wrote:
> > Comes Stephen Slade to say that the canonical way to test for the
> > end of proper list lst is (endp lst) rather than (null lst).

> > [...]

> IMO, ENDP is a language feature like many others with a
> confused specification. [...]
>
> Let's review the semantics of NULL and ENDP.
>
> NULL is defined over all lisp objects, returning T for NIL
> and NIL for anything else.
>
> ENDP is defined to return _true_ for NIL, _false_ for a
> CONS or NIL, and is undefined for any ATOM other than NIL.

Huh? For NIL, ENDP is supposed to return true as well as false? Did
you mean that "ENDP is defined to return _true_ for NIL, _false_ for a
CONS or ATOM, and is undefined for any ATOM other than NIL"? But that
doesn't make sense to me, either. I find the following description of
ENDP in the HyperSpec
<http://www.lispworks.com/reference/HyperSpec/Body/f_endp.htm#endp>

Returns true if list is the empty list. Returns false if list
is a cons.

I only find that ENDP is supposed to return false for a CONS and only
a CONS. From whence comes the "CONS or something"?

> However, in _safe_ code ENDP must signal TYPE-ERROR if given [...]
> The significant difference, then, is only the behavior on a non-NIL
> atom.

I was hoping that someone would please help me understand the
following

The purpose of endp is to test for the end of proper list.
Since endp does not descend into a cons, it is well-defined to
pass it a dotted list. However, if shorter ``lists'' are
iteratively produced by calling cdr on such a dotted list and
those ``lists'' are tested with endp, a situation that has
undefined consequences will eventually result when the non-nil
atom (which is not in fact a list) finally becomes the
argument to endp.

What does it mean when "shorter 'lists' are iteratively produced by
calling cdr on such a dotted list"? If someone would please produce
some code showing an example of this, I would very much appreciate it.

Johan Kullstam

unread,
Jan 10, 2003, 10:46:27 PM1/10/03
to
Damien Kick <dki...@email.mot.com> writes:

I think it simply means that you can call ENDP on a dotted list, e.g.,

[1]> (ENDP '(1 . 2))
=> NIL

but not on the CDR of a dotted list since

[2]> (ENDP (CDR '(1 . 2)))

*** - ENDP: A true list must not end with 2
1. Break [3]> :a

will call ENDP on the atom "2" which is neither a CONS nor NIL.

--
Johan KULLSTAM

0 new messages