home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 2 / FFMCD02.bin / new / dev / misc / cweb / examples / primes.w < prev    next >
Text File  |  1993-12-21  |  22KB  |  486 lines
  1. % PRIMES example of WEB/CWEB portability.  This documentation was
  2. % originally published in the article ``Literate Programming'' by Donald
  3. % E. Knuth in ``The Computer Journal'', May 1984, and later in the book
  4. % ``Literate Programming'', October 1991, where it appeared as the first
  5. % example of WEB programming for Pascal.  It has been translated into
  6. % CWEB by Andreas Scherer to show the ease of portability between
  7. % Pascal/WEB and C/CWEB.  As little changes as possible were made, so that
  8. % the section numbering of the Pascal and the C version are identical,
  9. % except that a small list of related literature was appended at the end.
  10. % Minor changes to include extra C functionality are mentioned in the text
  11. % that follows.  The `cite' feature of CWEB 2.8 is used.
  12.  
  13. % This program is distributed WITHOUT ANY WARRANTY, express or implied.
  14. % WEB Version --- Don Knuth, 1986
  15. % CWEB Version --- Andreas Scherer, 1993
  16.  
  17. % Copyright (c) 1993 Andreas Scherer
  18.  
  19. % Permission is granted to make and distribute verbatim copies of this
  20. % document provided that the copyright notice and this permission notice
  21. % are preserved on all copies.
  22.  
  23. % Permission is granted to copy and distribute modified versions of this
  24. % document under the conditions for verbatim copying, provided that the
  25. % entire resulting derived work is distributed under the terms of a
  26. % permission notice identical to this one.
  27.  
  28. \font\csc=cmcsc10
  29. \def\CWEB{{\tt CWEB}}
  30. \def\Pascal{{\csc Pascal}}
  31. \def\[{\ifhmode\ \fi$[\mkern-2mu[$}
  32. \def\]{$]\mkern-2mu]$\ }
  33. \def\Section{\mathhexbox278}
  34. \hyphenation{Dijk-stra}
  35.  
  36. \def\title{PRIMES (C Version 1.1)}
  37. \def\topofcontents{\null\vfill
  38.   \centerline{\titlefont Printing prime numbers}
  39.   \vskip15pt
  40.   \centerline{(C Version 1.1)}
  41.   \vfill}
  42. \def\botofcontents{\vfill
  43.   \noindent Copyright \copyright\ 1993 Andreas Scherer
  44.   \bigskip
  45.   \noindent Permission is granted to make and distribute verbatim copies of
  46.   this document provided that the copyright notice and this permission
  47.   notice are preserved on all copies.
  48.   \smallskip
  49.   \noindent Permission is granted to copy and distribute modified versions
  50.   of this document under the conditions for verbatim copying, provided that
  51.   the entire resulting derived work is distributed under the terms of a
  52.   permission notice identical to this one.}
  53.  
  54. @* Printing primes: An example of \CWEB\null. The following program is
  55. essentially the same as Edsger Dijkstra's@^Dijkstra, Edsger@> ``first
  56. example of step-wise program composition,'' found on pages 26--39 of his
  57. {\sl Notes on Structured Programming\/} [1], as presented by Donald E.
  58. Knuth@^Knuth, Donald E.@> on pages 103--112 of his {\sl Literate
  59. Programming\/} [2], but it has been translated into the \CWEB\ language by
  60. Andreas Scherer@^Scherer, Andreas@>.
  61. @.CWEB@>@.WEB@>
  62.  
  63. \[Double brackets will be used in what follows to enclose comments relating
  64. to \CWEB\ itself, because the chief purpose of this program is to introduce
  65. the reader to the \CWEB\ style of documentation. \CWEB\ programs are always
  66. broken into small sections, each of which has a serial number; the present
  67. section is number 1.\]
  68.  
  69. Dijkstra's program prints a table of the first thousand prime numbers. We
  70. shall begin as he did, by reducing the entire program to its top-level
  71. description. \[Every section in a \CWEB\ program begins with optional {\it
  72. commentary\/} about that section, and ends with optional {\it program
  73. text\/} for the section. For example, you are now reading part of the
  74. commentary in \Section1, and the program text for \Section1 immediately
  75. follows the present paragraph. Program texts are specifications of \Cee\ 
  76. programs; they either use \Cee\ language directly, or they use angle brackets
  77. to represent \Cee\ code that appears in other sections. For example, the
  78. angle-bracket notation `|@<Program to print...@>|' is \CWEB's way of saying
  79. the following: ``The \Cee\ text to be inserted here is called `Program to
  80. print $\ldots$ numbers', and you can find out all about it by looking at
  81. section 2.'' One of the main characteristics of \CWEB\ is that different
  82. parts of the program are usually abbreviated, by giving them such an
  83. informal top-level description.\]
  84.  
  85. @c
  86. @<Program to print the first thousand prime numbers@>
  87.  
  88. @ This program has no input, because we want to keep it rather simple. The
  89. result of the program will be to produce a list of the first thousand prime
  90. numbers, and this list will appear on the |stdout| file.
  91.  
  92. Since there is no input, we declare the value |MM==1000| as a compile-time
  93. constant. The program itself is capable of generating the first |MM| prime
  94. numbers for any positive |MM|, as long as the computer's finite limitations
  95. are not exceeded. The boolean values |TRUE| and |FALSE| are defined.
  96.  
  97. \[The program text below specifies the ``expanded meaning'' of `|@<Program
  98. to print...@>|'; notice that it involves the top-level descriptions of two
  99. other sections. When those top-level descriptions are replaced by their
  100. expanded meanings, a syntactically correct \Cee\ program will be obtained.\]
  101.  
  102. @d MM    1000
  103. @d TRUE     1
  104. @d FALSE    0
  105.  
  106. @<Program to print...@>=
  107. #include <stdio.h>
  108.  
  109. void main(void)
  110.    {
  111.    @<Variables of the program@>@;@#
  112.  
  113.    @<Print the first |MM| prime numbers@>@;
  114.    }
  115.  
  116. @* Plan of the program. We shall proceed to fill out the rest of the
  117. program by making whatever decisions seem easiest at each step; the idea
  118. will be to strive for simplicity first and efficiency later, in order to
  119. see where this leads us. The final program may not be optimum, but we want
  120. it to be reliable, well motivated, and reasonably fast.
  121.  
  122. Let us decide at this point to maintain a table that includes all of the
  123. prime numbers that will be generated, and to separate the generation
  124. problem from the printing problem.
  125.  
  126. \[The \CWEB\ description you are reading once again follows a pattern that
  127. will soon be familiar: A typical section begins with comments and ends with
  128. program text. The comments motivate and explain noteworthy features of the
  129. program text.\]
  130.  
  131. @<Print the first...@>=
  132.    @<Fill table |p| with the first |MM| prime numbers@>@;
  133.    @<Print table |p|                                 @>@;
  134.  
  135. @ How should table |p| be represented? Two possibilities suggest
  136. themselves: We could construct a sufficiently large array of boolean values
  137. in which the |k|th entry is |TRUE| if and only if the number |k| is prime;
  138. or we could build an array of integers in which the |k|th entry is the
  139. |k|th prime number. Let us choose the latter alternative, by introducing an
  140. integer array called |p[MM]|.
  141.  
  142. In the documentation below, the notation `|p[k]|' will refer to the |k|th
  143. element of array |p|, while `$p_k$' will refer to the |k|th prime number.
  144. If the program is correct, |p[k-1]| will either be equal to $p_k$ or it
  145. will not yet have been assigned any value. (Note that arrays in \Cee\ are
  146. indexed starting from 0 and not from 1 as in \Pascal)
  147. @^Differences between \Pascal\ and \Cee@>
  148.  
  149. \[Incidentally, our program will eventually make use of several more
  150. variables as we refine the data structures. All of the sections where
  151. variables are declared will be called `|@<Variables of...@>|'; the
  152. number `4' in this name refers to the present section, which is the first
  153. section to specify the expanded meaning of `|@<Variables of...@>|'.
  154. The note `{\eightrm See also~$\ldots$}' refers to all of the other sections
  155. that have the same top-level description. The expanded meaning of
  156. `|@<Variables of...@>|' consists of all the program texts for this name,
  157. not just the text found in \Section4.\]
  158.  
  159. @<Variables of the program@>=
  160.    int p[MM]; /* the first |MM| prime numbers, in increasing order */
  161.  
  162. @* The output phase. Let's work on the second part of the program first.
  163. It's not as interesting as the problem of computing prime numbers; but the
  164. job of printing must be done sooner or later, and we might as well do it
  165. sooner, since it will be good to have it done. \[And it is easier to learn
  166. \CWEB\ when reading a program that has comparatively few distracting
  167. complications.\]
  168.  
  169. Since |p| is simply an array of integers, there is little difficulty in
  170. printing the output, except that we need to decide upon a suitable output
  171. format. Let us print the table on separat