Literate Programming

LITERATE PROGRAMMING

in the midst of a program or procedure. For example,

a programmer often finds it most natural to define an

integer variable when a for loop is introduced, but the

rules of

PASCAL

insist that such a variable be declared

rather far away from that for loop. My WEB programs

overcome this problem by having sections like ‘ Local

variables for xyzzy ’ whenever there’s a rather lengthy

procedure ‘xyzzy ’ whose local variables should not be

declared all at once. But when a procedure is short, say

only half a dozen sections long, there’s usually no harm

in declaring its local variables in

PASCAL

style, because

the entire text of the procedure will tend to appear on

one or two adjacent pages of the documentation.

Another slightly awkward aspect of

PASCAL

is its

treatment of semicolons. If you look closely at the

prime-number example, you’ll see that I had to be a

bit careful about where I put semicolons; sometimes

they occur at the end of the expanded text of a section,

but usually they don’t. With a little self discipline, a

person can learn to do this quite satisfactorily, but it is

a nuisance until you get used to it.

L. ECONOMIC ISSUES

What does it cost to use WEB? Let’s look first at the

lowest level, where computer costs are considered, be-

cause it is easy to make quantitative statements at this

level. The running time to TANGLE a WEB file is approx-

imately the same as the time needed to compile the

resulting

PASCAL

program; hence the extra preprocess-

ing does not cost much. Similarly, WEAVE doesn’t take

long to produce a file for TEX. However, TEX needs a

comparatively large amount of time to typeset the final

document. For example, if we assume that each page

requires four seconds, it will take four minutes to pro-

duce a 60-page document. The running time for WEAVE-

plus-TEX is quite reasonable when you consider that

your program is effectively being converted into a fairly

substantial booklet; but the costs are sufficiently large

to discourage remaking and reprinting such a booklet

more than once or twice a day. When a new program is

being developed, it is therefore customary to work with

hardcopy documentation that is slightly obsolete, and

to read the WEB source file itself when up-to-date infor-

mation is required; the source file is sufficiently easy to

read for such purposes.

The costs of WEB are more difficult to estimate at

higher levels, but I have found to my surprise that the

total time of writing and debugging a WEB program is

no greater than the total time of writing and debug-

ging an

ALGOL

or

PASCAL

program, even though my

WEB programs are much better, and even though I am

putting substantially more documentation into the pro-

grams. Therefore I have lately been using WEB for all of

my programming, even for one-off jobs that I write “for

my eyes only” just to explore occasional problems. The

extra time I spend in preparing additional commentary

is regained because the debugging time is reduced.

In retrospect, the fact that a “literate” program takes

much less time to debug is not surprising, because the

WEB language encourages a discipline that I was previ-

ously unwilling to impose on myself. I had known for

a long time that the programs I construct for publi-

cation in a book, or the programs that I construct in

front of a class, have tended to be comparatively free

of errors, because I am forced to clarify my thoughts as

I do the programming. By contrast, when writing for

myself alone, I have often taken shortcuts that proved

later to be dreadful mistakes. It’s harder for me to fool

myself in such ways when I’m writing a WEB program,

because I’m in “expository mode” (analogous to class-

room lecturing) whenever a WEB is being spun. Ergo,

less debugging time.

Now that I am writing all my programs in WEB, an

unforeseen problem has, however, arisen: I suddenly

have a collection of programs that seem quite beautiful

in my own eyes, and I have a compelling urge to publish

all of them so that everybody can admire these works of

art. A nice little 10-page program can easily be written

and debugged in an afternoon and evening; if I keep

accumulating such gems, I’ll soon run out of storage

space, and my office will be encrusted with webs of my

own making. There is no telling what will happen if

lots of other people catch WEB fever and start foisting

their creations on each other. I can already envision the

appearance of a new journal, to be entitled Webs, for

the publication of literate programs; I imagine that it

will have a large backlog and a large group of dedicated

editors and referees.

M. RELATED WORK

Nothing about WEB is really new; I have simply com-

bined a bunch of ideas that have been in the air for a

long time. I would like to summarize in the next few

paragraphs the things that had the greatest influence

on my thinking as I put those pieces together.

George Forsythe wrote in 1966 that “A useful algo-

rithm is a substantial contribution to knowledge. Its

publication constitutes an important piece of scholar-

ship.”

6

His comments have always inspired me to strive

for excellence in programming, and they have played a

major rˆole in shaping my present view that it is worth-

while to consider every program as a work of literature.

The design of WEB was influenced primarily by the pi-

oneering work of Pierre-Arnoul de Marneffe,

7,8

whose

research on what he called “Holon Programming” has

not received the attention it deserves. His work was, in

turn, inspired by Arthur Koestler’s excellent treatise on

the structure of complex systems and organisms;

9

thus

we have another connection between programming and

literature. A somewhat similar system was indepen-

dently created by Edwin Towster.

10

I owe a great debt to Edsger Dijkstra, Tony Hoare,

Ole-Johan Dahl, and Niklaus Wirth for opening my eyes

to the importance of abstraction in the reading and

writing of programs, and to Peter Naur for stressing the

importance of a balance between formal and informal

methods.

Tony Hoare provided a special impetus for WEB when

he suggested in 1978 that I should publish my program

for TEX. Since very few large-scale software systems

were available in the literature, he had been trying

to promote the publication of well-written programs.

submitted to THE COMPUTER JOURNAL 13

---

D. E. KNUTH

Hoare’s suggestion was actually rather terrifying to me,

and I’m sure he knew that he was posing quite a chal-

lenge. As a professor of computer science, I was quite

comfortable publishing papers about toy problems that

could be polished up nicely and presented in an elegant

manner; but I had no idea how to take a piece of real

software, with all the compromises necessary to make it

useful to a large class of people on a wide variety of sys-

tems, and to open it up to public scrutiny. How could

a supposedly respectable academic, like me, reveal the

way he actually writes large programs? And could a

large program be made intelligible? My previous at-

tempts along these lines

11

were by now hopelessly out

of date. I decided that this would be a good time to

try out de Marneffe’s ideas; furthermore, the TEX sys-

tem itself provided me with new tools for printing and

format control, so I suspected that it would be possi-

ble to obtain state-of-the-art documentation by making

proper use of typography.

It is interesting to reread some of the comments that

Tony made ten years ago in his keynote address to the

first ACM symposium on Principles of Programming

Languages:

12

Documentation must be regarded as an integral

part of the process of design and coding. A good

programming language will encourage and assist

the programmer to write clear, self-documenting

code, and even perhaps to develop and display a

pleasant style of writing.

He foresaw many future trends, but not the impending

improvements in typesetting quality:

It is of course possible for a compiler or service

program to expand the abbreviations, fill in the

defaults, and make explicit the assumptions. But

in practice, experience shows that it is very un-

likely that the output of a computer will ever be

more readable than its input, except in such trivial

but important aspects as improved indentation.

Typographic formatting of computer programs has

a long tradition, originating with

ALGOL

and its im-

mediate precursors. I’m not sure who made the first

experiments, but I believe that the lion’s share of the

credit for developing excellent programming-language

typography belongs to two people: Peter Naur, who

edited the

ALGOL 60

report

13

and gave special care

to its presentation; and Myrtle Kellington, who served

for many years as executive editor of ACM publica-

tions and set the standards that have been adopted by

other journals. The computing profession owes much to

these people, who made published programs so much

more readable than they would otherwise have been;

the magnitude of their contribution can only be ap-

preciated by people who submit computer programs to

journals like Acta Arithmetica whose editors are unfa-

miliar with computer science. Bill McKeeman called

attention to formatting issues when he published Algo-

rithm 268, “

ALGOL 60

reference language editor,” in

1965.

14

There has been a flowering of such algorithms

in recent years; the papers by Oppen

15

and by Rose

and Welsh

16

are particularly noteworthy.

I began to design WEB in the spring of 1979, when

I constructed a prototype system that was called DOC.

Luis Trabb Pardo helped me to develop a suitable style

of exposition at that time; then Ignacio Zabala Salelles

gave a DOC a thorough test when he prepared a full im-

plementation of TEX in

PASCAL

. Zabala’s implemen-

tation was successfully transported to many different

computers,

17−20

and this experience was of immense

value to me when I cast WEB into its present form in

1981. Since then many significant improvements have

been suggested by my colleague David R. Fuchs, and

I have also benefited from the experiences of a large

number of outstanding people who volunteered to be

guinea pigs for pre-released versions of TEX. It’s im-

possible for me to name everyone who has helped, but

I would like to give special thanks to Arthur Samuel,

Howard Trickey, Joe Weening, and Pierre MacKay for

important contributions. I’m fortunate indeed to share

a working environment with such stimulating people.

When I originally designed the WEB system, I spent

about six weeks preparing the files TANGLE.WEB and

WEAVE.WEB, during which time I was continually chang-

ing the language and trying different styles of expo-

sition. (The programs were neither long nor compli-

cated, but this was rather intensive work, so I didn’t

get much else done during those six weeks. The first

two weeks were actually spent drafting the first ten per

cent of what is now TEX.WEB.) Then I spent about six

tedious hours with a text editor, hand-simulating the

behavior of TANGLE on TANGLE.WEB, so that I had a

program TANGLE.PAS that was ripe for debugging. At

first I had to correct errors both in TANGLE.WEB and

TANGLE.PAS, but soon TANGLE was working well enough

that I needed only TANGLE.WEB as a source file. Then

WEAVE.WEB could be tangled and debugged too. The

total time to create “Version 0” of the WEB system, in-

cluding the language design and the time to debug the

programs and write a brief manual for users, was about

eight weeks; then enhancements were added at the rate

of about one per month for the next 18 months. As a

result of this experience I think it’s reasonable to state

that a WEB-like system can be created from scratch in a

fairly short time, for some other pair of languages be-

sides TEX and

PASCAL

, by an expert system program-

mer who is conversant with both languages. Indeed, I

spoke about WEB on a recent visit to London and one

of the people in the audience decided to test this hy-

pothesis; shortly afterwards I received an elegant report

from Harold Thimbleby, who had just constructed an

excellent system called Cweb, based on Troff/Nroff and

C

instead of TEX and

PASCAL

.

21

N. RETROSPECT AND PROSPECTS

Enthusiastic reports about new computer languages,

by the authors of those languages, are commonplace.

Hence I’m well aware of the fact that my own experi-

ences cannot be extrapolated too far. I also realize that,

whenever I have encountered a problem with WEB, I’ve

simply changed the system; other users of WEB cannot

operate under the same ground rules.

However, I believe that I have stumbled on a way of

programming that produces better programs that are

more portable and more easily understood and main-

tained; furthermore, the system seems to work with

14 submitted to THE COMPUTER JOURNAL

---

LITERATE PROGRAMMING

large programs as well as with small ones. I’m pleased

that my work on typography, which began as an appli-

cation of computers to another field, has come full circle

and become an application of typography to the heart

of computer science; I like to think of WEB as a neat

“spinoff” of my research on TEX. However, all of my

experiences with this system have been highly colored

by my own tastes, and only time will tell if a large num-

ber of other people will find WEB to be equally attractive

and useful.

I made a conscious decision not to design a language

that would be suitable for everybody. My goal was to

provide a tool for system programmers, not for high

school students or for hobbyists. I don’t have anything

against high school students and hobbyists, but I don’t

believe every computer language should attempt to of-

fer all things to all people. A user of WEB needs to

be good enough at computer science that he or she is

comfortable dealing with several languages simultane-

ously. Since WEB combines TEX and

PASCAL

with a few

rules of its own, WEB programs can contain WEB syntax

errors, TEX syntax errors,

PASCAL

syntax errors, and

algorithmic errors; in practice, all four types of errors

occur, and a bit of sophistication is needed to sort out

which is which. Computer scientists tend to be better

at such things than other people. I have found that

WEB programs can be debugged rapidly in spite of the

profusion of languages, but I’m sure that many other

intelligent people will find such a task difficult.

In other words, WEB seems to be specifically for the

peculiar breed of people who are called computer sci-

entists. And I’m pretty sure that there are also a lot of

computer scientists who will not enjoy using WEB; some

of us are glad that traditional programming languages

have comparatively primitive capabilities for inserted

comments, because such difficulties provide a good ex-

cuse for not documenting programs well. Thus, WEB

may be only for the subset of computer scientists who

like to write and to explain what they are doing. My

hope is that the ability to make explanations more nat-

ural will cause more programmers to discover the joys

of literate programming, because I believe it’s quite a

pleasure to combine verbal and mathematical skills; but

perhaps I’m hoping for too much. The fact that at least

one paper has been written that is a syntactically cor-

rect

ALGOL 68

program

22

encourages me to persevere

in my hopes for the future. Perhaps we will even one

day find Pulitzer prizes awarded to computer programs.

And what about the future of WEB? If the next year or

so of trial use shows that a lot of other people besides

myself become “hooked” on this method of program-

ming, there will be many ways to incorporate the WEB

philosophy into a really effective programming environ-

ment. For example, it will be worthwhile to produce a

unified system that does both tangling and compiling,

instead of using separate programs as in Figure 1; and

it will also be worthwhile to carry the unification one

step further, so that run-time debugging as well as syn-

tactic debugging can be done entirely in terms of the

WEB source language. Furthermore, a WEB-like system

could be designed to incorporate additional modular-

ization, so that it would be easier to compile different

parts of a program independently. The new generation

of graphic workstations makes it desirable to display se-

lected program sections on demand, by using TEX only

on the sections that are of current interest, instead of

producing hardcopy for an entire document. And so

on; a considerable amount of additional research and

development will be appropriate if the idea of literate

programming catches on.

Acknowledgements

The preparation of this paper was supported in part by the Na-

tional Science Foundation under grants IST-8201926 and MCS-

8300984, and by the System Development Foundation. ‘TEX’ is

a trademark of the American Mathematical Society.

REFERENCES

1. D. E. Knuth, The TEXbook. Addison-Wesley, Reading, Mass.,

U.S.A. (1983).

2. O.-J. Dahl, E. W. Dijkstra, and C. A. R. Hoare, Structured Pro-

gramming. Academic Press, London and New York (1972).

3. D. E. Knuth, Structured programming with go to statements.

Computing Surveys 6, 261–301 (1974).

4. D. E. Knuth, The WEB System of Structured Documentation.

Stanford Computer Science Report CS980 (September 1983).

5. P. Naur, Formalization in program development. BIT 22, 437–

453 (1982).

6. G. E. Forsythe, Algorithms for scientific computation. Communi-

cations of the ACM 9, 255–256 (1966).

7. P. A. de Marneffe, Holon Programming. Univ. de Liege, Service

D’Informatique (December, 1973).

8. P. A. de Marneffe and D. Ribbens, Holon Programming, in A.

G¨

unther et al. (eds.), International Computing Symposium 1973 ,

Amsterdam, North-Holland (1974).

9. A. Koestler, The Ghost in the Machine. New York, Macmillan

(1968).

10. E. Towster, A convention for explicit declaration of environments

and top-down refinement of data. IEEE Transactions on Software

Engineering SE–5, 374–386 (1979).

11. D. E. Knuth, Computer-drawn flow charts. Communications of

the ACM 6, 555–563 (1963).

12. C. A. R. Hoare, Hints on Programming Language Design. Stan-

ford Computer Science Report CS403 (October 1973).

13. P. Naur (ed.) et al., Report on the algorithmic language ALGOL

60. Communications of the ACM 3, 299–314.

14. W. M. McKeeman, Algorithm 268. Communications of the ACM

8, 667–668 (1965).

15. D. Oppen, Prettyprinting. ACM Transactions on Programming

Languages and Systems 2, 465–483 (1980).

16. G. A. Rose and J. Welsh, Formatted programming languages.

Software—Practice & Experience 11, 651–669 (1981).

17. I. Zabala and L. Trabb Pardo, The status of the PASCAL imple-

mentation of TEX. TUGboat 1, 16–17 (1980).

18. I. Zabala, TEX-PASCAL and PASCAL compilers. TUGboat 2 (1),

11–12 (1981).

19. I. Zabala, Some feedback from PTEX installations. TUGboat 2

(2), 16–19 (1981).

20. I. A. Zabala, How portable is PASCAL? Draft of paper in prepa-

ration (1982).

21. H. Thimbleby, Cweb. Preprint, University of York (August 1983).

22. C. H. Lindsey, ALGOL 68 with fewer tears. The Computer Journal

15, 176–188 (1972).

Received September 1983

submitted to THE COMPUTER JOURNAL 15