6 ms·

Erik Naggum's writings were pretty influential on me as a young programmer, and there's still some value in this piece, but nowadays I find a lot of this insuff

Erik Naggum's writings were pretty influential on me as a young programmer, and there's still some value in this piece, but nowadays I find a lot of this insufferable. Yes, it's not actually easy to implement lists, and there's semantic value to Common Lisp's implementation. But... 1. You can't tout the benefits of constant time appending to the beginning of a list while ignoring the benefits of constant time lookup and modification within the list. And before anyone starts talking about "but most programs don't need random access because you just traverse the list"--yes, and vectors do that better too because of cache locality. Cache-aware implementations of Lisps are still an order of magnitude slower than vectors for traversals because dereferencing the cdr pointer is obligatory. If you start talking about speed being a benefit of Lisp in comparison to C (a comparison which Naggum introduces later here), you've lost the plot. 2. Nostalgia for an architecture that no longer existed even in 1998 when this was written is poor reasoning for opaque names. "car" and "cdr" aren't good names. It kind of doesn't matter much: once you learn them it's fine, but it is a slight barrier to Lisp's success, as it does present yet another small challenge for beginning Lisp programmers. 3. In general, the ragging on Scheme is rather pointless--I found my way to Lisp via Scheme. And a large part of why I ended up back in Scheme land (well, Racket by that point) was that it became clear to me that the Scheme community benefits from ideas learned in Common Lisp, while Common Lisp often (not always) rejects NIH ideas.

pfdietz 2y ago
It would be trivial to replace car and cdr in your code with any other symbol names you like. Even the Common Lisp standard supplies alternatives (first, rest). If this was not done, it was because people using lisp didn't see any great value in doing it.
- Majromax 2y ago
  Your point and the grandparent's point are not contradictory. 'car' and 'cdr' can be opaque pieces of jargon that make the language slightly but noticeably more difficult for new learners, and they also can be standard pieces of jargon that current users would find no value in changing. In that way, it's a bit like indentation in Python.
  - pfdietz 2y ago
    I think this illustrates that perceived shallow blemishes that upset newbies have nothing to do with success or failure of a programming language. Another example here is "all those parentheses", and perhaps even lack of static typing.
    - kerkeslager 2y ago
      It's a shallow blemish yes. I wouldn't say is has nothing to do with the success or failure--but as I said in my post, it kind of doesn't matter much. The problem I have here is this total unwillingness to admit that it is a blemish. Like because Common Lisp did it, it can't be wrong, so we have to come up with bizarre justifications for this like pretending some ancient hardware architecture is better than today's "braindamaged" CPUs.
      - pfdietz 2y ago
        I don't think anyway says it isn't a blemish. The point being made is that it's a trivial, irrelevant, and unimportant blemish.
        kerkeslager 2y ago
        The way Naggum presents it, it's as if it is not only not a blemish, but a work of genius.
        pfdietz 2y ago
        If I wanted to nitpick, I'll point out that I used "says", not "said". In the present tense, Naggum can no longer say anything at all. :/
  - zahlman 2y ago
    I would say that it's more like the `def` keyword in Python. People learn that it's short for "define" - but that doesn't make much sense given that other kinds of things can perfectly well be "defined". It also leads to beginners expressing themselves weirdly - I've read things like "so I have a defined function like so:" countless times.
rjsw 2y ago
Lisp has had vectors as well as lists for a long time. If you want a vector then use a vector.
- Jach 2y ago
  Yup, though usual caveats on if the item stored is itself a fat object requiring a pointer chase... SIMD exists as well, SBCL has it available out of the box through sb-simd. SBCL also tries to be a bit smart with its linked lists: when first making a list, if you make it sequentially (make the cons cells sequentially), it'll all be allocated sequentially. And regardless of that, when the garbage collector moves a list, its new location will be sequential. The OCaml people at Jane Street noted that if you just focus on cache lines, the overhead these days between list traversal vs. vector traversal can be closer to a factor of 2. Like 16 cycles vs. 30 cycles for a new cache line on an old Skylake architecture, thanks to prefetching -- explicit prefetching instructions are hard to get right, but CPUs have also gotten better in the last 10 years at automatic prefetching. (It might be even better on Apple's architecture which I believe has more line fill buffers?) A miss is still around 300 cycles though, and a cache line of 64 bytes very typically represents more than one item (e.g. 8 longs).
  - kerkeslager 2y ago
    > Yup, though usual caveats on if the item stored is itself a fat object requiring a pointer chase... SIMD exists as well, SBCL has it available out of the box through sb-simd. SBCL also tries to be a bit smart with its linked lists: when first making a list, if you make it sequentially (make the cons cells sequentially), it'll all be allocated sequentially. And regardless of that, when the garbage collector moves a list, its new location will be sequential. This is the sort of thing that I was referring to when I referred to "cache-aware implementations of Lisps".
- kerkeslager 2y ago
  This is obvious and irrelevant.
AnimalMuppet 2y ago
> And before anyone starts talking about "but most programs don't need random access because you just traverse the list"--yes, and vectors do that better too because of cache locality. Valid, though at the time (even 1998!) caches were less critical for performance than they are now, because the gap between processing speed and main memory speed was smaller. In fact, on the machines where Lisp originated, there was no cache.
- lispm 2y ago
  Lisp programs often needed large amounts of virtual memory. Factor ten (VM size vs. RAM size) was not unheard. RAM was basically a cache for that.
- kerkeslager 2y ago
  I am not sure of the architecture of the machines where Lisp originated, but for all the computers I had access to in 1998, the gap between memory speed and virtual memory speed was relevant. So perhaps I should have just said "locality" and not "cache locality". It's hard for me to imagine any sane architecture where using more memory and having if fragmented rather than contiguous is going to perform as well as using a contiguous block of memory. And to be clear, I'm not saying there are no upsides. Cons cells are very effective as a minimal yet highly expressive data structure. All I'm saying is that this post by Naggum, and a lot of writing about Common Lisp and other Lisps, pick out the upsides and present them as if they're all that exists, when the reality is that the choices described here are tradeoffs. Sometimes (often, even!) the tradeoffs are worth it. Sometimes they aren't. That doesn't fit the narrative that Lisp is god's gift to McCarthy who then gifted it to humanity, but it is reality.
  - lispm 2y ago
    > It's hard for me to imagine any sane architecture where using more memory and having if fragmented rather than contiguous is going to perform as well as using a contiguous block of memory. Yet many of the language runtimes are actually following the Lisp model. Just that it's there not the cons cell with two slots, but arrays and objects with slots. A Java program is a multitude of dynamically allocated objects with one or more slots, where many of the slots contain pointers to other objects. The memory management is done by the runtime (and, usually, its garbage collector). > Sometimes they aren't. That doesn't fit the narrative that Lisp is god's gift to McCarthy who then gifted it to humanity, but it is reality. Other than what you might think (and set up as a strawman), that's well known and the evolution of Lisp is also showing how the implementations had to deal with this problem. The LISP 1 implementation introduced mark&sweep garbage collection (-> McCarthy). As a reaction to it Collins proposed "reference counting" as another way to manage&reclaim allocated memory. Over time early Lisp programs (Macsyma is an example often mentioned) were problematic on multi-user time-shared machines. One reaction to that was to develop single user workstations for Lisp, where all the memory was available to a single user. There one then used large virtual memory, which still made memory access (for example during garbage collection) time consuming. A GC run of a large heap in VM could run for 30 minutes making the computer mostly unusable during that time. Vectors/Arrays and OOP objects then also used the model of dynamic allocation with many referenced objects (unless they were of some primitive types). Generational GCs, compacting GCs, hardware-supported GCs, etc. were invented and implemented. Full GCs through virtual memory heaps were rare then. The availability of cheaper RAM made it possible that more of the large heaps fit into RAM. Lisp implementations early on added vectors and other data structures. But they still often need pointers. A vector of records (called structures in Common Lisp) is usually a vector with pointers to records. For example Common Lisp implementations usually will not provide vectors of inline records. A vector of fixnums OTOH will be a vector without pointers -> the fixnums will be stored directly in the vector. In the end a Lisp heap is a huge graph of objects referencing other objects. This does not only effect CONS cells, but also vectors, arrays, records, ... -> they also reference other, non-primitive, objects via pointers. That's not very different from any other language runtime which uses dynamic memory allocation and a heap of linked objects (-> Java, JavaScript, ...). The problem of dealing/avoiding non-locality and pointer-chasing is there, too.
akater 2y ago
An ordered pair is a useful data structure, and it's beneficial to have special short names for accessors to its elements. Humanity got very lucky with the names “car” and “cdr”. Naggum does point that out. Any rule about any language could be labeled a barrier to its success because any such rule contributes to the cognitive load, making learning the language slightly more difficult than it would be without that rule. What matters more is how much cognitive load is there after you learn the rules. Common Lisp is very successful at it.

pfdietz 2y ago

It would be trivial to replace car and cdr in your code with any other symbol names you like. Even the Common Lisp standard supplies alternatives (first, rest). If this was not done, it was because people using lisp didn't see any great value in doing it.

Majromax 2y ago
Your point and the grandparent's point are not contradictory. 'car' and 'cdr' can be opaque pieces of jargon that make the language slightly but noticeably more difficult for new learners, and they also can be standard pieces of jargon that current users would find no value in changing. In that way, it's a bit like indentation in Python.
- pfdietz 2y ago
  I think this illustrates that perceived shallow blemishes that upset newbies have nothing to do with success or failure of a programming language. Another example here is "all those parentheses", and perhaps even lack of static typing.
  - kerkeslager 2y ago
    It's a shallow blemish yes. I wouldn't say is has nothing to do with the success or failure--but as I said in my post, it kind of doesn't matter much. The problem I have here is this total unwillingness to admit that it is a blemish. Like because Common Lisp did it, it can't be wrong, so we have to come up with bizarre justifications for this like pretending some ancient hardware architecture is better than today's "braindamaged" CPUs.
    - pfdietz 2y ago
      I don't think anyway says it isn't a blemish. The point being made is that it's a trivial, irrelevant, and unimportant blemish.
      - kerkeslager 2y ago
        The way Naggum presents it, it's as if it is not only not a blemish, but a work of genius.
        pfdietz 2y ago
        If I wanted to nitpick, I'll point out that I used "says", not "said". In the present tense, Naggum can no longer say anything at all. :/
- zahlman 2y ago
  I would say that it's more like the `def` keyword in Python. People learn that it's short for "define" - but that doesn't make much sense given that other kinds of things can perfectly well be "defined". It also leads to beginners expressing themselves weirdly - I've read things like "so I have a defined function like so:" countless times.

rjsw 2y ago

Lisp has had vectors as well as lists for a long time. If you want a vector then use a vector.

Jach 2y ago
Yup, though usual caveats on if the item stored is itself a fat object requiring a pointer chase... SIMD exists as well, SBCL has it available out of the box through sb-simd. SBCL also tries to be a bit smart with its linked lists: when first making a list, if you make it sequentially (make the cons cells sequentially), it'll all be allocated sequentially. And regardless of that, when the garbage collector moves a list, its new location will be sequential. The OCaml people at Jane Street noted that if you just focus on cache lines, the overhead these days between list traversal vs. vector traversal can be closer to a factor of 2. Like 16 cycles vs. 30 cycles for a new cache line on an old Skylake architecture, thanks to prefetching -- explicit prefetching instructions are hard to get right, but CPUs have also gotten better in the last 10 years at automatic prefetching. (It might be even better on Apple's architecture which I believe has more line fill buffers?) A miss is still around 300 cycles though, and a cache line of 64 bytes very typically represents more than one item (e.g. 8 longs).
- kerkeslager 2y ago
  > Yup, though usual caveats on if the item stored is itself a fat object requiring a pointer chase... SIMD exists as well, SBCL has it available out of the box through sb-simd. SBCL also tries to be a bit smart with its linked lists: when first making a list, if you make it sequentially (make the cons cells sequentially), it'll all be allocated sequentially. And regardless of that, when the garbage collector moves a list, its new location will be sequential. This is the sort of thing that I was referring to when I referred to "cache-aware implementations of Lisps".
kerkeslager 2y ago
This is obvious and irrelevant.

AnimalMuppet 2y ago

> And before anyone starts talking about "but most programs don't need random access because you just traverse the list"--yes, and vectors do that better too because of cache locality. Valid, though at the time (even 1998!) caches were less critical for performance than they are now, because the gap between processing speed and main memory speed was smaller. In fact, on the machines where Lisp originated, there was no cache.

lispm 2y ago
Lisp programs often needed large amounts of virtual memory. Factor ten (VM size vs. RAM size) was not unheard. RAM was basically a cache for that.
kerkeslager 2y ago
I am not sure of the architecture of the machines where Lisp originated, but for all the computers I had access to in 1998, the gap between memory speed and virtual memory speed was relevant. So perhaps I should have just said "locality" and not "cache locality". It's hard for me to imagine any sane architecture where using more memory and having if fragmented rather than contiguous is going to perform as well as using a contiguous block of memory. And to be clear, I'm not saying there are no upsides. Cons cells are very effective as a minimal yet highly expressive data structure. All I'm saying is that this post by Naggum, and a lot of writing about Common Lisp and other Lisps, pick out the upsides and present them as if they're all that exists, when the reality is that the choices described here are tradeoffs. Sometimes (often, even!) the tradeoffs are worth it. Sometimes they aren't. That doesn't fit the narrative that Lisp is god's gift to McCarthy who then gifted it to humanity, but it is reality.
- lispm 2y ago
  > It's hard for me to imagine any sane architecture where using more memory and having if fragmented rather than contiguous is going to perform as well as using a contiguous block of memory. Yet many of the language runtimes are actually following the Lisp model. Just that it's there not the cons cell with two slots, but arrays and objects with slots. A Java program is a multitude of dynamically allocated objects with one or more slots, where many of the slots contain pointers to other objects. The memory management is done by the runtime (and, usually, its garbage collector). > Sometimes they aren't. That doesn't fit the narrative that Lisp is god's gift to McCarthy who then gifted it to humanity, but it is reality. Other than what you might think (and set up as a strawman), that's well known and the evolution of Lisp is also showing how the implementations had to deal with this problem. The LISP 1 implementation introduced mark&sweep garbage collection (-> McCarthy). As a reaction to it Collins proposed "reference counting" as another way to manage&reclaim allocated memory. Over time early Lisp programs (Macsyma is an example often mentioned) were problematic on multi-user time-shared machines. One reaction to that was to develop single user workstations for Lisp, where all the memory was available to a single user. There one then used large virtual memory, which still made memory access (for example during garbage collection) time consuming. A GC run of a large heap in VM could run for 30 minutes making the computer mostly unusable during that time. Vectors/Arrays and OOP objects then also used the model of dynamic allocation with many referenced objects (unless they were of some primitive types). Generational GCs, compacting GCs, hardware-supported GCs, etc. were invented and implemented. Full GCs through virtual memory heaps were rare then. The availability of cheaper RAM made it possible that more of the large heaps fit into RAM. Lisp implementations early on added vectors and other data structures. But they still often need pointers. A vector of records (called structures in Common Lisp) is usually a vector with pointers to records. For example Common Lisp implementations usually will not provide vectors of inline records. A vector of fixnums OTOH will be a vector without pointers -> the fixnums will be stored directly in the vector. In the end a Lisp heap is a huge graph of objects referencing other objects. This does not only effect CONS cells, but also vectors, arrays, records, ... -> they also reference other, non-primitive, objects via pointers. That's not very different from any other language runtime which uses dynamic memory allocation and a heap of linked objects (-> Java, JavaScript, ...). The problem of dealing/avoiding non-locality and pointer-chasing is there, too.

akater 2y ago

An ordered pair is a useful data structure, and it's beneficial to have special short names for accessors to its elements. Humanity got very lucky with the names “car” and “cdr”. Naggum does point that out. Any rule about any language could be labeled a barrier to its success because any such rule contributes to the cognitive load, making learning the language slightly more difficult than it would be without that rule. What matters more is how much cognitive load is there after you learn the rules. Common Lisp is very successful at it.