←back to thread

Hofstadter on Lisp (1983)

(gist.github.com)
372 points Eric_WVGG | 3 comments | 16 Oct 24 13:44 UTC | HN request time: 0.611s | 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 #
susam ◴[16 Oct 24 17:03 UTC] No.41861327[source]▶
I was curious what it is like on Maclisp. Here is a complete telnet session with Lars Brinkhoff's public ITS:

  $ telnet its.pdp10.se 10003
  Trying 88.99.191.74...
  Connected to pdp10.se.
  Escape character is '^]'.


  Connected to the KA-10 simulator MTY device, line 0

  ^Z
  TT ITS.1652. DDT.1548.
  TTY 21
  3. Lusers, Fair Share = 99%
  Welcome to ITS!

  For brief information, type ?
  For a list of colon commands, type :? and press Enter.
  For the full info system, type :INFO and Enter.

  Happy hacking!
  :LOGIN SUSAM
  TT: SUSAM; SUSAM MAIL - NON-EXISTENT DIRECTORY
  :LISP

  LISP 2156
  Alloc? n


  *
  (status lispversion)
  /2156
  (car nil)
  NIL
  (cdr nil)
  NIL
  ^Z
  50107)   XCT 11   :LOGOUT

  TT ITS 1652  Console 21 Free. 19:55:07
  ^]
  telnet> ^D Connection closed.
  $
replies(1): >>41863165 #
dokyun ◴[16 Oct 24 19:56 UTC] No.41863165[source]▶
I recall reading that in early versions of Maclisp, taking the CAR or CDR of NIL worked differently: Taking its CAR would signal an error as you would expect, however taking its CDR would return the symbol plist of NIL, as internally the operation of CDR on the location of a symbol would access its plist, and that's how it was commonly done before there was a specific form for it (and it actually still worked that way into Lisp Machine Lisp, provided you took the CDR of the locative of a symbol).

Apparently the behaviour of the CAR and CDR of NIL being NIL was from Interlisp, and it wasn't until the designers of Maclisp and Interlisp met to exchange ideas that they decided to adopt that behaviour (it was also ostensibly one of the very few things they actually ended up agreeing on). The reason they chose it was because they figured operations like CADR and such would be more correct if they simply returned NIL if that part of the list didn't exist rather than returning an error, otherwise you had to check each cons of the list every time. (If somebody can find the source for this, please link it!)

replies(1): >>41864888 #
pfdietz ◴[16 Oct 24 23:19 UTC] No.41864888[source]▶
But of course cadr still has to check each access, to see if its of type (or cons null). So I don't see what was saved.
replies(2): >>41865747 #>>41893676 #
dokyun ◴[17 Oct 24 02:01 UTC] No.41865747[source]▶
It would be considered "the right thing" to do something that's so common you probably want it without asking. I don't think CADR would check for NIL since it's meant to be equivalent to (car (cdr x)), so if you wanted a safe list operation you would have to check it like this: (I'll use CADADR because it makes the issue more apparent)

  (and (car x)
       (cadr x)
       (cadar x)
       (cadadr x))
You would have to write this every time you want to see if there's a really CADADR, whereas if CAR and CDR can return NIL then you can just write (cadadr x) and CADADR can still be defined as (car (cdr (car (cdr x)))) and have the desired behaviour.
replies(1): >>41869079 #
1. pfdietz ◴[17 Oct 24 12:37 UTC] No.41869079[source]▶
Any argument of the form "you have to write this idiom" is covered by "so either it doesn't happen often, or one can use a macro". There's cognitive overhead to using a macro, but there's also cognitive overhead to remembering car and cdr work on nil. The latter is already paid for, so changing Common Lisp now doesn't make sense, but in an alternate world with a different design it would be a point.
replies(1): >>41872210 #
2. dokyun ◴[17 Oct 24 18:20 UTC] No.41872210[source]▶
There's more 'cognitive overhead' to making CADADR etc. a macro that expands to the above when CAR and CDR don't work that way, since then its implementation isn't consistent with what it's meant to be. If you made it a macro with a different name then you have two slightly different versions of CADADR and every other accessor, which is even more overhead. Apparently this idiom happened often enough that it was deemed desirable to simply make it the default behaviour. Accommodating common idioms is a pattern of "the right thing" design, from which Lisp is heavily derived, and if you're not a Lisp programmer then keeping this philosophy in mind is a good way to not have misconceptions about the design of the system.

However, thinking in terms of 'cognitive overhead' for a very minor design choice is very silly. I don't suffer any 'cognitive overhead' from having CAR and CDR work on NIL when I write Common Lisp because I'm used to it, but I do suffer 'cognitive overhead' when they don't in Scheme, which is the 'alternate world with a different design'. I am incredulous to the idea that one is actually superior to the other, and suppose that it is simply a matter of preference.

replies(1): >>41893690 #
3. kazinator ◴[20 Oct 24 07:45 UTC] No.41893690[source]▶
Under one of the two choices, we can reduce the amount of code, if we stick to certain easy representational conventions around how we use nil.