home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 2 / FFMCD02.bin / new / dev / misc / cweb / examples / commonwords.w next >
Text File  |  1993-12-21  |  28KB  |  730 lines
  1. % COMMONWORDS example of WEB/CWEB portability.  This documentation was
  2. % originally published in the ``Communications of the ACM'', Volume 29,6
  3. % (June 1986), and later in the book ``Literate Programming'', October 1991,
  4. % where it appeared as an example of WEB programming for Pascal by Donald
  5. % E. Knuth.  It has been translated into CWEB by Andreas Scherer to show
  6. % the ease of portability between Pascal/WEB and C/CWEB.  As little changes
  7. % as possible were made, so that the module numbering of the Pascal and
  8. % the C versions are virtually identical.  Restrictions of Pascal mentioned
  9. % in the WEB source were removed and the features of C were used instead.
  10.  
  11. % This program is distributed WITHOUT ANY WARRANTY, express or implied.
  12. % WEB Version --- Don Knuth, 1984
  13. % CWEB Version --- Andreas Scherer, 1993
  14.  
  15. % Copyright (c) 1993 Andreas Scherer
  16.  
  17. % Permission is granted to make and distribute verbatim copies of this
  18. % document provided that the copyright notice and this permission notice
  19. % are preserved on all copies.
  20.  
  21. % Permission is granted to copy and distribute modified versions of this
  22. % document under the conditions for verbatim copying, provided that the
  23. % entire resulting derived work is distributed under the terms of a
  24. % permission notice identical to this one.
  25.  
  26. \font\csc=cmcsc10
  27. \def\CWeb{{\tt CWEB}}
  28. \def\WEB{{\tt WEB}}
  29. \def\Pascal{{\csc Pascal}}
  30.  
  31. \def\title{COMMONWORDS (C Version 1.1)}
  32. \def\topofcontents{\null\vfill
  33.   \centerline{\titlefont Counting common word frequencies}
  34.   \vskip15pt
  35.   \centerline{(C Version 1.1)}
  36.   \vfill}
  37. \def\botofcontents{\vfill
  38.   \noindent Copyright \copyright\ 1993 Andreas Scherer
  39.   \bigskip
  40.   \noindent Permission is granted to make and distribute verbatim copies of
  41.   this document provided that the copyright notice and this permission
  42.   notice are preserved on all copies.
  43.   \smallskip
  44.   \noindent Permission is granted to copy and distribute modified versions
  45.   of this document under the conditions for verbatim copying, provided that
  46.   the entire resulting derived work is distributed under the terms of a
  47.   permission notice identical to this one.}
  48.  
  49. @* Introduction.  The purpose of this program is to solve the following
  50. problem posed by Jon Bentley@^Bentley, Jon Louis@>:
  51.  
  52. {\narrower\noindent Given a text file and an integer $k$, print the $k$
  53. most common words in the file (and the number of their occurrences) in
  54. decreasing frequency.\par}
  55.  
  56. Jon intentionally left the problem somewhat vague, but he stated that ``a
  57. user should be able to find the one hundred most frequent words in a
  58. twenty-page technical paper (roughly a 50K byte file) without undue
  59. emotional trauma.''
  60.  
  61. Let us agree that a {\it word\/} is a sequence of one or more contiguous
  62. letters; {\tt "Bentley"} is a word, but {\tt "ain't"} isn't.  The sequence
  63. of letters should be maximal, in the sense that it cannot be lengthened
  64. without including a nonletter.  Uppercase letters are considered equivalent
  65. to their lowercase counterparts, so that the words {\tt "Bentley"} and {\tt
  66. "BENTLEY"} and {\tt "bentley"} are essentially identical.
  67.  
  68. The given problem still isn't well defined, for the file might contain more
  69. than $k$ words, all of the same frequency; or there might not even be as
  70. many as $k$ words.  Let's be more precise:  The most common words are to be
  71. printed in order of decreasing frequency, with words of equal frequency
  72. listed in alphabetic order.  Printing should stop after $k$ words have been
  73. output, if more than $k$ words are present.
  74.  
  75. @ The |stdin| file is assumed to contain the given text.  If it
  76. begins with a positive decimal number (preceded by optional blanks), that
  77. number will be the value of $k$; otherwise we shall assume that $k=100$.
  78. Answers will be sent to the |stdout| file.
  79.  
  80. @d default_k 100 /* use this value if $k$ isn't otherwise specified */
  81.  
  82. @ Besides solving the given problem, this program is supposed to be an
  83. example of the {\tt CWEB} system, for people who know some \Cee\ but who
  84. have never seen {\tt CWEB} before.  Here is an outline of the program to be
  85. constructed:
  86. @^Differences between \Pascal\ and \Cee@>
  87.  
  88. @d FALSE 0
  89. @d TRUE 1
  90.  
  91. @c
  92. #include <stdio.h>
  93. #include <stdlib.h>
  94.  
  95. typedef unsigned char boolean; /* for logical switches */
  96. @<Type declarations@>@/
  97. @<Global variables@>@/
  98. @<Procedures for initialization@>@/
  99. @<Procedures for input and output@>@/
  100. @<Procedures for data manipulation@>@/
  101. @<The main program@>@/
  102.  
  103. @ The main idea of the {\tt CWEB} approach is to let the program grow in
  104. natural stages, with its parts presented in roughly the order that they
  105. might have been written by a programmer who isn't especially clairvoyant.
  106.  
  107. For example, each global variable will be introduced when we first know
  108. that it is necessary or desirable; the {\tt CWEB} system will take care of
  109. collecting these declarations into the proper place.  We already know about
  110. one global variable, namely the number that Bentley called $k$.  Let us
  111. give it the more descriptive name |max_words_to_print|.
  112.  
  113. @<Global variables@>=
  114. unsigned int max_words_to_print; /* at most this many words will be printed */
  115.  
  116. @ As we introduce new global variables, we'll often want to give them
  117. certain starting values.  This will be done by the |initialize| procedure,
  118. whose body will consist of various pieces of code to be specified when we
  119. think of particular kinds of initialization.
  120.  
  121. @<Procedures for initialization@>=
  122. void initialize(void)
  123.    {
  124.    int i; /* all-purpose index for initializations */
  125.  
  126.    @<Set initial values@>@;
  127.    }
  128.  
  129. @ The {\tt CWEB} system, which may be thought of as a preprocessor for
  130. \Cee, includes a macro definition facility so that portable programs are
  131. easier to write.  For example, we have already defined `|default_k|' to be
  132. 100.  Here are two more examples of {\tt CWEB} macros; they allow us to
  133. write, e.g., `|incr(count[p])|' as a convenient abbreviation for the
  134. statement `|count[p]=count[p]+1|'.
  135.  
  136. @d incr(A) /* increment a variable */
  137.    ++A
  138. @d decr(A) /* decrement a variable */
  139.    --A
  140.  
  141. @ Originally this program was written in the \Pascal\ {\tt WEB} language.
  142. In difference to \Cee, \Pascal\ uses labels and |goto| statements when
  143. abrupting procedures.  This isn't necessary for \Cee\ programs; they
  144. already know the |return| command, so this program will be totally
  145. |goto|-free.
  146. @^Differences between \Pascal\ and \Cee@>
  147.  
  148. @* Strategic considerations.  What algorithms and data structures should be
  149. used for Bentley's problem?  Clearly we need to be able to recognize
  150. different occurrences of the same word, so some sort of internal dictionary
  151. is necessary.  There's no obvious way to decide that a particular word of
  152. the input cannot possibly be in the final set, until we've gotten very near
  153. the end of the file; so we might as well remember every word that appears.
  154.  
  155. There should be a frequency count associated with each word, and we will
  156. eventually want to run through the words in order of decreasing frequency.
  157. But there's no need to keep these counts in order as we read through the
  158. input, since the order matters only at the end.
  159.  
  160. Therefore it makes sense to structure our program as follows:
  161.  
  162. @<The main program@>=
  163. void main(void)
  164.    {
  165.    initialize();
  166.    @<Establish the value of |max_words_to_print|@>@;
  167.    @<Input the text, maintaining a dictionary with frequency counts@>@;
  168.    @<Sort the dictionary by frequency@>@;
  169.    @<Output the results@>@;
  170.    }
  171.  
  172. @* Basic input routines.  Let's switch to a bottom-up approach now, by
  173. writing some of the procedures that we know will be necessary sooner or
  174. later.  Then we'll have some confidence that our program is taking shape,
  175. even though we haven't decided yet how to handle the searching or the
  176. sorting.  It will be nice to get the messy details of \Cee\ input out of
  177. the way and off our minds.
  178.  
  179. Here's a function that reads an optional positive integer, returning zero
  180. if none is present at the beginning of the current line.
  181.  
  182. @<Procedures for input and output@>=
  183. int read_int(void)
  184.    {
  185.    int n=0; /* the accumulated value */
  186.    char c; /* the character from the input we're reading */
  187.  
  188.    if( (c=fgetc(stdin)) != EOF ) {
  189.       for(; (c=='\n') || (c==' ') || (c=='\t'); c=fgetc(stdin));
  190.       while(c>='0' && c<='9') {
  191.          n = 10*n +