Hacker News Reader

Comment by imdhmd | Hacker News Reader

I am unable to understand the difference between (a b c) and (a b . c)

(a b c) is (a b c . nil). That is, (a . (b . (c . nil))). On the other hand, (a b . c) is (a . (b . c)). (Edit: rewrote post)

() is equivalent to an empty list and nil according to this notation, in which case both would be proper lists. But according to pg, in bel, (a b . c) is not a proper list.

Edit: I think I understand now, hmm.

Think of a proper list like a degenerate tree with all the values on the left and structure on the right. A dotted list puts the last value on the right, where nil would usually be.

Dotted lists are pretty rare. They mostly show up in association lists, where key/value pairs are stored as

  ((name . dave) (type . user))

and adding a pair to the front of the list shadows any other pairs with the same key.

While I think this is the correct interpretation, I do not think it's actually implied by the language specification. In fact, I think the notation (a b . c) is simply undefined -- there's no way to formally deduce what it means from what is defined.

> 2. When the second half of a pair is a list, you can omit the dot before it and the parentheses around it. So (a . (b ...)) can be written as (a b ...).

That defines (a b . c). Edit: Note that (b . c) is a list.

It doesn't. That definition applies only to expressions like (a b c) which do not contain the dot operator at all. (a b . c) is not of the form specified. Moreover, every object of the sort defined via (a b c ...) is a proper list, and (a b . c) is, as described in the specification, not a proper list, so it can't be covered by that definition. It's true that (b . c) is a list, but the form (b . c) does not occur in the expression (a b . c) so this isn't relevant. (You'd need the expression under analysis to instead be (a (b . c)).)

The rule I quoted states that (a . (b . c)) can be written as (a b . c).

That would only be true if (b . c) were a proper list. But it’s not. Strictly speaking, it’s not even a list if you go by the definition of list provided before your quoted rule. It’s later called a “dotted list” to distinguish it from a list, which must be nil-terminated.

Your position boils down to claiming that the rule you quoted is intended to cover lists as well as dotted lists. As stated, it only covers the former, which leaves (a b . c) undefined.

In the usage seen later throughout the document, dotted lists are a kind of list. It doesn't say its examples of how to build a list are exhaustive.

So you agree it’s ambiguous and one cannot formally deduce the meaning of the expression without making assumptions. One must assume that objects that don’t fit the definition of list can be substituted in for lists within some contexts (but not all).

Beyond that, dotted lists are introduced via the undefined example (a b . c), which requires one to go even further and make a second assumption (namely, assume the intention was to refer to (a . (b . c)), then assume the quoted transformation rule applies to certain non-lists allowing that to be rewritten as (a b . c)).

It is not the case that dotted lists don't fit the definition of list. What you point to as a definition wasn't a definition. Just examples. A definition would describe it as the minimal set of objects meeting those criteria. (A non-minimal set could include circular lists and/or pairs whose cdr is not a list.)

Since the document does use list in ways that encompass dotted lists and goes out of its way to define proper lists, we can infer that list includes dotted lists. Also, it's a long-running convention that the term "proper X" implies there are other kinds of X's.

I'd disagree with you on that. If the document can't clearly define the terms it's using, it cannot function as a formal specification of a language. The writing as it stands now is far too ambiguous to serve such a role. You have no reasonable retort to me except to say that the definition wasn't even a definition, and after that there is indeed no more abstract definition you can even point to. You're left using undefined terms to defend your interpretation as the "correct" one. That's not sufficient to defend the document as a specification. In fact, that's just further criticism of it.

Like I said, I'm confident your interpretation is the intended one. But you cannot prove it as such, and that's where we disagree.

I never claimed it was a formal specification. The question was, is the meaning of (a b . c) defined, and the answer is, yes, because (b . c) is a list.

And I say the answer is no, because (b . c) is an arbitrary pair, not a list. It would appear that we’re at an impasse.

Lists are made of cons cells, and a cons cell is simply a two-element array. In a list, the first element of a cons cell contains data and the second element contains a pointer to the next cons cell in the list.

How then should we represent the last cons cell in a list? We have two choices for what goes in the second element of the last cons cell:

1. The last piece of data, or

2. Nothing; i.e. a special non-pointer pointer. In Lisp this is called nil.

If we choose option 1 it's harder for code that traverses the list to be sure it has reached the end. It's also harder to splice a new element (a new cons cell) onto the end of the list dynamically.

Option 1 is the "dotted" form of ending a list and option 2 is the "proper" form.

Option 2 is more common in Lisp. From a type theory point of view, Option 2 restricts the second element of a cons cell to contain either a pointer to a cons cell or nil. This makes reasoning about code, compiling code, and optimizing code easier.

"Also by convention, the cdr of the last cons cell in a list is nil. We call such a nil-terminated structure a proper list. In Emacs Lisp, the symbol nil is both a symbol and a list with no elements. For convenience, the symbol nil is considered to have nil as its cdr (and also as its car)."

https://www.gnu.org/software/emacs/manual/html_node/elisp/Co...

I read the guide from the beginning and (a b . c) stood out to me too.

It's not a form allowed by all the preceding rules, and I wasn't sure what it meant either.

It definitely needs to be defined. Using only the paper, I assumed from the previous definitions that (a b . c) should be parsed as (x y) where x = a and y = b . c which can be re-written using only pair notation as (x . (y . nil) ) or (a . ((b . c) . nil)) and this made it very confusing to try to figure out what is meant by "improper."

Even if a definition for the notation (a b . c) is added, an example of such an improper list fully broken down into pairs would certainly still be appreciated by us readers who don't already think in Lisp :)

Think of the period symbol as the root of a branch in a tree. A true list has all left branches empty. A "dotted list" has to items on both branches at the very tip.

Reply on news.ycombinator.com