4 ms·

One weird thing I noticed is that they use a Vec instead of a linked-list to store lists. This is going to really mess with anyone who tries to do a lot of car/

One weird thing I noticed is that they use a Vec instead of a linked-list to store lists. This is going to really mess with anyone who tries to do a lot of car/cdr/cons-ing. Maybe that's out of scope for this guide.

oh_sigh 5y ago
Does anyone actually program like that besides for in lisp tutorials?
- jhgb 5y ago
  Of course people do that; it's very convenient.
  - mumblemumble 5y ago
    It is, but I do wonder if it's the most performant option. For grabbing individual elements, cadddr and friends are O(N) for linked lists while a O(1) implementation is possible for arrays. List eaters are an elegant design pattern, especially for picking apart recursive algorithms, but eating linked list wouldn't be nearly as cache-friendly as map/reduce over an array. It wouldn't get rid of all the pointer chasing, but even reducing one level of it is worth something. Perhaps, with modern language implementation technology, we could produce something like that, while also preserving persistence (at the semantic level), by, in the background, choosing mutation when there's only a single active reference to the list, and falling back to a copy-on-write discipline when there are multiple concurrent references. For what it's worth, I find I never program that way in Clojure. I realize Clojure not being as list-oriented is a point of contention for many people, and I'm not all that much of a lisper, so perhaps my opinion isn't worth much, but I've generally found that Clojure gives me most of what I want. I am more annoyed by the lack of reader macros. Though I also understand and respect Rich Hickey's decision there.
    - jhgb 5y ago
      > For grabbing individual elements, cadddr and friends are O(N) for linked lists That doesn't really make sense. cadddr is O(1), and so are all its c[ad]{1,4}r friends. > For what it's worth, I find I never program that way in Clojure. I suspect you don't do that because the language doesn't support it well. Which is fine, since going against the grain of a language is generally inadvisable, but it says nothing about the technique in itself.
      - mumblemumble 5y ago
        For a linked list implementation, car requires traversing one cons cell, cadr requires traversing two, caddr three, four for cadddr, and so on. That's about as textbook an example of O(N) as you can get.
        jhgb 5y ago
        But your N is bounded from above to 4, so pretty much anything using these functions won't be unbounded in time just because of use of these functions. If you're suggesting that using nth or elt on a list of arbitrary length is a bad idea, then yes, it is, but I certainly wasn't suggesting that.
- klyrs 5y ago
  Yes, linked lists are great for certain use cases. They make for very clear and performant code, especially if your language can special-case their memory management. In other cases, they're slow garbage, and that's where vectors shine.
- fulafel 5y ago
  Depends on the language I guess. In Clojure, no. In Common Lisp, probably.
dcsommer 5y ago
There are some good thoughts concerning when to use a linked list here: https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/
- brundolf 5y ago
  Your link talks about the general case. For better or worse, (most) Lisps give linked-list operations a special status as a fundamental primitive. For example, getting the tail of a list over and over is commonly used for iterating through its elements. If you try and do this with a Vec you'll be copying and re-allocating almost the whole thing on every loop iteration. Nothing about Lisp requires that you write code this way of course, but it's the epitome of what could be called "Lispy" (literally: "list processing language"), and any preexisting code or habits will hit a brick wall if those lists are implemented as Vecs
  - dgb23 5y ago
    To add, Clojure uses a sequence interface that is typically backed by a vector. Conj (instead of cons) is used to derive a new sequence with the thing added in front for lists (which are rarely used) and at the back for vectors.
    - brundolf 5y ago
      It supports both, as it should; Lists are still first-class citizens, it's just that vectors are too. Though also in Clojure's case vectors aren't really vectors, they're immutable persistent data structures that share memory as much as possible, which I think would actually solve most of the performance problem here. But the same is not true of Rust's Vec<>
      - nerpderp82 5y ago
        https://github.com/bodil/im-rs https://github.com/bodil/im-rs
tialaramex 5y ago
In theory a linked list has lots of attractive features as a data structure and when LISP Machines were a thing that theory translated into reality pretty well. Today losing data locality hurts really badly. Rust does provide a linked list, for the handful of cases where that really is what you wanted, but almost always even though in theory a vector should be worse, in practice it's better. For example if you build a toy system with a thousand small integers on the list, you might reason that removing the 500th via a vector instead of a linked list would be awful - you'd need to shuffle 500 of them forward compared to just swapping a pointer. But wait, on today's hardware the linked list approach involves about five hundred dependent cache misses. Before you find the 500th on the list to remove it, you have stalled the CPU for so long the vector implementation would have already finished doing its shuffling of 500 items forward in memory and moved on to something else. Now, if your list has 500 million items in it, and you often want to remove just the first item while appending to the far end, a Vector is indeed a bad fit. But there are still better alternatives than a Linked List, Rust provides a Deque but unlike the one a Lisp-enthusiastic professor may have showed you in data structures class, it's actually a similar structure to a vector not a linked list.
- brundolf 5y ago
  I'm not here to debate the virtues of linked-lists, I'm just pointing out that they're extremely idiomatic in Lisp, so it's weird to implement a basic Lisp that doesn't use them, because anybody running idiomatic code in it will be in for a big surprise.
  - karmakaze 5y ago
    Clojure already started the trend with renaming car/cdr and favouring vectors in places.
    - lispm 5y ago
      In Common Lisp: first and rest. The languages also provides functions working over both lists and vectors -> sequences.
- 5y ago

oh_sigh 5y ago

Does anyone actually program like that besides for in lisp tutorials?

jhgb 5y ago
Of course people do that; it's very convenient.
- mumblemumble 5y ago
  It is, but I do wonder if it's the most performant option. For grabbing individual elements, cadddr and friends are O(N) for linked lists while a O(1) implementation is possible for arrays. List eaters are an elegant design pattern, especially for picking apart recursive algorithms, but eating linked list wouldn't be nearly as cache-friendly as map/reduce over an array. It wouldn't get rid of all the pointer chasing, but even reducing one level of it is worth something. Perhaps, with modern language implementation technology, we could produce something like that, while also preserving persistence (at the semantic level), by, in the background, choosing mutation when there's only a single active reference to the list, and falling back to a copy-on-write discipline when there are multiple concurrent references. For what it's worth, I find I never program that way in Clojure. I realize Clojure not being as list-oriented is a point of contention for many people, and I'm not all that much of a lisper, so perhaps my opinion isn't worth much, but I've generally found that Clojure gives me most of what I want. I am more annoyed by the lack of reader macros. Though I also understand and respect Rich Hickey's decision there.
  - jhgb 5y ago
    > For grabbing individual elements, cadddr and friends are O(N) for linked lists That doesn't really make sense. cadddr is O(1), and so are all its c[ad]{1,4}r friends. > For what it's worth, I find I never program that way in Clojure. I suspect you don't do that because the language doesn't support it well. Which is fine, since going against the grain of a language is generally inadvisable, but it says nothing about the technique in itself.
    - mumblemumble 5y ago
      For a linked list implementation, car requires traversing one cons cell, cadr requires traversing two, caddr three, four for cadddr, and so on. That's about as textbook an example of O(N) as you can get.
      - jhgb 5y ago
        But your N is bounded from above to 4, so pretty much anything using these functions won't be unbounded in time just because of use of these functions. If you're suggesting that using nth or elt on a list of arbitrary length is a bad idea, then yes, it is, but I certainly wasn't suggesting that.
klyrs 5y ago
Yes, linked lists are great for certain use cases. They make for very clear and performant code, especially if your language can special-case their memory management. In other cases, they're slow garbage, and that's where vectors shine.
fulafel 5y ago
Depends on the language I guess. In Clojure, no. In Common Lisp, probably.

dcsommer 5y ago

There are some good thoughts concerning when to use a linked list here: https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/

brundolf 5y ago
Your link talks about the general case. For better or worse, (most) Lisps give linked-list operations a special status as a fundamental primitive. For example, getting the tail of a list over and over is commonly used for iterating through its elements. If you try and do this with a Vec you'll be copying and re-allocating almost the whole thing on every loop iteration. Nothing about Lisp requires that you write code this way of course, but it's the epitome of what could be called "Lispy" (literally: "list processing language"), and any preexisting code or habits will hit a brick wall if those lists are implemented as Vecs
- dgb23 5y ago
  To add, Clojure uses a sequence interface that is typically backed by a vector. Conj (instead of cons) is used to derive a new sequence with the thing added in front for lists (which are rarely used) and at the back for vectors.
  - brundolf 5y ago
    It supports both, as it should; Lists are still first-class citizens, it's just that vectors are too. Though also in Clojure's case vectors aren't really vectors, they're immutable persistent data structures that share memory as much as possible, which I think would actually solve most of the performance problem here. But the same is not true of Rust's Vec<>
    - nerpderp82 5y ago
      https://github.com/bodil/im-rs https://github.com/bodil/im-rs

tialaramex 5y ago

In theory a linked list has lots of attractive features as a data structure and when LISP Machines were a thing that theory translated into reality pretty well. Today losing data locality hurts really badly. Rust does provide a linked list, for the handful of cases where that really is what you wanted, but almost always even though in theory a vector should be worse, in practice it's better. For example if you build a toy system with a thousand small integers on the list, you might reason that removing the 500th via a vector instead of a linked list would be awful - you'd need to shuffle 500 of them forward compared to just swapping a pointer. But wait, on today's hardware the linked list approach involves about five hundred dependent cache misses. Before you find the 500th on the list to remove it, you have stalled the CPU for so long the vector implementation would have already finished doing its shuffling of 500 items forward in memory and moved on to something else. Now, if your list has 500 million items in it, and you often want to remove just the first item while appending to the far end, a Vector is indeed a bad fit. But there are still better alternatives than a Linked List, Rust provides a Deque but unlike the one a Lisp-enthusiastic professor may have showed you in data structures class, it's actually a similar structure to a vector not a linked list.

brundolf 5y ago
I'm not here to debate the virtues of linked-lists, I'm just pointing out that they're extremely idiomatic in Lisp, so it's weird to implement a basic Lisp that doesn't use them, because anybody running idiomatic code in it will be in for a big surprise.
- karmakaze 5y ago
  Clojure already started the trend with renaming car/cdr and favouring vectors in places.
  - lispm 5y ago
    In Common Lisp: first and rest. The languages also provides functions working over both lists and vectors -> sequences.
5y ago