Literate Programming

D. E. KNUTH

is an odd multiple of p

n

such that mult [n] < j + 2p

n

.

If mult [n] < j, we can increase mult [n] by 2p

n

and

the same conditions will hold. On the other hand if

mult [n] ≥ j, the conditions imply that j is divisible

by p

n

if and only if j = mult [n].

If p[n] is a factor of j, set j prime ← false

26

≡

while mult [n] < j do

mult [n] ← mult [n] + p[n] + p[n];

if mult [n] = j then j prime ← false

This code is used in section 22.

27.

Index.

Every identifier used in this program is

shown here together with a list of the section numbers

where that identifier appears. The section number is

underlined if the identifier was defined in that section.

However, one-letter identifiers are indexed only at their

point of definition, since such identifiers tend to appear

almost everywhere. [[An index like this is prepared au-

tomatically by the WEB software, and it is appended to

the final section of the program. However, underlining

of section numbers is not automatic; the user is sup-

posed to mark identifiers at their point of definition in

the WEB source file.]]

This index also refers to some of the places where key

elements of the program are treated. For example, the

entries for ‘Output format’ and ‘Page headings’ indi-

cate where details of the output format are discussed.

Several other topics that appear in the documentation

(e.g., ‘Bertrand’s postulate’) have also been indexed.

[[Special instructions within a WEB source file can be

used to insert essentially anything into the index.]]

Bertrand, Joseph, postulate: 21.

boolean : 15.

c: 7.

cc : 5, 7, 8, 10.

Dijkstra, Edsger: 1, 15.

Eratosthenes, sieve of: 24.

false : 13, 26.

integer : 4, 7, 12, 17, 24.

j: 12.

j prime : 13, 14, 15, 22, 26.

k: 12.

Knuth, Donald E.: 15.

m: 2.

mult : 24, 25, 26.

n: 23.

new line : 6, 9, 10.

new page : 6, 9.

ord : 17, 18, 19, 20, 21, 22, 23, 24, 25.

ord max : 17, 19, 23, 24.

output : 2, 6.

output format: 5, 9.

p: 4.

page : 6.

page headings: 9.

page number : 7, 8, 9.

page offset : 7, 8, 9.

prime number, definition of: 13.

print entry : 6, 10.

print integer : 6, 9.

print primes : 2.

print string : 6, 9.

row offset : 7, 9, 10.

rr : 5, 8, 9, 10.

square : 17, 18, 20, 21.

true : 4, 13, 22.

WEB: 1.

write : 6.

write ln : 6.

ww : 5, 6.

Fill table p with the first m prime numbers

11

Used in 3.

Give to j prime the meaning: j is a prime number

22

Used in 14.

If p[n] is a factor of j, set j prime ← false

26

Used in 22.

Increase j until it is the next prime number

14

Used in 11.

Initialize the data structures

16, 18

Used in 11.

Other constants of the program

5, 19

Used in 2.

Output a line of answers

10

Used in 9.

Output a page of answers

9

Used in 8.

Print table p

8

Used in 3.

Print the first m prime numbers

3

Used in 2.

Program to print the first thousand prime numbers

2

Used in 1.

Update variables that depend on j

20

Used in 14.

Update variables that depend on ord

21, 25

Used in 20.

Variables of the program

4, 7, 12, 15, 17, 23, 24

Used in 2.

D. HOW THE EXAMPLE WAS SPECIFIED

Everything reproduced above, from the table of con-

tents preceding the program to the indexes of identifiers

and section names at the end, was generated by ap-

plying the program WEAVE to a source file PRIMES.WEB

written in the WEB language. Let us now look at that

file PRIMES.WEB, in order to get an idea of what a WEB

user actually types.

There’s no need to show very much of PRIMES.WEB,

however, because that file is reflected quite faithfully

by the formatted output. Figure 2 contains enough of

the WEB source to indicate the general flavor; a reader

who is familiar with the rudiments of TEX will be able

to reconstruct all of PRIMES.WEB by looking only at the

formatted output and Figure 2.

Figure 2a starts with TEX commands (not shown in

full) that make it convenient to typeset double brack-

ets [[. . .]] and to give special typographic treatment to

names like ‘WEB’ and ‘

PASCAL

’. A WEB user generally

begins by declaring such special aspects of the docu-

ment format; for example, if nonstandard fonts of type

are needed, they are usually stated first. It may also

be necessary to specify the correct hyphenation of non-

English words that appear in the document.

Then comes ‘@*’, which starts the program proper.

WEB uses the symbol ‘@’ as an escape character for spe-

cial instructions to the WEAVE and TANGLE processors.

Everything between such special commands is either

expressed in TEX language or in

PASCAL

language, de-

pending on the context.

6 submitted to THE COMPUTER JOURNAL

---

LITERATE PROGRAMMING

\font\ninerm=cmr9

\let\mc=\ninerm % medium caps

\def\WEB{{\tt WEB}}

\def\PASCAL{{\mc PASCAL}}

\def\[{\ifhmode\ \fi$[\mkern-2mu[$}

\def\]{$]\mkern-2mu]$\ }

.

.

.

\hyphenation{Dijk-stra}

@* Printing primes: An example of \WEB.

The following program is essentially the same

as Edsger Dijkstra’s @^Dijkstra, Edsger@>

‘‘first example of step-wise program

composition,’’ found on pages 26--39

of his {\sl Notes on Structured

Programming},$^\Dijk$ but it has been

translated into the \WEB\ language. @.WEB@>

\[Double brackets will be used in what

follows to enclose comments relating to \WEB\

.

.

.

an informal top-level description.\]

@p @

prime numbers@>

Figure 2a. The beginning of PRIMES.WEB.

Each section of the program begins either with ‘@ ’

(i.e., at-sign and space) or ‘@*’ (i.e., at-sign and aster-

isk); WEB supplies the section numbers automatically.

The latter case, ‘@*’, denotes a major section of the

program, for which a special title is given. This title

will appear in boldface type, and it will also appear in

the table of contents, and as a running headline on all

pages of the woven documentation until another major

section begins. Each major section starts at the top of

a page. (Such page beginnings have been indicated by

horizontal lines in our example, because WEB’s normal

output format has been adapted to the format of this

journal. The output of WEAVE usually has a lot more

white space, and the individual lines of text are usually

quite a bit wider.)

The lines that follow in Figure 2a show a few more

WEB instructions: ‘@^’ marks the beginning of an index

entry to be set in roman type; ‘@>’ marks the end of an

argument to a WEB command; ‘@.’ marks the beginning

of an index entry to be set in typewriter type; ‘@p’

marks the beginning of the

PASCAL

program; and ‘@<’

marks the beginning of a top-level description, i.e., of a

section name in the WEB program.

Figure 2b immediately follows Figure 2a in the WEB

file. This material is what generated §2 of the doc-

umentation, and it illustrates the bilingual nature of

WEB: The commentary at the beginning of each section

is typed in TEX language, and the program text at the

end is typed in

PASCAL

language.

Language-switching between TEX and

PASCAL

is oc-

casionally desirable. For example, when you refer to

technical details about the program, you usually want

to describe them in

PASCAL

, hence you want WEAVE to

format them with the typographic conventions it uses

for

PASCAL

programs. Conversely, when you put com-

ments in a

PASCAL

program, you want the text of those

@ This program has no input, because we want

to keep it rather simple.

The result of the

program will be to produce a list of the

first thousand prime numbers, and this list

will appear on the |output| file.

Since there is no input, we declare the value

|m=1000| as a compile-time constant. The

program itself is capable of generating the

first |m| prime numbers for any positive |m|,

as long as the computer’s finite limitations

are not exceeded.

\[The program text below specifies the

‘‘expanded meaning’’ of ‘\X2:Program to print

$\ldots$ numbers\X’; notice that it involves

the top-level descriptions of three other

sections. When those top-level descriptions

are replaced by their expanded meanings, a

syntactically correct \PASCAL\ program will

be obtained.\]

@
=

program print_primes(output);

const @!m=1000;

@@;

var @@;

begin @
;

end.

Figure 2b. The WEB code that generated §2.

@ In order to keep this program reasonably

free of notations that are uniquely

\PASCAL esque, \[and in order to illustrate

.

.

.

The first three macro definitions here are

parametric; the other two are simple.\]

@d print_string(#)==write(#)

{put a given string into the |output| file}

@d print_integer(#)==write(#:1)

{put a given integer into the |output|

file, in decimal notation, using only as

many digit positions as necessary}

@d print_entry(#)==write(#:ww)

{like |print_integer|, but

|ww| character positions are filled,

inserting blanks at the left}

@d new_line==write_ln

{advance to a new line in the |output| file}

@d new_page==page

{advance to a new page in the |output| file}

Figure 2c. The WEB code that generated §6.

comments to be formatted by TEX in the normal way.

WEB files use vertical bars to introduce

PASCAL

format-

ting in the midst of TEX formatting; for example, Fig-

ure 2b says ‘the |output| file’ in order to typeset

‘the output file’.

The program text in Figure 2b begins with ‘@<’ in-

stead of with the ‘@p’ command used in Figure 2a,

because the program text in §2 is the expansion of

submitted to THE COMPUTER JOURNAL 7

---