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.
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.
One could absolutely use a Dequeue or some other optimized structure for a Lisp list, really depends on how the code is written.
How? With naked deque nodes? Since otherwise you wouldn't get Lisp lists, you couldn't have structure sharing, etc. And where would the reverse deque node pointer point to if multiple nodes pointed to the node in question?
it seems to me that removing single number from a random position in a list is also not what Lisp lists address, especially since Lisp implementations have vectors, too.
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
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<>
This is true if the list is writeable, but, if so surely a Lisp has to also keep duplicating the list or else it will get into trouble?
For reading the list why shouldn't Rust use a slice of the vector? The slice can't own anything, but that's OK, we aren't changing anything. The slice is very cheap, it's basically a pointer into the vector plus a length count.
Nope, it doesn't traditionally duplicate the list. It certainly is possible to get into trouble in your logic, but those are the presented semantics, and debating their virtue is out of scope
> why shouldn't Rust use a slice of the vector?
You're gonna get into ownership-hell if you can't give a separate Rc to each list tail, because those can get passed around wherever
This forces you to confront the reality you'd been dodging. Either you actually mutate this list in your program, and the "magic" of linked lists dissolves when it consumes all your memory, or as seems far more likely you get good performance from the better underlying data structure anyway and the "magic" of linked lists dissolves that way.
You only get good performance from linked lists today on the rare occasion when their lack of data locality is outweighed by some other factor. Sprinkling the Lisp idiom over things doesn't change that.
Here's an example where it's worth it: In highly concurrent systems you can't afford to use any sort of locking to protect data structures, the contention for the locks hurts too much, and you can't afford to reference count everything in those structures because even the contention on the reference counts also costs too much (everything looking at an item is storing to the reference count). So you use Hazard Pointers to avoid prematurely dropping anything. But any type of locking for your Hazard Pointers structure would have too much contention also, so you store the Hazard Pointers in a linked list, new ones can be slotted into place at the start of the list with an atomic compare-exchange. Each CPU core is writing to the Hazard Pointers it "owns" a lot, but they're deliberately too big to share with another CPU's cache, and any CPU cores that need to check the Hazard Pointers read from them all but never write so modern caches cope admirably.
The way those languages chose to handle this stuff has well-trod advantages and disadvantages. I don't love it personally, but I get it. Certainly it's worked well enough for a whole lot of software!
But I'm not commentating on it here. I'm just stating the divergence with the OP. Critiquing Lisp's 40+ year history and what parts of it should or shouldn't have been different is out of scope as far as I'm concerned. You're arguing against something that isn't being stated.
What sort of expectations do you think will be defeated? Beyond the fact that it's only a toy and not, in fact, a Common Lisp or Scheme? Almost everything is missing, but it's a toy. You noticed the Vec but apparently didn't notice the toy language still doesn't even have Cons at the end.
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.
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.