cwebman.tex

著名算法大师高爷爷设计的语言。此语言结合了Tex和C

Section names must otherwise match character for character, except
that consecutive characters of white space (spaces, tab marks, newlines, and/or
form feeds) are treated as equivalent to a single space, and such spaces are
deleted at the beginning and end of the name. Thus, `\.{@< Clear { }the
arrays @>}' will also match the name in the previous example.
Spaces following the ellipsis in abbreviations are ignored as well, but
not those before, so that `\.{@<Clear t ...@>}' would not match
`\.{@<Clear the arrays@>}'.

\section What \.{CTANGLE} Does.
We have said that a section begins with `\.{@\ }' or `\.{@*}', but we
didn't say how it gets divided up into a \TEX/ part, a middle part,
and a \CEE/ part. The middle part begins with the first appearance of
`\.{@d}' or `\.{@f}' in the section, and the \CEE/ part begins with
the first appearance of `\.{@c}' or `\.{@<section name@>=}'.  In the
latter case you are saying, in effect, that the section name stands
for the \CEE/ text that follows. Alternatively, if the \CEE/ part
begins with `\.{@c}' instead of a section name, the current section is
said to be {\sl unnamed}.

The construct `\.{@<section name@>}' can appear
any number of times in the \CEE/ part of a section:
Subsequent appearances indicate that a named section is being
``used'' rather than ``defined.'' In other words, the
\CEE/ code for the named section, presumably defined elsewhere, should be
spliced in at this point in the \CEE/ program.  Indeed,
the main idea of \.{CTANGLE} is to make a \CEE/ program out of
individual sections, named and unnamed.  The exact way in which this is done
is this: First all the macro definitions
indicated by `\.{@d}' are turned into \CEE/ preprocessor macro definitions
and copied at the beginning.
Then the \CEE/ parts of unnamed sections are copied down,
in order; this constitutes the first-order
approximation to the text of the program. (There should be at least
one unnamed section, otherwise there will be no program.) Then all section
names that appear in the first-order approximation are replaced by the \CEE/
parts of the corresponding sections, and this substitution process
continues until no section names remain. All comments are removed, because
the \CEE/ program is intended only for the eyes of the \CEE/ compiler.

If the same name has been given to more than one section, the \CEE/ text
for that name is obtained by putting together all of the \CEE/ parts in
the corresponding sections. This feature is useful, for example, in a
section named `Global variables', since one can then
declare global variables in whatever sections those variables are
introduced. When several sections have the same name, \.{CWEAVE} assigns the
first section number as the number corresponding to that name, and it
inserts a note at the bottom of that section telling the reader to `See
also sections so-and-so'; this footnote gives the numbers of all the other
sections having the same name as the present one. The \CEE/ text
corresponding to a section is usually formatted by \.{CWEAVE} so that the
output has an equivalence sign in place of the equals sign in the \.{CWEB}
file; i.e., the output says `$\langle\,$section
name$\,\rangle\equiv\null$\CEE/ text'. However, in the case of the second
and subsequent appearances of a section with the same name, this `$\equiv$'
sign is replaced by `$\mathrel+\equiv$', as an indication that the
following \CEE/ text is being appended to the \CEE/ text of another section.

As \.{CTANGLE} enters and leaves sections, it inserts preprocessor
\.{\#line} commands into the \CEE/ output file.  This means that
when the compiler gives you error messages, or when you debug your program,
the messages refer to line numbers in the \.{CWEB} file, and not in the
\CEE/ file.  In most cases you can therefore
forget about the \CEE/ file altogether.

\section What \.{CWEAVE} Does.
The general idea of \.{CWEAVE} is to make a \.{.tex} file from the \.{CWEB}
file in the following way: The first line of the \.{.tex} file
tells \TEX/ to input a file with macros that
define \.{CWEB}'s documentation conventions. The next lines of the file
will be copied from whatever \TEX/ text is in limbo before the first
section.  Then comes the output for each section in turn, possibly
interspersed with end-of-page marks.  Finally, \.{CWEAVE} will generate a
cross-reference index that lists each section number in which each \CEE/
identifier appears, and it will also generate an alphabetized list
of the section names, as well as a table of contents that
shows the page and section numbers for each ``starred'' section.

What is a ``starred'' section, you ask? A section that begins with `\.{@*}'
instead of `\.{@\ }' is slightly special in that it denotes a new major
group of sections. The `\.{@*}' should be followed by the title of this
group, followed by a period. Such sections will always start on a new page
in the \TEX/ output, and the group title will appear as a running headline
on all subsequent pages until the next starred section. The title will also
appear in the table of contents, and in boldface type at the beginning of
its section. Caution:  Do not use \TEX/ control sequences in such titles,
unless you know that the \.{cwebmac} macros will do the right thing with
them. The reason is that these titles are converted to uppercase when
they appear as running heads, and they are converted to boldface when they
appear at the beginning of their sections, and they are also written out to
a table-of-contents file used for temporary storage while \TEX/ is
working; whatever control sequences you use must be meaningful in all
three of these modes.

The \TEX/ output produced by \.{CWEAVE} for each section consists of
the following: First comes the section number (e.g., `\.{\\M123.}'
at the beginning of section 123, except that `\.{\\N}' appears in place of
`\.{\\M}' at the beginning of a starred section). Then comes the
\TEX/ part of the section, copied almost verbatim except as noted
below. Then comes the middle part and the \CEE/ part, formatted
so that there will be a little extra space between them if both are
nonempty. The middle and \CEE/ parts are obtained by inserting
a bunch of funny-looking \TEX/ macros into the \CEE/ program; these
macros handle typographic details about fonts and proper math spacing,
as well as line breaks and indentation.

\section C Code in \TEX/ Text and Vice Versa.
When you are typing \TEX/ text, you will probably want to make frequent
reference to variables and other quantities in your \CEE/ code, and you
will want those variables to have the same typographic treatment
when they appear in your text as when they appear in your
program.  Therefore the \.{CWEB} language allows you to get the effect of
\CEE/ editing within \TEX/ text, if you place `\.|' marks before and
after the \CEE/ material. For example, suppose you want to say something
like this:
$$\hbox{ If \\{pa} is declared as `\&{int} ${}{*}\\{pa}$',
the assignment $\\{pa}\K{\AND}\|a[\T{0}]$ makes \\{pa}
point to the zeroth element of \|a.}$$
The \TEX/ text would look like this in your \.{CWEB} file:
$$\lpile{\.{If |pa| is declared as `|int *pa|', the}\cr
\.{assignment |pa=\&a[0]| makes |pa| point
to the zeroth element of |a|.}\cr}$$
And \.{CWEAVE} translates this into something you are glad you didn't have
to type:
$$\lpile{\.{If \\\\\{pa\} is declared as
  `\\\&\{int\} \$\{\}\{*\}\\\\\{pa\}\$',}\cr
\.{the assignment \$\\\\\{pa\}\\K\{\\AND\}\\|a[\\T\{0\}]\$}\cr
\.{makes \\\\\{pa\} point to the zeroth element of \\|a.}\cr}$$
Incidentally, the cross-reference index that \.{CWEAVE} would make, in
the presence of a comment like this, would include
the current section number as one of the index entries for \\{pa},
even though \\{pa} might not appear in the \CEE/ part of
this section. Thus, the index covers references to identifiers in
the explanatory comments as well as in the program itself; you will
soon learn to appreciate this feature. However, the identifiers
\&{int} and \|a\ would not be indexed,
because \.{CWEAVE} does not make index entries for reserved words or
single-letter identifiers. Such identifiers are felt to be so ubiquitous
that it would be pointless to mention every place where they occur.

Although a section begins with \TEX/ text and ends with \CEE/ text, we
have noted that the dividing line isn't sharp, since \CEE/ text can be
included in \TEX/ text if it is enclosed in `\pb'.  Conversely, \TEX/ text
appears frequently within \CEE/ text, because everything in
comments (i.e., between \.{/*} and \.{*/}, or following \.{//})
is treated as \TEX/ text.
Likewise, the text of a section name consists of \TEX/ text, but
the construct \.{@<section name@>} as a whole is expected to be found
in \CEE/ text; thus, one typically goes back and forth
between the \CEE/ and \TEX/ environments in a natural way, as in these
examples:
$$
\displaylines{
\hbox{\.{if} \.{(x==0)} \.{@<Empty} \.{the} \.{|buffer|} \.{array@>}} \cr
\hbox{\.{...} \.{using}  \.{the} \.{algorithm}
\.{in} \.{|@<Empty} \.{the} \.{|buffer|} \.{array@>|.}} }
$$
The first of these excerpts
would be found in the \CEE/ part of a section, into which the code
from the section
named ``Empty the \\{buffer} array'' is being spliced. The second excerpt
would be found in the \TEX/ part of the section, and the named section
is being ``cited'', rather than defined or used.
(Note the `\pb' surrounding the section name in this case.)

\section Macros.
The control code \.{@d} followed by
$$\\{identifier}\.{ }\hbox{\CEE/ text}\qquad\hbox{or by}\qquad
\\{identifier}\.(\\{par}_1,\ldots,\\{par}_n\.{) }\hbox{\CEE/ text}$$
(where there is no blank between the
\\{identifier} and the parentheses in the second case) is
transformed by \.{CTANGLE} into a preprocessor command, starting with
\.{\#define}, which is printed at the top of the \CEE/ output file
as explained earlier.

A `\.{@d}' macro definition can go on for several lines, and the
newlines don't have to be protected by backslashes, since \.{CTANGLE}
itself inserts the backslashes.   If
for any reason you need a \.{\#define} command at a specific spot in
your \CEE/ file, you can treat it as \CEE/ code, instead of as a
\.{CWEB} macro; but then you do have to protect newlines yourself.

\section Strings and constants.
If you want a string to appear in the \CEE/ file, delimited by pairs of
\.' or \." marks as usual, you can type it exactly so in the \.{CWEB} file,
except that the character `\.@' should be typed `\.{@@}' (it becomes a
control code, the only one that can appear in strings; see below).
Strings should end on the same line as they begin, unless there's a
backslash at the end of lines within them.

\TEX/ and \CEE/ have different ways to refer to octal and hex constants,
because \TEX/ is oriented to technical writing while \CEE/ is oriented to
computer processing.  In \TEX/ you
make a constant octal or hexadecimal by prepending \.' or \.",
respectively, to it; in \CEE/ the constant should be preceded by \.0
or \.{0x}.  In \.{CWEB} it seems reasonable to let each convention hold
in its respective realm; so in \CEE/ text you get $40_8$ by typing
`\.{040}', which \.{CTANGLE} faithfully copies into the \CEE/ file (for
the compiler's benefit) and which \.{CWEAVE} prints as $\T{\~40}$.
Similarly, \.{CWEAVE} prints the hexadecimal \CEE/ constant `\.{0x20}'
as \T{\^20}. The use of italic font for octal digits and typewriter font
for hexadecimal digits makes the meaning of such constants clearer in
a document. For consistency, then, you
should type `\.{|040|}'  or `\.{|0x20|}'
in the \TEX/ part of the section.

\section Control codes.
A \.{CWEB} {\sl control code\/}
is a two-character combination of which the first is `\.@'.
We've already seen the meaning of several control codes; it's time to
list them more methodically.

In the following list,
the letters in brackets after a control code indicate in what contexts that
code is allowed.  $L$ indicates that the code is allowed in limbo; $T$
(for \TEX/), $M$ (for middle), and $C$ (for \CEE/) mean that the code is
allowed in each of the three parts of a section, at top level---that
is, outside such constructs as `\pb' and section names.  An arrow $\to$
means that the control code terminates the present part of the \.{CWEB}
file, and inaugurates the part indicated by the letter following the
arrow.  Thus $[LTMC\to T]$ next to \.{@\ } indicates that this control
code can occur in limbo, or in any of the three parts of a section, and
that it starts the (possibly empty) \TEX/ part of the following section.

Two other abbreviations can occur in these brackets: The letter $r$ stands for
{\it restricted context}, that is, material inside \CEE/ comments, section
names, \CEE/ strings and control texts (defined below); the letter
$c$ stands for {\it inner \CEE/ context}, that is, \CEE/ material
inside `\pb' (including `\pb's inside comments, but not those
occurring in other restricted contexts).  An asterisk $*$ following
the brackets means
that the context from this control code to the matching \.{@>} is
restricted.

Control codes involving letters are case-insensitive; thus \.{@d} and
\.{@D} are equivalent. Only the lowercase versions are mentioned
specifically below.

\gdef\@#1[#2] {\penalty-50\yskip\hangindent 2em\noindent\.{@#1\unskip
  \spacefactor1000{ }}$[#2]$\quad}
\def\more{\hangindent 2em \hangafter0}
\def\subsec{\penalty-300\medskip\noindent}

\@@ [LTMCrc] A double \.@ denotes the single character `\.@'. This is
the only control code that is legal everywhere.
Note that you must use this convention if you are giving an internet
email address in a \.{CWEB} file (e.g., \.{levy@@math.berkeley.edu}).

\subsec
Here are the codes that introduce the \TEX/ part of a section.

\@\ [LTMC\to T] This denotes the beginning of a new (unstarred)
section. A tab mark or form feed or
end-of-line character is equivalent to a space when it follows an \.@
sign (and in most other cases).

\@* [LTMC\to T] This denotes the beginning of a new starred
section, i.e., a section that begins a new major group. The title of the new
group should appear after the \.{@*}, followed by a period. As explained
above, \TEX/ control sequences should be avoided in such titles unless
they are quite simple. When \.{CWEAVE} and \.{CTANGLE} read a \.{@*}, they
print an asterisk on the terminal
followed by the current section number, so that the user
can see some indication of progress. The very first section should be starred.

\more You can specify the ``depth'' of a starred section by typing \.* or a
decimal number after the \.{@*}; this indicates the relative ranking
of the current group of sections in the program hierarchy. Top-level
portions of the program, introduced by \.{@**}, get their names typeset
in boldface type in the table of contents; they are said to have
depth~$-1$. Otherwise the depth is a nonnegative number, which governs
the amount of indentation on the contents page. Such indentation helps
clarify the structure of a long program. The depth is assumed to be 0
if it is not specified explicitly; when your program is short, you