1

I remember this anecdote from shortly after I graduated college, so it was on the internet at least in 2014. The point of the anecdote was that two equally valid solutions to a problem can take drastically different approaches with different cost and difficulty and each have value as measured by different metrics. I can't recall, however, if I heard this spoken in a YouTube presentation (possibly at Strange Loop or Google IO) or if I read it on an online post, but I know I heard the story online.

The story went roughly like this:

A company needed to accomplish some task (perhaps finding the sum of all accounts who were overdue)

They hired a famous software architect with 40 years of experience

The architect gathered specs, built a definition of the problem, and worked for 6 months. When he was done he had written tens of thousands of lines of code including very elegant solutions to problems the likes of which the industry had never seen. And his code worked perfectly

Then another developer came along and solved the same problem in an hour with 6 lines of bash script

In the postscript of the story (perhaps discussing it afterwards) they mentioned that technically the bash script utilized other tools like awk, sed, and grep so you need to factor in the lines of code for those programs as well to find that this one-hour solution was technically less efficient and had more total code involved - yet it was solved faster and it worked just as well.

I'm hoping someone can help me find the source of this story

closed as off-topic by kimchi lover, Chenmunka, Gallifreyan Nov 7 at 15:05

  • This question does not appear to be about literature, within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • I'm not voting to close right now, but I think this pushes the scope of Literature. Even if it is on-topic, I think the chances of you discovering the source of the anecdote are likely to me much higher elsewhere. While there are almost certainly people here who read programming literature it isn't a focus of this site. – Spagirl Nov 6 at 12:55
  • 2
    I'm voting to close this question as off-topic because it is not about literature. – kimchi lover Nov 6 at 14:37
  • @kimchilover That's fair, I just tried here because after asking on meta.stackexchange this was the most relevant place anyone could think to recommend: meta.stackexchange.com/a/337571/153147 – stevendesu Nov 6 at 16:06
  • @stevendesu Why don't you send an email to Brian Kernighan (see cs.princeton.edu/people/profile/bwk for contact details). – kimchi lover Nov 6 at 16:11
  • 1
    @kimchilover I would argue that any story is relevant to literature. The tale of the Fox and the Grapes is a fable, a subset of literature, even though it was passed down orally for hundreds of years and not written, and it's an incredibly short anecdote rather than a full novel. In this case, there is a famous story about a man (Donald Knuth) who wrote a complex solution to a problem, then another man (Doug McIlroy) introduced a much simpler solution to the same problem. It's a modern-day fable in its own right, plus a historical account (another subset of literature) – stevendesu Nov 7 at 14:33
7

TL;DR: This story is recognisable as a mangled version of Donald Knuth’s solution to the ‘K most common words’ problem and Doug McIlroy’s review of it, in the June 1986 Communications of the ACM.

Literate programming

In the 1980s, Jon Bentley wrote a column called ‘Programming Pearls’ that appeared in the Communications of the ACM. He devoted the columns for May and June 1986 to a description of Donald Knuth’s ‘literate programming’ paradigm which he had used to develop the computer typesetting systems METAFONT and TeX. The May column described the principles of literate programming and Knuth’s ‘WEB’ software, and introduced the following challenge:

When I first read Knuth’s “Literate Programming” paper referenced under Further Reading, I was quite impressed by his approach. When I read the large programs referenced there, I was overwhelmed: for the first time, somebody was proud enough of a substantial piece of code to publish it for public viewing, in a way that is inviting to read. I was so fascinated that I wrote Knuth a letter, asking whether he had any spare programs handy that I might publish as a “Programming Pearl.”

But that was too easy for Knuth. He responded, “Why should you let me choose the program? My claim is that programming is an artistic endeavor and that the WEB system gives me the best way to write beautiful programs. Therefore I should be able to meet a stiffer test: I should be able to write a superliterate program that will be noticeably better than an ordinary one, whatever the topic. So how about this: You tell me what sort of program you want me to write, and I’ll try to prove the merits of literate programming by finding the best possible solution to whatever problem you pose—at least the best by current standards.”

He laid some ground rules for the task. The program had to be short enough to fit comfortably in a column, say, an afternoon’s worth of programming. It had to be a complete program (not just a fragment), and could not stress input and output (Knuth has boilerplate to handle that problem, but that isn’t of interest to most readers). Because his “Literate Programming” article is built around a program to print prime numbers, this assignment should avoid number-theoretic problems.

I chose a problem that I had assigned to several classes on data structures.

Given a text file and an integer K, you are to print the K most common words in the file (and the number of their occurrences) in decreasing frequency.

Jon Bentley (1986). ‘Literate Programming’. Communications of the ACM 29:5, pp. 365–368.

Knuth’s solution

Jon Bentley gave over his June 1986 column to Knuth’s literate solution to the ‘K most common words’ problem. Knuth solved the problem by deploying a recently invented data structure, Frank Liang’s ‘hash trie’, a form of prefix tree with the representations of the nodes interleaved in an array in order to make the most efficent use of the available space:

Given a word in the buffer, we will want to look for it in a dynamic dictionary of all words that have appeared so far. We expect many words to occur often, so we want a search technique that will find existing words quickly. Furthermore, the dictionary should accommodate words of variable length, and (ideally) it should also facilitate the task of alphabetic ordering.

These constraints, suggest a variant of the data structure introduced by Frank M. Liang in his Ph.D. thesis [“Word Hy-phen-a-tion by Com-pu-ter,” Stanford University, 1983]. Liang’s structure, which we may call a hash trie, requires comparatively few operations to find a word that is already present, although it may take somewhat longer to insert a new entry. Some space is sacrificed—we will need two pointers, a count, and another 5-bit field for each character in the dictionary, plus extra space to keep the hash table from becoming congested—but relatively large memories are commonplace nowadays, so the method seems ideal for the present application.

Donald Knuth (1986). ‘Common Words’. Communications of the ACM 29:6, pp. 473–474.

McIlroy’s review

Jon Bentley commissioned a review of Knuth’s solution from Doug McIlroy. McIlroy was impressed by Knuth’s virtuousity but critical of his engineering approach:

I found Don Knuth’s program convincing as a demonstration of WEB and fascinating for its data structure, but I disagree with it on engineering grounds. The problem is to print the K most common words in an input file (and the number of their occurrences) in decreasing frequency. Knuth’s solution is to tally in an associative data structure each word as it is read from the file. The data structure is a trie, with 26-way (for technical reasons actually 27-way) fan-out at each letter. To avoid wasting space all the (sparse) 26-element arrays are cleverly interleaved in one common arena, with hashing used to assign homes. Homes may move underfoot as new words cause old arrays to collide. The final sorting is done by distributing counts less than 200 into buckets and insertion-sorting larger counts into a list. […]

Knuth’s purpose was to illustrate WEB. Nevertheless, it is instructive to consider the program at face value as a solution to a problem. A first engineering question to ask is: how often is one likely to have to do this exact task? Not at all often, I contend. It is plausible, though, that similar, but not identical, problems might arise. A wise engineering solution would produce—or better, exploit—reusable parts.

Doug McIlroy, ‘A Review’. Communications of the ACM 29:6, pp. 478–479.

McIlroy pointed out that the ‘K most common words’ problem could be solved using standard Unix tools via a short shell script:

The following shell script was written on the spot and worked on the first try. It took 30 seconds to handle a 10,000-word file on a VAX-11/750™.

(1)  tr -cs A-Za-z '
     ' |
(2)  tr A-Z a-z |
(3)  sort |
(4)  uniq -c |
(5)  sort -rn |
(6)  sed ${1}q

If you are not a Unix adept, you may need a little explanation, but not much, to understand this pipeline of processes. The plan is easy:

  1. Make one-word lines by transliterating the complement (-c) of the alphabet into newlines (note the quoted newline), and squeezing out (-s) multiple newlines.

  2. Transliterate upper case to lower case.

  3. Sort to bring identical words together.

  4. Replace each run of duplicate words with a single representative and include a count (-c).

  5. Sort in reverse (-r) numeric (-n) order.

  6. Pass through a stream editor; quit (q) after printing the number of lines designated by the script’s first parameter (${1}).

McIlroy, p. 479.

I recommend reading both the May and June 1986 ‘Programming Pearls’ columns—they are classics of the computer programming literature, and Knuth’s solution remains a jewel of elegance and readability despite its impracticality.

  • Thank you so much, that's exactly the story I was looking for. I remembered the problem was a fairly simple one ("print the K most common words") but couldn't remember what the actual problem was at all. The only detail I could remember was the the elegant solution was a 6-line shell script. The story came to mind because the reference I heard to it (which I believe was made as part of a developer conference) compared the solution to a published statistic that developers tend to make 15-50 bugs per 1000 lines of code, so the fewer lines of code the better (hence 6 lines > thousands of lines) – stevendesu Nov 6 at 21:28
  • Unfortunately for Knuth here, the task Jon Bentley chose is one for which the above Unix tools are admirably suited. Programmers who have expertly crafted programs need not fear that some Unix expert will show up and solve the same problem in 6 lines of shell-script, so the anecdote is not really relevant to the programmers of today. – Rosie F Nov 10 at 17:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.