4 ms·

> It is necessary that there be a special empty-list object which is a list but not a cons. That is not true. NIL could be a CONS. In fact, it acts just like

by lisper 4y ago

> It is necessary that there be a special empty-list object which is a list but not a cons. That is not true. NIL could be a CONS. In fact, it acts just like a CONS whose CAR and CDR are itself. The only way in which NIL does not behave like a CONS is that it does not answer true to CONSP. But that doesn't matter because it answers true to NULL, so you can build a CL-style CONSP if you want it by checking for (AND (CONSP thing) (NOT (NULL thing))). It is not even necessary that NIL be unique. The only thing that is necessary is that there be some non-empty set of distinguished objects with a predicate to test for membership in that set which by convention designate the ends of lists.

rosebay 4y ago
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.
Chinjut 4y ago
If NIL were a CONS, how would you distinguish between an empty list and a list of length one containing NIL?
- lisper 4y ago
  The same way you do now: (NIL) would not answer true to NULL. And it would not be EQ to NIL.
  - Chinjut 4y ago
    If NIL were a CONS whose CAR is NIL and whose CDR is NIL, wouldn't NIL be the same as (CONS NIL NIL) = (NIL . NIL) = '(NIL)?
    - lisper 4y ago
      It depends on what you mean by "the same". It is already "the same" in the sense that the CAR and CDR of both NIL and (NIL) are all NIL. They just aren't EQUAL, despite the fact that their CARs and CDRs are EQUAL (in fact, they are all EQ).
    - tmtvl 4y ago
      Technically not, because a cons of two objects is not eq to another cons of the same two objects. (eq (cons 1 2) (cons 1 2)) ;; => nil It's memory locations, after all.
      - Chinjut 4y ago
        I see, fair enough. I forgot to switch out of pure functional programming/referential transparency mode for this discussion. Fine, you can take NIL to be one particular (NIL . NIL) that's different from all other (NIL . NIL)s, the only particular (NIL . NIL) that is considered a list of length 0 while all other (NIL . NIL)s are lists of length 1.

by lisper 4y ago

rosebay 4y ago

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.

Chinjut 4y ago

If NIL were a CONS, how would you distinguish between an empty list and a list of length one containing NIL?

lisper 4y ago
The same way you do now: (NIL) would not answer true to NULL. And it would not be EQ to NIL.
- Chinjut 4y ago
  If NIL were a CONS whose CAR is NIL and whose CDR is NIL, wouldn't NIL be the same as (CONS NIL NIL) = (NIL . NIL) = '(NIL)?
  - lisper 4y ago
    It depends on what you mean by "the same". It is already "the same" in the sense that the CAR and CDR of both NIL and (NIL) are all NIL. They just aren't EQUAL, despite the fact that their CARs and CDRs are EQUAL (in fact, they are all EQ).
  - tmtvl 4y ago
    Technically not, because a cons of two objects is not eq to another cons of the same two objects. (eq (cons 1 2) (cons 1 2)) ;; => nil It's memory locations, after all.
    - Chinjut 4y ago
      I see, fair enough. I forgot to switch out of pure functional programming/referential transparency mode for this discussion. Fine, you can take NIL to be one particular (NIL . NIL) that's different from all other (NIL . NIL)s, the only particular (NIL . NIL) that is considered a list of length 0 while all other (NIL . NIL)s are lists of length 1.