Knuth and McIlroy Approach a Problem (2021) | Hacker News Reader

Knuth and McIlroy Approach a Problem (2021)

matt-rickard.com

58 pointsingve26 comments

Once again: this does not demonstrate Knuth's approach to solving a problem, it demonstrates Knuth's approach to pedagogy.

also it was not a 'competition'

I'm reminded of the old adage about playing chess with a pigeon. It knocks down the pieces, shits on the board and flies off.

What made you remind of it?

The response to Knuth.

He wrote a general program to solve the problem. The supposed solution in bash depends on the exact programs existing already. If you changed any of the original requirements you'd need to do write a c program to do the new type of filtering. If you did it for the literate program you need to read some prose and modify some already existing code.

While there seems to be a difference in how they perceived what the stated problem actually was (where Knuth interpreted it as a call for a pedagogically laid out solution and McIlroy seemingly didn't?) I disagree with your conclusion here.

They chose different languages to express themselves in or with. Bash and WEB, respectively. Given other and perhaps even changing requirements, who knows what they'd have done? Why would McIlroy have had to resort to implementing (parts of) his solution in C and not, say, AWK or just in terms of more and other Bash constructs?

The conciseness, perhaps even terseness, to McIlroys expression is very elegant and despite the fact that I could not repeat that, I'd still call him a winner in a number of different hypothetical competitions drawn from this context of interactions.

And I'm in love with Donald Knuth!

The story, as a dialogue:

Knuth: I've come up with an idea I like, called literate programming, and a system called WEB. I wrote TeX in WEB.

Bentley: I took a look, and I love it! But TeX is 600 pages long; could you give me a WEB example of a few pages, that I can publish in my magazine column?

Knuth: Sure, but that would be too easy: why don't YOU tell me what program to write in WEB?

Bentley: Ok, write me a WEB program to find the top K most common words in a text file.

Knuth: Sure, here's a WEB program for the problem, as you asked. It's long enough that your readers can see the main features of WEB, and I also came up with a new data structure so that everyone learns something.

Apparently, according to many commentators (such as the linked post), Knuth ought to have instead replied with something like:

Knuth: Ok, well, you asked me to write a program to illustrate WEB, but actually… Most of your readers won't know this, because it's still 1986, but if they go to a place like Bell Labs they can find the Unix operating system, where Doug McIlroy has come up with a system for combining programs called Unix pipelines, and other people have already written text-processing programs with names like 'tr', 'sort' and 'uniq' (you can look up what they do). So, if any of your readers is using such a system, they can just use those pre-existing programs with an appropriate pipeline. Ta-da! Even though this solution is much slower, I'm sure you won't mind that I didn't give you a WEB program for your column as you asked.

This reply would make no sense! Only with a game of telephone/whispers does the story become cast as a "competition". Anyway, for completeness, the rest of the story was:

Bentley: Thank you for your program. I've asked Doug McIlroy to write a review.

McIlroy: (After writing the review.) BTW, our Unix land is awesome, we have this thing called pipes; we could solve this problem with just…

A couple of previous discussions (there have been many):

https://news.ycombinator.com/item?id=31301777 - Donald Knuth was framed (2020) | May 2022 | 137 comments

https://news.ycombinator.com/item?id=30017311 - More shell, less egg (2011) | Jan 2022 | 24 comments

https://news.ycombinator.com/item?id=22406070 - Donald Knuth was framed | Feb 2020 | 183 comments

Evolution of Haskell Programmer[1] comes to mind.

[1]: http://www.willamette.edu/~fruehr/haskell/evolution.html

If you want to understand McIlroy's code, you can always read the what McIlroy wrote in what McIlroy wrote in Communications of the ACM.

If you want to understand Knuth's code, you can always read what Knuth wrote in the code Knuth wrote.

To the degree "programs must be written for people to read, and only incidentally for machines to execute" McIlroy's code traded incidental complexity for brevity. Considering his ordinary expectation that readers would be "old Unix hands" at Bell Labs, this is probably an entirely reasonable engineering tradeoff.

Knuth's intended audience has always included at least his future self. To the degree "debugging is twice as hard as writing code in the first place" verbosity is also an entirely reasonable engineering tradeoff. He's been working with some of some of his algorithms for sixty years.

If I had a criticism of McIlroy's response -- and I say "had" because it's been forty years more or less -- it's the either or approach. Literate programming is a not-for-me for a lot of people. That doesn't make it bad or good. Just a not-for-me.

But hell, forty years ago we didn't have so many chances to scratch itches to argument. Arguments always drive engagement for publishers.

Some things don't change very much.

https://news.ycombinator.com/item?id=18699342

Every few years, I contemplate the idea of trying out literate programming. I get that notebooks have continued to trends of "mixing prose and code" to great success ; however, I really wonder how the "out of order programming" works out in practice.

Sadly, I never managed to go passed the "my editor cannot show syntax highlighting for a mix of languages." :/

This is doable in Emacs, using org-mode and org-babel.

You're right, I should have mentioned org-babel as the closest thing to something that would work for me.

However, as soon as I start using noweb syntax for "out of order" programming, I stumble into long standing bugs (references are not always found, links in the tangled code are broken, detangling does not work, etc...)

Not sure what editor you use, but most syntax highlighters these days can mix languages: you see this e.g. in HTML <style> tags and Markdown fenced code blocks.

As for 'out of order programming', I think that TANGLE-style reordering is a lot less important with modern programming languages: they don't do one-pass compilation and so can deal with forward references. Note that most of the cross-references in Knuth's program could be replaced with function calls or constant names, rather than the semiautomatic inlining that WEB performs.

I've had some success in writing literate programs in a Markdown file, with a small script to extract the code blocks into a file for execution. This seems to work fine, at least on a small scale, and is very easy to implement and then extend if needed.

Edit: and by “small script” I mean:

    import sys
    code = False
    for line in sys.stdin.read().splitlines():
        if line == '```': code = False # End block
        if code: print(line) # Only output block contents
        if line == '```md': code = True # Start block

It also seems worth noting that you can get much the same result just by writing a lot of comments; this technique is mainly useful when you also want more formatting than can be reasonably squeezed into plain text. /edit

Another point is how long did Knuth spend on this solution? These days this is an interview question to be completed in an hour, lol.

When did they hold the competition? I believe the textbook solution to this is using a heap.

It wasn't a competition. As I remember it, Jon Bentley asked Knuth to write an introductory example of literate programming, and McIlroy to review it in something like the way a literary critic would critique an essay. Both responses were thoughtful. I learned more from the Knuth, but then I was already familiar with the Unix philosophy.

To use the heap you still need to look up the words efficiently.

It’s reprinted in Knuth collections so even he notes the point - there’s a time and place for everything.

And one requires WEB and the other requires the entire Unix tool chain.

(And the only reason the Unix critique is ever mentioned is because of the literate programming version. Which would programmatical archeologists love to find in 2525 - if man is still alive?)

> To use the heap you still need to look up the words efficiently.

Why? Just split the text and put everything into the heap, the heap algorithm will maintain the sorted order by rebalancing during insertion

The textbook solution I assume you meant, to find the most common k elements of a list, uses an updatable priority queue (heap). This orders the (key, count) pairs by the count. But that's a separate question from how you look up the key (i.e. given a word, find the pair whose count you want to increment), which is what Knuth's hash tries were for here.

Thanks for the clarification

It seems the date was 1986. What I find surprising is McIlroy's solution feels completely modern still, one could still solve the problem more or less in the same manner today when writing a command pipeline on a unix derived os. Even the names and syntax of the commands hasn't changed.

That unfortunate remark by McIlroy did more harm to himself that Knuth.

Only because you agree with Knuth.

Both McIlroy and Knuth have valid points. There's a reason that not all shell scripts are written in the literate style. There's also a good reason why large programs aren't written like shell scripts

> Both McIlroy and Knuth have valid points.

Knuth was asked to write a program illustrating his technique of literate programming, which he did. He was not making a "point". He was making an example. Very different things. McIlroy came in and made a point in his review. Other people, presumably illiterate because the source is available and we can know what was written, made it into a competition or debate. Which it was not.

There's nothing to "agree" with Knuth here. He wrote it to demonstrate WEB and literate programming, not because he thought it was the best-fit solution to this task.

Ok, but McIlroy was asked to critique it. I suppose you could say that he was asked to critique a literate program, but that seems to me like complaining to Mr Ford, because you asked for a faster horse, and he came back with a car. Literate program is meant to solve a problem. The goal should be finding the best way to solve that problem. Not solving the problem based on some preconceived notion.

Perhaps "agree" was the wrong word, but this exchange is remembered for a reason.

Reply on news.ycombinator.com