6 ms·

I tend to agree but would be happy to be proven wrong by more knowledgeable folks in these comments. However I assume here we are talking about dotted lists an

I tend to agree but would be happy to be proven wrong by more knowledgeable folks in these comments. However I assume here we are talking about dotted lists and not ‘proper’ ones?

lisper 4y ago
No. Dotted lists are just a notational convention. All lists can be written in dotted notation. You can define NIL as follows: (setf NIL (cons 0 0))) (setf (car NIL) NIL) (setf (cdr NIL) NIL) Then: (defun null (thing) (eq thing NIL)) You also have to add a bunch of special cases to other functions: (defun cl-style-consp (thing) (and (consp thing) (not (null thing))) (defun cl-style-symbolp (thing) (or (symbolp thing) (null thing)) (defun cl-style-symbol-name (thing) (if (null thing) "NIL" (symbol-name thing))) and a few others. In fact, many CL implementations actually implement NIL that way so that CAR and CDR of NIL return NIL without having to make that a special case.
- mtreis86 4y ago
  In other words CL-USER> (equalp '(1 2 3) '(1 . (2 . (3 . nil)))) => T
- creepycrawler 4y ago
  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).

I tend to agree but would be happy to be proven wrong by more knowledgeable folks in these comments. However I assume here we are talking about dotted lists and not ‘proper’ ones?

lisper 4y ago

No. Dotted lists are just a notational convention. All lists can be written in dotted notation. You can define NIL as follows: (setf NIL (cons 0 0))) (setf (car NIL) NIL) (setf (cdr NIL) NIL) Then: (defun null (thing) (eq thing NIL)) You also have to add a bunch of special cases to other functions: (defun cl-style-consp (thing) (and (consp thing) (not (null thing))) (defun cl-style-symbolp (thing) (or (symbolp thing) (null thing)) (defun cl-style-symbol-name (thing) (if (null thing) "NIL" (symbol-name thing))) and a few others. In fact, many CL implementations actually implement NIL that way so that CAR and CDR of NIL return NIL without having to make that a special case.

mtreis86 4y ago
In other words CL-USER> (equalp '(1 2 3) '(1 . (2 . (3 . nil)))) => T
creepycrawler 4y ago
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).