Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The empty list

tfeb.org

Post reply on HN
Print view View original

71–80 of 109 posts

Re: The empty list

#71

Post by bhk »

gumby wrote: post #16

I like that the article was non judgement. The real world is messy and Common Lisp formalized existing practice among several branches of an already old language from before programming language theory. There are a number things worth “fixing” and it’s delightful that so much interest and implementation in this regard has been sustained for so long. But to the ideologues, I can only quote Emerson: "A foolish consiste…

To help someone learn to use a language, we should be judgemental and call special attention to all of its shortcomings and gotchas. I don't see value in sweeping them under the rug. That kind of language advocacy is a zero-sum game (or negative-sum).

For example:

> ... it is not at all strange that there is an object whose type is both list and symbol.

Actually, it is strange, and unfortunate. One should think about examples of code that might store different types of values in a variable or data structure, using e.g. `symbolp` and `listp` to distinguish the different representations, and consider how the collision between the symbol nil and empty list could produce unexpected behavior. One must be aware and remain vigilant.

> the things which are not necessary are that it be a symbol, and that it represent falsity.

Other non-necessary things: `car` and `cdr` special cases for `()`, self-evaluating `()`.

> CL requires precisely one implementationally-weird object, while Scheme requires two, or three if you count #t

There is nothing intrinsically weird about having an empty list object. The only thing weird about it is the behavior of `car`, `cdr`, and `symbolp` in CL.

Also, there is nothing weird about having a proper boolean type. On the other hand, if CL's `(type-of 't)` actually returns `boolean` and not `symbol`, as the article indicates, then that is indeed weird.

Re: The empty list

#72

Post by gumby »

bhk wrote: post #71
gumby wrote: post #16

I like that the article was non judgement. The real world is messy and Common Lisp formalized existing practice among several branches of an already old language from before programming language theory. There are a number things worth “fixing” and it’s delightful that so much interest and implementation in this regard has been sustained for so long. But to the ideologues, I can only quote Emerson: "A foolish consiste…

To help someone learn to use a language, we should be judgemental and call special attention to all of its shortcomings and gotchas. I don't see value in sweeping them under the rug. That kind of language advocacy is a zero-sum game (or negative-sum). For example: > ... it is not at all strange that there is an object whose type is both list and symbol. Actually, it is strange, and unfortunate. One should think about…

If you want that kind of clarity, use another lisp, like Scheme, that doesn't have the legacy quirks. There are plenty to choose from that make different choices.

That's kind of my point.

Re: The empty list

#73

Post by bombolo »

shadowgovt wrote: post #61
chrisweekly wrote: post #49

Earlier quoted context omitted.

I'm not familiar with the "scorpion in a jar" idiom; guessing it's something like [to kill the scorpion you have to open the jar]... care to elucidate?

It's a reference to the "Codeless Code" link I shared upthread: 'All nothings are not equal.' A language that supports null and empty list as separate things opens the risk "what happens when the user passes null to something expecting a list?" It is, at least, something a language with good static typing can mitigate by disallowing null as a list argument. And then there's Java...

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

Re: The empty list

#74

Post by hayley-patton »

NoboruWataya wrote: post #18

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…

> 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

You can, but appending some list L and an empty list, or an empty list and L yields L in either case; there's nothing to append. Subsequent appends will be more interesting, e.g.

    CL-USER> (append '(x) (append '(y z) '()))
    (X Y Z)
> The empty list is nil, and `(append nil foo)` seems to just yield `foo`, not `(list foo)`

Right. Conceptually APPEND appends lists and not bare elements; try (append '() '(foo))

Re: The empty list

#75

Post by Jtsummers »

NoboruWataya wrote: post #18

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, you see the same pattern in Erlang and others
Pushing (and popping) work on the front of lists. Counterintuitively, vector-push and vector-pop work on the end of the vector (though the rationale around performance is the same,). By pushing/popping on the front of the list the action can be done in constant time. `push item place` is equivalent to this whether it's precisely this under the hood for an implementation or not:

  (setf place (cons item place))
Pop is this:

  (prog1
    (car place)
    (setf place (cdr place)))
(Maybe I've been spending too much time in the hyper spec, my equivalence examples could have been copy/pasted from it and I wrote them before double checking.)

Pop: http://clhs.lisp.se/Body/m_pop.htm#pop

Push: http://clhs.lisp.se/Body/m_push.htm#push

Re: The empty list

#76

Post by shadowgovt »

bombolo wrote: post #73
shadowgovt wrote: post #61

Earlier quoted context omitted.

It's a reference to the "Codeless Code" link I shared upthread: 'All nothings are not equal.' A language that supports null and empty list as separate things opens the risk "what happens when the user passes null to something expecting a list?" It is, at least, something a language with good static typing can mitigate by disallowing null as a list argument. And then there's Java...

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 that in JavaScript (and Java), every argument that takes an array could also take null and mean something different by it, triggering a runtime error as a result, is a design foot-gun. Rarely are both null and [] as different symbols appropriate; those languages made that a by-default-always-allowed feature.

Re: The empty list

#77

Post by creepycrawler »

lisper wrote: post #39
creepycrawler wrote: post #31

Earlier quoted context omitted.

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

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

Re: The empty list

#78

Post by lisper »

creepycrawler wrote: post #77
lisper wrote: 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.…

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 CDR to recognize when they see this symbol and return it. Another way to handle it is to represent NIL as a cons cell whose CAR and CDR point to itself and write SYMBOLP and SYMBOL-NAME to recognize when they see this privileged cons cell and return T and "NIL" respectively. (There are a lot of other special cases -- this is not an exhaustive list.)

However you slice it, the concept of a dotted list is a non-sequitur because that has NOTHING to do with how NIL is implemented internally, which what I am talking about.

Re: The empty list

#79

Post by kazinator »

bhk wrote: post #71
gumby wrote: post #16

I like that the article was non judgement. The real world is messy and Common Lisp formalized existing practice among several branches of an already old language from before programming language theory. There are a number things worth “fixing” and it’s delightful that so much interest and implementation in this regard has been sustained for so long. But to the ideologues, I can only quote Emerson: "A foolish consiste…

To help someone learn to use a language, we should be judgemental and call special attention to all of its shortcomings and gotchas. I don't see value in sweeping them under the rug. That kind of language advocacy is a zero-sum game (or negative-sum). For example: > ... it is not at all strange that there is an object whose type is both list and symbol. Actually, it is strange, and unfortunate. One should think about…

Lisp dialects that have deviated from these choices require the programmer to write hideously verbose code, unable to take advantage of the economic idioms they afford.
Post reply on HN