Live data from Hacker News

The empty list

tfeb.org

81–90 of 109 posts

Re: The empty list

#81

I've been trying to learn CL by using it to do AOC. As someone coming from mostly Python, there is a lot about it that confuses and, occasionally, frustrates me. Maybe I'm just missing something obvious but it doesn't seem like you can start with an empty list that you can repeatedly append to. The empty list is nil, and `(append nil foo)` seems to just yield `foo`, not `(list foo)`. So trying to append to that objec…

There's a huge amount of documentation telling you that NIL is an empty list. It isn't. It has none of the mechanics of an empty list in Python etc. It's more like a null link, and has quite a bit in common with /0 as a string terminator. It does different things on its own and in the context of a list. The key is that Lisp list items are stored as car (link/pointer to an item) and cdr (link to the next item/s in the…

> NIL is an empty list.... It isn't. It has none of the mechanics of an empty list in Python etc.

I can see how NIL is confusing when coming from Python, but I think this comment has it backwards. The idea of lists as chains or trees of pointers with a distinguished termination value predates LISP by a few years. Moreover, this kind of list predates Python's use of the term by more than 35 years. If you treat lists as just a particularly useful subclass of trees of CONS cells, then they and NIL make perfect sense. Python's lists are fine too, they're just a different kind of thing.

Re: The empty list

#82
post #73

Earlier quoted context omitted.

In C you sometimes have to pass int* instead of int, because you want null to signify that you aren't passing a value, rather than passing a value of 0. The two things aren't interchangeable. An empty string and a string of length 0 aren't the same thing. You'd just end up needing an extra boolean parameter for "is_null".

Agreed. I'm not a fan of 0===false===null for equality / truthiness tests. But "null is empty list" is categorically different and fine by me. > You'd just end up needing an extra boolean parameter Correct. Or an Option() wrapper or another box. Such an unusual construction is fine because, as you noted, the cases where one would want to distinguish null from empty list are rare. Rare cases should stick out. The fact…

> I'm not a fan of 0===false===null for equality / truthiness tests. But "null is empty list" is categorically different and fine by me.

Wat?

You might want to signify that you are not passing a list instead of you are passing an empty list. Same way that happens with any other type…

> The fact that in JavaScript (and Java)

Well in JS it's completely insane. With typed python if you say "list of XXX" null is not accepted by linters. You need to specify it's also an option.

Re: The empty list

#83

I've been trying to learn CL by using it to do AOC. As someone coming from mostly Python, there is a lot about it that confuses and, occasionally, frustrates me. Maybe I'm just missing something obvious but it doesn't seem like you can start with an empty list that you can repeatedly append to. The empty list is nil, and `(append nil foo)` seems to just yield `foo`, not `(list foo)`. So trying to append to that objec…

`append` on lists is equivalent to concatenation, not Python's append which is equivalent to `vector-push` or `vector-push-extend` in Lisp (and which, as the name suggests, takes a vector for the place and not a list). For performance reasons, the more conventional behavior in Lisp to collect values would be: (let ((some-place nil)) (push an-item some-place) ... (nreverse some-place)) ;; if the order really matters,…

> For performance reasons, the more conventional behavior in Lisp to collect values would be

What you describe is what a human typical would write.

For tools this is optimized. For example in (loop for e in list collect (oddp e)) this usually would be optimized. It would not add to the end and then reverse. Instead, it would keep a pointer to the end and add to the end via that pointer.

Re: The empty list

#84
post #27

Earlier quoted context omitted.

No, that's not a contradiction. To add a canonical false value you would have to change the semantics of the language, which means you have to change the standard. In general changing standards is possible, but in the case of CL it is not possible for practical reasons: changing standards costs money and no one would fund such an effort. CL is moribund, not unlike Smalltalk, APL, and COBOL.

>CL is moribund, not unlike Smalltalk, APL, and COBOL. If someone wants to do some hobby/small-scale but complex programming in LISP, what kind of dialect should they use? Scheme/Racket or something else?

As a programming language, CL isn't moribund. There are several high-quality Common Lisp implementations. There's just no real chance of there being a revision of the language standard.

Re: The empty list

#85
I distinctly remember from over two decades ago that, as I was exploring Lisp under the guidance of Shapiro's book Common Lisp: An Interactive Approach, the situation with nil being a symbol, empty list and false was simply a fantastic design, and it likely helped me get hooked on Lisp.

My view today is that if anything calls itself Lisp and doesn't have these design elements, it is, in a way, vandalizing the word "Lisp".

Re: The empty list

#86
post #78

Earlier quoted context omitted.

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

You don't need to be quite so condescending. I understand all this perfectly well. But the concept of a "dotted list" has to do with how a list is serialized, not how it is represented in the internally, which is what I am talking about. NIL is weird in CL and different implementations handle this weirdness in different ways. One way to handle it is to represent NIL as a symbol whose name is "NIL" and write CAR and C…

The name "dotted list" comes from how the list is serialized, yes, but not the concept. You can write a function dotted-list-p that takes an object and returns the value of (and (consp object) (cdr (last object))). Indeed, it is not related to the NIL issue, and I made no such assumption. You can read an equivalent definition that uses different words in the CLHS glossary.

You admit to talking about "how NIL is implemented internally", hence my original remark that you are conflating implementation tricks with language semantics. From language semantics point of view, NIL is not weird, it is an ordinary symbol, like NIK or NIM. Lisp tradition assigns it certain roles, like representing the empty list, representing the false value, representing the empty type, and also has conveniences like having NIL evaluate to itself or having CAR and CDR take lists instead of conses.

I didn't mean to be condescending. I know you are not a baby Lisper. The matter at hand is very basic, and I understand the desire to present a more sophisticated take, but believe it leads to (and reflects) a distorted ontological view of Lisp if taken seriously. NIL is not weird, it is a simple symbol. We just assigned it a few roles and made a few conveniences. Why did we pick it for those roles? Arbitrary choice. Why did we choose to extend the domain of CAR and CDR? Practical choice. Let the puritans complain and build their own ivory tower languages. Lisp is pragmatic. Could an implementor choose to represent NIL as a closet cons for simple CAR and CDR implementations and special case everything else? Sure. But this has nothing to do with the ontology of Lisp.

Re: The empty list

#87
post #82

Earlier quoted context omitted.

Agreed. I'm not a fan of 0===false===null for equality / truthiness tests. But "null is empty list" is categorically different and fine by me. > You'd just end up needing an extra boolean parameter Correct. Or an Option() wrapper or another box. Such an unusual construction is fine because, as you noted, the cases where one would want to distinguish null from empty list are rare. Rare cases should stick out. The fact…

> I'm not a fan of 0===false===null for equality / truthiness tests. But "null is empty list" is categorically different and fine by me. Wat? You might want to signify that you are not passing a list instead of you are passing an empty list. Same way that happens with any other type… > The fact that in JavaScript (and Java) Well in JS it's completely insane. With typed python if you say "list of XXX" null is not acce…

JavaScript already has undefined as a primitive that could be used to signify you are not passing a list as opposed to passing an empty list.

I think we are talking around agreement here, which is that JavaScript was not particularly well-designed.

Re: The empty list

#88
post #78

Earlier quoted context omitted.

You don't need to be quite so condescending. I understand all this perfectly well. But the concept of a "dotted list" has to do with how a list is serialized, not how it is represented in the internally, which is what I am talking about. NIL is weird in CL and different implementations handle this weirdness in different ways. One way to handle it is to represent NIL as a symbol whose name is "NIL" and write CAR and C…

The name "dotted list" comes from how the list is serialized, yes, but not the concept. You can write a function dotted-list-p that takes an object and returns the value of (and (consp object) (cdr (last object))). Indeed, it is not related to the NIL issue, and I made no such assumption. You can read an equivalent definition that uses different words in the CLHS glossary. You admit to talking about "how NIL is imple…

> The name "dotted list" comes from how the list is serialized, yes, but not the concept.

Yes, it does. Dotted lists are entirely related to serialization. The only reason they matter is that, by convention, (a b ... z) is a shorthand notation for (a . (b . (... (z . nil)) ...) and (a b ... z . anything-but-nil) is a shorthand notation for (a . (b . (... (z . anything-but-nil)) ...)

> You can write a function dotted-list-p

Of course you can. So what? You can write a predicate for any (computable) property. I can write a function list-ends-in-3-p. That doesn't mean that lists that end in 3 matter.

The reason "dotted lists" are called dotted lists is entirely because of their serialization behavior: dotted lists have a dot in their serialization and non-dotted-lists don't. And the reason that the I/O behavior is what it is is that it turns out that punning cons cells as linked lists is a useful hack (or at least it was in 1958). But it is only a hack. There is no reason that the data structure used to represent pairs has to be the same data structure that is used to represent linked lists. Indeed, one could argue that this punning is actually a serious mistake. There should be pairs, with CAR and CDR fields which can take on any value, and there should be (linked) lists, with a FIRST field that can take on any value, and a REST field that is restricted to only contain another linked list (including a privileged empty list object). In such a design, the whole concept of "dotted list" would be non-sensical. You could still write (a . nil) or (a . ()) but that would no longer be the same object as (a), the former being a pair and the latter being a list.

So you see the concept of dotted list is rooted entirely in an I/O hack that John McCarthy invented back in 1958 so he could build linked lists out of punned pairs rather than make them a separate data type.

> NIL is not weird, it is an ordinary symbol, like NIK or NIM

No, NIL is not an "ordinary symbol". NIL is both a symbol and a list. NIL answers T to LISTP. No other symbol does that. You can call CAR, CDR, LENGTH, ASSOC etc. on NIL and not get an error. You cannot do that with any other symbol.

NIL is the only symbol to which you cannot give a function binding. In some implementations, attempting to do so triggers its own error message:

    Clozure Common Lisp Version 1.12.1 (v1.12.1-10-gca107b94) DarwinX8664
    ? (defun nil () t)
    > Error: Using NIL as a function name is silly.
Also, NIL answers T to LISTP but not to CONSP. So you can call CAR and CDR on it but not RPLACA and RPLACD. And, at the risk of stating the obvious, NIL answers T to NULL.

NIL is the only object with these properties. That is the very definition of "weird". (And note that I have made no reference to implementation details here.)

> The matter at hand is very basic

No, it isn't, or we wouldn't be arguing about it.

Re: The empty list

#89
post #78

Earlier quoted context omitted.

You don't need to be quite so condescending. I understand all this perfectly well. But the concept of a "dotted list" has to do with how a list is serialized, not how it is represented in the internally, which is what I am talking about. NIL is weird in CL and different implementations handle this weirdness in different ways. One way to handle it is to represent NIL as a symbol whose name is "NIL" and write CAR and C…

The name "dotted list" comes from how the list is serialized, yes, but not the concept. You can write a function dotted-list-p that takes an object and returns the value of (and (consp object) (cdr (last object))). Indeed, it is not related to the NIL issue, and I made no such assumption. You can read an equivalent definition that uses different words in the CLHS glossary. You admit to talking about "how NIL is imple…

> having CAR and CDR take lists instead of conses.

(car nil) and (cdr nil) safely returning nil was introduced in InterLisp, according to Gabriel's HOPL palper. At some big Lisp summit in the early 1970's, InterLisp decided to adopt MacLisp's readtables, and MacLisp adopted (car nil) -> nil.

Why the empty list is a symbol is natural: math uses symbols to refer to such things. For instance the empty set is notated both {} and ∅: empty braces or the special null set symbol.

I mean, why have symbols refer to things in a language that is consciously oriented toward symbolic processing, whose initial creators were people with math backgrounds? It's pretty much a forgone no-brainer.

Re: The empty list

#90
post #39

Earlier quoted context omitted.

> 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…

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

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

Post reply on HN