Literate Programming

D. E. KNUTH

Well, imagine that you are writing a small subroutine

that updates part of a data structure, and suppose that

the updating takes only one or two lines of code. In

practical programs, there’s often something that can go

wrong, if the user’s input is incorrect, so the subroutine

has to check that the input is correct before doing the

update. Thus, the subroutine has the general form

procedure update ;

begin if input data is invalid then

Issue an error message and try to recover ;

Update the data structure ;

end.

A subtle phenomenon occurs in traditional program-

ming languages: While writing the program for ‘ Issue

an error message and try to recover ’, a programmer

subconsciously tries to get by with the fewest possible

lines of code, since the program for ‘ Update the data

structure ’ is quite short. If an extensive error recovery

is actually programmed, the subroutine will appear to

have error-message printing as its main purpose. But

the programmer knows that the error is really an excep-

tional case that arises only rarely; therefore a lengthy

error recovery doesn’t look right, and most program-

mers will minimize it (without realizing that they are

doing so) in order to make the subroutine’s appearance

match its intended behavior. On the other hand when

the same task is programmed with WEB, the purpose

of update can be shown quite clearly, and the possibil-

ity of error recovery can be reduced to a mere mention

when update is defined. When another section entitled

‘ Issue an error message and try to recover ’ is subse-

quently written, the whole point of that section is to do

the best error recovery, and it becomes quite natural to

write a better program as a result.

This fact—that WEB allows you to let each part of

the program have its appropriate size, without distort-

ing the readability of other parts—means that good

programmers find their WEB programs better than their

PASCAL

programs, even though their

PASCAL

programs

once looked like the work of an expert.

K. STYLISTIC ISSUES

I found that my style of using WEB evolved quite a bit

during the first year. The general format, in which each

section beings with commentary and ends with a formal

program fragment, is extremely versatile; you have the

freedom to say anything you want, yet you must make a

decision about how you’ll do it. I imagine that different

programmers will converge to quite different styles, but

I would like to note down some of the things that have

seemed to work best for me.

Consider first the question of macros versus section

names. A named section, like ‘ Issue an error mes-

sage and try to recover ’, is essentially the same as a

parameterless macro; WEB provides both. I prefer to

use parameterless macros for “small” things that can

be embodied in a word or two, but named sections for

longer portions of the program that merit a fuller de-

scription.

I usually start the name of a section with an im-

perative verb, but I give a declarative commentary at

the beginning of a section. Thus, PRIMES.WEB says

‘8. Now that appropriate . . . Print table p

8

≡ . . . ’;

I wouldn’t do the opposite and say ‘8. Print the table.

Code for printing

8

≡ . . . ’.

The name of a section (enclosed in angle brackets)

should be long enough to encapsulate the essential char-

acteristics of the code in that section, but it should not

be too verbose. I found very early that it would be a

mistake to include all of the assumptions about local

and global variables in the name of each section, even

though such information would strictly be necessary to

isolate that section as an independent module. The

trick is to find a balance between formal and informal

exposition so that a reader can grasp what is happening

without being overwhelmed with detail.

5

Another lesson I learned early in the game was that

the name of a section should explicitly mention any

nonstandard control structures, even though its data

structures can often be left implied. Furthermore, if

the control flow is properly explained, you can avoid

the usual errors associated with goto statements; such

statements can safely be introduced in a restrained but

natural manner.

For example, §14 of the prime-printing example could

be reprogrammed as follows, using ‘loop’ as a macro

abbreviation for ‘while true do’:

Increase j until it is the next prime number

14

≡

loop begin j ← j + 2;

Update variables that depend on j

20

;

If j is prime, goto found

22

;

end;

found :

With this change, §22 could become

If j is prime, goto found

22

≡

n ← 2;

while n < ord do

begin If p[n] is a factor of j, goto not found

26

;

n ← n + 1;

end;

goto found ;

not found :

if §26 changes in the obvious way. The resulting pro-

gram will be more efficient on most machines; and I

believe that it is actually easier to read and to write,

in spite of the fact that two goto statements appear,

because the labels have been used with appropriate in-

terpretations of their abstract significance.

Of course,

PASCAL

makes it difficult to use goto

statements, because Wirth decided that labels should

be numeric, and that they should be declared in ad-

vance. If I were to introduce the goto statements as

suggested, I would have to define numeric macros found

and not found , and I would have to insert ‘label found ,

not found ’ into the program at the right place. Such

extra work is a bit of a nuisance, but it can be done in

WEB without spoiling the exposition.

PASCAL

has a few other misfeatures that prove to

be inconvenient with respect to WEB exposition. The

worst of these is the inability to declare local variables

12 submitted to THE COMPUTER JOURNAL

---