From e0c6872cf40896c7be36b11dcc744620f10adf1d Mon Sep 17 00:00:00 2001 From: Norbert Preining Date: Mon, 2 Sep 2019 13:46:59 +0900 Subject: Initial commit --- web/literateprog/primes.contents | 6 + web/literateprog/primes.contents_z | Bin 0 -> 170 bytes web/literateprog/primes.tex | 555 ++++++++++++++ web/literateprog/primes.tex_z | Bin 0 -> 12180 bytes web/literateprog/primes.web | 414 ++++++++++ web/literateprog/primes.web_z | Bin 0 -> 9830 bytes web/literateprog/web.tex | 1477 ++++++++++++++++++++++++++++++++++++ web/literateprog/web.tex_z | Bin 0 -> 40392 bytes 8 files changed, 2452 insertions(+) create mode 100644 web/literateprog/primes.contents create mode 100644 web/literateprog/primes.contents_z create mode 100644 web/literateprog/primes.tex create mode 100644 web/literateprog/primes.tex_z create mode 100644 web/literateprog/primes.web create mode 100644 web/literateprog/primes.web_z create mode 100644 web/literateprog/web.tex create mode 100644 web/literateprog/web.tex_z (limited to 'web/literateprog') diff --git a/web/literateprog/primes.contents b/web/literateprog/primes.contents new file mode 100644 index 0000000000..0c3abd3bc4 --- /dev/null +++ b/web/literateprog/primes.contents @@ -0,0 +1,6 @@ +\Z { Printing primes: An example of {\fam \ttfam \tentt WEB}}{1}{1} +\Z { Plan of the program}{3}{3} +\Z { The output phase}{5}{4} +\Z { Generating the primes}{11}{8} +\Z { The inner loop}{22}{11} +\Z { Index}{27}{13} diff --git a/web/literateprog/primes.contents_z b/web/literateprog/primes.contents_z new file mode 100644 index 0000000000..383207c656 Binary files /dev/null and b/web/literateprog/primes.contents_z differ diff --git a/web/literateprog/primes.tex b/web/literateprog/primes.tex new file mode 100644 index 0000000000..b14a43bae8 --- /dev/null +++ b/web/literateprog/primes.tex @@ -0,0 +1,555 @@ +\input webmac +% limbo material +\font\ninerm=amr9 +\let\mc=\ninerm % medium caps for names like PASCAL +\def\WEB{{\tt WEB}} +\def\PASCAL{{\mc PASCAL}} +\def\[{\ifhmode\ \fi$[\![$} +\def\]{$]\!]$\ } +\def\<{$\langle\,$} +\def\>{$\,\rangle$} +\def\Dijk{{2}} % unnecessary when combined with text of paper +\def\goto{{3}} % ditto +\hyphenation{Dijk-stra} % ditto +\def\sec{{\tensy x}} +\hsize=84mm + + +\N1. Printing primes: An example of \WEB. +The following program is essentially the same as Edsger Dijkstra's +``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. + +\[Double brackets will be used in what follows to enclose comments +relating to \WEB\ itself, because the chief purpose of this program +is to introduce the reader to the \WEB\ style of documentation. +\WEB\ programs are always broken into small sections, each +of which has a serial number; the present section is number~1.\] + +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. \[Every section in a \WEB\ program begins with optional {\it +commentary\/} about that section, and ends with optional {\it program +text\/} for the section. For example, you are now reading part of the +commentary in \sec1, and the program text for \sec1 immediately follows +the present paragraph. Program texts are specifications of \PASCAL\ +programs; they either use \PASCAL\ language directly, or they use angle +brackets to represent \PASCAL\ code that appears in other sections. For +example, the angle-bracket notation `\X2:Program to print $\ldots$ +numbers\X' is \WEB's way of saying the following: ``The \PASCAL\ text to +be inserted here is called `Program to print $\ldots$ 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.\] + +\Y\P\X2:Program to print the first thousand prime numbers\X\par +\fi + +\M2. 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.\] + +\Y\P$\4\X2:Program to print the first thousand prime numbers\X\S$\6 +\4\&{program}\1\ \37$\\{print\_primes}(\\{output})$;\6 +\4\&{const} \37$\|m=1000$;\5 +\X5:Other constants of the program\X\6 +\4\&{var} \37\X4:Variables of the program\X\6 +\&{begin} \37\X3:Print the first \|m prime numbers\X;\6 +\&{end}.\par +\U section~1.\fi + + +\N3. 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 numbers that will be generated, and to separate the generation +problem from the printing problem. + +\[The \WEB\ description you are reading once again follows 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.\] + +\Y\P$\4\X3:Print the first \|m prime numbers\X\S$\6 +\X11:Fill table \|p with the first \|m prime numbers\X;\6 +\X8:Print table \|p\X\par +\U section~2.\fi + +\M4. How should table \|p be represented? Two possibilities suggest +themselves: We could construct a sufficiently large array +of boolean values in which 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 \|kth entry is the \|kth prime number. Let us choose the latter +alternative, by introducing an integer array called $\|p[1\to\|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 $k$th +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 `\X4:Variables of the +program\X'; the number `{\eightrm4}' in this name refers to the +present section, which is the first section to specify the +expanded meaning of `\'. +The note `{\eightrm See also $\ldots$}' refers to all of the other +sections that have the same top-level description. The expanded meaning of +`\X4:Variables of the program\X' consists of all the program texts +for this name, not just the text found in~\sec4.\] + +\Y\P$\4\X4:Variables of the program\X\S$\6 +\4\|p: \37\&{array} $[1\to\|m]$ \1\&{of}\5 +\\{integer};\C{the first \|m prime numbers, in increasing order}\2\par +\A sections~7, 12, 15, 17, 23, and~24. +\U section~2.\fi + + +\N5. 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}\cdot\\{cc}$. + +\Y\P$\4\X5:Other constants of the program\X\S$\6 +$\\{rr}=50$;\C{this many rows will be on each page in the output}\6 +$\\{cc}=4$;\C{this many columns will be on each page in the output}\6 +$\\{ww}=10$;\C{this many character positions will be used in each column}\par +\A section~19. +\U section~2.\fi + +\M6. In order to keep this program reasonably free of notations 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 introduced 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 {\it macro definitions\/} +between the opening comments and the closing program text. The +general format for each section is actually tripartite: commentary, +then definitions, then program. Any of the three parts may be absent; +for example, the present section contains no program text.\] + +\[Simple macros simply substitute a bit of \PASCAL\ code for an +identifier. Parametric macros are similar, but they also substitute +an argument wherever `\#' occurs in the macro definition. The first three +macro definitions here are parametric; the other two are simple.\] + +\Y\P\D \37$\\{print\_string}(\#)\S\\{write}(\#)$\C{put a given string into the % +\\{output} file}\par +\P\D \37$\\{print\_integer}(\#)\S\\{write}(\#:1)$\C{put a given integer into +the \\{output} file, in decimal notation, using only as many digit +positions as necessary}\par +\P\D \37$\\{print\_entry}(\#)\S\\{write}(\#:\\{ww})$\C{like \\{print\_integer}, +but \\{ww} character positions are filled, inserting blanks at the left}\par +\P\D \37$\\{new\_line}\S\\{write\_ln}$\C{advance to a new line in the % +\\{output} file}\par +\P\D \37$\\{new\_page}\S\\{page}$\C{advance to a new page in the \\{output} +file}\par +\fi + +\M7. 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 `$+\S$' 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.\] + +\Y\P$\4\X4:Variables of the program\X\mathrel{+}\S$\6 +\4\\{page\_number}: \37\\{integer};\C{one more than the number of pages printed +so far}\6 +\4\\{page\_offset}: \37\\{integer};\C{index into \|p for the first entry on the +current page}\6 +\4\\{row\_offset}: \37\\{integer};\C{index into \|p for the first entry in the +current row}\6 +\4\|c: \37$0\to\\{cc}$;\C{runs through the columns in a row}\par +\fi + +\M8. Now that appropriate auxiliary variables have been introduced, the process +of outputting table~\|p almost writes itself. + +\Y\P$\4\X8:Print table \|p\X\S$\6 +\&{begin} \37$\\{page\_number}\K1$;\5 +$\\{page\_offset}\K1$;\6 +\&{while} $\\{page\_offset}\L\|m$ \1\&{do}\6 +\&{begin} \37\X9:Output a page of answers\X;\6 +$\\{page\_number}\K\\{page\_number}+1$;\5 +$\\{page\_offset}\K\\{page\_offset}+\\{rr}\ast\\{cc}$;\6 +\&{end};\2\6 +\&{end}\par +\U section~3.\fi + +\M9. A simple heading is printed at the top of each page. + +\Y\P$\4\X9:Output a page of answers\X\S$\6 +\&{begin} \37$\\{print\_string}(\.{\'The\ First\ \'})$;\5 +$\\{print\_integer}(\|m)$;\6 +$\\{print\_string}(\.{\'\ Prime\ Numbers\ ---\ Page\ \'})$;\5 +$\\{print\_integer}(\\{page\_number})$;\5 +\\{new\_line};\5 +\\{new\_line};\C{there's a blank line after the heading}\6 +\&{for} $\\{row\_offset}\K\\{page\_offset}\mathrel{\&{to}}\\{page\_offset}+% +\\{rr}-1$ \1\&{do}\5 +\X10:Output a line of answers\X;\2\6 +\\{new\_page};\6 +\&{end}\par +\U section~8.\fi + +\M10. The first row will contain +$$\hbox{$\|p[1]$, $\|p[1+\\{rr}]$, $\|p[1+2\ast\\{rr}]$, \dots;}$$ +a similar pattern holds for each value of the \\{row\_offset}. + +\Y\P$\4\X10:Output a line of answers\X\S$\6 +\&{begin} \37\&{for} $\|c\K0\mathrel{\&{to}}\\{cc}-1$ \1\&{do}\6 +\&{if} $\\{row\_offset}+\|c\ast\\{rr}\L\|m$ \1\&{then}\5 +$\\{print\_entry}(\|p[\\{row\_offset}+\|c\ast\\{rr}])$;\2\2\6 +\\{new\_line};\6 +\&{end}\par +\U section~9.\fi + + +\N11. 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 introduced later. + +\Y\P$\4\X11:Fill table \|p with the first \|m prime numbers\X\S$\6 +\X16:Initialize the data structures\X;\6 +\&{while} $\|k<\|m$ \1\&{do}\6 +\&{begin} \37\X14:Increase \|j until it is the next prime number\X;\6 +$\|k\K\|k+1$;\5 +$\|p[\|k]\K\|j$;\6 +\&{end}\2\par +\U section~3.\fi + +\M12. We need to declare the two variables \|j and~\|k that were just +introduced. + +\Y\P$\4\X4:Variables of the program\X\mathrel{+}\S$\6 +\4\|j: \37\\{integer};\C{all primes $\L\|j$ are in table \|p}\6 +\4\|k: \37$0\to\|m$;\C{this many primes are in table \|p}\par +\fi + +\M13. 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' could be coded very simply: +`\ignorespaces \&{repeat} $\|j\K\|j+1$;\unskip\ +\; +\ignorespaces \&{until} \\{j\_prime}\unskip'. +And to compute the boolean value \\{j\_prime}, the following +would suffice: `\ignorespaces$\\{j\_prime}\K\\{true}$; \&{for} $\|n\K1% +\mathrel{\&{to}}\|k$ \&{do}\unskip\ +\'. + +\fi + +\M14. However, it is possible to obtain a much more efficient algorithm by +using more facts of number theory. In the first place, we can speed +things up a bit by recognizing 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: + +\Y\P$\4\X14:Increase \|j until it is the next prime number\X\S$\6 +\1\&{repeat} \37$\|j\K\|j+2$;\5 +\X20:Update variables that depend on~\|j\X;\6 +\X22:Give to \\{j\_prime} the meaning: \|j~is a prime number\X;\6 +\4\&{until}\5 +\\{j\_prime}\2\par +\U section~11.\fi + +\M15. The \&{repeat} loop in the previous section introduces a boolean +variable \\{j\_prime}, so that it will not be necessary to resort to +a \&{goto} statement. (We are following Dijkstra,$^\Dijk$ not Knuth.$^\goto$) + +\Y\P$\4\X4:Variables of the program\X\mathrel{+}\S$\6 +\4\\{j\_prime}: \37\\{boolean};\C{is \|j a prime number?}\par +\fi + +\M16. In order to make the odd-even trick work, we must of course initialize +the variables \|j, \|k, and $\|p[1]$ as follows. + +\Y\P$\4\X16:Initialize the data structures\X\S$\6 +$\|j\K1$;\5 +$\|k\K1$;\5 +$\|p[1]\K2$;\par +\A section~18. +\U section~11.\fi + +\M17. Now we can apply more number theory in order to obtain further +economies. If \|j is not prime, its smallest prime factor $p_n$ will +be $\sqrt j$ or less. Thus if we know a number \\{ord} such that +$$p[\\{ord}]^2>j,$$ and if \|j is odd, we need only test for divisors +in the set $\{p[2], \ldots, p[\\{ord}-1]\}$. This is much faster than +testing divisibility by $\{p[2],\ldots,p[k]\}$, since \\{ord} tends +to be much smaller than~\|k. \ (Indeed, when \|k is large, the +celebrated ``prime number theorem'' implies that the value of \\{ord} +will be approximately $2\sqrt{k/\!\ln k}$.) + +Let us therefore introduce \\{ord} into the data structure. A moment's +thought makes it clear that \\{ord} changes in a simple way when \|j +increases, and that another variable \\{square} facilitates the +updating process. + +\Y\P$\4\X4:Variables of the program\X\mathrel{+}\S$\6 +\4\\{ord}: \37$2\to\\{ord\_max}$;\C{the smallest index $\G2$ such that +$p_{ord}^2>j$}\6 +\4\\{square}: \37\\{integer};\C{$\\{square}=p_{ord}^2$}\par +\fi + +\M18. \P$\X16:Initialize the data structures\X\mathrel{+}\S$\6 +$\\{ord}\K2$;\5 +$\\{square}\K9$;\par +\fi + +\M19. The value of \\{ord} will never get larger than a certain value +\\{ord\_max}, which must be chosen sufficiently large. It turns out that +\\{ord} never exceeds~30 when $\|m=1000$. + +\Y\P$\4\X5:Other constants of the program\X\mathrel{+}\S$\6 +$\\{ord\_max}=30$;\C{$p_{ord\_max}^2$ must exceed $p_m$}\par +\fi + +\M20. When \|j has been increased by~2, we must increase \\{ord} by unity +when $j=p_{ord}^2$, i.e., when $\|j=\\{square}$. + +\Y\P$\4\X20:Update variables that depend on~\|j\X\S$\6 +\&{if} $\|j=\\{square}$ \1\&{then}\6 +\&{begin} \37$\\{ord}\K\\{ord}+1$;\5 +\X21:Update variables that depend on~\\{ord}\X;\6 +\&{end}\2\par +\U section~14.\fi + +\M21. At this point in the program, \\{ord} has just been increased by unity, +and we want to set $\\{square}:=p_{ord}^2$. A surprisingly subtle point +arises here: How do we know that $p_{ord}$ has already been computed, +i.e., that $\\{ord}\L\|k$? If there were a gap in the sequence of prime +numbers, +such that $p_{k+1}>p_k^2$ for some~$k$, then this part of the program would +refer to the yet-uncomputed value $\|p[\|k+1]$ unless some special test were +made. + +Fortunately, there are no such gaps. But no simple proof of this fact is +known. For example, Euclid's famous demonstration that there are +infinitely many prime numbers is strong enough to prove only that +$p_{k+1}<=p_1\ldots p_k+1$. Advanced books on number theory come to our +rescue by showing that much more is true; for example, ``Bertrand's +postulate'' states that $p_{k+1}<2p_k$ +for all~$k$. + +\Y\P$\4\X21:Update variables that depend on~\\{ord}\X\S$\6 +$\\{square}\K\|p[\\{ord}]\ast\|p[\\{ord}]$;\C{at this point $\\{ord}\L\|k$}\par +\A section~25. +\U section~20.\fi + + +\N22. The inner loop. +Our remaining task is to determine whether or not a given integer~\|j is prime. +The general outline of this part of the program is quite simple, +using the value of \\{ord} as described above. + +\Y\P$\4\X22:Give to \\{j\_prime} the meaning: \|j~is a prime number\X\S$\6 +$\|n\K2$;\5 +$\\{j\_prime}\K\\{true}$;\6 +\&{while} $(\|n<\\{ord})\W\\{j\_prime}$ \1\&{do}\6 +\&{begin} \37\X26:If $\|p[\|n]$ is a factor of~\|j, set $\\{j\_prime}\K% +\\{false}$\X;\6 +$\|n\K\|n+1$;\6 +\&{end}\2\par +\U section~14.\fi + +\M23. \P$\X4:Variables of the program\X\mathrel{+}\S$\6 +\4\|n: \37$2\to\\{ord\_max}$;\C{runs from 2 to \\{ord} when testing +divisibility}\par +\fi + +\M24. Let's suppose that division is very slow or nonexistent on our +machine. We want to detect nonprime odd numbers, which are odd multiples +of the set of primes $\{p_2,\ldots,p_{ord}\}$. + +Since \\{ord\_max} is small, it is reasonable to maintain an auxiliary table of +the smallest odd multiples that haven't already been used to show that +some~\|j is nonprime. In other words, our goal is to ``knock out'' all +of the odd multiples of each $p_n$ in the set $\{p_2,\ldots,p_{ord}\}$, +and one way to do this is to introduce an auxiliary table that serves as +a control structure for a set of knock-out procedures that are being +simulated in parallel. (The so-called ``sieve of Eratosthenes'' +generates primes by a similar method, but +it knocks out the multiples of each prime serially.) + +The auxiliary table suggested by these considerations is a \\{mult} +array that satisfies the following invariant condition: For $2\L\|n<\\{ord}$, +$\\{mult}[\|n]$ is an odd multiple of $p_n$ such that $\\{mult}[n]{$\,\rangle$} +\def\Dijk{{2}} % unnecessary when combined with text of paper +\def\goto{{3}} % ditto +\hyphenation{Dijk-stra} % ditto +\def\sec{{\tensy x}} +\hsize=84mm + +@* 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\ itself, because the chief purpose of this program +is to introduce the reader to the \WEB\ style of documentation. +\WEB\ programs are always broken into small sections, each +of which has a serial number; the present section is number~1.\] + +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. \[Every section in a \WEB\ program begins with optional {\it +commentary\/} about that section, and ends with optional {\it program +text\/} for the section. For example, you are now reading part of the +commentary in \sec1, and the program text for \sec1 immediately follows +the present paragraph. Program texts are specifications of \PASCAL\ +programs; they either use \PASCAL\ language directly, or they use angle +brackets to represent \PASCAL\ code that appears in other sections. For +example, the angle-bracket notation `\X2:Program to print $\ldots$ +numbers\X' is \WEB's way of saying the following: ``The \PASCAL\ text to +be inserted here is called `Program to print $\ldots$ 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.\] + +@p @ + +@ 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. + +@* 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 numbers that will be generated, and to separate the generation +problem from the printing problem. + +\[The \WEB\ description you are reading once again follows 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.\] + +@= +@; +@ + +@ How should table |p| be represented? Two possibilities suggest +themselves: We could construct a sufficiently large array +of boolean values in which 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 +alternative, by introducing an integer array called |p[1..m]|. + +In the documentation below, the notation `|p[k]|' will refer to the +|k|th element of array~|p|, while `$p_k$' will refer to the $k$th +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 `\X4:Variables of the +program\X'; the number `{\eightrm4}' in this name refers to the +present section, which is the first section to specify the +expanded meaning of `\'. +The note `{\eightrm See also $\ldots$}' refers to all of the other +sections that have the same top-level description. The expanded meaning of +`\X4:Variables of the program\X' consists of all the program texts +for this name, not just the text found in~\sec4.\] + +@=@!p:array[1..m] of integer; + {the first |m| prime numbers, in increasing order} + +@* 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|\cdot|cc|$. +@^output format@> + +@= +@!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} + +@ In order to keep this program reasonably free of notations 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 introduced 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 {\it macro definitions\/} +between the opening comments and the closing program text. The +general format for each section is actually tripartite: commentary, +then definitions, then program. Any of the three parts may be absent; +for example, the present section contains no program text.\] + +\[Simple macros simply substitute a bit of \PASCAL\ code for an +identifier. Parametric macros are similar, but they also substitute +an argument wherever `\#' occurs in the macro definition. 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} + +@ 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 `$+\S$' 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.\] + +@= +@!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} + +@ Now that appropriate auxiliary variables have been introduced, the process +of outputting table~|p| almost writes itself. + +@= +begin page_number:=1; page_offset:=1; +while page_offset<=m do + begin @; + page_number:=page_number+1; + page_offset:=page_offset+rr*cc; + end; +end + +@ A simple heading is printed at the top of each page. +@^output format@> @^page headings@> + +@= +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 + @; +new_page; +end + +@ The first row will contain +$$\hbox{|p[1]|, |p[1+rr]|, |p[1+2*rr]|, \dots;}$$ +a similar pattern holds for each value of the |row_offset|. + +@= +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 + +@* 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 introduced later. + +@= +@; +while k; + k:=k+1; p[k]:=j; + end + +@ We need to declare the two variables |j| and~|k| that were just +introduced. + +@= +@!j:integer; {all primes |<=j| are in table |p|} +@!k:0..m; {this many primes are in table |p|} + +@ 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 + +Therefore the section of the program that is called `\' could be coded very simply: +`\ignorespaces|repeat j:=j+1;|\unskip\ +\; +\ignorespaces|until j_prime|\unskip'. +And to compute the boolean value |j_prime|, the following +would suffice: `\ignorespaces|j_prime:=true; for n:=1 to k do|\unskip\ +\'. + +@ However, it is possible to obtain a much more efficient algorithm by +using more facts of number theory. In the first place, we can speed +things up a bit by recognizing 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: + +@= +repeat j:=j+2; @; +@; +until j_prime + +@ The |repeat| loop in the previous section introduces a boolean +variable |j_prime|, so that it will not be necessary to resort to +a |goto| statement. (We are following Dijkstra,$^\Dijk$ not Knuth.$^\goto$) +@^Dijkstra, Edsger@> @^Knuth, Donald E.@> + +@= +@!j_prime:boolean; {is |j| a prime number?} + +@ In order to make the odd-even trick work, we must of course initialize +the variables |j|, |k|, and |p[1]| as follows. + +@= +j:=1; k:=1; p[1]:=2; + +@ Now we can apply more number theory in order to obtain further +economies. If |j| is not prime, its smallest prime factor $p_n$ will +be $\sqrt j$ or less. Thus if we know a number |ord| such that +$$p[|ord|]^2>j,$$ and if |j| is odd, we need only test for divisors +in the set $\{p[2], \ldots, p[|ord|-1]\}$. This is much faster than +testing divisibility by $\{p[2],\ldots,p[k]\}$, since |ord| tends +to be much smaller than~|k|. \ (Indeed, when |k| is large, the +celebrated ``prime number theorem'' implies that the value of |ord| +will be approximately $2\sqrt{k/\!\ln k}$.) + +Let us therefore introduce |ord| into the data structure. A moment's +thought makes it clear that |ord| changes in a simple way when |j| +increases, and that another variable |square| facilitates the +updating process. + +@= +@!ord:2..ord_max; {the smallest index |>=2| such that $p_{ord}^2>j$} +@!square:integer; {$|square|=p_{ord}^2$} + +@ @= +ord:=2; square:=9; + +@ The value of |ord| will never get larger than a certain value +|ord_max|, which must be chosen sufficiently large. It turns out that +|ord| never exceeds~30 when |m=1000|. + +@= +@!ord_max=30; {$p_{ord\_max}^2$ must exceed $p_m$} + +@ When |j| has been increased by~2, we must increase |ord| by unity +when $j=p_{ord}^2$, i.e., when |j=square|. + +@= +if j=square then + begin ord:=ord+1; + @; + end + +@ At this point in the program, |ord| has just been increased by unity, +and we want to set $|square|:=p_{ord}^2$. A surprisingly subtle point +arises here: How do we know that $p_{ord}$ has already been computed, +i.e., that |ord<=k|? If there were a gap in the sequence of prime numbers, +such that $p_{k+1}>p_k^2$ for some~$k$, then this part of the program would +refer to the yet-uncomputed value |p[k+1]| unless some special test were +made. + +Fortunately, there are no such gaps. But no simple proof of this fact is +known. For example, Euclid's famous demonstration that there are +infinitely many prime numbers is strong enough to prove only that +$p_{k+1}<=p_1\ldots p_k+1$. Advanced books on number theory come to our +rescue by showing that much more is true; for example, ``Bertrand's +postulate'' @^Bertrand, Joseph, postulate@> states that $p_{k+1}<2p_k$ +for all~$k$. + +@= +square:=p[ord]*p[ord]; {at this point |ord<=k|} + +@* The inner loop. +Our remaining task is to determine whether or not a given integer~|j| is prime. +The general outline of this part of the program is quite simple, +using the value of |ord| as described above. + +@= +n:=2; j_prime:=true; +while (n; + n:=n+1; + end + +@ @= +@!n:2..ord_max; {runs from 2 to |ord| when testing divisibility} + +@ Let's suppose that division is very slow or nonexistent on our +machine. We want to detect nonprime odd numbers, which are odd multiples +of the set of primes $\{p_2,\ldots,p_{ord}\}$. + +Since |ord_max| is small, it is reasonable to maintain an auxiliary table of +the smallest odd multiples that haven't already been used to show that +some~|j| is nonprime. In other words, our goal is to ``knock out'' all +of the odd multiples of each $p_n$ in the set $\{p_2,\ldots,p_{ord}\}$, +and one way to do this is to introduce an auxiliary table that serves as +a control structure for a set of knock-out procedures that are being +simulated in parallel. (The so-called ``sieve of Eratosthenes'' +@^Eratosthenes, sieve of@> generates primes by a similar method, but +it knocks out the multiples of each prime serially.) + +The auxiliary table suggested by these considerations is a |mult| +array that satisfies the following invariant condition: For |2<=n= +@!mult:array[2..ord_max] of integer; {runs through multiples of primes} + +@ When |ord| has been increased, we need to initialize a new element of +the |mult| array. At this point $j=p[|ord|-1]^2$, so there is no +need for an elaborate computation. + +@= +mult[ord-1]:=j; + +@ The remaining task is straightforward, given the data structures +already prepared. Let us recapitulate the current situation: The +goal is to test whether or not |j|~is divisible by~$p_n$, without +actually performing a division. We know that $j$~is odd, and that +|mult[n]| is an odd multiple of~$p_n$ such that $|mult|[n]=j|, the +conditions imply that |j|~is divisible by~$p_n$ if and only if +|j=mult[n]|. + +@= +while mult[n]0pt \setbox255=\vbox{\unvbox\lefttop + \setbox0=\lastbox\unvbox0\vskip\skip\lefttop\unvbox255}\fi + \setbox0=\vsplit255 to\dimen0 + \ifdim\ht\righttop>0pt \setbox255=\vbox{\unvbox\righttop + \setbox0=\lastbox\unvbox0\vskip\skip\righttop\unvbox255}\fi + \setbox2=\vsplit255 to\dimen0 + \onepageout\pagesofar + \unvbox255 \penalty\outputpenalty} +\def\pagesofar{\unvbox\partialpage + \wd0=\hsize \wd2=\hsize \hbox to\pagewidth{\box0\hfil\box2}} +\def\balancecolumns{\setbox0=\vbox{\unvbox255} \dimen0=\ht0 + \advance\dimen0 by\topskip \advance\dimen0 by-\baselineskip + \divide\dimen0 by2 \splittopskip=\topskip + {\vbadness=10000 \loop \global\setbox3=\copy0 + \global\setbox1=\vsplit3 to\dimen0 + \ifdim\ht3>\dimen0 \global\advance\dimen0 by1pt \repeat} + \setbox0=\vbox to\dimen0{\unvbox1} + \setbox2=\vbox to\dimen0{\unvbox3} + \pagesofar} + +\def\CJrule{\hrule height\ruleht} +\baselineskip=11pt +\parskip=0pt plus 1pt +\def\beginsection #1\par{\goodbreak\vskip9mm plus4mm minus 2mm + \vbox{\CJrule width \hsize \kern5pt} + \kern-3pt + \nointerlineskip + \leftline{\strut\bf#1} + \CJrule + \kern12pt\nobreak\noindent\ignorespaces} +\def\caption #1. #2.{\leftline{\def\TeX{T\kern-.2em\lower.5ex\hbox{E}X}% + \tenssb Figure #1.\enspace\tenss#2.}} + +\def\WEB{{\tt WEB}} +\def\PASCAL{{\mc PASCAL}} +\def\sec{{\tensy x}} +\def\<{$\langle\,$} +\def\>{$\,\rangle$} +\newbox\circlebox +\setbox\circlebox=\hbox{\man Y} +\def\encircle#1{\kern6pt\hbox to\wd\circlebox{\hss\tt#1\hss}\kern-\wd\circlebox + \raise10pt\copy\circlebox\kern6pt} + +\def\ttverbatim{\begingroup \tt \parindent=0pt \obeylines + \uncatcodespecials \catcode`/=0 \obeyspaces} +\let\endverbatim=\endgroup +{\obeyspaces\global\let =\ } % let active space = control space +\def\uncatcodespecials{\def\do##1{\catcode`##1=12 }\dospecials} +\def\cvdots{\kern3pt\qquad\smash\vdots} + +\newcount\refno \newif\ifshowit +\def\ref{\showittrue\makeref} +\def\silentref{\showitfalse\makeref} +\def\references{} % this will grow until it holds all the references +\def\makeref#1#2{\advance\refno by1 \edef#1{{\the\refno}}% + \toks0=\expandafter{\references}% + {\def\rm{\eightss}\def\sl{\eightssi}\def\bf{\eightssb}\def\tt{\eighttt}% + \def\TeX{T\kern-.2em\lower.5ex\hbox{E}\kern-.000em X}% + \xdef\references{\the\toks0 \noexpand\item{\the\refno.}#2\par}}% + \ifshowit\edef\next{\spacefactor=\the\spacefactor\space}% + $^{\the\refno}$\next\fi} +\hyphenation{Dijk-stra} +\hyphenchar\tentt=-1 % no hyphenation in the typewriter font + +\titlepage +\leftline{\kern13mm\CompJtitle Literate Programming} +\kern6mm +\CJrule +\kern4.5mm +\leftline{\kern13mm\bf Donald E. Knuth} +\kern2pt +\leftline{\kern13mm\eightrm Computer Science Department, Stanford University, + Stanford, CA 94305, USA} +\kern4mm +\CJrule +\kern6mm +\leftline{\kern13mm\vbox{\hsize=151mm\CompJabstract\noindent +The author and his associates have been experimenting for the past several +years with a programming language and documentation system called \WEB. +This paper presents \WEB\ by example, and discusses why the new +system appears to be an improvement over previous ones.}} +\bigskip\bigskip +\begindoublecolumns + +\beginsection A. INTRODUCTION + +The past ten years have witnessed substantial improvements in programming +methodology. This advance, carried out under the banner of ``structured +programming,'' has led to programs that are more reliable and easier to +comprehend; yet the results are not entirely satisfactory. My purpose +in the present paper is to propose another motto that may be appropriate +for the next decade, as we attempt to make further progress in the +state of the art. I believe that the time is ripe for significantly +better documentation of programs, and that we can best achieve this by +considering programs to be {\it works of literature}. Hence, my title: +``Literate Programming.'' + +Let us change our traditional attitude to the construction of programs: +Instead of imagining that our main task is to instruct a {\it computer\/} +what to do, let us concentrate rather on explaining to {\it human beings\/} +what we want a computer to do. + +The practitioner of literate programming can be regarded as an essayist, whose +main concern is with exposition and excellence of style. Such an author, +with thesaurus in hand, chooses the names of variables carefully and explains +what each variable means. He or she strives for a program that is +comprehensible because its concepts have been introduced in an order that +is best for human understanding, using a mixture of formal and informal +methods that re\"\i nforce each other. + +I dare to suggest that such advances in documentation are possible because +of the experiences I've had during the past several years while working +intensively on software development. By making use of several ideas that +have existed for a long time, and by applying them systematically in a +slightly new way, I've stumbled across a method of composing programs +that excites me very much. In fact, my enthusiasm is so great that I must warn +the reader to discount much of what I shall say as the ravings of a fanatic +who thinks he has just seen a great light. + +Programming is a very personal activity, so I can't be certain that what has +worked for me will work for everybody. Yet the impact of this new approach on +my own style has been profound, and my excitement has continued unabated +for more than two years. I~enjoy the new methodology so much that it is hard +for me to refrain from going back to every program that I've ever written +and recasting it in ``literate'' form. I~find myself unable to resist working +on programming tasks that I would ordinarily have assigned to student +research assistants; and why? Because it seems to me that at last I'm able +to write programs as they should be written. My programs are not only +explained better than ever before; they also are better programs, +because the new methodology encourages me to do a better job. For these +reasons I am compelled to write this paper, in hopes that my experiences +will prove to be relevant to others. + +I must confess that there may also be a bit of malice in my choice of +a title. During the 1970s I was coerced like everybody else into adopting +the ideas of structured programming, because I couldn't bear to be found +guilty of writing {\it unstructured\/} programs. Now I have a chance +to get even. By coining the phrase ``literate programming,'' I am imposing +a moral commitment on everyone who hears the term; surely nobody wants +to admit writing an {\it il{}literate\/} program. + +\beginsection B. THE \WEB\ SYSTEM + +I hope, however, to demonstrate in this paper that the title is not merely +wordplay. The ideas of literate programming have been embodied in a language +and a suite of computer programs that have been developed at Stanford +University during the past few years as part of my research on algorithms +and on digital typography. This language and its associated programs +have come to be known as the \WEB\ system. My goal in what follows is +to describe the philosophy that underlies \WEB, to present examples +of programs in the \WEB\ language, and to discuss what may be the future +implications of this work. + +I chose the name \WEB\ partly because it was one of the few three-letter +words of English that hadn't already been applied to computers. But as time +went on, I've become extremely pleased with the name, because I~think +that a complex piece of software is, indeed, best regarded as a {\it web\/} +that has been delicately pieced together from simple materials. We +understand a complicated system by understanding its simple parts, and by +understanding the simple relations between those parts and their immediate +neighbors. If we express a program as a web of ideas, we can emphasize +its structural properties in a natural and satisfying way. + +\WEB\ itself is chiefly a combination of two other languages: +(1)~a document formatting language and (2)~a programming language. +My prototype \WEB\ system uses \TeX\ as the document formatting +language and \PASCAL\ as the programming language, but the same +principles would apply equally well if other languages were +substituted. Instead of \TeX, one could use a language like Scribe +or Troff; instead of \PASCAL, one could use {\mc ADA}, {\mc ALGOL}, +{\mc LISP}, {\mc COBOL}, {\mc FORTRAN}, {\mc APL}, {\mc C}, etc., or +even assembly language. The main point is that \WEB\ is inherently +bilingual, and that such a combination of languages proves to be much +more powerful than either single language by itself. \WEB\ does not +make the other languages obsolete; on the contrary, it enhances them. + +I naturally chose \TeX\ to be the document formatting language, in the +first \WEB\ system, because \TeX\ is my own creation;\ref\TeXbook{D. E. Knuth, +{\sl The \TeX book}. Addison-Wesley, Reading, Mass., U.S.A. (1983).} +I wanted to acquire a lot of experience in harnessing \TeX\ to a variety +of different tasks. I~chose \PASCAL\ as the programming language because +it has received such widespread support from educational institutions all +over the world; it is not my favorite language for system programming, but +it has become a ``second language'' for so many programmers that it +provides an exceptionally effective medium of communication. Furthermore +\WEB\ itself has a macro-processing ability that makes \PASCAL's +limitations largely irrelevant. + +Document formatting languages are newcomers to the computing scene, but +their use is spreading rapidly. Therefore I'm confident that we will be +able to expect each member of the next generation of programmers to be +familiar with a document language as well as a programming language, +as part of their basic education. Once a person knows both of the +underlying languages, there's no trick at all to learning \WEB, because +the \WEB\ user's manual is fewer than ten pages long. + +A \WEB\ user writes a program that serves +as the source language for two different system routines. (See Figure~1.) +One line of processing is called {\it weaving\/} the web; it produces +a document that describes the program clearly and that facilitates program +maintenance. The other line of processing is called {\it tangling\/} the +web; it produces a machine-executable program. The program and its +documentation are both generated from the same source, so they are +consistent with each other. + +\bigskip +\centerline{\vbox{ + \halign{&\hss#\hss\cr + &&&\TeX\cr + \noalign{\vskip-4pt} + &&\encircle{TEX}&\enspace\rightarrowfill\enspace&\encircle{DVI}\cr + \multispan2\hfil\smash{\raise4pt\hbox{\tt WEAVE}\kern-1pt}$\nearrow$ \cr + \noalign{\vskip6pt} + \encircle{WEB}\cr + \noalign{\vskip6pt} + \multispan2\hfil\smash{\lower6pt\hbox{\tt TANGLE}\kern-1pt}$\searrow$ \cr + &&\encircle{PAS}&\enspace\rightarrowfill\enspace&\encircle{REL}\cr + \noalign{\vskip-2pt} + &&&\mc\ PASCAL\ \cr} + }} +\nobreak\medskip +\caption 1. Dual usage of a {\tt WEB} file. +\bigbreak + +Let's look at this process in slightly more detail. Suppose you have +written a \WEB\ program and put it into a computer text file called +{\tt COB.WEB} (say). To generate hardcopy documentation for your program, +you can run the {\tt WEAVE} processor; this is a system program that takes +the file {\tt COB.WEB} as input and produces another file {\tt COB.TEX} +as output. Then you run the \TeX\ processor, which takes {\tt COB.TEX} +as input and produces {\tt COB.DVI} as output. The latter file, +{\tt COB.DVI}, is a ``device-independent'' binary description of how +to typeset the documentation, so you can get printed output by applying +one more system routine to this file. + +You can also follow the other branch of Figure~1, by running the +{\tt TANGLE} processor; this is a system program that takes the file +{\tt COB.WEB} as input and produces a new file {\tt COB.PAS} as output. +Then you run the \PASCAL\ compiler, which converts {\tt COB.PAS} to +a binary file {\tt COB.REL} (say). Finally, you can run your program +by loading and executing {\tt COB.REL}. The process of ``compile, load, +and go'' has been slightly lengthened to ``tangle, compile, load, and go.'' + +\beginsection C. A COMPLETE EXAMPLE + +Now it's time for me to stop presenting general platitudes and to move on +to something tangible. Let us look at a real program that has been written +in \WEB. The numbered paragraphs that follow are the actual output of a +\WEB\ file that has been ``woven'' into a document; a computer has also +generated the indexes that appear at the program's end. If my claims for +the advantages of literate programming have any merit, you should be able +to understand the following description more easily than you could +have understood the same program when presented in a more conventional +way. However, I am trying here to explain the format of \WEB\ documentation +at the same time as I am discussing the details of a nontrivial algorithm, +so the description below is slightly longer than it would be if it were +written for people who already have been introduced to \WEB. + +\silentref\Dijk{O.-J.~Dahl, E.~W. Dijkstra, and C.~A.~R. Hoare, +{\sl Structured Programming}. Academic Press, London and New York (1972).} +\silentref\goto{D. E. Knuth, Structured programming with {\bf go to} +statements. {\sl Computing Surveys\/ \bf6}, 261--301 (1974).} + +Here, then, is the computer-generated output: + +\bigskip +\CJrule +\medskip +\begingroup +\def\prune\input webmac{\input primes.contents} +\def\Z#1#2#3{\line{\ignorespaces#1\ \dotfill\ {\tensy x}#2}} +\def\M#1.{\MN#1.\iftrue\medbreak\startsection\ignorespaces} +\def\firstmod{1} +\def\N#1.#2.{\MN#1.\iftrue\nobreak + \ifx\modno\firstmod\medskip\else\bigskip\fi + \CJrule\medbreak\startsection + {\bf\ignorespaces#2.\quad}\ignorespaces} +\def\inx{\par\medbreak + \def\:##1, {\par\hangindent2em\noindent##1:\kern1em} + \def\[##1]{$\underline{##1}$} + \rm \rightskip0pt plus2.5em \tolerance10000 \let\*=\lapstar + \hyphenpenalty10000 \parindent0pt} +\def\fin{\par\bigskip\CJrule\medbreak + \parfillskip0pt plus1fil + \def\note##1##2.{\hfil\penalty-1\hfilneg\quad{\eightrm##1 ##2.}} + \def\U{\note{Used in}} + \def\:{\par\hangindent 2em}\let\*=*} +\let\con=\par +\parskip=0pt +\expandafter\prune\input primes +\endgroup + +\beginsection D. HOW THE EXAMPLE WAS SPECIFIED + +Everything reproduced above, from the table of contents preceding the +program to the indexes of identifiers and section names at the end, +was generated by applying the program {\tt WEAVE} to a source file +{\tt PRIMES.WEB} written in the \WEB\ language. Let us now look at that +file {\tt PRIMES.WEB}, in order to get an idea of what a \WEB\ user +actually types. + +There's no need to show very much of {\tt 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 {\tt PRIMES.WEB} by looking only at the formatted +output and Figure~2. + +\leftfloat +\ttverbatim +/hrule +/medskip +\font\ninerm=cmr9 +\let\mc=\ninerm % medium caps +\def\WEB{{\tt WEB}} +\def\PASCAL{{\mc PASCAL}} +\def\[{\ifhmode\ \fi$[\mkern-2mu[$} +\def\]{$]\mkern-2mu]$\ } +/cvdots +\hyphenation{Dijk-stra} +/medskip +@* 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@> +/medskip +\[Double brackets will be used in what +follows to enclose comments relating to \WEB\ +/cvdots +an informal top-level description.\] +/medskip +@p @ +/endverbatim +\medskip +\caption 2a. The beginning of {\tt PRIMES.WEB}. +\medskip +\hrule +\endfloat + +Figure 2a starts with \TeX\ commands (not shown in full) that make it +convenient to typeset double brackets $[\mkern-2mu[\ldots]\mkern-2mu]$ +and to give special typographic treatment to names like `\WEB' and `\PASCAL'. +A \WEB\ user generally begins by declaring such special aspects of the +document 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 `{\tt@*}', which starts the program proper. \WEB\ uses the +symbol `{\tt@}' as an escape character for special instructions to the +{\tt WEAVE} and {\tt TANGLE} processors. Everything between such special +commands is either expressed in \TeX\ language or in \PASCAL\ language, +depending on the context. + +Each section of the program begins either with `{\tt@ }' (i.e., at-sign +and space) or `{\tt@*}' (i.e., at-sign and asterisk); \WEB\ supplies the +section numbers automatically. The latter case, `{\tt@*}', denotes a +{\it 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 {\tt 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: +`{\tt@\char`^}' marks the beginning of an index entry to be set in roman +type; `{\tt@>}' marks the end of an argument to a \WEB\ command; +`{\tt@.}'\ marks the beginning of an index entry to be set in typewriter +type; `{\tt@p}' marks the beginning of the \PASCAL\ program; and `{\tt@<}' +marks the beginning of a top-level description, i.e., of a section +name in the \WEB\ program. + +\rightfloat +\ttverbatim +/hrule +/medskip +@ 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. +/medskip +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. +/medskip +\[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.\] +/medskip +@= +program print_primes(output); +const @!m=1000; +@@; +var @@; +begin @; +end. +/endverbatim +\medskip +\caption 2b. The \WEB\ code that generated \sec2. +\ttverbatim +/bigskip +/hrule +/medskip +@ In order to keep this program reasonably +free of notations that are uniquely +\PASCAL esque, \[and in order to illustrate +/cvdots +The first three macro definitions here are +parametric; the other two are simple.\] +/medskip +@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} +/endverbatim +\medskip +\caption 2c. The \WEB\ code that generated \sec6. +\medskip +\hrule +\endfloat + +Figure 2b immediately follows Figure~2a in the \WEB\ file. This material +is what generated \sec2 of the documentation, 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 occasionally desirable. +For example, when you refer to technical details about the program, you +usually want to describe them in \PASCAL, hence you want {\tt WEAVE} to format +them with the typographic conventions it uses for \PASCAL\ programs. +Conversely, when you put comments in a \PASCAL\ program, you want +the text of those comments to be formatted by \TeX\ in the normal way. +\WEB\ files use vertical bars to introduce \PASCAL\ formatting in the +midst of \TeX\ formatting; for example, Figure~2b says `{\tt the +|output| file}' in order to typeset `the \\{output} file'. + +The program text in Figure~2b begins with `{\tt@<}' instead of with the +`{\tt@p}' command used in Figure~2a, because the program text in~\sec2 +is the expansion of a specific top-level description. Notice that the +top-level description has been abbreviated to `{\tt@}'. +Since the names of sections tend to be rather long, it is a nuisance to +type them in full each time; \WEB\ allows you to type `{\tt...}'\ after you +have given enough text to identify the remainder uniquely. + +The `{\tt@!}'\ operation in the program text of Figure~2b governs the +underlining of index entries. The `{\tt@;}'\ specifies an invisible symbol +that has the effect of a semicolon in \PASCAL\ syntax. Commands such as these +are comparatively unimportant, but they are available for polishing up +the final documentation when you want to maintain fine control. + +Figure 2c shows key portions of the \WEB\ text that generated \sec6. +Notice that the command `{\tt@d}' introduces a macro definition. +All features of \WEB\ that appear in our example program are illustrated +in Figures 2a, 2b, and~2c; the remainder of {\tt PRIMES.WEB} simply +uses the same conventions again and again. In fact, most of the \WEB\ +file is much simpler than the examples shown here; Figure~2 has +illustrated only the difficult parts. + +\beginsection E. THE TANGLED OUTPUT + +Figure 3 shows the \PASCAL\ program {\tt PRIMES.PAS} that results when +{\tt TANGLE} is applied to {\tt PRIMES.WEB}. This program is not intended +for human consumption---it's only supposed to be readable by a \PASCAL\ +compiler---so {\tt TANGLE} does not go to great pains to produce a +beautiful format. Notice that underlines have been removed from the +identifier names, and that all of the letters have been converted to +uppercase (except in strings); {\tt TANGLE} tries to produce a format +that will be acceptable to a standard \PASCAL\ compiler. + +{\tt TANGLE} removes all of the commentary in the \WEB\ file, but it +inserts new comments of its own. If for some reason you need +to correlate the tangled \PASCAL\ code with the woven documentation, +you can find the program text for, say, \sec8 by looking between +the comments `{\tt\char`\{8:\char`\}}' and `{\tt\char`\{:8\char`\}}'. + +A comparison of Figure~3 to Figure~2 should make it clear why the +{\tt TANGLE} processor has acquired its name. + +\rightfloat +\ttverbatim +/hrule +/medskip +{1:}{2:}PROGRAM PRINTPRIMES(OUTPUT); +CONST M=1000;{5:}RR=50;CC=4;WW=10;{:5}{19:} +ORDMAX=30;{:19}VAR{4:} +P:ARRAY[1..M]OF INTEGER;{:4}{7:} +PAGENUMBER:INTEGER;PAGEOFFSET:INTEGER; +ROWOFFSET:INTEGER;C:0..CC;{:7}{12:}J:INTEGER; +K:0..M;{:12}{15:}JPRIME:BOOLEAN;{:15}{17:} +ORD:2..ORDMAX;SQUARE:INTEGER;{:17}{23:} +N:2..ORDMAX;{:23}{24:} +MULT:ARRAY[2..ORDMAX]OF INTEGER;{:24} +BEGIN{3:}{11:}{16:}J:=1;K:=1;P[1]:=2;{:16} +{18:}ORD:=2;SQUARE:=9;{:18}; +WHILE K \&{then}\cr +\quad \;\cr +\;\cr +\&{end}.\cr}}$$ +A subtle phenomenon occurs in traditional programming languages: While +writing the program for `\', +a programmer subconsciously tries to get by with the fewest possible +lines of code, since the program for `\' is +quite short. If an extensive error recovery is actually programmed, the +subroutine will appear to have error-message printing as its main purpose. +But the programmer knows that the error is really an exceptional case that +arises only rarely; therefore a lengthy error recovery doesn't look right, +and most programmers will minimize it (without realizing that they are doing +so) in order to make the subroutine's appearance match its intended behavior. +On the other hand when the same task is programmed with \WEB, the purpose +of \\{update} can be shown quite clearly, and the possibility of error +recovery can be reduced to a mere mention when \\{update} is defined. +When another section entitled `\' is subsequently written, the whole point of that section is to do +the best error recovery, and it becomes quite natural to write a better program +as a result. + +This fact---that \WEB\ allows you to let each part of the program have +its appropriate size, without distorting the readability of other parts---means +that good programmers find their \WEB\ programs better than their \PASCAL\ +programs, even though their \PASCAL\ programs once looked like the work +of an expert. + +\beginsection K. STYLISTIC ISSUES + +I found that my style of using \WEB\ evolved quite a bit during the first +year. The general format, in which each section beings with commentary and +ends with a formal program fragment, is extremely versatile; you have the +freedom to say anything you want, yet you must make a decision about how +you'll do it. I imagine that different programmers will converge to +quite different styles, but I would like to note down some of the things +that have seemed to work best for me. + +Consider first the question of macros versus section names. A named section, +like `\', is essentially the +same as a parameterless macro; \WEB\ provides both. I prefer to use +parameterless macros for ``small'' things that can be embodied in a word +or two, but named sections for longer portions of the program that +merit a fuller description. + +I usually start the name of a section with an imperative verb, but I give +a declarative commentary at the beginning of a section. Thus, +{\tt PRIMES.WEB} says `{\bf 8.}~Now that appropriate $\ldots$ +\X8:Print table $p$\X$\;\S\;$\dots\thinspace'; I wouldn't do the opposite +and say `{\bf8.}~Print the table. \X8:Code for printing\X$\;\S\;$\dots'. + +The name of a section (enclosed in angle brackets) should be long enough +to encapsulate the essential characteristics of the code in that section, +but it should not be too verbose. I found very early that it would be a +mistake to include all of the assumptions about local and global variables +in the name of each section, even though such information would strictly +be necessary to isolate that section as an independent module. The trick is +to find a balance between formal and informal exposition so that a reader +can grasp what is happening without being overwhelmed with detail.\ref\Naur% +{P. Naur, Formalization in program development. {\sl BIT\/ \bf22}, +437--453 (1982).} + +Another lesson I learned early in the game was that the name of a section +should explicitly mention any nonstandard control structures, even though +its data structures can often be left implied. Furthermore, if the control +flow is properly explained, you can avoid the usual errors associated +with \&{goto} statements; such statements can safely be introduced in +a restrained but natural manner. + +For example, \sec14 of the prime-printing example could be reprogrammed as +follows, using `\&{loop}' as a macro abbreviation for `\&{while} \\{true} +\&{do}': +$$\vbox{\halign{\hbox to\hsize{#\hfil}\cr +\X14:Increase $j$ until it is the next prime number\X$\;\S$\cr +\quad\&{loop begin} $j\K j+2$;\cr +\qquad\X20:Update variables that depend on $j$\X;\cr +\qquad\X22:If $j$ is prime, \&{goto} \\{found}\X;\cr +\qquad\&{end};\cr +\\{found}:\cr}}$$ +With this change, \sec22 could become +$$\vbox{\halign{\hbox to\hsize{#\hfil}\cr +\X22:If $j$ is prime, \&{goto} \\{found}\X$\;\S$\cr +\quad$n\K2$;\cr +\quad\&{while} $n<\\{ord}$ \&{do}\cr +\qquad\&{begin} \X26:If $p[n]$ is a factor of $j$, \&{goto} \\{not\_found}\X;\cr +\qquad$n\K n+1$;\cr +\qquad\&{end};\cr +\quad\&{goto} \\{found};\cr +\\{not\_found}:\cr}}$$ +if \sec26 changes in the obvious way. The resulting program will be more +efficient on most machines; and I believe that it is actually easier to +read and to write, in spite of the fact that two \&{goto} statements +appear, because the labels have been used with appropriate interpretations +of their abstract significance. + +Of course, \PASCAL\ makes it difficult to use \&{goto} statements, +because Wirth decided that labels should be numeric, and that they +should be declared in advance. If I were to introduce the \&{goto} +statements as suggested, I would have to define numeric macros +\\{found} and \\{not\_found}, and I would have to insert +`\&{label} \\{found}, \\{not\_found}' into the program at the right place. +Such extra work is a bit of a nuisance, but it can be done in \WEB\ without +spoiling the exposition. + +\PASCAL\ has a few other misfeatures that prove to be inconvenient with +respect to \WEB\ exposition. The worst of these is the inability to +declare local variables 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 `\' 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. + +\beginsection L. ECONOMIC ISSUES + +What does it cost to use \WEB? Let's look first at the lowest level, where +computer costs are considered, because it is easy to make quantitative +statements at this level. The running time to {\tt TANGLE} a \WEB\ file is +approximately the same as the time needed to compile the resulting +\PASCAL\ program; hence the extra preprocessing does not cost much. +Similarly, {\tt 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 produce a 60-page document. The +running time for {\tt 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 information 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 debugging an +{\mc ALGOL} or {\mc PASCAL} program, even though my \WEB\ programs are +much better, and even though I am putting substantially more documentation +into the programs. 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 previously unwilling to impose on myself. I had known for a long +time that the programs I construct for publication 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 classroom 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 {\sl 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. + +\beginsection M. RELATED WORK + +Nothing about \WEB\ is really new; I have simply combined 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 algorithm is a substantial +contribution to knowledge. Its publication constitutes an important +piece of schol\-ar\-ship.''\ref\GEF{G. E. Forsythe, Algorithms for +scientific computation. {\sl Communications of the ACM\/ \bf9}, 255--256 +(1966).} His comments have always inspired me to strive for excellence +in programming, and they have played a major r\^^Dole in shaping my present +view that it is worthwhile to consider {\it every\/} program as a +work of literature. + +The design of \WEB\ was influenced primarily by the pioneering work +of Pierre-Arnoul de Marneffe,\ref\deM{P. A. de Marneffe, {\sl Holon +Programming}. Univ.~de Liege, Service D'Informatique (December, 1973).}$^,$% +\ref\deMR{P. A. de Marneffe and D. Ribbens, Holon Programming, in +A. G\"unther et al.\ (eds.), {\sl International Computing Symposium 1973\/}, +Amsterdam, North-Holland (1974).} 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;\ref\Koest{A. +Koestler, {\sl The Ghost in the Machine}. New York, Macmillan (1968).} +thus we have another connection between programming and literature. +A somewhat similar system was independently created by Edwin Towster.\ref\Tow% +{E. Towster, A convention for explicit declaration of environments +and top-down refinement of data. {\sl IEEE Transactions on Software +Engineering\/ \bf SE--5}, 374--386 (1979).} + +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. Hoare's suggestion was +actually rather terrifying to me, and I'm sure he knew that he was posing +quite a challenge. 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 systems, 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 attempts along these +lines\ref\CF{D. E. Knuth, Computer-drawn flow charts. {\sl +Communications of the ACM\/ \bf 6}, 555--563 (1963).} 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\ system itself provided me +with new tools for printing and format control, so I suspected that it +would be possible 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:\ref\Hoare{C. A. R. Hoare, {\sl Hints on +Programming Language Design}. Stanford Computer Science Report CS403 +(October 1973).} +\smallskip +{\narrower\noindent +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. +\smallskip} +\noindent He foresaw many future trends, but not the impending improvements in +typesetting quality: +\smallskip +{\narrower\noindent +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 unlikely that the +output of a computer will ever be more readable than its input, except +in such trivial but important aspects as improved indentation. +\smallskip} + +Typographic formatting of computer programs has a long tradition, originating +with {\mc ALGOL} and its immediate 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 {\mc ALGOL~60} report\ref\Alg{P. Naur +(ed.)~et al., Report on the algorithmic language ALGOL 60. +{\sl Communications of the ACM\/ \bf3}, 299--314.} and gave special +care to its presentation; and Myrtle Kellington, who served for many years +as executive editor of ACM publications 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 appreciated by people who submit computer programs to journals +like {\sl Acta Arithmetica\/} whose editors are unfamiliar with computer +science. Bill McKeeman called attention to formatting issues when he +published Algorithm~268, ``{\mc ALGOL~60} reference language editor,'' +in 1965.\ref\McK{W. M. McKeeman, Algorithm 268. {\sl Communications +of the ACM\/ \bf8}, 667--668 (1965).} There has been a flowering of +such algorithms in recent years; the papers by Oppen\ref\DO{D. Oppen, +Prettyprinting. {\sl ACM Transactions on Programming Languages and +Systems\/ \bf2}, 465--483 (1980).} and by Rose and Welsh\ref\RW{G. A. +Rose and J. Welsh, Formatted programming languages. {\sl Software---% +Practice \char'46\ Experience\/ \bf11}, 651--669 (1981).} are particularly +noteworthy. + +I began to design \WEB\ in the spring of 1979, when I constructed a prototype +system that was called {\tt DOC}. Luis Trabb~Pardo helped me to develop +a suitable style of exposition at that time; then Ignacio Zabala~Salelles +gave a {\tt DOC} a thorough test when he prepared a full implementation +of \TeX\ in \PASCAL. Zabala's implementation was successfully transported +to many different computers,\ref\Z{I. Zabala and L. Trabb Pardo, +The status of the PASCAL implementation of \TeX. {\sl TUGboat\/ \bf1}, +16--17 (1980).}\silentref\ZZ{I. Zabala, \TeX-PASCAL and PASCAL compilers. +{\sl TUGboat\/ \bf2} (1), 11--12 (1981).}\silentref\ZZZ{I. Zabala, +Some feedback from PTEX installations. {\sl TUGboat\/ \bf2} (2), 16--19 +(1981).}$^-$\ref\ZZZZ{I. A. Zabala, How +portable is PASCAL? Draft of paper in preparation (1982).} +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 impossible 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 {\tt TANGLE.WEB} and {\tt WEAVE.WEB}, +during which time I was continually changing the language and +trying different styles of exposition. (The programs were neither +long nor complicated, 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 {\tt TEX.WEB}.) Then I spent about six tedious hours with +a text editor, hand-simulating the behavior of {\tt TANGLE} on +{\tt TANGLE.WEB}, so that I had a program {\tt TANGLE.PAS} that +was ripe for debugging. At first I had to correct errors both in +{\tt TANGLE.WEB} and {\tt TANGLE.PAS}, but soon {\tt TANGLE} was +working well enough that I needed only {\tt TANGLE.WEB} as a +source file. Then {\tt WEAVE.WEB} could be tangled and debugged +too. The total time to create ``Version~0'' of the \WEB\ system, +including 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 {\tt WEB}-like system can be created +from scratch in a fairly short time, for some other pair of +languages besides \TeX\ and \PASCAL, by an expert system +programmer 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 hypothesis; shortly afterwards I +received an elegant report from Harold Thimbleby, who had just constructed +an excellent system called {\tt Cweb}, based on Troff/Nroff and {\mc +C} instead of \TeX\ and \PASCAL.\ref\Thim{H. Thimbleby, {\sl Cweb}. +Preprint, University of York (August 1983).} + +\beginsection 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 +experiences 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 port\-able and more easily understood and +maintained; furthermore, the system seems to work with large programs as +well as with small ones. I'm pleased that my work on typography, which +began as an application 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 +number 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 offer 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 simultaneously. 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 scientists. 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 excuse 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 natural 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 correct {\mc ALGOL 68} +program\ref\ft{C. H. Lindsey, ALGOL 68 with fewer tears. {\sl The +Computer Journal\/ \bf15}, 176--188 (1972).} 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 programming, there will be many ways to incorporate the \WEB\ +philosophy into a really effective programming environment. 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 syntactic debugging can be done +entirely in terms of the \WEB\ source language. Furthermore, a \WEB-like +system could be designed to incorporate additional modularization, +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 selected 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. + +\bigskip\leftline{\bf Acknowledgements} +\smallskip +{\eightrm\baselineskip9pt +\noindent The preparation of this paper was supported in part by +the National Science Foundation under grants IST-8201926 and MCS-8300984, +and by the System Development Foundation. `\TeX' is a trademark of the +American Mathematical Society.\par} + +\enddoublecolumns % prepare for the references +\bigskip\bigskip +\hbox to\pagewidth{\hss\bf REFERENCES\hss\strut} +\CJrule width\pagewidth +\bigskip +\begindoublecolumns +\let\rm=\eightss \let\sl=\eightssi \let\bf=\eightssb \rm +\baselineskip=9pt +\tolerance=1000 +\references +\bigskip +\noindent +Received September 1983 +\enddoublecolumns +\kern6mm +\CJrule width\pagewidth +\bye diff --git a/web/literateprog/web.tex_z b/web/literateprog/web.tex_z new file mode 100644 index 0000000000..0bc281760a Binary files /dev/null and b/web/literateprog/web.tex_z differ -- cgit v1.2.3