Literate Programming

LITERATE PROGRAMMING

in other sections. For example, the angle-bracket nota-

tion ‘ Program to print . . . numbers

2

’ is WEB’s way of

saying the following: “The

PASCAL

text to be inserted

here is called ‘Program to print . . . numbers’, and you

can find out all about it by looking at section 2.” One

of the main characteristics of WEB is that different parts

of the program are usually abbreviated, by giving them

such an informal top-level description.]]

Program to print the first thousand prime

numbers

2

2.

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 mean-

ing” of ‘ Program to print . . . numbers

2

’; notice that

it involves the top-level descriptions of three other sec-

tions. When those top-level descriptions are replaced

by their expanded meanings, a syntactically correct

PAS-

CAL

program will be obtained.]]

Program to print the first thousand prime

numbers

2

≡

program print primes (output );

const m = 1000;

Other constants of the program

5

var Variables of the program

4

begin Print the first m prime numbers

3

;

end.

This code is used in section 1.

3.

Plan of the program.

We shall proceed to fill

out the rest of the program by making whatever deci-

sions seem easiest at each step; the idea will be to strive

for simplicity first and efficiency later, in order to see

where this leads us. The final program may not be op-

timum, but we want it to be reliable, well motivated,

and reasonably fast.

Let us decide at this point to maintain a table that

includes all of the prime numbers that will be gener-

ated, and to separate the generation problem from the

printing problem.

[[The WEB description you are reading once again fol-

lows a pattern that will soon be familiar: A typical

section begins with comments and ends with program

text. The comments motivate and explain noteworthy

features of the program text.]]

Print the first m prime numbers

3

≡

Fill table p with the first m prime numbers

11

;

Print table p

8

This code is used in section 2.

4.

How should table p be represented? Two possi-

bilities suggest themselves: We could construct a suffi-

ciently large array of boolean values in which the kth

entry is true if and only if the number k is prime; or

we could build an array of integers in which the kth

entry is the kth prime number. Let us choose the lat-

ter alternative, by introducing an integer array called

p[1 . . m].

In the documentation below, the notation ‘p[k]’ will

refer to the kth element of array p, while ‘p

k

’ will refer

to the kth prime number. If the program is correct, p[k]

will either be equal to p

k

or it will not yet have been

assigned any value.

[[Incidentally, our program will eventually make use of

several more variables as we refine the data structures.

All of the sections where variables are declared will

be called ‘ Variables of the program

4

’; the number

‘

4

’ in this name refers to the present section, which is

the first section to specify the expanded meaning of

‘ Variables of the program ’. The note ‘

See also

. . .’

refers to all of the other sections that have the same top-

level description. The expanded meaning of ‘ Variables

of the program

4

’ consists of all the program texts for

this name, not just the text found in §4.]]

Variables of the program

4

≡

p: array [1 . . m] of integer ; { the first m prime

numbers, in increasing order }

See also sections 7, 12, 15, 17, 23, and 24.

This code is used in section 2.

5.

The output phase.

Let’s work on the second

part of the program first. It’s not as interesting as the

problem of computing prime numbers; but the job of

printing must be done sooner or later, and we might as

well do it sooner, since it will be good to have it done.

[[And it is easier to learn WEB when reading a program

that has comparatively few distracting complications.]]

Since p is simply an array of integers, there is little

difficulty in printing the output, except that we need to

decide upon a suitable output format. Let us print the

table on separate pages, with rr rows and cc columns

per page, where every column is ww character positions

wide. In this case we shall choose rr = 50, cc = 4, and

ww = 10, so that the first 1000 primes will appear on

five pages. The program will not assume that m is an

exact multiple of rr · cc .

Other constants of the program

5

≡

rr = 50; { this many rows will be on each page in

the output }

cc = 4; { this many columns will be on each page

in the output }

ww = 10; { this many character positions will be

used in each column }

See also section 19.

This code is used in section 2.

6.

In order to keep this program reasonably free of no-

tations that are uniquely

PASCAL

esque, [[and in order

to illustrate more of the facilities of WEB,]] a few macro

definitions for low-level output instructions are intro-

duced here. All of the output-oriented commands in

the remainder of the program will be stated in terms of

five simple primitives called print string , print integer ,

print entry , new line , and new page .

[[Sections of a WEB program are allowed to contain

macro definitions between the opening comments and

the closing program text. The general format for each

section is actually tripartite: commentary, then defini-

tions, then program. Any of the three parts may be

absent; for example, the present section contains no

program text.]]

submitted to THE COMPUTER JOURNAL 3

---