Donald Knuth was framed (2020)
buttondown.email
buttondown.email
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”:
• 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 https://tug.org/docs/liang/ (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).
• Part 2 would go into the Bentley–Knuth-McIlroy story:
• Part 2a ("Before"): Bentley's thesis/book on writing efficient programs, and the Programming Pearls 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". (“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”) 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 Pearls column, and published one program of Knuth's (the random-numbers one) and asked him to write another (the frequent words one).
• 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.
• 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 (https://news.ycombinator.com/item?id=22406070). The short-lived LP column in CACM that it spawned (https://shreevatsa.net/post/programming-pearls/) 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).
• Part 3 would compare the two approaches (even though they are not meant to be compared!), mention how at https://codegolf.stackexchange.com/questions/188133/ 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).
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…
Just publish a volume every few years, and fascicles as necessary, and then eventually…
- show how to write a spreadsheet application
- here you go, couple of hundred pages it is though
- ahh, silly person, why not type 'excel'
So what happened next? Everybody rolled eyes, or people said 'yeah, typing excel is pure genious'?
This happens repeatedly (not just this example, many others), and since the vast majority of people are never going to go back to the original sources we have a giant game of telephone. Generation after generation are given a variation on the summary theme, further and further removed from the original context. The speaker will elaborate on the criticism, but since they didn't read it themselves they're actually just bullshitting (semi-honest effort as they're pulling in the information they were given, but it's still bullshitting because they didn't bother to read).
https://en.m.wikipedia.org/wiki/Literate_programming#Critiqu...
We should look into this. Want me to add a Jira Epic?
It takes a little while before habits change, but I think I have learnt more in the last year at age 40 than I did in my first year of undergraduate aged 19.
An aspect of Observable which is particularly compelling since Knuth is the fact that inter-notebook dependencies are hyperlinks, so these are not standalone literate programming artifacts, but they are a graph of explanation too. You can learn a lot by surfing notebook dependencies. Bundling code with documentation is such a win.
The other thing about Observable is the cells are reactive, so your documentation is not necessarily static either. You can provide animated interactive explanations too.
More info on the different types of content you can embed
https://observablehq.com/@observablehq/cell-modes
More info on the spreadsheet like execution ordering:
https://observablehq.com/@observablehq/observables-not-javas... More info on the literate programming support
This seems to be re-inventing that.
Hm, that's really relative... on Babel, you can also have reactive cells, and while it's true that having Obervable run on the web + JS is great, I could say that Babel "is more" because it supports pretty much any language, not only JS, and does not require an internet connection to work.
https://observablehq.com/ambassadors
I am trying to build a serverless compute layer on top of observable.
https://observablehq.com/@endpointservices/webcode
If I was shilling webcode.run then I would think a disclosure would be appropriate, but as I was just talking about how great Observable is as a literate programming env, I do not think I have anything to disclose.
I mean, if I was participating in a computer programming class and given the same problem as an assignment, I would write a program to satisfy the requirements. If then told that I should have written a few lines of shell script instead and given a poor grade, I would be livid at the instructor.
As an aside, I was interested to know if there are LP tools for shell scripting. A cursory search turned this up:
jupyter + xon.sh kernel almost can do it too.
Well notebooks aren't exactly to explain programs but to experience with them, no weave or tangle, you can only execute them if your cells are in top-down order.
Anyhow, being able to save the experimentation fragments can lead to better documentation compared to when you experiment in a different terminal.
There is a paper [0] which documents an interesting disagreement about a project: The developers considered it a huge success but management considers it a complete disaster. Very different interpretation. Does it work?
As an example for religious behavior we could look at Powerpoint. An application which is used with practically religious fervor. However, the application is mostly misused so badly that the goal of supporting the transfer of knowledge or persuading people is not achieved. Does it work?
Without agreement about the goal/requirements, you can not determine if the resulting software works. In my experience, precise goals/requirements are often missing, so a simple question like "does it work?" is also open to interpretation.
[0] Software Developer Perceptions about Software Project Failure: A Case Study by Kurt R Linberg, 1999
Someone give this guy a medal.
There's probably tons of (academic and industry) research on the topic from sociological and economical aspects. Well, if not so much with a focus on how fashions emerge and manifest themselves within the field of programming, probably at least in many other fields.
And then? It was reimplemented in 'icon', incompatible Proteine, too, and the community feel apart.
That's a real pity because noweb got almost everything right.
However.
Imnsho the real challenge for literate programming is IDE support. Not only do you embed languages into each other. In addition you chip chop your code into fragments and distribute them all over your file...
For their purpose, incrementally derive some computation and data analysis, that's fine. For describing a complex system to both a human reader and a machine, in that order, that would not be enough.
Both of these motivations are valid and good. The hard part is knowing at what level of each do we get the best balance of the two.
In one the situation, the "novel" analogy would be appropriate. For instance, I would be very interested in detailed explanations of something like PostgreSQL. A well-written book by someone (or "someones") with intimate knowledge of that code could be tremendously valuable. Here I have in mind something that actually walks through parts of the code, in a literate programming style.
On the other hand, maybe you don't want that much detail, but you still want some understanding of the code in order to do a small task - in that vein, something of the 'car manual' variety would be more appropriate.
I can imagine a full spectrum, from a multi-volume Knuth-like set to something on the order of a single-page cheat sheet. The problem is, it always comes down to how much time do you have to accomplish what you need to accomplish, and how much time will those writing the checks allow you to make informed choices on how things are documented (which, unfortunately, is all too often, ZERO).
It seems to me that both McIlroy’s original critique and this blog post miss the point by a mile. It’s completely meaningless to compare the relative merits of the two solutions, because Knuth’s ultimate goal isn’t to produce a solution.
Doing a presentation on literate programming has to deal with two more or less contradictory concerns — you need a sufficiently simple problem that your audience can follow along, but you need your solution to be complex enough that you can actually illustrate LP.
A sorted frequency table is a simple enough problem statement, a trie is a sufficiently elaborate solution that doesn’t feel too contrived while also being familiar enough that the audience can follow along. Knuth’s approach was pretty much the perfect way to hit both of those requirements!
I don’t follow: aren’t you effectively restating the blog post’s argument? How did the blog post miss the point?
As one of the essays linked yesterday noted, Knuth did not pick the problem, he specifically asked the editor to do so, such that he would not necessarily select a problem perfectly suited to LP.
The origin of composing simple programs that do one thing well is likely was originated as the consequence of the introduction of shell pipelines (or the genius pre-designed property).
Pipelines is a good example of "less is more" concept.
Source: big Perl evangelist back in the 1900s.
You were really ahead of your time.
I think people genuinely get confused that the century that has dates like 19XX was the 20th century, so they say "1900s" to cover for it. But that has an established meaning, namely 1900-1909.
I'm not going to claim to know the history of how terminology develops. But I don't think I have ever come across someone using "XX00s" to refer solely to the first 10 years of that time period.
The general rule of thumb for reading numbers is to treat every trailing 0 as a marker of an insignificant figure, so a number like "1,000,000" is presumed to have 1 significant figure and not 6. By this rule, the most natural interpretation of 1900s is that it encompasses 1900-1999.
Not to anyone I have ever known. I have never before this post today heard anyone say that "the nineteen hundreds" means 1900-1909. It always refers to 1900-1999.
I've only ever heard of 1900-1909 referred to as "the aughts" ( https://en.wikipedia.org/wiki/Aughts ) - which, admittedly, always sounded weird to me, but I wasn't alive then.
1700s may refer to:
- The century from 1700 to 1799, almost synonymous with the 18th century (1701–1800)
- 1700s (decade), the period from 1700 to 1709
I now realize that my motivations are same as literate programming. My focus is to get features integrated into codebase. A developer should only do incremental programming, which will insert code into centrally hosted codebase.
Both have important points.
Edit: I'm a bit tired of all these "this is not something that you would actually ever do" caveats, well, don't show it then?
Because solving real world problems in a solid way is often too complicated for a presentation, but to show something special you sometimes have no other choice to come up with non real solution that show the principle. But I agree that you can do this in a bad or good way.
But almost nobody has to solve this on practice. The ones that do have recreated the idea again and again (today's most common iteration are Jupyter notebooks), because it's a great idea. But they are always a waste of time for most people.
Except that they do solve problems people have, just not problems you have. They are meant for, or at least often employed by, the disabled community.
https://www.vox.com/the-goods/2018/9/20/17791354/products-pe...
Ultimately his approach won and today >90% of programming is just stitching together the code someone else wrote so it sorta works for your problem.
Much maligned here nodejs ecosystem is implementation of his approach to web development.
We'd never get anything done if we programmed like Knuth. You can do good literate programming but you have to be living in a truly slow world to do it like Knuth does.
I'd like to see the TeX program written in a shell script.
1. We're substituting characters and we're looking for is all word characters, and what we replace with is a newline. That doesn't seem terribly useful at a first glance, so either -c or -s is probably a negation. So this probably splits by words, producing newline separated words.
2. Change A-Z into a-z, that's obviously uppercase to lowercase. Confirms that text is what we're working with.
3. Sort alphabetically.
4. Remove duplicates and count.
5. Sort numerically.
6. Not entirely sure what 'sed ${N}q` does.
So yeah, I can get most of the way there without looking at the manual at all, making the reasonable guess that it results in a list of words sorted by frequency. My main point of confusion would be with sed, because it's hard to search manuals for the meaning of 'q' and I'd have used 'head' instead. Looking up what's the deal with 'tr' is about 5 seconds.
But yeah, head -n (--lines) would do the job here perfectly while being more readable, no clue why it wasn't used.
It's a shame that it's only primarily used for Data Science experimentation & teaching.
Features that actually are important: Code can be written in fragments. The output is a program. Fragments can be appended to.
It's not a bad tool but I think it's a bit ugly and relies too much on saving state in the notebook.
In firstclass languages a complex problem can be solved by chaining together functions and can be written in a single statement (this depends on the implmentation of functions and types that are returned). Somtime 2 or three statements.
Versus using core language statements and packages to implement conditional logic, control structures, and operations. Relying less on packages that extend the launguage. Having full control over the implementation.
Personally I prefer declarative and wrapping it with verbose inline documentation.
One downside to this is maintaining the build environment. Packages are versioned and fucntions change overtime (deprecated in favor of new implmentations that replace the old function). Somtimes Declaritive implementations must be refactored to support newer version of packages.
Impertive implementations tend to be more durable and have fewer dependencies.
And it has its merits: you see how a problem is tackled.
I believe this should be obvious.
The idea of a company having its engineers livestream all their production work kind of terrifies me, but might also be kind of an interesting way to do business.
I wonder though if being able to write code and explain it at the same time is a skill like singing and playing guitar at the same time. I’ve never live-streamed though so couldn’t say. Any tips for trying it out, good reasons to do it or reasons not to?
The equivalent in commercial settings should be pair programming. I was on the headset with another programmer who would realize some concepts only as he put them in words and explained them to me.
But the same thing was the case in academic settings. I could tackle some problems only in dialogue (again over headsets) and only in mutual we would even be able to come up with many solutions. I found that it only works in a pair settings and it breaks down in a setting of three.
I think once we engage the speaking part of our brain we unlock something that makes us find solutions instead of take ambiguous shortcuts.
Advocating for LP in commercial product development sounds like dreaming. No way would someone who has to meet deadlines write these long, qualitative descriptions of what the code was doing. Martin's suggestion of building the 'narrative' into the code itself sounds much better in those cases.
So Unix classic McIlroy's is good for quick run, daily driver who can't really evolve much, at least not at a little price. Knuth on it's side equally felled in the same trap on the opposite side of the spectrum.
The real outcome is that Unix model is wrong, and it's a well-known things behind the Unix Hater's Handbook simply when unix choose to through it's principles in a bin making GUIs from the first CDE and beyond where no small programs nor composability via efficient IPCs is there. Sole IPCs available cut/copy/paste. The right choice was done before: with Smalltalk systems at Xerox, with Lisp-based systems after them: which means a moderately literate and discoverable environment where anything can be easy integrate in code so where shell-scripting is actually the same of system programming and the literate part, based on literate code, is just literate composition not much different then the classic human notes compositions from Mundaneum to ZettelKasten. That's is. Unfortunately since NOBODY want to admit mistakes especially if they was made in the past and imply large areas of development nearly no one want to talk about those terms...
otp-secret | 2fa-code | pbcopyI know some have analyzed their (unsafe) protocols and now use desktop otp software, but that's not a thing should ever be needed in the first place: banks who mandate the usage of unsafe platforms (and the rise of Android banking malware is a nice proof) must be forbidden by law with sanctions severe enough no one ever try to push such systems just to grab more data from their customers.
A thing we already see for EV recharge and other activities.
The point is that in a near future our identity will be only provable by them, NOT by States [1] so a private company can say who you are or not, not your government. We will been able to pay things only if the new substantial de-fact dictator, the GAFAM, decide that we can, since all payments will pass through their platform [2], we will be weighted from the birth by bid data analysis on our DNA [3] having careers pre-defined by social scoring systems (witch means by bad choices and corruption, like in China and UK) well trapped in such dystopia.
I understand that casual citizens can't understand but on HN it should be a hot topic if we still have hope.
So the point is mandate a total ban of such practice, imposing and open IT for the profit of the whole society not of some big&powerful against all the rest. Witch means coming back to classic IT vision, because actual IT is born back then and distorted just to evolve in such limited, limiting and dangerous manners...
[1] http://www.koreaherald.com/view.php?ud=20191029000735
https://apnews.com/article/smartphones-germany-5daa87f5b6f2b...
https://www.apple.com/newsroom/2021/09/apple-announces-first...
https://arstechnica.com/?p=1791967
[2] one of the many
https://www.theguardian.com/money/2021/sep/06/the-end-of-the...
[3] https://www.axios.com/china-makes-genetics-data-national-res...
https://www.dailymail.co.uk/news/article-10200315/Government...
https://www.codastory.com/authoritarian-tech/pakistan-biomet...
https://restofworld.org/2021/the-dystopian-danger-of-a-manda...
That's what computer science in the 1970s and the 1980s was all about. Clever algorithms. Especially at MIT. Read the classic HAKMEM from 1972.[1]
But Jupyter Notebooks does it more like a REPL where every code block can be executed separately, which is nice too. Afaik this is also possible in Emacs' org mode.
Another extremely important successor to Knuth’s ideas is the built-in documentation comment formats that most programming languages have. They tend to eschew linear narrative in favour of navigable hypertext, which is honestly a good idea for many purposes but sadly relegates the “overall vision” stuff to supplementary documentation.
It's nonsense - the various shell scripting languages are more than capable of implementing those various tasks without simply shelling out to C, and so should be required to. Otherwise a C programmer has access to system() and start() and those support pipes even.
Given some text input via stdin, we want to find the word that appears most often. The main body of the shell script is as follows - each section uses plain shell utilities and has been developed and tested with (blah blah, maybe mention the version of the utils we used in case GNU versions work but BSD don't or something)
<<makeLines>> | <<convertToLowerCase>> | <<sortAndCountLines>> | <<sortLinesByFrequency>> | <<takeFirst>>
<<makeLines>> = tr -cs A-Za-z '\n'
<<convertToLowerCase>> = tr A-Z a-z
<<sortAlphabeticallyAndCount>> = sort | uniq -c
<<sortNumerically>> = sort -rn
<<takeFirst>> = sed ${1}q
This is the first time I'd ever written anything approaching LP (I just copied the style in the article) so I just quickly dashed it out with placeholder comments, though I'd maybe include a worked example of the program in action too showing the output at each step. Now obviously it's longer than the little shell snippet that was posted, but even though it is a relatively tiny problem to apply LP to, you can see that there is still some value to it - I've been able to make it clear that only the latin alphabet is considered, I've highlighted a potential oopsie in case someone inexperienced in tries to re-use it (-r/-R), I was able to state that there's an alternative approach to the final step and give a reason why I chose my way.
<<game-loop>> ==
while (!dead) {
<<get-input>>
<<update-world>>
<<display-world>>
}
<<main.c>> ==
<<includes>>
<<globals>> // if appropriate
int main() {
<<initialize-game>>
<<game-loop>>
return 0;
}
And, you can (like I said, text macro-ish) reuse blocks of code in multiple places. Maybe you have some common header files, you could write this:
In order to have access to OpenGL capabilities, many of the .c files
will require this header block:
<<OpenGL-includes>> ==
#include<GL.h>
...