
Pragramming Pearls
than an ordinary one, whatever the topic. So how
well as readers: Rob Pike writes, “Publishing pro-
about this: You tell me what sort of program you
grams is a healthy habit. Every program I’ve written
want me to write, C
rind I’ll try to prove the merits of knowing it was to be published was improved by
literate programming by finding the best possible so-
that knowledge. I think more clearly when I’m writ-
lution to whatever problem you pose’--at least the
ing for an audience, and find it helps to pretend
best by current standards.”
there always is one.”
He laid some ground rules for the task. The pro-
gram 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 frag-
ment), 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 fre-
quency.
I left open a number of issues, such as the precise
definition of words and limits on sizes such as maxi-
mum number of words. I did impose an efficiency
constraint: a user should be able to find the 100 most
frequent words in a twenty-page technical paper
without undue emotional trauma.
An lmportant Solution. In addition to defining (and
naming) the area, Knuth has made two fundamental
contributions to literate programming. The first is
his WEB system, which has been used to develop
several large (and widely used) programs. His in-
sights, though, transcend the particular system: his
“Literate Programming” paper describes WEB look-
alikes implemented for other programming and
document-production languages. The second funda-
mental contribution is a body of literate programs
written in WEB, several of which are referenced un-
der Further Reading. Most computer scientists are as
cowardly as I am; our published programs are rarely
more than tiny (and highly polished) subroutines.
Knuth is almost unique in publishing the code to
workhorse programs. He even believes that it is cor-
rect: in the book ‘@X: The Program he writes that
“I believe that the final bug in TEX was discovered
and removed on November 27, 1985” and offers the
princely sum of $20.48 to the finder of any error still
lurking in the code.
This problem has several pleasant attributes: it
combines simple text manipulation with searching
(to increment the count of this input word) and sort-
ing (for output in decreasing frequency). Further-
more, it’s useful: I run such a program on documents
I write, to find overused worcls.
Next month’s column presents Knuth’s literate so-
lution to this problem. Problem 1 encourages you to
tackle the problem yourself to increase your appreci-
ation of Knuth’s program.
Problems in Paradise. Because it is based on Pascal,
WEB inherits all the universality and some of the
problems of the language (although it nicely patches
several serious defects of Pascal). A WEB program is
written in a mixture of WEB, m, and Pascal; that
can be a barrier both for learning to use the system
and for debugging a program. And the very name
“literate programming” implies that its practitioners
must be competent in both literature and program-
ming; it is hard enough to find people with one of
those skills, let alone both (though WEB does amplify
one’s abilities).
Principles
An Important Problem. Most real programs are writ-
ten to be executed but not read; many published
programs are written to be read but have never been
executed.3 Knuth’s work on literate programs is an
important step towards programs fit for both man
and computing beast. That’s good news for writers as
‘Although I assigned the pn,gram to he described next month. Knuth chose
Program I himself. When I wnt him the “assignment” described above. he
returned both the requested solution and a solution to a problem described in
an earlier column. He has kindly allowed both programs to be published.
3 There are exceptions. The programs in Kernighan and Plauger’s Soffware
Tools
are widely used and were included in the text directly from their
executable form (the book and the programs were published by Addison-
Wesley in 1976; a Pascal version appeared in 1981). I am less exacting with
the small programs that appear in this column: I usually test and debug them
in a real language (typically C or AWK). then transliterate the trusted code
into the Pascal-like pseudocode that I use in the column.
Problems
1. Knuth’s programming problem (finding the K
most common words in a document) can be in-
terpreted in several ways; Knuth’s assignment is
somewhere between a and b. Try the problem
yourself in one or more of these versions.
a. An exercise in simple programming. In an
Algol-like language, implement the simplest
program to solve the problem (simplicity
might be measured by lines of source code).
b. An exercise in efficient programming. In an
Algol-like language, implement the most
efficient program to solve the problem
(measured in terms of time and/or space).
360
Communications of the ACM May 1986 Volume 29 Number 5