6 ms·

You are conflating implementation tricks with language semantics. In Lisp, NIL is always an atom, never a cons. Also, a dotted list is a nonempty list where t

You are conflating implementation tricks with language semantics. In Lisp, NIL is always an atom, never a cons. Also, a dotted list is a nonempty list where the cdr of the last cons is not NIL. It is not a notational convention. A list (a b c) is not a dotted list, even if you write it as (a . (b . (c . nil))).

lisper 4y ago
> You are conflating implementation tricks with language semantics. No, I'm not. > In Lisp, NIL is always an atom, never a cons. That depends on what you mean by "atom". If by "atom" you mean something that answers true to the ATOM predicate then yes, NIL is an atom. But if by "atom" you mean something that produces an error if you try to call CAR or CDR on it then no, NIL is not an atom, it is equal to (CONS NIL NIL) because (CAR NIL) and (CDR NIL) are both NIL. So the result of (ATOM NIL) is an arbitrary choice. And CL arguably got it wrong because it fails to preserve the invariant that if (ATOM X) is true then (CAR X) and (CDR X) will produce errors. [UPDATE] > a dotted list is a nonempty list where the cdr of the last cons is not NIL But this is just terminology. In CL, NIL behaves exactly the same as (NIL . NIL) with respect to CAR and CDR. Indeed, it is exactly this confusion that is the basis for a lot of criticism of CL's design. In Scheme, the empty list is unambiguously atomic: trying to take the CAR or CDR of the empty list in Scheme is an error, as with any other atom.
- Chinjut 4y ago
  But NIL is not equal to (CONS NIL NIL). (CONS X NIL) = '(X), a list of length 1 containing X, so (CONS NIL NIL) = '(NIL), a list of length 1 containing NIL. But NIL is a list of length 0, not a list of length 1. The wart is that it should never have been the case that you could call CAR and CDR on NIL. But even though you can wartily call them on NIL, there is still clearly a very important distinction between NIL and (CONS (CAR NIL) (CDR NIL))!
  - lisper 4y ago
    > But NIL is not equal to (CONS NIL NIL). Yes, that's true, but that is a special case. For all other objects X and Y, if (CAR X) is equal to (CAR Y) and (CDR X) is equal to (CDR Y) then X and Y are equal. NIL and (NIL) are the only exception. And the fact that they are an exception is a consequence of the design decision to allow CAR and CDR to be called on NIL and return NIL. > The wart is that it should never have been the case that you could call CAR and CDR on NIL. Yes, that is the whole point. > But even though you can wartily call them on NIL, there is still clearly a very important distinction between NIL and (CONS (CAR NIL) (CDR NIL))! You could have as well said between NIL and (CONS NIL NIL) or just (NIL). And yes, this is true. Nonetheless, it is possible to implement NIL as a privileged cons cell with both CAR and CDR pointing to itself under the hood, and many CL implementations actually do this. It's a design decision. You have to put the warty code somewhere. You can put it in CAR and CDR, or you can put it in NULL, EQUAL, SYMBOLP, etc. But you have to put it somewhere.
- creepycrawler 4y ago
  When baby Lispers are born, the first thing they are taught is a dichotomy: the universe is split into conses and atoms. Cons cells are simple and composed of two components, which are called the car and cdr. There are functions to retrieve what's stored in these components, which are called CAR and CDR. Atoms may be as complex as you like. They include objects like numbers, characters, strings, arrays, symbols, etc. NIL is not a cons cell, but a symbol. We can represent lists by chaining cons cells. We may start with an empty list, and by convention this is the symbol NIL. If we also choose to designate NIL as the false value, and everything else as true values, then it is useful to modify CAR and CDR so that they take not only conses, but also the symbol NIL, and return NIL, which is false, and the empty list. We then say that CAR and CDR take a list, i.e. an object of type (or cons null). We do not say that NIL is a cons. Your [UPDATE] shows that you still don't understand what is meant by "dotted list". I already gave a definition of one, but did not give an example. An example of a dotted list is (a b . c) i.e. the last cons has a cdr that is (i) an atom (otherwise, it wouldn't have been the last cons) and (ii) not NIL (which is the conventional empty list designation).
  - kazinator 4y ago
    (a b . c), as an object is an improper list. The printed notation is a dotted list. By an informal metonymy, the internal object is called a dotted list. It's only an informal usage among Lisp coders. The correct terminology is "improper" for the object and "dotted" for the spelling. Note that (a b c . nil) is dotted, but it's the same as (a b c) which is proper. Unfortunately, the Common Lisp specification encodes the "dotted list" informality in the Glossary. Common Lisp does things like that. Furthermore Common Lisp uses "dotted list" as an essential term denoting a subset of of "improper list". An "improper list" is circular or not terminated by nil. A dotted list is only the latter. That's in spite of the fact that a circular list will print with the dot notation: #1=(a b c . #1#)! Circular lists are dotted when completely printed, under the circle notation. Another problem is that the append function and others support the idea of a non-nil atom being an empty dotted list. For instance (append '(a b c) 'd) will work and produce (a b c . d). Yet the "dotted list" definition excludes such an atom. If we go by the presence of a dot, that is correct, but then we know from circular lists not being dotted that that isn't the criterion.

lisper 4y ago

> You are conflating implementation tricks with language semantics. No, I'm not. > In Lisp, NIL is always an atom, never a cons. That depends on what you mean by "atom". If by "atom" you mean something that answers true to the ATOM predicate then yes, NIL is an atom. But if by "atom" you mean something that produces an error if you try to call CAR or CDR on it then no, NIL is not an atom, it is equal to (CONS NIL NIL) because (CAR NIL) and (CDR NIL) are both NIL. So the result of (ATOM NIL) is an arbitrary choice. And CL arguably got it wrong because it fails to preserve the invariant that if (ATOM X) is true then (CAR X) and (CDR X) will produce errors. [UPDATE] > a dotted list is a nonempty list where the cdr of the last cons is not NIL But this is just terminology. In CL, NIL behaves exactly the same as (NIL . NIL) with respect to CAR and CDR. Indeed, it is exactly this confusion that is the basis for a lot of criticism of CL's design. In Scheme, the empty list is unambiguously atomic: trying to take the CAR or CDR of the empty list in Scheme is an error, as with any other atom.

Chinjut 4y ago
But NIL is not equal to (CONS NIL NIL). (CONS X NIL) = '(X), a list of length 1 containing X, so (CONS NIL NIL) = '(NIL), a list of length 1 containing NIL. But NIL is a list of length 0, not a list of length 1. The wart is that it should never have been the case that you could call CAR and CDR on NIL. But even though you can wartily call them on NIL, there is still clearly a very important distinction between NIL and (CONS (CAR NIL) (CDR NIL))!
- lisper 4y ago
  > But NIL is not equal to (CONS NIL NIL). Yes, that's true, but that is a special case. For all other objects X and Y, if (CAR X) is equal to (CAR Y) and (CDR X) is equal to (CDR Y) then X and Y are equal. NIL and (NIL) are the only exception. And the fact that they are an exception is a consequence of the design decision to allow CAR and CDR to be called on NIL and return NIL. > The wart is that it should never have been the case that you could call CAR and CDR on NIL. Yes, that is the whole point. > But even though you can wartily call them on NIL, there is still clearly a very important distinction between NIL and (CONS (CAR NIL) (CDR NIL))! You could have as well said between NIL and (CONS NIL NIL) or just (NIL). And yes, this is true. Nonetheless, it is possible to implement NIL as a privileged cons cell with both CAR and CDR pointing to itself under the hood, and many CL implementations actually do this. It's a design decision. You have to put the warty code somewhere. You can put it in CAR and CDR, or you can put it in NULL, EQUAL, SYMBOLP, etc. But you have to put it somewhere.
creepycrawler 4y ago
When baby Lispers are born, the first thing they are taught is a dichotomy: the universe is split into conses and atoms. Cons cells are simple and composed of two components, which are called the car and cdr. There are functions to retrieve what's stored in these components, which are called CAR and CDR. Atoms may be as complex as you like. They include objects like numbers, characters, strings, arrays, symbols, etc. NIL is not a cons cell, but a symbol. We can represent lists by chaining cons cells. We may start with an empty list, and by convention this is the symbol NIL. If we also choose to designate NIL as the false value, and everything else as true values, then it is useful to modify CAR and CDR so that they take not only conses, but also the symbol NIL, and return NIL, which is false, and the empty list. We then say that CAR and CDR take a list, i.e. an object of type (or cons null). We do not say that NIL is a cons. Your [UPDATE] shows that you still don't understand what is meant by "dotted list". I already gave a definition of one, but did not give an example. An example of a dotted list is (a b . c) i.e. the last cons has a cdr that is (i) an atom (otherwise, it wouldn't have been the last cons) and (ii) not NIL (which is the conventional empty list designation).
- kazinator 4y ago
  (a b . c), as an object is an improper list. The printed notation is a dotted list. By an informal metonymy, the internal object is called a dotted list. It's only an informal usage among Lisp coders. The correct terminology is "improper" for the object and "dotted" for the spelling. Note that (a b c . nil) is dotted, but it's the same as (a b c) which is proper. Unfortunately, the Common Lisp specification encodes the "dotted list" informality in the Glossary. Common Lisp does things like that. Furthermore Common Lisp uses "dotted list" as an essential term denoting a subset of of "improper list". An "improper list" is circular or not terminated by nil. A dotted list is only the latter. That's in spite of the fact that a circular list will print with the dot notation: #1=(a b c . #1#)! Circular lists are dotted when completely printed, under the circle notation. Another problem is that the append function and others support the idea of a non-nil atom being an empty dotted list. For instance (append '(a b c) 'd) will work and produce (a b c . d). Yet the "dotted list" definition excludes such an atom. If we go by the presence of a dot, that is correct, but then we know from circular lists not being dotted that that isn't the criterion.