Hofstadter on Lisp (1983)

(gist.github.com)

372 points Eric_WVGG | 1 comments | 16 Oct 24 13:44 UTC | HN request time: 0.222s | 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]▶

>>41861244 #

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]▶

>>41861327 #

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]▶

>>41863165 #

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 #

1. kazinator ◴[20 Oct 24 07:42 UTC] No.41893676[source]▶

>>41864888 #

What's saved is that your code just calls that function, rather than open-coding that check.

Suppose you wrote this code in more than two or three places:

  (if (and (consp x) (consp (cdr x))
    (car (cdr x)))

you might define a function for that. Since there is cadr, you don't have to.

Also, that function may be more efficient, especially if our compiler doesn't have good CSE. Even if x is just a local variable, there is the issue that (cdr x) is called twice. A clever compiler will recognize that the value of x has not changed, and generate only one access to the cdr.

The function can be coded to do that even in the absence of such a compiler.

(That is realistic; in the early lifecycle of a language, the quality of library functions can easily outpace the quality of compiler code generation, because the library writers use efficient coding tricks, and perhaps even drop into a lower level language where beneficial.)

If x itself is a complex expression:

  (if (and (consp (complex-expr y)) (consp (cdr (complex-expr y)))
    (car (cdr (complex-expr y))))

we will likely code that as:

  (let ((x (complex-expr y)))
    ...)

The function call gives us all that for free: (cadr (complex-expr y)). The argument expression is evaluated once, and bound to the formal parameter that the function refers to, and the function body can do manual CSE not to access the cdr twice.

↑