I beg to disagree.
In kernels, drivers, and embedded systems they are very common.
- My values represent runs of characters in the document.
- Inserts in the tree may split a run.
- Runs have a size - 0 if the run is marked as deleted or the number of characters otherwise. The size changes as we process edits
- Every inserted character has an ID. I need to be able to look up any run by its ID, and then edit it. (Including querying the run’s current position in the tree and editing the run’s size).
It’s an interesting data structure problem, and it took a few weeks to have a good solution (and a few weeks more later rewriting it in safe rust & improving performance in the process).
I love this stuff. I think it’s pretty rare to find a reason to code your own collection types these days, but it certainly comes up from time to time!
Absolutely! That is one of the places you want to use that style of programming. As the base classes and built in structs do not really cover it yet.
Also as a counterpoint sometimes the built in ones have some very interesting degenerate cases. I had one in an old library that basically doubled its memory footprint every time you exceeded its buffer. That was a point to change it to be a fixed allocation or something else. If i had no idea of the fundamentals I would have been totally in the weeds and no idea why it was doing it.
Seems like the glaring exception to the rule!
(write-string (cdr '(write-string "hello-world"))) also has to work, so it's pretty easy to materialize that semantics at any point.
Nope; it has linked list syntax (that certainly isn't ignored even by very good compilers). Syntax isn't semantics.
The semantics is that a function write-string is called, with a string as its argument.
The second expression has linked list processing in its semantics because you stuck in a cdr, as well as a quote which makes a piece of the program available as run-time list datum. (This is semantics that could be easily optimized away in the executable form, but I would say that it has linked list processing in its abstract semantics.)
We're looking at the same string and seeing different things. You're seeing `(write-string "hello world")` as a program, I'm seeing it as an expression.
It has linked list semantics, which you can preserve until runtime like this `'(write-string "hello world")`. Note that I didn't change the string, I changed its context. If the original were living in a string, and you called read on it, it would become a linked list. If you called eval on that list, it would become a function call. This is basic stuff which I'm well aware you know, so I'm not sure what all the quibbling is about.
You literally need a linked list to write a program in a language in which the code becomes linked lists. And you're going to have a bad time writing Lisp if you don't get the hang of cons cells, early and often.
Is "code is data" true, or false? You're trying to have it both ways here.
The "large number of programmers who have learned about linked lists but haven't run into many cases where they needed them in the world world" include approximately zero programmers who have wielded Lisp in anger, is my point. I thought that was pretty clear from context, but I guess not.
You're also likely provoking list manipulation by running C hello world. The C grammar has lists, like lists of parameter declarators in a function, or argument expressions in a function call.
By the time you've compiled your C program, you've likely "used", lists, trees and hash tables.
Classic line-numbered BASIC interpreters stored the lines as a linked list. For instance in
10 PRINT "Hello"
20 GOTO 10
So in addition to not being able to write C hello without linked lists, the same holds for BASIC.
The way you present your idea about Lisp is harmful because it is likely to be misinterpreted and become misinformation in the eyes of those who not so well informed.
The Lisp community still has to deal with nonsense like that the execution of Lisp programs is slow because linked lists are continuously being traversed, or that the only data structure is a list.
Think about how you might be playing into that. What do you think it looks like when you say that you can't write a hello world, without using linked lists.
SBCL:
* (defun hello-world () (write-string "hello world"))
HELLO-WORLD
* (disassemble #'hello-world)
; disassembly for HELLO-WORLD
; Size: 36 bytes. Origin: #x100311C85C ; HELLO-WORLD
; 5C: AA0A40F9 LDR R0, [THREAD, #16] ; binding-stack-pointer
; 60: 4A0B00F9 STR R0, [CFP, #16]
; 64: EAFDFF58 LDR R0, #x100311C820 ; "hello world"
; 68: 570080D2 MOVZ NARGS, #2
; 6C: 29EC80D2 MOVZ TMP, #1889
; 70: BE6B69F8 LDR LR, [NULL, TMP] ; WRITE-STRING
; 74: DE130091 ADD LR, LR, #4
; 78: C0031FD6 BR LR
; 7C: E00120D4 BRK #15 ; Invalid argument count trap
Out of all the programmers in the world, what percentage of them do you think work in the kernel/driver/embedded spaces?
The % who have touched kernel bits, wrote a triangle engine scene renderer, wrote a compiler, touched server metal in production, have worked on ASICs, and can put together ML/AI building blocks shrinks way, way down to a handful of living humans.
This is about how many work in kernels/embedded systems/etc vs more common programming gigs. And that's less about how many are trained to do so, but rather how many are needed.
Second, linked lists are useful in a lot more places than that. Probably a better proxy would be low-level coders. You almost always want a linked list somewhere when you're dealing with memory addresses and pointers. Maybe not for the primary collections, but there are always secondary ones that need to maintain a collection with a different membership or ordering, and vectors of pointers don't have many clear advantages over intrusive linked lists for those secondary collections.
I did start to encounter some fresh grads with degrees that said "computer science" on them that couldn't answer some basic linked list questions. I was beginning to think it was a bad set of questions until I hit those kids. If you claim to know "computer science" and don't know what a linked list is, especially beyond some text books stuff, I'm probably not interested.
My experience in embedded, everything is hardcoded as a compile time constant, including fixed size arrays (or vectors of a fixed capacity)
A common way to implement these is to have an array of messages, sized for the worst case scenario and use this as the message pool.
You keep the unused messages in a single linked "free-list", and keep the used messages in a double linked queue or fifo structure.
That way you get O(1) allocation, de-allocation, enqueue and dequeue operations for your message queue.
Another example for this paradigm are job queues. You might have several actuators or sensors connected to a single interface and want to talk to them. The high level "business" logic enqueues such jobs and an interrupt driven logic works on these jobs in the background, aka interrupts.
And because you only move some pointers around for each of these operations it is perfectly fine to do so in interrupt handlers.
What you really want to avoid is to move kilobytes of data around. That quickly leads to missing other interrupts in time.
In embedded world, memory often needs to be exactly controlled, and allocation failures are fatal without a more complex MMU. In kernel world, I believe the main reason is that allocations can block.
In addition, a lot of data structures might be shared across multiple cores. Linked lists can be traversed and mutated concurrently (although with a bit of care).
I'd be convinced once I see pure Rust kernels geared towards modern machines suddenly using linked lists everywhere. Otherwise I'm leaning towards it being a side-effect of the language choice and culture.
Also because I've seen the same kind of reasoning applied to compilers (e.g. "of course you need linked lists in compilers, they are extremely graph traversal heavy"). But one look at modern compilers implemented in Rust paint a very different picture, with index-based vectors, data-oriented design and flattened ASTs everywhere.
It can be solved (or worked around), but it's understandable that people don't _want_ to do that.
I/e in a DMA-based ethernet driver, the ethernet MAC receives packets asynchronously from the processor, perhaps faster than the processor can ingest them. So the mac interrupts the processor to give it new packets, and the processor can't sit processing the packets in the interrupt context, so it needs to put them into some ordered list for processing later when it has downtime. In a true embedded system, the memory for this list is going to be fixed or statically allocated, but you still don't really want to have an array-style list with fixed indexing, as you'll have to manage what happens when the index wraps around back to 0 etc, so instead you just construct a linked list in that pre-allocated memory.
I wouldn't say linked lists aren't really used in high-level applications, as I said they're used all over the place whenever you have external asynchronous communication, it's just that modern high-level frameworks/libs totally abstract this away from most people writing high level code.