I guess this was posted after someone saw this come up on HN yesterday: <a href="https://news.ycombinator.com/item?id=31295427" rel="nofollow">https://news.ycombinator.com/item?id=31295427</a><p>I've been planning (for 2+ years now so it probably won't happen) writing a large blog post about this matter, which would be called “Tries, Packed Tries, and the Bentley–Knuth–McIlroy story”:<p>• Part 1 would introduce the trie data structure both abstractly (the tree structure) and concretely (how exactly to represent the children of a node), with the trade-offs: as a linked list (space-efficient, slow lookup), as an array (fast lookup, takes space), or as some more nontrivial tree structure itself (“yo dawg…”). Then we'd discuss the really cool idea of “packing” the array, as nicely described in Frank Liang's thesis <a href="https://tug.org/docs/liang/" rel="nofollow">https://tug.org/docs/liang/</a> (also mentioned in TAOCP Exercise 6.3:4 and answer, which incidentally refers to the CACM Bentley–Knuth–McIlroy article that we're talking about). We'd also illustrate how hyphenation is done in the TeX program using packed tries (maybe this can be a separate post).<p>• Part 2 would go into the Bentley–Knuth-McIlroy story:<p>• Part 2a ("Before"): Bentley's thesis/book on writing efficient programs, and the <i>Programming Pearls</i> column. Knuth writing TeX first for himself in SAIL in 1977–78. The instant interest and ports/rewrites it led to. Knuth responding by rewriting TeX into its current form in 1980–82, and how the goals of portable software (thus Pascal, and its limitations! see BWK rant) and of eventually publishing it as a book led him to the idea of literate programming, which he still considers the most important outcome of his years into the TeX project. Meanwhile, at Bell Labs, McIlroy's invention of Unix pipes, and the instant excitement of "pipe day". (<i>“It was absorbed instantly into one's outlook on programming. And by the end of the week secretaries were piping the output of NROFF into the printer”</i>) The Unix philosophy, and how it took a while to spread. How these three threads came together in 1986, when Bentley read Knuth's TeX, wrote about LP in his <i>Pearls</i> column, and published one program of Knuth's (the random-numbers one) and asked him to write another (the frequent words one).<p>• Part 2b (the program): How Knuth ingeniously combined the idea of packed tries with that of hashing with linear probing, to create the data structure especially for this problem (maybe we can call it a hash-packed trie?). Another look at his very nice idea/program, presented differently (maybe some illustrations of how the data structure works), and some design choices he made.<p>• Part 2c (the review and later): How Bentley got McIlroy to review it, a close reading of the review: its actual content and points about LP and Knuth's style, and finally the (first sentence and) last part where McIlroy used the review to advertise his own Unix philosophy and the short shell pipeline version. The further reactions to this, including Bentley's remarks in the same column, and later articles and reactions like the "prefabs" comment (<a href="https://news.ycombinator.com/item?id=22406070" rel="nofollow">https://news.ycombinator.com/item?id=22406070</a>). The short-lived LP column in CACM that it spawned (<a href="https://shreevatsa.net/post/programming-pearls/" rel="nofollow">https://shreevatsa.net/post/programming-pearls/</a>) and how it fizzled out, how it turns out everyone wants to do LP in their own system. How the story got bastardized over time (the misleading "More shell less egg" blog post for example, and some other examples of people misunderstanding the history entirely).<p>• Part 3 would compare the two approaches (even though they are not meant to be compared!), mention how at <a href="https://codegolf.stackexchange.com/questions/188133/" rel="nofollow">https://codegolf.stackexchange.com/questions/188133/</a> I simply translated Knuth's program into C++ and beat the then-fastest Rust solution (since beaten again by translation from C++ back into Rust: still based on the trie idea though!), some words about cache misses and 32-bit “pointers” in a 64-bit world (and Knuth's rant about it).<p>Something like that: it's probably too long for me to ever get around to writing it (or for anyone to be interested in reading), though…