% Copyright 1991 by Norman Ramsey. All rights reserved.
% See file COPYRIGHT for more information.
% l2h substitution nw `noweb`
% some insanity is needed to avoid getting a double square bracket
% l2h substitution [ **[****[**
% l2h substitution ] **]****]**
\def\nw{{\tt noweb}}
\def\[{\ifhmode\ \fi$[\mkern-2mu[$}
\def\]{$]\mkern-2mu]$}
\title{Printing Primes: An example of \nw}
\section{Printing Primes: An example of \nw}
The following program is essentially the program that appears in
Reference~\cite{knuth:literate}, the first article on literate programming,
but rendered using \nw.
An important differents is the {\tt WEB} has macros, but \nw\ does not.
Knuth's program is itself essentially the same as Edsger Dijkstra's
``first example of step-wise program composition.''~\cite[pages
26--39]{dahl:structured}.
Dijkstra's program prints a table of the first thousand prime numbers.
We shall begin as he did, by reducing the entire program to its
top-level description.
<<*>>=
<>
@
\[Double brackets will be used in what follows to enclose comments
relating to \nw\ itself.
This definition of the root module could have been eliminated by
choosing to use
\begin{quote}
\tt notangle -R'program to print the first thousand prime numbers'
\end{quote}
to extract the program.\]
@ This program has no input, because we want to keep it 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.
<>=
program `print_primes(output);
const m = 1000;
<>
var <>
begin <>
end.
@
\section{Plan of the program}
We shall proceed to fill out the rest of the program by making
whatever decisions 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 optimum, 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 numebrs that will be generated, and to sepaerate the
genreation problem from the printing problem.
<>=
<>;
<>
@
How should table [[p]] be represented?
Two possibilities suggest themselves: We could construct a
sifficiently large aray of boolean values in whith the $k$th entry is
[[true]] if and only if the number $k$ is prime; or we could build an
array of integers in which the $k$th entry is the $k$th prime number.
Let us choose the latter alternatice, by introducing an intereger
array called [[p[1..m]]].
In the documentation below, the notation [[p[k]]] will refer to the
[[k]]th element of the array [[p]], while $p_k$ will refer to the
$k$th prime number.
If the program is correct [[p[k]]] will equal $p_k$ or it will not yet
have nbeen asigned any value.
<>=
p: array [1..m] of integer;
{ the first m prime numbers, in increasing order }
@
\section{The output phase}
<>=
rr = 50;
cc = 4;
ww = 10;
<>=
`page_number: integer;
`page_offset: integer;
`row_offset: integer;
c: 0..cc;
@
<>=
begin page_number := 1; page_offset := 1;
while page_offset <= m do
begin <