The strange thing about Erik is that he was sweet, gentle and helpful in person. I spent a fair amount of time with him, and never once saw any of the behavior he was famous for on usenet.
He was highly intelligent but he had an odd childhood and was somewhat isolated socially, in the real world. It’s what ultimately killed him. At least outside of tech. Near the end he was almost a cult-like figure, at conferences especially. He would accumulate a hoard of fans. I’m unsure if he liked that.
He really loved coming to the Bay Area.
I definitely miss him irl.
Sorry for the ramblings. I’m on mobile and editing is hard.
I never got the chance to interact with, much less meet, Erik, but I think the thing people misunderstand about even his more vitriolic messages (his XML rant warms my heart to this day), is that he wasn't being an asshole, he was pursuing values people had increasingly abandoned. He was an impassioned idealist.
There was a time when technologists aggressively cared about the technically correct solution as a opposed to the "business correct" or "socially correct" answer. Erik's rants (which I'm more familiar with) didn't criticize the uninitiated, they attacked people who didn't care to know better.
He's the fundamental opposite of today's Twitter/X "shitposter", those who promote rage for clicks and engagement above understanding and thinking. He inspired you (or at least young me) to be good enough, to understand well enough, that when you spoke you wouldn't insight the rage of people like him. He was a warning to neophytes not to get too cocky before you learned the ropes. He was an object lesson that ego was far less important than understanding. Something lost on the most recent Twitter/X generation.
I'm certain anyone resembling Erik out there in the world would not have survived the tech industry the last 10 years and for me that is a tragedy. I hope Erik's name forever lives on in internet lore and at least some new people setting out secretly hope to understand their field enough not to invoke the rage of his lurking spirit.
Great to see someone take down XML, what a nightmare. Of course for markup nowaday we use the pragmatically simple "README.md" not "README.xml", although I'm sure the latter is quite popular amongst Java circles.
Anybody interested in efficient list (and other data structures, but mostly lists) implementation will probably find the VList approach interesting (relevant paper archived at https://trout.me.uk/lisp/vlist.pdf)
A ( linked ) list is a collection of CONS ( Construct ) cells.
A CONS cells can extract, via the commands:
‘car’ ( Contents of Address Register ) - the payload ( data item in list );
‘cdr’ ( Contents of Decrement Register ) - the link ( to the next list item, e.g. CONS cell )
The names are for historical reasons ( using two halves of a single register ) lost in the beards of yore.
The linked list appears simple, this belies the fact of its exquisite perfection and the great thought that went into inventing, perfecting and implementing it.
“[The ‘list’ command]… creates a series of conses and sets the CAR pointers to point to each argument. which you have provided. (LIST (LIST 1 2) (LIST 3 4)) => ((1 2) (3 4))
But simplest: Address pairs are extremely simple, obviously. But they can implement anything.
Lists, structures, arrays, trees, arbitrarily complex multidimensional and irregular data types.
Using symbols as representational "links" they can even implement general (multi-, etc.) graphs. Which is everything.
But remove one of those addresses, and all you have left are linked series of addresses, ending with one element, or an end-of-series marker. That isn't general or very useful.
When you use lists to define a data structure, you can linearize the whole structure. I.e. (... (...) ... ( ... ) ... ... )
What you can't do is have some leaf of the structure refer back to a higher point in the structure. Which is what you need to represent a graph. I.e. any point can refer to any other point.
So instead, you linearize but use symbols to define a referencable point, and then to refer to it.
I.e. ( ... (....) (define a ( ... )) ... ( ... ( ... a .... ) ... a ... ) ... )
In this case, "define a" indicates that the next list isn't just accessible at that location, but wherever "a" appears later. And then we reference it in more then one place later.
This allows not only tree-like structures to be linearized, but graphs.
Everything is still lists, and lists-of-lists, but just as symbol or number elements can appear at more than on place, now lists in the structure can be referenced in more than once place.
All done with just pairs of addresses and symbols. Even numbers can be built out of pairs of addresses and symbols.
I.e. a binary number: (one one zero one zero zero one zero)
Of course, a friendly language is going to add lots of notation on top of address-pairs and symbols, for numbers, looping, functions, decimal number, etc. to make common code and data forms much easier to type and read than a jungle of parentheses.
--
This is very much the reason we have defined and referenced symbols in all code (or complete data languages). So that linear text can describe a graph. And the same process occurs, first the text is parsed into a tree (parsing), then at some point, symbols defining references are replaced with addresses of symbol definitions (linking).
The result is code can be a graph. We can have two functions that call each other, etc. Not just tree expressions.
I see, interesting. I never really thought about LISP as low-level. It was always just something that I implement in C however I want to. You gave me a bit of a new perspective on it.
Low level in implementation, meaning a representation that matches the native hardware data, code and storage conventions.
The advantage being hardware-level representations are the easiest to optimize for that hardware.
But also mathematically, where low level means simplest and fewest primitive abstractions that allow easy representation and manipulation of code and data. LISP's paired references and symbolic linking are very low level in that sense.
The advantage here is that with so few abstractions, code and data relationships are easy to define, analyze, transform, as well as evaluate.
And small numbers of simple abstractions are very easy to implement. As you obviously know from experience.
I have also created several little LISPs in aid of other projects.
Another language I have recreated opportunistically is FORTH. It can be viewed as a trade off between being low-level with respect to hardware, and in terms of simple abstractions. Not as flexible as LISP, but more efficient on typical hardware. Its basic abstractions consists of two dynamic lists. The first, a stream (a running list) of instructions that manipulate data on the second, a stack (a dynamic list we append and remove items from). And symbols for linking.
Yes, I know what you mean. I'm reading McCarthy's original paper now and what I'm noticing is that not all of it is low level in the second sense. For example, mathematically cond would be implemented with copairing/matching over left- and right-injections. Coproduct is the dual category to the product category that pairs belong to, so would be more natural than the higher-level cond, but much less efficient in practice.
I found it intriguing that the original post there claims that
(cons (list 1 2) (list 3 4))
intuitively seems to have the length 2 whereas the correct length is 3. I find 3 more intuitive though. It could be because right from my early days of learning various Lisps, I learnt about lists in terms of cons cells.
There are many ways to explain this, such as by drawing diagrams of the cons cells from first principles, printing out each cons and list on a REPL and confirming the equivalences, etc. Here's one that happens to be my take on it. I'll be (ab)using the equals sign (=) to mean that the expression on the LHS and the one on the RHS are equivalent.
First let us build a list of three items using cons cells:
> intuitively seems to have the length 2 whereas the correct length is 3. I find 3 more intuitive though. It could be because right from my early days of learning various Lisps, I learnt about lists in terms of cons cells.
That's just how cons is defined. the first argument is a list and the second is an arbitrary object, and the result has the elements from the list plus the other object. It doesn't take a bunch of algebraic manipulation to understand this definition. It just takes a recognition that an "arbitrary object" could be a list, as well as a recognition that the other definition you imply ("make a new list with both arguments as elements") would have to either be variadic (which in turn would obviate `list`) or would only ever be able to make lists of exactly 2 elements. (The point is that `cons` can serve as a simpler primitive, and `list` can be implemented in terms of it.)
Note that the value returned by cons is guaranteed to have type cons, and it is guaranteed that a fresh cons is created. Neither is true for list*; note that its return type is t.
This doesn't come across as "caustic" as when I previously read it. And the "bile" isn't directed so much at Lee as it is at something he wrote; "All in all, the pairs notion is redundant."
Naggum genuinely seems to be hoping that his long and thorough explanation will convince Lee of his point of view, and not as a put down.
> I hope you understand and appreciate what I have written above so the
following does not apply to you anymore.
The "following" where he goes off on what Lee wrote, but not on Lee himself.
It might be worth it for me to re-read Naggum's posts, now that I have a better understanding of where he was coming from.
Not caustic? "Short-sighted users", "stupid language designers who believe too strongly in strong typing", "certainly can't be bothered to invent a useful concept for their short-sighted programmers", "dumb people who implement something the simple way, so it becomes complex and generally useless to everybody else", "unlike today's braindamaged CPU's", "just look at what C programmers do when they need lists! shudder".
Sure, you may believe that LISP is the greatest invention since the sliced bread, and everything went downhill after that but even if you are correct — that's still just, like, your opinion, man.
I wrote "not *as* caustic" ... in particular, he wasn't being caustic toward Lee, but rather to the idea of cons pairs being redundant.
It's enough of distinction to make me think I should re-examine what Naggum had to say - in this and in other posts - and not get caught up in any pre-conceived notions I might have had about him.
Consider that you may be eavesdropping on the sort of self-talk the author engages in. The clear reasoning mixed with vituperation makes me suspect he probably beats himself up. There is a lot of worry over being mistaken and stupid.
I'm unfamiliar with the author, so I could be way off base.
It was pretty mild for Naggum. Like the GP I was expecting a higher density of that sort of thing, but maybe my memory is too slanted by his worst flames.
Unfortunately, from my experience, Xah Lee is someone who will ignore information from others if it requires to correct what he wrote/spoke, especially when he claims something authoritatively when in reality he has no in-depth, if any, information on the subject
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.
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.
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.
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.
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.
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.
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.
> 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.
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.
> 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.
This is moving the goalposts. My critique was about list implementation, not about implementing the entire runtime.
> Yet many of the language runtimes are actually following the Lisp model.
This is frankly not true in any way relevant to this conversation. Using garbage collection is not equivalent to using the entire Lisp model. Java, JavaScript, Python, Lua, Ruby, C#, etc. do not make extensive use of linked lists in their standard libraries, instead preferring--you guessed it--vectors. Hashmaps in modern languages are implemented as... vectors again. And if you dig into how structs are implemented in say, C#, they are implemented as contiguous blocks of memory.
Yes, there are some things contiguous blocks of memory can't do, so everyone has to support nested data structures, but by default, most languages push you toward contiguous memory in their standard libraries and idioms whenever possible, because it's just so obviously more performant for the vast majority of cases.
> 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.
Yes, and my point is that having cons cells as a ubiquitous data structure in your language greatly exacerbates this problem. The extremely common case of lists does not need to entail pointer chasing, and in the vast majority of cases it should not entail pointer chasing, and contrary to your claims here, in most languages it does not entail pointer chasing. Lisp-family languages are fairly unique in this problem. Ironically, higher order functions like map/reduce/etc. push you toward operating on lists as a whole which is exactly the case where vectors most outshine linked lists.
> My critique was about list implementation, not about implementing the entire runtime.
Linked lists are actually managed by the runtime.
Example on a esoteric platform, a Lisp Machine, a real, but outdated, computer. But we still have Virtual Lisp Machines, which have a virtualized implementation (not as in a microcoded CPU, as the real ones were).
If I cons a list via CONS, I get a linked list made of cons cells. But over the lifetime of the list, this may change. At some point in time the runtime may decide to copy the list (for example because it has a copying garbage collector). The effect then is that the list is allocated in contiguous memory. The program itself does not see a difference.
First the list (1 2 3) is allocated as [1 | -> [2 | -> [3 | NIL]]], written in Lisp as (1 . (2 . (3 . NIL))) . At some point in time the runtime changes this transparently to [1][2][3], where the cells are tagged, such that the successor is in the next memory word and where the last element is tagged that it has no successor. That's called cdr-coding.
Now If I copy a list, with COPY-LIST I always get a cdr-coded list as a result. Several list functions return cdr-coded lists, instead of linked lists.
This cdr-coding method is not much used anymore, since there is not much of an advantage: either one uses linked lists (because they are easy to use and have useful properties, like that CONS does not need to copy its arguments) or other available data structures (vectors, structures, ...).
What is still used are locality improving garbage collectors.
> Using garbage collection is not equivalent to using the entire Lisp model. Java, JavaScript, Python, Lua, Ruby, C#, etc. do not make extensive use of linked lists in their standard libraries, instead preferring--you guessed it--vectors.
Lisp also makes use of vectors, where necessary. These languages with managed memory like Java have the same object/reference model as Lisp and the same calling mechanisms. linked lists are only a special case (-> java.util.LinkedList).
Say we have N cities. Each city is a an object of class CITY. Each city will have attributes, for example NAME and PEOPLE-NUMBER. Now we want to keep two "lists" of them one sorted by name and another one sorted by PEOPLE-NUMBER.
We need two vectors and N city objects. In Lisp the city objects are not stored in the vectors. They are stored somewhere in the heap. -> there goes your "contiguous memory" to bust. The vectors are pointers into a heap. Every access to the nth city object through one of the nicely contiguous vectors, references an object which is stored somewhere else.
That model is used in many languages implementations. It's the Lisp model of memory management, introduced with Lisp 1 -> dynamic memory management plus a garbage collector to reclaim unused space.
> And if you dig into how structs are implemented in say, C#, they are implemented as contiguous blocks of memory.
That's also the case in Lisp. But a struct (or list or vector) of structs usually points to those being somewhere on the heap. A struct/list/vector of structs is not a single contiguous block of memory. structs in slots are typically not inlined. Some languages inline data non-primitive structures, Lisp usually does not.
> contiguous blocks of memory
That's can be an illusion. In a virtual memory system, the memory is made from pages of a fixed size. Random pages are cached in RAM, influenced by their usage pattern over time.
> in most languages it does not entail pointer chasing
It does, see above. Just not tail pointers in the list.
> Ironically, higher order functions like map/reduce/etc. push you toward operating on lists as a whole which is exactly the case where vectors most outshine linked lists.
That's why in Common Lisp the functions MAP and REDUCE work over vectors, too.
> Lisp-family languages are fairly unique in this problem.
see Prolog and various functional languages, ... some even have basic strings implemented as linked lists of characters (which Common Lisp does not do).
If we look at data structures, one tries do address quite a bit more than "contiguous memory", for example persistence, runtime updates and runtime lookups, ... see for examples: https://cstheory.stackexchange.com/a/1550
> Lisp also makes use of vectors, where necessary. These languages with managed memory like Java have the same object/reference model as Lisp and the same calling mechanisms. linked lists are only a special case (-> java.util.LinkedList).
You seem insistent on missing my point.
"Where necessary?" is almost always, because vectors almost always outperform linked lists based on cons cells. If your program uses cons cells at all, chances are you made the wrong choice. Lisp doesn't make use of vectors in many cases "where necessary" because "where necessary" is a whole lot more than Lisp's structure, libraries, and community encourage you to do.
Simply pointing out that java.util contains a Linked List implementation means nothing. I wrote Java full time professionally for ~5 years and never saw that used once. If Python or C# ship with linked list implementations I'm not aware of them because they're also never used.
To be frank, if your program uses linked lists at all, it's probably a mistake from a performance perspective. There simply aren't many cases where a linked list is a better choice than a vector. And this is a mistake that Lisp programs make all the time because cons cells are so baked into the language.
> > in most languages it does not entail pointer chasing
> It does, see above. Just not tail pointers in the list.
It is both dishonest and rude to not even quote a full sentence when you're trying to refute something.
Tail pointers on the list being avoided is exactly my point, a fact which you obfuscated by removing context. That is a huge amount of added cache thrashing, even with cache-aware allocation. This is not something you can just pretend is a minor issue.
Are you even capable of admitting that Lisp has serious faults, or do you really think it's completely, 100% perfect? This isn't a rhetorical question: I legitimately would like to hear what serious faults you think Lisp has, because if you can't present any problems with Lisp at all, then you simply aren't capable of participating usefully in conversations about Lisp. Lisp is a human invention which includes human mistakes, and if you can't admit that, anything you say about it is going to suffer from crippling bias and can't be trusted.
And to be clear, I'm not interested in further whataboutism. If your idea of a problem with Lisp is something where you can end with "but every other language has this problem too", stop--that's just further proving your inability to criticize Lisp. I'm happy to describe serious problems unique to any of the languages I've mentioned in this thread, but that's not the current topic of discussion.
Pointer chasing in linked lists is a cause of performance problems in Lisp and it isn't a cause of performance problems in other languages. No, not for retrieving each individual item, I'm talking about moving from one item to the next. Every single thing you've said in this thread has been trying to move the goalposts to make it seem like this isn't a problem or it isn't unique to Lisp. It is a problem. It is unique to Lisp(s).
The list or vector is 10000 elements long and 100 times reversed and the difference in runtime is tiny. The list version is only marginally slower, but allocates a lot more memory.
I can also construct cases, where the list is much faster. Adding a one element list/vector to the front:
CL-USER 22 > (time (test1 10000 100))
Timing the evaluation of (TEST1 10000 100)
User time = 0.016
System time = 0.000
Elapsed time = 0.012
Allocation = 9148776 bytes
0 Page faults
GC time = 0.000
#(A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A ...)
CL-USER 26 > (time (test2 10000 100))
Timing the evaluation of (TEST2 10000 100)
User time = 0.000
System time = 0.000
Elapsed time = 0.000
Allocation = 1042248 bytes
0 Page faults
GC time = 0.000
(A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A ...)
Here the runtime for lists is much faster, since it does not copy the complete list or -> lists share storage, consing to the front is cheap.
-> for many practical use cases for lists the total runtime and the runtime difference does not matter
Obviously there are also many case where a list would perform much worse, like accessing the last element of a list.
> Are you even capable of admitting that Lisp has serious faults
You seem to be keen to find "faults". Usually things are not black and white. There is no true and false, but engineering trade-offs. These tradeoffs can Lisp make the wrong choice for problems. Many of the trade-offs are also influenced by non-technical issues: like the amount of engineering time invested into a language implementation: see SUN/Oracles investment into Java.
So, you did tests to show that linked lists are slower AND use more memory? Which we both already knew? Why?
> I can also construct cases, where the list is much faster. Adding a one element list/vector to the front:
Oh good, I'll keep that in mind for the next time I am forced to prepend a bunch of items to a list, which I expect to happen approximately 0 times before I die of old age.
> > Are you even capable of admitting that Lisp has serious faults
> You seem to be keen to find "faults". Usually things are not black and white. There is no true and false, but engineering trade-offs. These tradeoffs can Lisp make the wrong choice for problems. Many of the trade-offs are also influenced by non-technical issues: like the amount of engineering time invested into a language implementation: see SUN/Oracles investment into Java.
So... what I'm hearing here is, that no, you aren't capable of admitting that Lisp has faults.
I'm aware that tradeoffs exist. I'm also aware that faults exist. These two can both be true.
It seems to me that being slower and using more memory and getting nothing in return isn't a tradeoff.
> So, you did tests to show that linked lists are slower AND use more memory? Which we both already knew? Why?
I showed you that it often does not matter much.
> Oh good, I'll keep that in mind for the next time I am forced to prepend a bunch of items to a list, which I expect to happen approximately 0 times before I die of old age.
It's not that uncommon, for example for a simple stack implementation.
> So... what I'm hearing here is, that no, you aren't capable of admitting that Lisp has faults.
With this discussion style you won't get very far.
> It seems to me that being slower and using more memory and getting nothing in return isn't a tradeoff.
Right, I think that's a useful task for you to actually think about: what do we get in return?
> I showed you that it often does not matter much.
...which we also both already knew.
The thing is, it does matter sometimes; often enough that there's no good reason to take the less performant route by default.
> > Oh good, I'll keep that in mind for the next time I am forced to prepend a bunch of items to a list, which I expect to happen approximately 0 times before I die of old age.
> It's not that uncommon, for example for a simple stack implementation.
1. Does Lisp not come with a stack implementation? In general, I do not plan to implement simple stacks.
2. Pushing items onto a stack isn't inherently a prepend operation. It's generally a "put it on an end" operation, meaning you could append it. Now, with a linked list that would be slower, so obviously you prepend if you're using a linked list, but if you're using a vector, you append. And, lo and behold, appending-vector-based stack performs better than a prepending-linked-list-based stack, because cache. So if I do implement a simple stack, I implement it with a vector (example[1]).
I'm a professional. I'm not writing high school CS level demo programs. If I need a stack, I'm generally using the standard implementation that ships with the language, and if the language doesn't have one, I implement a stack with a vector because there's no upside to implementing it as a linked list. So no, it's not common to prepend to a list, and unless your language is intended for writing high school CS level programs, it probably shouldn't prominently feature linked lists as a normal way to do things, and if it does, that's a problem. Not a tradeoff, because you're not getting anything in return. A problem.
> > So... what I'm hearing here is, that no, you aren't capable of admitting that Lisp has faults.
> With this discussion style you won't get very far.
And how far has your jumping in to defend Lisp and never admitting it has any faults gotten you?
> Right, I think that's a useful task for you to actually think about: what do we get in return?
Nothing I need or want.
Yes, I know the answer you're fishing for is "immutability" but the fact is if you're operating on lists as a whole, i.e. your map/reduce/etc. type operations, you can achieve immutability with vectors, and it will be more performant when you do so.
It took me about a minute to find an instance of list linking in Java sources (OpenJDK):
class JVMCIRuntime: public CHeapObj<mtJVMCI> {
../
JVMCIRuntime* _next;
The Linux kernel has list linking all over the place. Userland libraries and utilities ditto.
I don't think I've ever worked on a C++ or C project that had no linked lists anywhere. I'm trying to think of an example but coming up blank.
Quite often but not always linked lists in C are intrusive. Certain object are going to be put into exactly one list. Or more than my list but only one at a time. So the link pointer or pointers are embedded into that object. And so no memory allocation is required to insert those objects into a list. A classic example of this is putting a process structure onto a scheduling queue. You would never want a vector for this, for reasons that a professional such as yourself should understand.
> Quite often but not always linked lists in C are intrusive.
Yes, and that's a significantly different data structure from a cons-cell based list, so I don't think it's particularly relevant. C and C++ certainly aren't examples of one of the languages lispm is claiming uses the Lisp model.
> And so no memory allocation is required to insert those objects into a list.
This is a pretty key distinction which doesn't apply to the linked list objects I'm talking about.
Let's not pretend this proves your point in any way. Intrusive lists in a manually managed memory system are incomparable to the cons cell based linked lists in a garbage collected system which you're defending. This is particularly true when the intrustive lists require no memory allocation.
> Pushing items onto a stack isn't inherently a prepend operation.
a stack has no idea of "prepend" or similar. It's defined by abstract like operations PUSH, POP, IS-EMPTY, MAKE-STACK. How it is implemented is an implementation detail.
> It's generally a "put it on an end" operation,
Which you made up. There is nothing "generally" like that.
> meaning you could append it. Now, with a linked list that would be slower,
and to append would be unnecessary.
> So if I do implement a simple stack, I implement it with a vector (example[1]).
That's a simple "bounded" & "fixed size" stack.
> I'm a professional.
Okay. ;)
> Yes, I know the answer you're fishing for is "immutability"
> > Pushing items onto a stack isn't inherently a prepend operation.
> a stack has no idea of "prepend" or similar. It's defined by abstract like operations PUSH, POP, IS-EMPTY, MAKE-STACK. How it is implemented is an implementation detail.
You say that as if the fact that it's an implementation detail means it doesn't matter.
Implementation details do, in fact, matter.
> > It's generally a "put it on an end" operation,
> Which you made up. There is nothing "generally" like that.
So you're saying that stacks don't have a "push" operation? Or that you don't understand what "push" does?
> > meaning you could append it. Now, with a linked list that would be slower,
> and to append would be unnecessary.
Literally picking and quoting parts of two sentences out of context to state the obvious as if it's a response to anything I said in context is a new low even for you.
> > So if I do implement a simple stack, I implement it with a vector (example[1]).
> That's a simple "bounded" & "fixed size" stack.
No, it's not. Are you aware that vectors can be resized?
> > Yes, I know the answer you're fishing for is "immutability"
> That would be one answer. Can you think of more?
I'm not going to make your argument for you. If you have something to say, say it.
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).
> 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".
Well, shit. Educational, but filled with bile. This post is an example of how to go wrong and make yourself and everyone around you unhappy, while still being right.
Brings back unhappy memories of the conversation style in Usenet. I didn't dare to use newsgroups after I asked some wrong thing as a 15-year-old in some computing-related group and got dumped on by angry adult men.
I get it that they were frustrated by Eternal September and whatever. But thinking back to those times makes me appreciate the moderation culture that dang has created here, as well as the non-linear structure that moves less popular comments out of the way of attention.
He's responding to Xah Lee, well known to be one of the most abrasive and unpleasant people in the lisp community. The hostility might not be desired but it was certainly earned.
Xah Lee wasn't a part of the Lisp community. He was a Usenet troll, active in several programming related newsgroups, not just comp.lang.lisp. He had never written a line of Lisp (or anything more challenging) and never contributed anything, during his Usenet times. His effect on these newsgroups was extremely negative. Discussing with him was useless. Erik Naggum tried and failed (as others did). Erik was a part of the Lisp community, but unfortunately also with negative behavior, especially on comp.lang.lisp. He could write long&useful explanations, but discussions with him were often not pleasant.
Those pages usually just say "Something went wrong. Try reloading."
After several reloads, I was able to see that the second one said, "lol, this [redacted] lispm [redacted] is badmouthing me again," the third one was basically a link to http://xahlee.info/emacs/misc/hackernews_lispm.html, and the first one was a repost of some of the (extremely abrasive and unpleasant) text on that page.†
On his page about Naggum, which is linked from the above, he writes:
> During 1998 to 2004 when i read comp.lang.lisp mostly of his posts, i also post maybe a couple a month on average. Most of my posts are trolls (of the good sort (see: Netiquette Anthropology.)), and part of it is riding his name, criticizing or making fun of his attackers, and criticizing or lampoon him too. They are mostly not technical. Most are writing exercises too.
This does clearly demonstrate that the characterization in this thread of Xah Lee as abrasive, unpleasant, and a Usenet troll is correct.
Of course line counts measure effort (the cost) rather than any measure of actual user benefit. But I think we can fairly say that Xah has by now put more effort into writing code for the Lisp community than Naggum did in his lifetime.
† Personal conflicts between lispm and Xah go back many years. http://xahlee.info/UnixResource_dir/writ/scheme_fail.html is one of numerous places where Xah personally attacked lispm, in this case because of a factual disagreement about the historical dynamics of programming language adoption.
> However, it also appears that lispm's characterization of Xah as never having written a line of Lisp hasn't been correct for many years.
Read again what I wrote above: "He had never written a line of Lisp (or anything more challenging) and never contributed anything, during his Usenet times." The "during his Usenet times" applies to both parts. People often asked on something like comp.lang.lisp for programming help, I can't remember that he actually wrote solutions or debugged problems (unlike, for example, Erik Naggum, who was providing his expertise). All I ever saw was him derailing discussions about the language.
Later then he was configuring GNU Emacs keybindings. He was then, later, scripting GNU Emacs.
Sure he doesn't like to be reminded of his destructive role as one of the most active trolls in Usenet programming related newsgroups. The Usenet archives document this though and he has actually said that he was trolling back then.
It's a bit sad that you waste your time with this topic... That's the hole I was talking about. Get out of it.
With that qualification I think your criticism of Xah is correct, although it entails that debate and trolling don't constitute "contributing anything". That, in turn entails that Naggum's thousands of posts also don't constitute any sort of a "contribution", though of course the small amount of functionality he added to Emacs does. This is debatable, but I do believe it's correct.
It's puzzling to me that you responded to my comment, which quoted Xah saying that he was trolling back then, by saying, "The Usenet archives document this though and he has actually said that he was trolling back then." Possibly you didn't see that part of my comment; did I edit it in after you read it? Certainly I edited it in before you posted your comment, because my editing window for that comment closed 19 minutes before you posted yours. Were there other parts of the comment that you also didn't read?
I don't think he's stopped being a destructive troll, but without Naggum's enthusiastic collaboration he is much less effective. I'd like to say that the changes in the online environment over the last 20 years have reduced the damage that any single troll can do, but eight years ago a Twitter troll got himself elected President of the USA, and seems likely to do so again.
When you say "this topic", I'm not sure whether you mean "the history of Lisp"† or "the social dynamics of online communities", but in either case you can save your tears; both of those topics are fascinating and enormously rewarding to study. Your demand to "get out of it" is not appreciated—it is a breach of civility to elevate yourself above me in that fashion, as if I were your servant—and I will not comply with it.
I asked you a similar question attempting to clarify what you meant in https://news.ycombinator.com/item?id=41760084, and I appreciate your slight clarification on that question here. I've put a lot of effort into attempting to understand your flames so that I can respond to the substance they have, but without your collaboration it's impossible.
______
† This gloss seems unlikely, because you've dedicated a lot of time studying this topic yourself.
It doesn't look like Xah was really trolling here, most of his responses are pretty polite. And he seems to indicate at this point in time he wasn't really familiar with lisp, so I'd venture to guess he wasn't nearly as prominent as he later became.
Most of the stuff I've seen has not been so polite, he's such a notorious hater. Still, it can be entertaining in a way, in small doses (I imagine I'd feel a bit different if I was forced to share a newsgroup commons for years), and such a critic can provide a good perspective once in a while. Even though he's still around I think of him as a character as much as Naggum was, even if they were very different in important ways. The world is richer from having more characters.
The other day I ran into a "gem" from Xah that just made me laugh at its expression. Willing to tank the karma/flag to reproduce:
① I fucking hate this motherfucking tech geeking hacker fucks who
leave dead links on the web and don't fucking care. What the fuck?
Aren't these elite, elegant, coding experts who always take perfection
in algorithm, code, style, language, etc?
I don't understand, how could they, have their home page dead?
I laughed again when some followup links to his site 404'd. It's not at all a fair attack, but man, sometimes I really hate dead links too...
I think he's hilarious, and at a time where a lot of programming pundits only pretend to be subversive and shameless, I welcome Xah's unflitered presentation of his opinions. He often makes a lot of good points, and I tend to find his stances on things thought-provoking even if I disagree with him.
That was Naggum's trademark: Extremely good explanations coupled with zero tolerance for fools. As long as you asked him a question in good faith, he treated you with courtesy. But I confess I relished the entertainment of reading his deconstructions of bad-faith actors.
Naggum died much too young. I hope he has found peace.
And these people always say they're "just being direct".
It's a good litmus test for me in my own writing. Am I actually being direct or just indulging in anger? What happens if I just get to the point and say what I want? I have found I get more of what I want that way.
It’s been a while since I’ve seen those photos on the wikipedia page, which I took. He was very photogenic. He came to Berkeley for a Lisp conference. Brings back some really good memories. Thanks.
Naggum destroyed the Lisp community by driving away everyone who didn't relish it. (Like you, Xah Lee did relish it, even when the bad-faith actor being "deconstructed" was a character he was playing—perhaps especially then!) He also had, as you can see in this post, zero tolerance for people preferring different tradeoffs from his own (often because they held different values), which fragmented it.
German has this great word for your comment: "unterkomplex". The English "simplistic" might come near. comp.lang.lisp was not "the Lisp community", Naggum did not single handedly destroy it, you ignore the other participants, the general Usenet dynamics and its overall fate...
Usenet was important for the development of many other language communities, and Lisp was denied that opportunity. Naggum didn't act alone, certainly, and bad blood existed in the Lisp community since before Usenet (Stallman is a difficult person, and we can all be grateful he never actually bombed the Symbolics offices), but he was the pivotal figure in how things played out in the late 01990s. There wasn't a Naggum-free alternative general Lisp venue where new users (or Lispers who merely disagreed with Naggum, such as Schemers) could post without fear of public humiliation, so mostly they didn't. It's a rare undergraduate who doesn't count public humiliation among their worst fears, and for people like Steele, Weinreb, Gabriel, Friedman, and Stallman, participation on Usenet was all downside with no upside.
Lisp started to recover immediately when Naggum died. Or, more accurately, when he got too sick to post.
I could make the same criticism of HN, but to a much smaller degree.
Kaz is of course correct that in Lisp, as in any language, there's a silent majority of programmers who don't post in public forums like Usenet. But they depend on the efforts of those who do for things like FAQs and free software.
None of this has to do with me; I can't have posted to comp.lang.lisp more than a few times, and I don't recall ever interacting with Naggum.
Most of what I've said is self-evidently correct, and almost all of the rest is relatively easy to verify by reading the archives of old mailing lists and Usenet.
The only exception is my insinuation that Stallman was tempted to bomb the Symbolics offices, which I don't have a reliable source for; maybe you could find out by asking Stallman, or Stallman's former friends and former coworkers.
"self-evidently correct" is not a good word if you want to discuss things with people who were actually active in the wider Lisp communities, including comp.lang.lisp, other newsgroups, various mailing lists, Lisp conferences, etc.
My objective here is not to attack you for your partisan support of Naggum; rather, I want to understand what alternative perspective you're coming from in which my observations perhaps aren't self-evidently correct—though I note that you've carefully avoided actually saying they aren't, leaving open the interpretation that it's just that you wish I'd phrase it differently.
> My objective here is not to attack you for your partisan support of Naggum
Look, I'm not supporting Naggum.
From the actual Lisp users I've met in real life, few were reading comp.lang.lisp, almost none was posting there. Very few would even know who the people there were.
The actual people in the Lisp community I admire are many - I could list 100 - they had a much greater impact on what was happening. Most of them never used comp.lang.lisp . Among women the participation rate was near zero!
Most of the interesting communication was in specific communities over mailing lists. I fondly remember SLUG (the Symbolics Lisp Users Group), the MCL mailing list, and several others.
comp.lang.lisp had the most negative impact by trolls, like the one Naggum was answering, which caused endless bullshit discussions and which had very destructive behavior. We never found a way to deal with that. What it killed in the end was that the time for Usenet was over, Google groups, spam, it was mostly irrelevant and a much more toxic Internet took over. See 4chan, various Reddit groups (though the Lisp subreddits at Reddit do better) and X for much worse communication systems. Plus Lisp was in a general demise in the 90s. Not the Usenet caused the demise of Lisp, but the demise of Lisp was causing a general lack of interest. Cause and effect were different of what you claim.
For you the contact to Lisp could be mostly net related (?). When I was learning at the university roughly up to 20 professors were in some way or another involved in Lisp projects. There were people I've seen in real life, often daily. There were many people with deep Lisp knowledge (and this was not even the US). You can bet that none of them used or cared about comp.lang.lisp. Same for the people in the projects and the students.
What you think was "the Lisp community", was just a popular online community of mostly random people, with less impact on what actually happened in the Lisp communities, then you believe.
It seems like our points of view are closer together than I had thought.
I first learned about Lisp because my uncle lent me a Lisp textbook; later, an executive at the company I was working at lent me SICP and exploded my brain. Most actual Lisp users I've met in real life weren't reading comp.lang.lisp either. But it's true that most of my contact with Lisp has been over the internet.
That's because most of my contact with any technical discipline has been over the internet, because almost everyone's has been, for 30 years now. It would be inconceivable to say, 25 years ago, "Most actual Perl users I've met don't read comp.lang.perl.misc," or, "Most actual Python users I've met don't read comp.lang.python," but it was and is true of Lisp. Sharing code and discussions over the internet has been a superpower for the programming-language communities that have managed it, including cross-language communities; I first got to know pg on the Lightweight Languages mailing list, for example. Meanwhile, Lisp users were isolated in the kinds of tiny single-implementation ghettoes you describe, or were collaborating only with other researchers at the same institution.
What I'm pointing to is precisely the fact that comp.lang.lisp was just mostly random people with little impact on what actually happened in Lisp. Every person who might have taken up Lisp, who instead focused on Perl or PHP or Haskell, was a missed opportunity for Lisp to thrive. As with the undiscovered antibiotics resulting from our current pharmaceuticals regulatory regime, the costs are invisible, but staggering. They are the Lispers that weren't born during the 01990s, the Lisps that didn't get finished or even started, the libraries that got written in Perl or JavaScript because Quicklisp and Leiningen didn't exist yet (as far as I can tell, there's still no equivalent for Scheme.)
You're right that trolls like Xah were what made comp.lang.lisp unusable. However, despite the almost 800 lines of code he contributed to Emacs, Naggum was one of them—the worst of all. Those 800 lines are apparently the totality of his public code, and in total they're smaller than some of his individual hate-filled posts to comp.lang.lisp. The period of Naggum's unquestioned domination of the newsgroup was precisely the period during which Usenet was the most important groupware medium. And the practice of establishing dominance by public ridicule didn't end at the boundaries of Usenet; as dang points out above, to this day we still have to combat it in virtually every public discussion of Lisp. That's Naggum's lasting legacy.
Since he became inactive, though, the situation has improved dramatically. We have Arc, Clojure (and Leiningen!), SBCL (which started while Naggum was still active but took years to become popular), the entire Racket empire (now built on the redoubtable Chez compiler), several new "Little" books, miniKANREN, Hy, Quicklisp, R7RS-small, and, as you point out, reasonably functional subreddits. #Lisp on Libera is a pleasant place, and Emacs Lisp and Guile now have native-code compilers. ACL2 and PVS are significant minorities in formal methods. You can even run PDP-1 LISP, or modify and reassemble it with MIDAS.
I don't think that's true, although maybe you could define "Perl programmers" to include people who downloaded broken, insecure CGI scripts from Matt's Script Archive and made random changes to them until they seemed to work. Even a lot of those people relied on clpm for guidance—often asking questions rather than just lurking. As you can remember, we didn't have Stack Overflow at the time, or even PerlMonks, so clpm was pretty much the main public forum for people to ask questions or announce libraries. Corporate and academic institutions to support Perl basically didn't exist; perl.com was running off Tom Christiansen's home internet connection for several years.
I don't know what "hole" you're talking about. The hole of correctly describing how the Lisp community destroyed itself by permitting Naggum to dominate its public communications, and to some extent has recovered since then?
Perhaps you're implicitly criticizing me for violating some taboo so dreadful you don't dare even to name it; for example, a taboo on speaking ill of the dead. Unfortunately, any truthful accounting of almost any tragic historical events requires willingness to speak ill of the dead, so I'm more than willing to "dig" myself into that "hole". I'd like to invite you to join me here; cowering in fear like that is unworthy of you.
comp.lang.lisp is not the same thing as "the Lisp community".
Even in the heyday, the Usenet news groups represented a minority. For any language, OS or tech stack, there were many more programmers off Usenet than on.
A programming language newsgroup represents the intersection between interest in that language and interest in Usenet.
He made it a kind of game or culture. Also iiuc he's answering to a certain person who was known to be regularly walking on the line of trolling. That might have added more fuel to the fire.
Erik Naggum (RIP) was particularly noted for having lots of bile if you got on the wrong side of him.
Xah Lee is noted for being especially abrasive and pretty much gets on the wrong side of everybody.
Putting the two together was always a spectacle worth a bucket or two of popcorn.
And, the real answer to "Why cons cells?" is the same reason as "What is up with the names car and cdr?". The only two data structures which are cheap enough (in both RAM and CPU) for the machines of the time (IBM 704 from 1954!) to deal with are arrays (via index registers) and pairs (via register sections which gives us car/cdr).
It is possible for your brain to parse information from people you don't have a personal connection with as what the message is and skip the how. Not sure why people get lit up by the how; who cares about that from people you don't give a toss about? These days you have AI for it; Claude can give you a lovely summary of the facts without the how. My brain does that automatically since I was in high school. Comments from anyone but close friends or close relatives cannot make me 'unhappy', no matter what they are.
He was highly intelligent but he had an odd childhood and was somewhat isolated socially, in the real world. It’s what ultimately killed him. At least outside of tech. Near the end he was almost a cult-like figure, at conferences especially. He would accumulate a hoard of fans. I’m unsure if he liked that.
He really loved coming to the Bay Area.
I definitely miss him irl.
Sorry for the ramblings. I’m on mobile and editing is hard.