summaryrefslogtreecommitdiff
path: root/web/funnelAC/hackman/h_ch2.tex
diff options
context:
space:
mode:
Diffstat (limited to 'web/funnelAC/hackman/h_ch2.tex')
-rw-r--r--web/funnelAC/hackman/h_ch2.tex443
1 files changed, 443 insertions, 0 deletions
diff --git a/web/funnelAC/hackman/h_ch2.tex b/web/funnelAC/hackman/h_ch2.tex
new file mode 100644
index 0000000000..89cdf6fc86
--- /dev/null
+++ b/web/funnelAC/hackman/h_ch2.tex
@@ -0,0 +1,443 @@
+%==============================================================================%
+% Start of Ch2.tex %
+%==============================================================================%
+%
+% Copyright
+% ---------
+% Copyright (C) 1992 Ross N. Williams.
+% This file contains a chapter of the FunnelWeb Hacker's Manual.
+% See the main TeX file for this manual for further information.
+%
+%==============================================================================%
+
+\chapter{FunnelWeb Implementation}
+\label{chapimplementation}\xx{FunnelWeb}{implementation}
+
+\section{Introduction}
+
+This chapter contains notes on the actual C code that implements
+FunnelWeb~V3. This chapter is rather patchy. It has acted mainly as
+a dumping ground for ideas that I bothered to write about during
+development.
+
+\section{History of FunnelWeb Implementations}
+\xx{FunnelWeb}{history}\x{FunnelWeb version 1}\x{FunnelWeb version 2}%
+\x{FunnelWeb version 3}
+
+The first implementation of FunnelWeb (FunnelWeb~V1) was written in
+Ada\x{Ada}
+in December 1986. The project was initially canned as requiring too
+much time, but was resurrected when I decided to commit to
+Ada\paper{USDOD83} and
+realized that I needed a program to write to help me to learn Ada.
+FunnelWeb~V1 was, in fact, my first Ada program. It took about one
+month to write.
+
+FunnelWeb~V1 was used intensively by myself to write Ada programs
+from January~1986 to July~1989 at which time
+I finished my Ph.D.\x{Ph.D.} and lost access to
+the VAX. During this time at least twenty thousand lines of code were generated
+using FunnelWeb. Hardly anyone but myself used
+FunnelWeb.\xx{FunnelWeb}{past use}
+
+After losing access to Ada and the Vax (and hence to FunnelWeb), I was forced
+back to programming the non-literate way. From time to time I found that I
+needed to use some of my old programs that I had written using Ada and
+FunnelWeb. I knew that Ada would become available on more machines, but
+certainly FunnelWeb wouldn't. I recognised a strong need for a portable
+version of FunnelWeb written in~C but didn't have the time or energy
+to create one.
+
+About this time (late 1989), David Hulse,\xn{David}{Hulse}
+at the time a student in
+Computer Science at the University of Adelaide,\xx{University}{Adelaide}
+volunteered to translate the 4000 line Ada version of FunnelWeb into~C.
+To my knowledge this translation process took about three weeks
+(in December 1989). The result was called FunnelWeb~V2 and was
+formally signed into the public domain on 5~May 1992.
+
+In general, David Hulse did a good job. However, the resultant code
+suffered from one or few serious defects, the most serious of which was
+a lack of portability.
+
+Lack of portability of the C~code, combined with the need for a rather
+solid design review, combined with the need to
+strengthen the program to bring it up to production standard, resulted
+in my performing a complete reworking of the code. The C code was
+entirely, but incrementally, replaced or reformatted.
+The code was also strengthened and new features were added.
+This process took about two months (November and December 1991).
+A further two months (approx) were spent writing documentation, constructing
+a regression test suite, porting the program to different machines,
+and sorting out the legal issues involved in its release.
+
+I would like to take this opportunity to record a debt of gratitude to
+David Hulse who translated FunnelWeb from Ada to~C. Although my
+reworking of his C~code obliterated most of his code,
+his translation was pivotal to the development process.
+Without his effort in moving from Ada to~C, I'm not sure that I
+would have mustered the energy and time to complete the process and
+bring FunnelWeb up to its current standard.
+
+\section{Why FunnelWeb Wasn't Used to Write Itself}
+\xx{FunnelWeb}{writing itself}
+
+After Knuth created the Web literate preprocessing system, he
+re-wrote it using Web and distributed the source code in Web source form.
+To allow the Web source code to be tangled by users not yet having a
+copy of Web, he also included the tangled Pascal code for the Tangler.
+
+While this approach is heroic and serves to convey a commitment and
+a confidence in literate programming, it seemed to me that writing FunnelWeb
+in FunnelWeb would simply be asking for trouble.\xx{trouble}{asking for}
+For a start, it would be
+very hard to modify any feature of FunnelWeb that had been used to write
+FunnelWeb, and the thought of what would happen if the working executable
+became inoperative for some reason does not bear thinking upon.
+
+One million billion computer programs were written in the non-literate
+style before FunnelWeb was created. Why not one more?
+
+\section{Coding Style}
+\xx{coding}{style}
+
+Although FunnelWeb wasn't coded under any particular coding standard,
+it was coded in accordance with a fairly strict personal style of C
+which developed during the development of FunnelWeb. This style was
+subsequently embodied in a real C coding standard prepared for the
+South\x{South Australian Government Department of Lands}
+Australian Government
+Department of Lands.\footnote{The standard
+is currently unavailable, but is likely to be released or
+published eventually.} Unfortunately, FunnelWeb was not
+formally developed under the standard and so some holes remain in
+FunnelWeb's coding style. This section aims to describe some of the more
+important aspects of the coding style.
+
+\thing{Portability:} This\x{portability}
+was a major goal of the FunnelWeb implementation.
+Two excellent books guided this move to portability.
+They were \paper{Rabinowitz90} (which deals with C code itself)
+and \paper{Horton90} (which deals with the portability of various library
+calls). Other works such as \paper{Kernighan88} and
+\paper{ANSI} were also helpful.
+
+\thing{Identifiers:} \paper{Rabinowitz90}\x{identifier}{length}
+specifies that for
+wide portability, identifiers of block and file scope should be unique to
+eight characters, and identifiers of program scope should be unique to
+six characters. I have gone further in FunnelWeb and actually made these
+restrictions actual limits on identifier length.
+
+Because names must be so short, a system of abbreviations was developed to
+organize the identifiers used within FunnelWeb. Each abbreviation consists
+of a letter pair. Here are \i{some} of the abbreviations
+used:\xx{identifier}{abbreviations}
+
+\begin{verbatim}
+bp - Body Part.
+cm - Compare. Used to prefix comparison routines that return [-1,0,1].
+dc - Document component.
+dm - Dump package.
+el - Element.
+eq - Equal. Used to prefix comparison routines that return a boolean.
+ex - Expression.
+f - Global files.
+ll - List of lists.
+ln - Line record.
+ls - List Package.
+lr - Lister package.
+ma - Macro.
+mc - Macro Call.
+mn - Macro Name.
+op - Options package.
+pr - Parser.
+ps - Position record.
+sc - Scrap record.
+sn - Section.
+tb - Table package.
+ty - Typesetter directive.
+wf - Write file package.
+wl - Write with EOL (misc.c).
+wr - Write (misc.c).
+\end{verbatim}
+
+\thing{Pointers:} Variables or types denoting
+pointers\xx{pointers}{naming} start with \dqp{p\_}.
+
+\thing{Types:} Names denoting types end in \dqp{\_t}.
+Thus, a type for a pointer to a table would be named
+\p{p\_tb\_t}.\xx{types}{naming}
+
+\thing{File names:} All files\xx{filenames}{length}
+used in FunnelWeb have file names that are
+from one to eight characters long and file extensions that are from one to
+three characters long. This ensures that the files can be portably moved
+to all kinds of machines, even MSDOS!\x{MSDOS}
+
+\section{Use of Memory}
+\xx{use of}{memory}
+
+FunnelWeb is not a memory-stressed program. However, during its development,
+problems with the management of memory seemed to crop up again and again.
+This section documents some of these problems and the solutions adopted.
+
+There are three places where memory can be obtained: the heap, the stack,
+and from static variables. The following three sections deal with each
+of these areas.
+
+\section{The Heap}
+\xx{heap}{memory}
+
+One of the great frustrations of being a user is to find that a computer
+program is complaining about lack of memory when one knows full well that
+one has allocated at least ten times as much memory to the program as it
+would ever need to do its job. The reason for such error messages usually
+has to do with the programmer setting a fixed \dq{reasonable} limit to
+a particular data structure and then locking it up into an array whose
+bound is specified by a constant. While the use of arrays can increase the
+speed of a program, it also means that the user cannot increase the capacity
+of the program without obtaining the source code and recompiling it,
+which is usually a daunting option.
+
+The alternative is to use the heap for all data structures that can
+grow in proportion to the size of the user's input. This rule has been
+followed rigorously in FunnelWeb. This means that as memory spaces
+increase, users will be able to hand their version of FunnelWeb more
+memory without having to recompile it.
+
+\topicbreak
+
+Some problems arose early on the Macintosh\x{Macintosh}
+in the use of the heap. It seems
+that some of the allocations I was attempting to make were failing for some
+obscure reason, possibly my fault. Whatever it was, it went away when I
+replaced direct calls to \p{malloc}\x{malloc}
+with calls to a mini package I wrote
+(called \p{memory}) that allocated large chunks of memory and then doled out
+small pieces as required by the rest of the
+program.\xx{memory}{package}
+
+Having a package to manage all the memory allocation had two other benefits.
+
+First, only one check was required in the entire program to see if memory
+had run out (in the memory package), and if that failed, the program could
+be brought to a screaming halt. This organization was far preferable to
+having each piece of code that needed to allocate memory having to check
+to see if \p{malloc} had failed.
+
+Second, the decision to construct a mini-shell within FunnelWeb to
+support regression testing meant that FunnelWeb proper could be run
+many times in any given invocation of FunnelWeb. As a consequence it was
+necessary to make sure that there was no memory
+leakage\xx{memory}{leakage} between invocations
+of FunnelWeb proper. This was accomplished by reworking the memory package
+to operate a watermark system. The user of the package, when requesting
+memory, could request \dq{temporary} or \dq{permanent}. If permanent, the
+memory package forgot that it had allocated the memory. If temporary, the
+memory package places the allocated block on a list. There was then a
+function in the memory package that could be called to deallocate all the
+temporary memory. Thus, so long as all requests for memory within FunnelWeb
+proper were for temporary memory, and that memory was freed at the end of
+every run, one could be sure that there was no memory leakage.
+
+\section{The Stack}
+\xx{stack}{memory}\xx{stack}{size}
+
+For a while during the development of FunnelWeb a particularly nasty bug
+proved extremely hard to find. The symptom was that FunnelWeb would crash,
+sometimes at random, but more often upon entering a particular function.
+In the end about a day of specific debugging was required before the problem
+was tracked down to a stack problem. It turned out that somehow
+(either the fault of the Macintosh or the THINK~C language system), only
+6K was being allocated for stack space!!!!!!!
+
+This experience led me immediately to go through the entire program and
+eliminate (or remove to the heap) any automatic variable declarations that
+used more than one hundred or so bytes.
+
+The lesson is clearly that C~programs that use more than a few thousand bytes of
+stack space are risking their portability. All large data structures should be
+placed in the heap.
+
+\section{Static Variables}
+\xx{memory}{static}\xx{static}{variables}
+
+Static variables also proved a problem on the Macintosh.
+It turns out that
+the Macintosh\x{Macintosh} THINK~C compiler\xx{ThinkC}{compiler}
+does not allow more than 32K of statics
+\i{in the entire program}. For a while this restriction was
+a serious threat to the program as it was discovered that constant strings
+were included in this total! However, some searching revealed a compiler
+option that removed the strings from the static category.
+
+Nevertheless, the 32K limit is rather severe. Again, it seems that for
+portability reasons, C~programs that use a lot of static variables are risking
+their portability. As a result, the FunnelWeb code avoids static variables
+where possible in favour of the heap.
+
+\section{Implementing Text Indentation}
+\xx{text}{indentation}
+
+At one point during the development of FunnelWeb, text indentation was
+fully implemented. However, it was subsequently removed because it was
+considered a dangerous feature. This section records the way in which
+text indentation was implemented so that if the feature ever has to be put
+back, this technique can be used again.
+
+
+1. Create a new field in the \p{sc\_t} record call \p{sc\_postn}.
+
+\begin{verbatim}
+ char *sc_postn; /* Pointer in the range [sc_first,sc_last+1]. */
+ /* It is the minimum possible value of sc_postn for */
+ /* which EOL does not appear in *sc_postn..*sc_last. */
+ /* i.e. Points to the byte following the first EOL in */
+ /* the scrap or sc_first if EOL does not appear. */
+\end{verbatim}
+
+2. Modify the scanner so that it generates this field.
+Sendtext should be modified so that
+it accepts an argument for the \p{p\_postn} value.
+
+\begin{verbatim}
+LOCAL void sendtext P_((p_ps_t,char *,char *,char *,bool));
+LOCAL void sendtext(p_tkps,p_first,p_last,p_postn,is_white)
+/* Appends a text token to the end of the token list. */
+/* IN: p_ps is a pointer to a position structure giving the position of the */
+/* first character of the token. */
+/* IN: p_first and p_last point to the first and last byte of the text scrap. */
+/* IN: p_postn has the same definition as sc_postn (see fwdata.h). */
+/* IN: is_white should be set to TRUE iff scrap is entirely whitespace. */
+p_ps_t p_tkps;
+char *p_first;
+char *p_last;
+char *p_postn;
+bool is_white;
+{
+ tk_t token;
+
+ /* Empty text scraps should never be generated. */
+ assert(p_first<=p_last,"sendtext: Text scrap bounds are bad.");
+
+ /* If ch=EOL then we should be scanning more text, not shipping it! */
+ assert(ch!=EOL,"senttext: Shipping text while still more to scan.");
+
+ /* Check that p_postn is in range. See definition in fwdata.h. */
+ assert(p_first<=p_postn && p_postn<=p_last+1,
+ "sendtext: p_postn is out of range.");
+
+ /* Debug: Check the p_postn field using a brute force check. */
+ {
+ char *i,*j;
+ j=p_first;
+ for (i=p_first;i<=p_last;i++)
+ if (*i==EOL)
+ j=i+1;
+ assert(j==p_postn,"sendtext: sc_postn field is incorrect.");
+ }
+
+ /* Load the text token. */
+ token.tk_kind = TK_TEXT;
+ ASSIGN(token.tk_ps,*p_tkps);
+ token.tk_sc.sc_first = p_first;
+ token.tk_sc.sc_last = p_last;
+ token.tk_sc.sc_postn = p_postn;
+ token.tk_white = is_white;
+ token.tk_parno = 0;
+ ls_add(token_list,PV &token);
+}
+\end{verbatim}
+
+Then all the calls to sendtext have to be changed:
+
+\begin{verbatim}
+/* @ instructs FunnelWeb to replace the special construct with the */
+/* special character. Luckily one appears just before the @ !! */
+/* Note: FALSE is OK because space is not a legal specialch. */
+/* Note: Setting parameter p_postn to p_ch-1 is OK as EOL is not a */
+/* legal specialch. */
+sendtext(&ps_spec,p_ch-1,p_ch-1,p_ch-1,FALSE);
+break;
+
+/* + instructs FunnelWeb to insert an EOL. We can't look to the end of */
+/* the previous line to find an EOL as this might be the first line. */
+/* Running ahead to the end of the line is expensive, and having the */
+/* liner mini-package maintain a variable for it would be extra */
+/* housekeeping. Instead of all this, we just point to a static. */
+{CONST static char stateol = EOL;
+ sendtext(&ps_spec,&stateol,&stateol,(&stateol)+1,TRUE);}
+break;
+
+/* If we hit something that ends a text token */
+/* then we can transmit a white text token. */
+if (ch==specialch || ch==EOFCH)
+ {sendtext(&ps_start,p_first,p_ch-1,MAX(p_sol,p_first),TRUE); return;}
+
+/* Otherwise we have some more (non-white) text to scan. */
+/* We can then send a non-white text token. */
+while (ch!=specialch && ch!=EOFCH)
+ NEXTCH;
+sendtext(&ps_start,p_first,p_ch-1,MAX(p_sol,p_first),FALSE);
+\end{verbatim}
+
+The dump code needs to be changed too!
+
+\begin{verbatim}
+ wf_str(p_wf,"\"");
+assert(token->tk_sc.sc_first !=NULL,"dm_tkls: NULL ptr1.");
+assert(token->tk_sc.sc_last !=NULL,"dm_tkls: NULL ptr2.");
+for (i=token->tk_sc.sc_first; i<=token->tk_sc.sc_last; i++)
+ {
+ if (i==token->tk_sc.sc_postn)
+ wf_str(p_wf,"<postn>");
+ if (*i=='\n')
+ wf_wl(p_wf,"");
+ else
+ dm_byte(p_wf,*((ubyte_ *) i));
+ }
+if (i==token->tk_sc.sc_postn)
+ wf_str(p_wf,"<postn>");
+wf_str(p_wf,"\"");
+}
+\end{verbatim}
+
+3. Over in the Tangle module, create a massive array of pointers to scraps
+to be used as a stack. Maintain pointers into the stack called \p{current} and
+\i{base} (similar to the blank indentation variables). Implement the following:
+
+\begin{itemize}
+
+\item To write out a scrap, scan it byte by byte. Output each byte. When
+you hit an EOL, pop the stack back to \p{base}. Then write out an EOL
+followed by the stack contents but writing each scrap only from \p{postn} to
+end end of each scrap.
+When you have finished the new scrap, push it on the stack.
+
+\item When you hit a new macro to expand, save \p{base}. Restore it later.
+
+\end{itemize}
+
+The \p{postn} field solves the big problem of
+how to cope with something like this:
+
+\begin{verbatim}
+The rain in Spain
+falls mainly @<on the plain@>
+\end{verbatim}
+
+The trouble is that we want to text indent the lines in
+\p{@<on the plain@>} with
+just \dqp{falls mainly~}. However, this string is only part of a scrap. The
+solution is to get the scanner to record, in the \p{postn} field of each scrap,
+the position of the first byte with a EOL-free run to the end of the scrap.
+
+This scheme is very efficient because all we are doing is pushing and popping
+pointers to scraps on a stack array. The main disadvantage is that the
+array must necessarily be finite and would impose a limit on the depth
+of indentation nesting (not a big problem).
+
+%==============================================================================%
+% Start of Ch2.tex %
+%==============================================================================%