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

101–109 of 109 posts

Re: The empty list

#101

Post by kazinator »

lisper wrote: post #100
kazinator wrote: post #99

Earlier quoted context omitted.

The former is somewhat reasonable for having pi denote 3.14159... and such. It brings in its own difficulties. If nil is a variable/constant which evaluates to some nil object, then to talk about nil itself, we have to quote it. The object which it denotes doesn't print as nil; it has its own printed rep like () and we will end up seeing that printed rep and using it. So then we have two nil representations to deal w…

> to talk about nil itself, we have to quote it. So? That's no different than if you want to talk about 'pi rather than pi a.k.a. 3.14159... > So then we have two nil representations to deal with No different than "pi" and "3.14159". > If () isn't self-evaluating (like the criminally stupid design in Scheme), we have to quote it: '(). I agree, () should be self-evaluating just like numbers and vectors. The behavior o…

> First, the list terminator need not be the same thing as the empty list.

No it doesn't, but that choice happens to give us a compact recursive definition.

> There can be multiple list terminators ... multiple empty lists ...

Sure, and 2022 can be written MMXXII, and whatnot.

Mathematically, there is one empty list, so why proliferate it?

There can be multiple empty strings which is useful if strings are mutable. If strings are immutable, it's silly to have more than one empty string.

The empty list is immutable, so ...

> under no circumstances should taking the CAR or CDR of an empty list do anything other than signal an error.

Lisp 1 and 1.5 had it that way, certainly. It's mostly just inconvenient. A good mix is to have strict vectors and strings which signal on out-of-bounds, but lists which are forgiving. Forgiving lists allow good old Ashwin Ram to have:

  (cdr (assq key a-list))
rather than

  (let ((val (assq key a-list)))
     (cond ((not (null? val)) (cdr val))
          (else nil)))

Re: The empty list

#102

Post by bjoli »

ruricolist wrote: post #9

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.

Why? It is largely inconsequential. You save a line or two, but there are bigger fish. Clos, contitions and restarts, and types change how you actually write code. Nil being false doesn't mean anything. You can save a line of code when iterating over a list, which is handy, but it lacks meaning.

Multiple namespaces are a nuisance for about one day until you have gotten used to them.

Re: The empty list

#103

Post by lisper »

kazinator wrote: post #101
lisper wrote: post #100

Earlier quoted context omitted.

> to talk about nil itself, we have to quote it. So? That's no different than if you want to talk about 'pi rather than pi a.k.a. 3.14159... > So then we have two nil representations to deal with No different than "pi" and "3.14159". > If () isn't self-evaluating (like the criminally stupid design in Scheme), we have to quote it: '(). I agree, () should be self-evaluating just like numbers and vectors. The behavior o…

> First, the list terminator need not be the same thing as the empty list. No it doesn't, but that choice happens to give us a compact recursive definition. > There can be multiple list terminators ... multiple empty lists ... Sure, and 2022 can be written MMXXII, and whatnot. Mathematically, there is one empty list, so why proliferate it? There can be multiple empty strings which is useful if strings are mutable. If…

> If strings are immutable, it's silly to have more than one empty string.

I guess Common Lisp is silly then.

    Clozure Common Lisp Version 1.12.1 (v1.12.1-10-gca107b94) DarwinX8664
    ? (eq "" "")
    NIL
> (cdr (assq key a-list))

Much better to have an abstract associative map (dictionary) type with an opaque implementation rather than punning cons cells (which locks you in to an O(n) implementation). ALists are interesting from a historical point of view but they should never be used in modern code without hiding them under a layer of abstraction.

And even if you are going to pun cons cells to build an associative map, alists are the wrong way to do it because it forces you to duplicate the keys for every frame. Much better to use D-lists ((key1 key2 ...) val1 val2 ...) because that lets you re-use the key list, which can cut your memory usage in half, and provides a much more straightforward path from interpreter to compiler for pedagogical purposes.

Re: The empty list

#104

Post by lispm »

kagevf wrote: post #94
lispm wrote: post #83

Earlier quoted context omitted.

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

Would the code to maintain a pointer on the last element look something like this? (let* ((list (list 1 2 3 4)) (last (last list))) (rplacd last (list 5 6)) (setf last (last last)) (format t "list: ~a~%last: ~a~%" list last)) => list: (1 2 3 4 5 6) last: (6)

in an iteration:

  (let* ((rlist (list '()))
         (last  list))

    (flet ((collect (item)
             (setf (cdr last) (list item)
                   last       (cdr last))
             item)
           (finish ()
             (cdr rlist)))

      (dotimes (i 10)
        (collect i))

      (finish)))

Re: The empty list

#105

Post by kagevf »

lispm wrote: post #104
kagevf wrote: post #94

Earlier quoted context omitted.

Would the code to maintain a pointer on the last element look something like this? (let* ((list (list 1 2 3 4)) (last (last list))) (rplacd last (list 5 6)) (setf last (last last)) (format t "list: ~a~%last: ~a~%" list last)) => list: (1 2 3 4 5 6) last: (6)

in an iteration: (let* ((rlist (list '())) (last list)) (flet ((collect (item) (setf (cdr last) (list item) last (cdr last)) item) (finish () (cdr rlist))) (dotimes (i 10) (collect i)) (finish)))

Thank you for the reply!

And I see that even in my original attempt, I could have used (setf (cdr)) instead of (rplacd)...

Re: The empty list

#106

Post by lispm »

lispm wrote: post #104
kagevf wrote: post #94

Earlier quoted context omitted.

Would the code to maintain a pointer on the last element look something like this? (let* ((list (list 1 2 3 4)) (last (last list))) (rplacd last (list 5 6)) (setf last (last last)) (format t "list: ~a~%last: ~a~%" list last)) => list: (1 2 3 4 5 6) last: (6)

in an iteration: (let* ((rlist (list '())) (last list)) (flet ((collect (item) (setf (cdr last) (list item) last (cdr last)) item) (finish () (cdr rlist))) (dotimes (i 10) (collect i)) (finish)))

  (let* ((rlist (list '()))
         (last  rlist))

    (flet ((collect (item &aux (cons-cell (list item)))
             (setf (cdr last) cons-cell
                   last       cons-cell)
             item)
           (finish ()
             (cdr rlist)))

      (dotimes (i 10)
        (collect i))

      (finish)))

Re: The empty list

#107

Post by kazinator »

lisper wrote: post #103
kazinator wrote: post #101

Earlier quoted context omitted.

> First, the list terminator need not be the same thing as the empty list. No it doesn't, but that choice happens to give us a compact recursive definition. > There can be multiple list terminators ... multiple empty lists ... Sure, and 2022 can be written MMXXII, and whatnot. Mathematically, there is one empty list, so why proliferate it? There can be multiple empty strings which is useful if strings are mutable. If…

> If strings are immutable, it's silly to have more than one empty string. I guess Common Lisp is silly then. Clozure Common Lisp Version 1.12.1 (v1.12.1-10-gca107b94) DarwinX8664 ? (eq "" "") NIL > (cdr (assq key a-list)) Much better to have an abstract associative map (dictionary) type with an opaque implementation rather than punning cons cells (which locks you in to an O(n) implementation). ALists are interesting…

Strings aren't immutable in Lisp, so there isn't a huge benefit to making (eq "" "").

It may be undefined behavior to modify "", but it's not the same thing. Suppose that mutating "" signals an error; that still leaves the problem that some other string which you are allowed to mutate can be mutated empty, yet is a distinct object from that empty string.

Moreover, though every string has "" as a suffix, it's not by way of pointing to a "" object. A unique "" wouldn't serve the role of terminator.

A language with immutable strings could intern all strings, so they are de facto symbol, and then exact string comparison is eq. That implies there is only one empty string object.

Re: The empty list

#108

Post by lisper »

kazinator wrote: post #107
lisper wrote: post #103

Earlier quoted context omitted.

> If strings are immutable, it's silly to have more than one empty string. I guess Common Lisp is silly then. Clozure Common Lisp Version 1.12.1 (v1.12.1-10-gca107b94) DarwinX8664 ? (eq "" "") NIL > (cdr (assq key a-list)) Much better to have an abstract associative map (dictionary) type with an opaque implementation rather than punning cons cells (which locks you in to an O(n) implementation). ALists are interesting…

Strings aren't immutable in Lisp, so there isn't a huge benefit to making (eq "" ""). It may be undefined behavior to modify "", but it's not the same thing. Suppose that mutating "" signals an error; that still leaves the problem that some other string which you are allowed to mutate can be mutated empty, yet is a distinct object from that empty string. Moreover, though every string has "" as a suffix, it's not by w…

> Strings aren't immutable in Lisp

Neither are lists. Only the empty list is immutable, and likewise empty strings. It really is a completely equivalent situation. There is no principled reason that the empty list should be unique and the empty string not.

Re: The empty list

#109

Post by kazinator »

lisper wrote: post #108
kazinator wrote: post #107

Earlier quoted context omitted.

Strings aren't immutable in Lisp, so there isn't a huge benefit to making (eq "" ""). It may be undefined behavior to modify "", but it's not the same thing. Suppose that mutating "" signals an error; that still leaves the problem that some other string which you are allowed to mutate can be mutated empty, yet is a distinct object from that empty string. Moreover, though every string has "" as a suffix, it's not by w…

> Strings aren't immutable in Lisp Neither are lists. Only the empty list is immutable, and likewise empty strings. It really is a completely equivalent situation. There is no principled reason that the empty list should be unique and the empty string not.

Yes there is a principled reason. If we accept that we have a list which is recursively defined using a binary cell aggregate structure, as a right-leaning tree shape, then it is advantageous to have an atomic, unique empty list at the bottom of the recursion. That atomic empty list can be represented as a machine word. We can perform a single comparison to detect the terminator: is it that object or not? Anything else, though workable, is a gratuitous complication.

The empty string is mutable. Even the literal one is potentially mutable: you can try it at your own risk. You ca make a mutable empty string with (make-string 0) or by mutating a non-empty string.

Any mutable string can be mutated to make it empty:

   (delete #\a (make-string 3 :initial-element #\a)) -> ""
Since strings aren't linked structures with a terminator, the comparison is moot.
Post reply on HN