Hacker News Reader

Comment by susam | Hacker News Reader

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.
  $

View on HN

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!)

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.

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.

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.

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.

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.

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.

Reply on news.ycombinator.com