Literate Programming

D. E. KNUTH

[[Simple macros simply substitute a bit of

PASCAL

code for an identifier. Parametric macros are similar,

but they also substitute an argument wherever ‘#’ oc-

curs in the macro definition. The first three macro def-

initions here are parametric; the other two are simple.]]

define print string (#) ≡ write (#)

{ put a given string into the output file }

define print integer (#) ≡ write (# : 1)

{ put a given integer into the output file,

in decimal notation, using only as many

digit positions as necessary }

define print entry (#) ≡ write (# : ww ) { like

print integer , but ww character positions

are filled, inserting blanks at the left }

define new line ≡ write ln

{ advance to a new line

in the output file }

define new page ≡ page

{ advance to a new page

in the output file }

7.

Several variables are needed to govern the output

process.

When we begin to print a new page, the

variable page number will be the ordinal number of that

page, and page offset will be such that p[page offset ] is

the first prime to be printed. Similarly, p[row offset ]

will be the first prime in a given row.

[[Notice the notation ‘+ ≡’ below; this indicates that

the present section has the same name as a previous

section, so the program text will be appended to some

text that was previously specified.]]

Variables of the program

4

+≡

page number : integer ; { one more than the number

of pages printed so far }

page offset : integer ; { index into p for the first entry

on the current page }

row offset : integer ; { index into p for the first entry

in the current row }

c: 0 . . cc ; { runs through the columns in a row }

8.

Now that appropriate auxiliary variables have been

introduced, the process of outputting table p almost

writes itself.

Print table p

8

≡

begin page number ← 1; page offset ← 1;

while page offset ≤ m do

begin Output a page of answers

9

;

page number ← page number + 1;

page offset ← page offset + rr ∗ cc ;

end;

end

This code is used in section 3.

9.

A simple heading is printed at the top of each page.

Output a page of answers

9

≡

begin print string (´The First ´);

print integer (m);

print string (´ Prime Numbers −−− Page ´);

print integer (page number ); new line ; new line ;

{ there’s a blank line after the heading }

for row offset ← page offset to page offset + rr − 1

do

Output a line of answers

10

;

new page ;

end

This code is used in section 8.

10.

The first row will contain

p[1], p[1 + rr ], p[1 + 2 ∗ rr ], . . . ;

a similar pattern holds for each value of the row offset .

Output a line of answers

10

≡

begin for c ← 0 to cc − 1 do

if row offset + c ∗ rr ≤ m then

print entry (p[row offset + c ∗ rr ]);

new line ;

end

This code is used in section 9.

11.

Generating the primes.

The remaining task

is to fill table p with the correct numbers. Let us do

this by generating its entries one at a time: Assuming

that we have computed all primes that are j or less, we

will advance j to the next suitable value, and continue

doing this until the table is completely full.

The program includes a provision to initialize the

variables in certain data structures that will be intro-

duced later.

Fill table p with the first m prime numbers

11

≡

Initialize the data structures

16

;

while k < m do

begin Increase j until it is the next prime

number

14

;

k ← k + 1; p[k] ← j;

end

This code is used in section 3.

12.

We need to declare the two variables j and k that

were just introduced.

Variables of the program

4

+≡

j: integer ; { all primes ≤ j are in table p }

k: 0 . . m; { this many primes are in table p }

13.

So far we haven’t needed to confront the issue of

what a prime number is. But everything else has been

taken care of, so we must delve into a bit of number

theory now.

By definition, a number is called prime if it is an

integer greater than 1 that is not evenly divisible by

any smaller prime number. Stating this another way,

the integer j > 1 is not prime if and only if there exists

a prime number p

n

< j such that j is a multiple of p

n

.

Therefore the section of the program that is called

‘ Increase j until it is the next prime number ’ could be

coded very simply: ‘repeat j ← j +1; Give to j prime

the meaning: j is a prime number ; until j prime ’.

And to compute the boolean value j prime , the follow-

ing would suffice: ‘j prime ← true ; for n ← 1 to k do

If p[n] divides j, set j prime ← false ’.

14.

However, it is possible to obtain a much more ef-

ficient algorithm by using more facts of number theory.

In the first place, we can speed things up a bit by rec-

ognizing that p

1

= 2 and that all subsequent primes

are odd; therefore we can let j run through odd values

only. Our program now takes the following form:

Increase j until it is the next prime number

14

≡

repeat j ← j + 2;

Update variables that depend on j

20

;

Give to j prime the meaning: j is a prime

number

22

;

until j prime

This code is used in section 11.

4 submitted to THE COMPUTER JOURNAL

---