[HN Gopher] The empty list
___________________________________________________________________
The empty list
Author : todsacerdoti
Score : 65 points
Date : 2022-12-17 15:05 UTC (7 hours ago)
(HTM) web link (www.tfeb.org)
(TXT) w3m dump (www.tfeb.org)
| ruricolist wrote:
| Personally I feel about Scheme's distinction between false and
| the empty list the way Schemers feel about CL's distinction
| between variables and functions.
| neilv wrote:
| An annoying thing about `nil` is when it stomps a namespace in
| which you're using symbols, such as in a minilanguage, by being
| read as the nil value rather than as the symbol `nil`.
|
| Besides it being obvious, I actually ran into this in a real-
| world situation, with some super-rapid work on a dataset of only
| about 100 entries, where it turned out one user's real name had
| the initials N.I.L.
| pfdietz wrote:
| You should not have been reading that in a package that
| inherited from COMMON-LISP. Did you really want user names that
| happened to be COMMON-LISP symbols to collide?
| neilv wrote:
| That time was in Emacs Lisp. And it was very rapid-convenient
| to be using symbols.
|
| When I moved to Scheme, I liked that it didn't have that
| particular collision. Though quasiquoting had some collisions
| unnecessarily (when they already had precedent of using the
| `#` character to introduce special values).
| gumby wrote:
| 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
| consistency is the hobgoblin of little minds, adored by little
| statesmen and [programming] philosophers and divines."
| JoelMcCracken wrote:
| I like the way scheme does it, but IMO this is one of the least
| significant reasons scheme choices are much preferable to cl imo.
| It's just a much cleaner, friendlier language overall
| tmtvl wrote:
| I really like Scheme, though the Common Lisp type system has
| completely won me over (especially with defstar).
| djha-skin wrote:
| It's very difficult to deserialize in serialize things like yaml
| and json in CL because it doesn't have a distinct false object.
| When you do deserialize `false` it turns into nil. Then when you
| serialize it back again it turns into `null`. From a practical
| perspective, this is annoying.
|
| I don't hate using it as a language, it's fine, but because it's
| different enough than other languages it confuses people.
| User23 wrote:
| I agree that it's annoying. It is possible to work around
| without too much trouble by defining some other constant that
| evaluates to nil to distinguish.
| dragonwriter wrote:
| > It's very difficult to deserialize in serialize things like
| yaml and json in CL because it doesn't have a distinct false
| object.
|
| Its not particularly hard to represent JSON's type system in CL
| and deserialize JSON to CL objects.
|
| Its also not particularly hard to construct and use a model of
| CL data in JSON from CL. (Its even easier with YAML.)
|
| OTOH, yes, JSONs data model is almost exactly JS's data model
| (minus anything callable, which js a lot of JS, and with a
| slightly different model of numbers, but anything that doesn't
| exactly match JS's model is canonically unreliable and so
| discouraged), So with any thing other than JS using JSON, you
| have to determine if your use case is modeling your language's
| data in JSON or JSON's data model in your language, while with
| a particular subset of JS you can just ignore the distinction.
| stassats wrote:
| > it's different enough than other languages it confuses
| people.
|
| And javascript integers (or lack thereof) don't match CL
| integers. So if you want to interoperate between distinct
| languages you do have to consider the differences anyway.
| lisper wrote:
| I share your frustration, particularly since one could add a
| canonical false value to CL in a backwards-compatible way. But
| it's too late now.
|
| But as a practical solution you could de-serialize false into,
| say, :false, in order to distinguish them from empty lists, and
| then do a post-processing step to turn those into nils if you
| wanted to.
| kmstout wrote:
| > you could de-serialize false into, say, :false ...
|
| That's the approach that st-json [0] builds on:
|
| - true and false become :true and :false, respectively
|
| - [] becomes nil
|
| - {} becomes #s(st-json:jso :alist nil)
|
| ---
|
| [0] in QuickLisp and at https://github.com/marijnh/ST-JSON
| lisper wrote:
| Yeah, good point. IMHO the lack of a canonical
| serialization for hash tables is a much more serious
| omission than not having a separate boolean false value.
| thomastjeffery wrote:
| > in a backwards-compatible way. But it's too late now.
|
| You just contradicted yourself.
| lisper wrote:
| 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.
| ykonstant wrote:
| >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?
| lisper wrote:
| Personally I do all my personal coding in CL but it's a
| matter of taste. Another word for "moribund" is "stable"
| and that can be a good thing. But it really is mostly
| personal preference. And you might want to add Clojure to
| your list of languages to consider.
|
| The reason I like CL is that I find it is a local optimum
| impedance match for my brain in language design space.
| But that is at least in part because I have been using it
| for 35 years so I am used to its quirks (of which there
| are many). But it also has lots of really nice features,
| some of which are still unique to CL and which I find
| indispensable to my coding style. Generic functions are
| at the top of that list, and a close second is the macro
| system.
| baq wrote:
| I'm afraid you're confusing 'stable' with 'stagnant'.
| (The dictionary suggests 'dying'... I won't go there ;))
| lisper wrote:
| CL is not stagnant. SBCL and Quicklisp are still active,
| and Franz is still a going concern.
| rhn_mk1 wrote:
| Serialization formats not designed specifically for the
| language should not be treated as serializers for objects in
| that language.
|
| That is, JSON is not a representation of objects in your
| language. It's your application that holds a representation of
| JSON data. If you're not paying attention to the translation
| layer between your native objects and the JSON ones, you'll hit
| problems sooner or later.
| scatters wrote:
| JSON is the JavaScript Object Notation; it's in the name! The
| closer your language's object model is to JavaScript, the
| more likely it is you'll get away with treating it as a
| direct serialization format. Conversely, the further your
| language is from JavaScript, the more you'll need to add
| types specifically to represent JSON.
| shadowgovt wrote:
| Yep. It's probably the case that one should have a more
| complicated serializer / deserializer for JSON in CL (one that
| takes into account the expected JSON datatypes) because JSON is
| yet another type and value system from Scheme's and CL's, but
| there's an isomorphism from the Scheme one to the JSON one and
| there's no such similar isomorphism for the primitive CL types
| (though were one so inclined, one could certainly build one in
| one's own application).
|
| I'd be willing to argue that this is indicative of JSON's
| unnecessary complexity (inherited from its source language...
| why does JavaScript need a false _and_ an empty array _and_ a
| null and _even_ an undefined?), but reasonable developers can
| disagree on that point.
| bombolo wrote:
| You want empty lists because you can't iterate a null. So an
| empty list should be an empty list, otherwise it will require
| special code to check for the null case.
| shadowgovt wrote:
| Do you mean you can't iterate a null in JavaScript or in
| LISP?
|
| You can't iterate a null in JavaScript, but that's a design
| decision of the language that could have gone another way;
| `for (const elem of null) {do();}` could have been
| specified to be valid JavaScript that never calls `do()`,
| but it wasn't because it wasn't.
| bombolo wrote:
| Well if you could iterate a null, you'd also be able to
| sum 2 nulls. And you'd need null to carry a length (of
| zero, I presume).
| shadowgovt wrote:
| Correct. Which could, of course, all be defined.
|
| - null + null === null ; list + null === list; null +
| list === list
|
| - null.length === 0 /* should probably make it a runtime
| error to write this property, or allow it but have the
| result be a list with length elements, all undefined */
|
| (Note: somewhat hilariously, null + null is already
| defined in JavaScript. It, of course, is 0. Wat. ;) )
|
| Whether null and empty list should be different or the
| same is an old argument, and both directions lead to
| different problems. http://thecodelesscode.com/case/6
| bombolo wrote:
| Why not just have empty lists instead of null then? :D
| Seems simpler.
| shadowgovt wrote:
| I agree. I use quite a few languages that don't have the
| "scorpion in a jar" problem where an argument might be an
| empty list or null (some that address it with static
| typing, some where the two values are the same value).
| chrisweekly wrote:
| 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?
| shadowgovt wrote:
| 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...
| adwn wrote:
| > _why does JavaScript need a false and an empty array and a
| null and even an undefined?)_
|
| Why does Lisp need a 0 and a nil? Because numbers are
| conceptually different from lists, and the number 0 is
| conceptually different from no number at all.
|
| Why does JavaScript need a false and an empty array and a
| null and an undefined? Because all of those represent
| different concepts. Trying to stuff as many concepts as
| possible into a single representation doesn't necessarily
| make a language better (though I'm certainly not claiming
| that JavaScript is the epitome of good language design).
| tlarkworthy wrote:
| There is no undefined value in JSON. (Of course ommitting
| something is like an undefined)
|
| https://stackoverflow.com/questions/13796751/json-
| undefined-...
| mik1998 wrote:
| I don't see the benefit of the Scheme approach at all. As far as
| I'm concerned, the empty list being also the false object makes
| certain list functions more elegant to implement and it is mostly
| irrelevant elsewhere.
| cratermoon wrote:
| The Null Object[1] is a useful thing. It can represent the
| behavior when there's no correct behavior. It exists in languages
| like SmallTalk as well as LISP and LISP-derived languages.
|
| In Go, you can call methods on nil objects. [2]
|
| 1 https://wiki.c2.com/?NullObject
|
| 2 https://go.dev/play/p/mgayNTjdacL
| lisper wrote:
| > 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.
| Chinjut wrote:
| If NIL were a CONS, how would you distinguish between an empty
| list and a list of length one containing NIL?
| lisper wrote:
| The same way you do now: (NIL) would not answer true to NULL.
| And it would not be EQ to NIL.
| Chinjut wrote:
| 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)?
| tmtvl wrote:
| 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 wrote:
| 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.
| lisper wrote:
| 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).
| rosebay wrote:
| 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 wrote:
| 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.
| creepycrawler wrote:
| 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 wrote:
| > 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 wrote:
| 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 wrote:
| > 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.
| mtreis86 wrote:
| In other words CL-USER> (equalp '(1 2 3)
| '(1 . (2 . (3 . nil)))) => T
| NoboruWataya wrote:
| 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 object
| will (probably) raise an error.
| tuukkah wrote:
| append concatenates lists so you'd need (append nil '(foo))
| DonaldFisk wrote:
| It actually leaves both its arguments unaltered and creates a
| new list. There's another function called nconc which does
| concatenate them, changing its first argument to the new list
| (unless its first argument is NIL).
| aidenn0 wrote:
| Note that append does not copy the last argument, so there
| is structure sharing when you use it.
| DonaldFisk wrote:
| The easiest way to think about this, as Tim mentions in his
| article, is that in Common Lisp, you can write nil as '(), so
| if foo is defined as the list (d e f), (append nil foo) is
| equivalent to (append '() '(d e f)) which more obviously
| evaluates to (d e f), just as (append '(a b c) '(d e f))
| evaluates to (a b c d e f). It's better to think of Lisp
| append's first argument being appended onto its second: (append
| '(a b) '(c d)) => (cons 'a (append '(b) '(c d))) => (cons 'a
| (cons 'b (append '() '(c d)))) => (cons 'a (cons 'b '(c d))) =>
| (cons 'a '(b c d)), which evaluates to (a b c d). The lists '(a
| b) and '(c d) are still unaltered at the end of the
| computation, and a new list '(a b c d) is returned by the call
| to append.
| todd8 wrote:
| What is AOC? It's hard to keep up with all the acronyms.
| Thiez wrote:
| https://adventofcode.com/
| todd8 wrote:
| Thanks I was just on that website!
| aidenn0 wrote:
| Lists in python are what are called vectors in almost every
| other language.
|
| You can make a resizable vector in CL and use vector-push-
| extend to do things just like python.
| shadowgovt wrote:
| In LISP, the cheap / straightforward operation is attaching
| things to the front of a list.
|
| Appending to the rear of a list is (usually) going to be the
| more expensive operation (naively, doing so requires walking
| all the way to the end of the list, because lists are more like
| linked list constructs than arrays that silently resize as
| needed).
| TheOtherHobbes wrote:
| 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 list)
| pairs.
|
| Lisp's dot notation makes this explicit, but it's hidden behind
| syntactic sugar because it's messy and hard to read.
| (a b c) is really (a . (b . (c . NIL)))
|
| Each dot shows the cdr of the preceding car.
|
| On its own NIL is just a constant. It has no listy features -
| specifically no slots for car or cdr values. Although you can
| do things like (length NIL) you can't _change_ it. It 's simply
| not a list.
|
| You can add car/cdr pointers to it with cons. Now you can use
| NIL in a list.
|
| You can use NIL as a cdr list terminator. (something . NIL)
| means the list is over. There are no more cdrs after it.
|
| You can use NIL as an empty car placeholder. (NIL . something)
| means the car has no value, but the list continues onwards with
| a cdr link.
|
| In your example (append NIL foo) actually returns (foo . NIL).
| NIL is being used as a cdr terminator. Lisp hides the ". NIL"
| because syntactic sugar.
|
| If you (append NIL foo) again, you still get (foo) because NIL
| already terminates the list and there's no reason to add
| another NIL after it.
|
| (push foo NIL) throws an error because push is destructive and
| is attempting to change NIL. Which isn't allowed.
|
| (cons NIL a) gives you (NIL a) because NIL is being prepended
| as an empty car pointer. This is how you get NILs into a list
| without it collapsing around itself.
|
| Anyway. This is confusing because you have a single symbol
| doing three different things in three different contexts.
| Worse, syntactic sugar and the various function internals hide
| this from you. And the documentation tells you something that
| isn't true.
|
| So unless you look at the source and/or learn how the various
| functions understand and use NIL you will be confused.
|
| The up side is a REPL is interactive and easy to play with, so
| it's not a huge effort to experiment and see what falls out.
| martinflack wrote:
| APPEND is for concatenating two lists. If you're trying to add
| a value, then if your NIL is already in a variable, use PUSH to
| add the value (to the front). This will build the result list
| in reverse, so you can NREVERSE it at the end.
| User23 wrote:
| There's a relatively straightforward deque implementation too
| if you need to append in addition to pushing. It can require
| a little rebalancing, but I imagine it amortizes to constant
| time.
| gus_massa wrote:
| I think what you want to do is (cons 'foo nil)
|
| It's in the oposite order. It starts with the empty list and it
| adds foo in the head.
|
| An extension is (cons 'bar (cons 'foo nil))
|
| that is equivalent to (list 'bar 'foo)
| pfdietz wrote:
| The section on the `t` value could also have added that in the
| Common Lisp standard, there are a great many functions that
| returns a boolean value. When they return a true value, all that
| is required is that they return a value that isn't nil. This
| could be `t`, and often is, but is not required to be.
|
| There are only a few forms that are required to return `t` for
| true, calls to the functions `not` and `null` being two of them.
| So, to coerce a true to `t`, one does `(not (not <form>))`.
| [deleted]
| tuukkah wrote:
| TLDR (at the end): "Certainly the CL approach carries more
| historical baggage."
|
| > _Combining the empty list and the special false object can lead
| to particularly good implementations perhaps._
|
| I suppose they wanted the null pointer to represent them both in
| RAM, because every CPU has an instruction to test whether a value
| is zero, or even a flag that is set for free when you encounter
| the value.
| lisper wrote:
| That's one reason. Another is that it allows you to use the
| idiom (if X ...) to test for non-null rather than (if (not
| (null X)) ...)
| tuukkah wrote:
| Indeed, although some languages achieve the same by defining
| multiple falsy values, e.g. JS has 9 such values:
| https://developer.mozilla.org/en-US/docs/Glossary/Falsy
| lisper wrote:
| Yeah, but this causes its own set of problems when, for
| example, you are surprised that 0.0 is false but -0.0 is
| true.
|
| In general, punning of any kind is a Really Bad Idea when
| code gets complicated.
___________________________________________________________________
(page generated 2022-12-17 23:00 UTC)