←back to thread

Hofstadter on Lisp (1983)

(gist.github.com)
372 points Eric_WVGG | 1 comments | 16 Oct 24 13:44 UTC | HN request time: 0s | source
Show context
susam ◴[16 Oct 24 16:53 UTC] No.41861244[source]▶
> Attempting to take the car or cdr of nil causes (or should cause) the Lisp genie to cough out an error message, just as attempting to divide by zero should evoke an error message.

Interestingly, this is no longer the case. Modern Lisps now evaluate (car nil) and (cdr nil) to nil. In the original Lisp defined by John McCarthy, indeed CAR and CDR were undefined for NIL. Quoting from <https://dl.acm.org/doi/pdf/10.1145/367177.367199>:

> Here NIL is an atomic symbol used to terminate lists.

> car [x] is defined if and only if x is not atomic.

> cdr [x] is also defined when x is not atomic.

However, both Common Lisp and Emacs Lisp define (car nil) and (cdr nil) to be nil. Quoting from <https://www.lispworks.com/documentation/HyperSpec/Body/f_car...>:

> If x is a cons, car returns the car of that cons. If x is nil, car returns nil.

> If x is a cons, cdr returns the cdr of that cons. If x is nil, cdr returns nil.

Also, quoting from <https://www.gnu.org/software/emacs/manual/html_node/elisp/Li...>:

> Function: car cons-cell ... As a special case, if cons-cell is nil, this function returns nil. Therefore, any list is a valid argument. An error is signaled if the argument is not a cons cell or nil.

> Function: cdr cons-cell ... As a special case, if cons-cell is nil, this function returns nil; therefore, any list is a valid argument. An error is signaled if the argument is not a cons cell or nil.

replies(6): >>41861327 #>>41861751 #>>41862379 #>>41862873 #>>41862933 #>>41868929 #
sph ◴[16 Oct 24 17:48 UTC] No.41861751[source]▶
Sadly this is not the case with Scheme and it makes for very unergonomic code, especially for a newbie like me.

Which is a shame, because I prefer (Guile) Scheme to Common Lisp.

replies(2): >>41862075 #>>41863892 #
BoiledCabbage ◴[16 Oct 24 21:11 UTC] No.41863892[source]▶
> Sadly this is not the case with Scheme and it makes for very unergonomic code,

How so? If car of nil returns nil, then how does a caller distinguish between a value of nil and a container/list containing nil?

The only way is they can check to see if it's a cons pair or not? So if you have to check if it's a cons pair then you're doing the same thing as in scheme right?

I may be missing something, but isn't it effectively the same amount of work just potentially? Need to check for nil and need to check if it's a pair?

replies(2): >>41864352 #>>41893182 #
1. kazinator ◴[20 Oct 24 05:50 UTC] No.41893182[source]▶
> how does a caller distinguish between a value of nil and a container/list containing nil

Very easily; but the point is that it's very often easy to design things so that the caller doesn't have to care.

For instance, lookup in an associative list can just be (cdr (assoc key alist)).

If the key is not found, assoc returns nil, and so cdr returns nil.

Right, so when we use this shortcut, we have an ambiguity: does the list actually have that key, but associated with the value nil? Or does it not have the key.

Believe it or not, we can design the data representation very easily such that we don't care about the difference between these two cases; we just say we don't have nil as a value; a key with a value nil is as good as a missing key.

This situation is very often acceptable. Because, in fact, data structures are very often heavily restrained in what data types they contain. Whenever we assert that, say, a dictionary has values that are, say, strings, there we have it: values may not be nil because nil is not a string. And so the ambiguity is gone.

A nice situation occurs when keys are associated with lists of values. A key may exist, but be associated with an empty list (which is nil!). Or it may not exist. We can set things up so that we don't care about distinguishing these two. If key K doesn't exist then K is not associated with a list of items, which is practically the same as being associated with an empty list of items. If we split hairs, it isn't, but in a practical application things can be arranged so it doesn't matter.