\documentstyle[11pt]{article} \title {Literate Programming on a Team Project\thanks{This research has been sponsored in part by the USAF, Rome Air Development Center, under contract number F30602--86--C--0071. The first author gratefully acknowledges the support of the Fannie and John Hertz Foundation. This paper is reprinted from {\em Software---Practice \& Experience}, 21(7):677--683, July 1991.}} \author{Norman Ramsey\thanks{Current address: Department of Computer Science, Princeton University, Princeton, New Jersey 08544.} \hskip3pt and Carla Marceau\\\mbox{}\\Odyssey Research Associates\\ 301A Harris B. Dates Drive\\Ithaca, New York 14850} \date{February 4, 1991} \setcounter{secnumdepth}{0} \setcounter{tocdepth}{6} \renewcommand{\baselinestretch}{1.33} \makeatletter \def\refno#1{\nocite{#1}\@ifundefined {b@#1}{{\bf ?}\@warning {Reference number `#1' on page \thepage \space undefined}}% {\hbox{\csname b@#1\endcsname}}} \makeatother \def\remark#1{\marginpar{\raggedright\hbadness=10000\footnotesize\it #1}} % \def\remark#1{\relax} \let\logo=\sc \font\logo=logo10 \def\metafont{{\logo METAFONT}} \begin{document} % 1 \clubpenalty=10000 \widowpenalty=10000 \maketitle \begin{abstract} % 2 % % We used {\tt WEB} on a group project to write a large program, over % % 33,000~lines. % % The program was not intended to be published. % % We encountered many problems using {\tt WEB}, but we believe we are % % better off for having used it. % % We describe both the problems and why we believe {\tt WEB} was % % beneficial despite them. % We used literate programming, with {\tt WEB}, on a group project to % write a program of % over 33,000~lines. % The program, Penelope, was not intended to be published, but the % literate source has served as good internal documentation through % development and maintenance. % Using {\tt WEB} without help from its developer uncovered a number of % problems, which are described below. % Despite the problems, {\tt WEB} has been effective in helping us % document the design and implementation of Penelope. We used literate programming on a team project to write a 33,000-line program for the Synthesizer Generator. The program, Penelope, was written using {\tt WEB}, a tool designed for writing literate programs. Unlike other {\tt WEB} programs, many of which have been written by {\tt WEB}'s developer or by individuals, Penelope was not intended to be published. We used {\tt WEB} in the hope that both our team and its final product would benefit from the advantages often attributed to literate programming. The {\tt WEB} source served as good internal documentation throughout development and maintenance, and it continues to document Penelope's design and implementation. Our experience also uncovered a number of problems with {\tt WEB}. \end{abstract} % 2 \section{Introduction} Donald Knuth coined the term ``literate programming'' when describing {\tt WEB}, the tool he used to build \TeX~\cite{knuth:literate}. He believes that ``the time is ripe for significantly better documentation of programs, and that we can best achieve this by considering programs to be {\em works of literature}.'' Knuth and others have presented examples of such programs~\cite{bentley:lp1,bentley:lp2,cvw:loom,gries:pearls}. Literate programming is usually discussed in the context of publishing programs or of publishing books or articles about programs. \TeX\ and {\metafont}, the original applications of {\tt WEB}, have been published as books~\cite{knuth:tex,knuth:metafont}. Other published literate programs seem to be primarily for teaching. Programs to find random sequences and count common words were written to illustrate the power of literate programming~\cite{bentley:lp1,bentley:lp2}. Another program to count common words is a tutorial on how to develop and tune a small program~\cite{cvw:loom}. Another illustrates formal methods of program development and the use of abstract data types~\cite{gries:pearls}. A valedictory assessment points out three common aspects of the published literate programs: cosmetics, polish, and verisimilitude, of which verisimilitude---the property of using one input to produce both compilable program and published document--is deemed essential~\cite{cvw:assessment}. Additional expectations of a literate programming tool include flexible order of elaboration, ability to develop program and documentation concurrently in one place, cross-references, and indexing~\cite{thimbleby:review}. {\tt WEB} is the principal tool used for literate programming; a number of implementations are available~\cite{knuth:literate,thimbleby:cweb,guntermann:cweb,levy:cweb,sewell:mangle,ramsey:building}. {\tt WEB} programmers interleave source code and descriptive text in a single document. When using {\tt WEB}, a programmer divides the source code into small textual units called {\em modules}, and each module carries associated documentation. In the {\tt WEB} source, different modules may be written in any order. The programmer is encouraged to choose an order that helps explain the program. The modules are like macro definitions; they have the form \begin{quote} % 2 \tt@<{\em module name\/}@>={\em body} \end{quote} % 2 where the body contains both code and references to other modules. {\tt WEB} programmers can also define and use macros similar to C~preprocessor macros. One module is unnamed; its body represents the underlying program. Two filters process {\tt WEB} source. {\tt TANGLE} reads the {\tt WEB} source and expands the unnamed module according to its definition. References to named modules are expanded where they occur, and the end result is that {\tt TANGLE} extracts the underlying program from the {\tt WEB} source. This program is formed from the code fragments that the programmer put into the module definitions, assembled in the order required by the compiler. A second filter, {\tt WEAVE}, reads the {\tt WEB} source and converts it to \TeX\ input, with which {\TeX} can produce high-quality typeset documentation of the program. Examples of {\tt WEB} source and typeset documentation can be found in Reference~\refno{knuth:literate}. \section{Using Literate Programming} Penelope is a language-based editor intended to help programmers develop formally verified Ada programs~\cite{ramsey:developing,marceau:interactive,guaspari:formal}. It parses annotated Ada programs, performs static semantic checking and overload resolution, computes weakest preconditions by predicate transformation, simplifies the resulting preconditions, and helps users construct proofs of those preconditions. Its source code is an editor specification for the Synthesizer Generator~\cite{reps:synthesizer:89}. The Synthesizer Generator builds an editor of attributed syntax trees. When a user defines a tree, the editor attributes it. When the user changes the tree, the editor recomputes only those attribute values that have changed~\cite{reps:generating}. Penelope has two written specifications: the Ada language reference manual and a denotational-style definition of Ada predicate transformers~\cite{adalrm,polak:predicate}. After three years of work, the {\tt WEB} source for the editor is over 33,000 lines. Over 13,000 of those lines are interleaved documentation. The editor has been used to verify a software repeater for an asynchronous communication line and security properties of a part of the ASOS operating system kernel~\cite{marceau:verified,weber:beyond,anderson:asos}. Seven programmers have written {\tt WEB} source, but no more than four have worked on it at any one time. At this writing, the editor is being extended to support Ada libraries. % programs that use data abstraction. We decided to write the editor as a literate program because we expected implementing predicate transformation to be error-prone. To avoid errors, we used {\tt WEB} to juxtapose the specification and implementation of each predicate transformer. We used {\TeX}'s math mode to write the specifications in the notation of denotational semantics.~\cite{polak:predicate,polak:program}. The right model for a literate program that is being maintained and extended is not the novel but the car repair manual. We began writing new code as an explanation or tutorial for our colleagues, but as the text grew we treated it more like a reference work. As with any document, we revised repeatedly to clarify meaning. We often used {\tt TANGLE}'s reordering mechanism to make major revisions in the {\tt WEB} source without changing the underlying program. % Parnas and Clements say this; see {parnas:rational} We divided Penelope into parts according to functionality: we wrote chapters on abstract syntax, concrete syntax, predicate transformation, static semantic checking, proof construction, and simplification of terms. Each of the first four chapters follows the structure of the Ada Language Reference Manual, since each is closely related to Ada. Only knowledge of the Ada manual is required to navigate this code; a reader who knows where to find the {\tt exit} statement in the Ada manual can find the predicate transformation of the {\tt exit} statement in the corresponding section of the predicate transformation chapter. We gave the final chapters structures related to the problems of simplification and proof construction. Penelope has grown so large that each chapter is itself structured like a reference work. Sections within chapters have a different structure. They are tutorials that use the traditional approach to documentation: begin with a problem statement or specification, discuss possible solutions, explain the design of the preferred solution, then develop the implementation and its description. A short introductory chapter describes the major parts of the program the organization used to form the text. A ``how to find it'' section helps readers find source code. We have used the Penelope source not only for reference but also to introduce new programmers to the project. % ??? % For example, as a prelude to extending the % Ada subset handled by Penelope, a new project member might read Chapter % 6 of the Red Dragon Book and also the chapter of Penelope on static % semantic checking. We used some of the cosmetic features of {\tt WEB}; we found tables of variables, functions, and files all useful to describe the organization of the code. When working on Ada static semantic checking, we found it useful to include in the {\tt WEB} source some fragments of relevant documents. The fragments included visibility and overloading rules from the Ada reference manual~\cite{adalrm} and a presentation of the Ada type system derived from Reference~\refno{ganzinger:operator}. \section{Evaluating {\tt WEB}} Using {\tt WEB} without help from its developer uncovered a number of problems. Some problems relate to the criteria in References \refno{cvw:assessment}~and~\refno{thimbleby:review}, but others do not. We had no trouble with {\tt WEB}'s fundamental mechanisms, the section and the named module. They provide verisimilitude and flexible order of elaboration. The small size of modules makes it feasible to develop code and documentation in one place using an ordinary text editor. The order of fragments is the same in the {\tt WEB} source and in the published document, which simplifies polishing. \medskip We found some of {\tt WEB}'s cosmetic features inadequate, others superfluous. Cosmetics should include appropriate media for presenting programs: not just math and tables but also diagrams and figures~\cite{bentley:more-pearls:graphics,bentley:lp2,sedgewick:algorithms}. Describing data structures was hampered by {\TeX}'s lack of support for diagrams and pictures. {\TeX} does make it easy to use mathematical notation, which helped considerably in describing predicate transformation, the simplifier, and the proof system used in the proof constructor. Programmers complained more about prettyprinting than about all other {\tt WEB} problems combined. {\tt WEAVE} ignores the programmer's choice of indentation and line breaks; it breaks and indents lines on the basis of the syntactic categories of tokens. (Programmers can force line breaks by inserting special control sequences like {\tt@/} into their program text, but that's about all.) We spent too much time tinkering with prettyprinting, trying to make {\tt WEAVE}'s output acceptable to everyone. We would have been better off with no prettyprinter, or with a prettyprinter that changed only the typographic treatment of program fragments without changing the placement of tokens on the page. We used the index of identifiers during reviews only, usually to find function definitions and to locate code that had been misplaced. \medskip {\tt WEB} formats interleaved documentation using {\TeX}, which some programmers already use for writing documents. {\tt WEB} and {\TeX} are integrated poorly. One cannot lift pieces of {\tt WEAVE}'s output and put them in other documents without adjusting the \TeX\ code. {\tt WEB} works even less well with \LaTeX; \LaTeX\ constructs cannot be used in {\tt WEB} source, and getting {\tt WEAVE} output to work in \LaTeX\ documents requires tedious adjustments by hand. The other direction is easier; we wrote project documents using \LaTeX, and, with some adjustments, we could include excerpts from these documents in our code. %%%%%%%% Carla wants no more details % \remark{I can give more details. For example, the {\tt webmac} macros % should make it easy to pull out the {\tt WEAVE} output routine and use % a plain \TeX\ or \LaTeX output routine---but they don't. % This is a sore point with me.} %%%%%%%%% We were accustomed to writing \LaTeX\ documents, so it was annoying to be forced to switch to plain \TeX\ to write programs. % \paragraph{Editing {\tt WEB} source} \medskip \TeX's input often looks very different from \TeX's output, especially when mathematics is used. Similarly, {\tt WEB} source looks very different from the typeset document produced by {\tt WEAVE} and {\TeX}. When people use \TeX\ to write papers, it may be acceptable for the \TeX\ input to be full of confusing hieroglyphics, because the {\TeX} input is almost never read---only the printed version is read. {\tt WEB} source is read frequently because programmers must edit it. Both the difficulty of reading the source and the marked difference between source and listing complicate editing. \medskip % \paragraph{Structuring the document} {\tt WEAVE}'s standard table of contents mechanism is a list of section names. (A section is a named group of modules together with their interleaved documentation.) This flat structure is inadequate for describing even a moderate-sized program. Extra structure in the form of ``parts'' has been added to the book version of {\TeX}; a part contains several sections~\cite{knuth:tex}. We changed {\tt WEAVE}'s table of contents mechanism to make hierarchical organization possible. The new mechanism supports chapters, sections, and two levels of subsections. We did so without changing {\tt WEAVE} itself; instead we changed the \TeX\ macros that support {\tt WEAVE}. The new macros recognize special symbols at the beginnings of section names; these symbols indicate which sections are really chapters, subsections, and so on. Using this hierarchy made the table of contents an important guide to the code; the only practical way to find a particular part of the editor code was to begin with the table of contents. The {\tt WEAVE} listing of Penelope is over 800~pages; its table of contents is about 8~pages. We needed to extract and print parts of this document, but {\tt WEAVE} processes only complete documents. We extracted parts in two ways. When we wanted just a few, small, closely related parts, we created a special {\tt WEB} file that held just those parts, and printed it. For something more general, we used a shell script that removed parts of {\tt WEAVE}'s output before passing the rest to {\TeX}. This script recognized the special symbols in the section names so that, for example, we could include or exclude whole chapters by name, without having to enumerate their contents. It would have been more expensive, and no less awkward, to use standard mechanisms for extracting pages from {\TeX}'s output. Special symbols in section names are an awkward way of indicating structure. A more natural way of indicating structure, like the {\LaTeX} mechanism, would have been welcome. Tools should make it easy to use the structure to help readers extract excerpts from literate programs. \medskip % \paragraph{Fit with configuration management tools} {\tt WEB} works poorly with {\tt make}~\cite{feldman:make}. {\tt TANGLE} is designed to read and write a complete program. Some {\tt TANGLE}s can write multiple files, which can then be compiled separately, but those files all get rewritten every time the {\tt WEB} source changes, and {\tt make} therefore recompiles them all. This problem is familiar; other preprocessors, like {\tt yacc}~\cite{johnson:yacc}, can also cause excessive recompilation. The workaround described on page 265 of Reference~\refno{kernighan:unix} works for {\tt TANGLE}. %%%%%%%% Carla wants no more details % \remark{Workaround doesn't help too much when the output % from {\tt TANGLE} includes information about source line numbers?} %%%%%%%%% {\tt WEB} users may be tempted to break their {\tt WEB} source into many files and run them through {\tt TANGLE} separately. Doing so defeats the purpose of writing a literate program; separate compilation does not necessarily imply separate explanation. For example, one would prefer to place a unit's specification and implementation in the same {\tt WEB} source, even when they should be compiled separately. \medskip % \paragraph{Fit with compilers and debuggers} Our {\tt TANGLE}~\cite{ramsey:spiderwebman} emits the {\tt\#line} directive of the C preprocessor, making messages from compilers and debuggers refer to line numbers in the {\tt WEB} source instead of to those in {\tt TANGLE}'s output. Not all compilers or all {\tt TANGLE}s support such mechanisms. Renumbering is essential for large programs. \section{Discussion} Most literate programming papers refer to programs that are polished, publishable ``works of art.'' Our primary goal in writing Penelope was not to write a publishable program, nor to evaluate literate programming as a software engineering technique, but to build a prototype editor embodying the results of research in formal verification. Our experience has given us some subjective impressions of the benefits of applying literate programming to team development, as well as more specific conclusions about the difficulties of applying literate programming. There are few published techniques for writing literate programs, especially for writing large ones. Most of our programmers complained about the awkward tools and about the lack of guidance in their use. We were unable to develop precise methods for writing literate programs or even clear criteria about what constituted a literate program. Instead, we relied on peer review of programs, rewriting them until the project members understood them. These programs were rarely polished to the point necessary for publication; less polished presentations were adequate. One review of a literate program emphasizes the role of juxtaposed code and documentation~\cite{thimbleby:review}. It cites several benefits of this juxtaposition, including an incentive to explain and hence to understand what one is doing. During peer reviews of Penelope, we insisted that explanations of programs include explanations of design. % this insistence mitigated against the % tendency of programmers to begin implementing without thinking about % design. % We found that % the juxtaposition reduced the overhead % involved in maintenance; Juxtaposing design documentation and code reduced the overhead of maintenance because maintainers reading the code did not have to look elsewhere for design documents. We cannot say to what extent literate programming can replace standard software development methodology. However, putting a clear description of design in our source code helped make it possible for a changing team of programmers to develop it over a span of three years. We were able to apply standard guidelines, like those in Reference~\refno{parnas:rational}, to describing Penelope's design. We believe literate programming helped us substantially. This belief is based not on measurements but on our subjective comparisons of experience on this project to other projects. A programmer who has used standard software development systems at an international computer manufacturing company reports that a key difference in Penelope was that the documentation was {\em used}, precisely because of its proximity to the source code. The project manager, when at a large software house, learned to expect technical staff first to criticize implementations for drifting away from the original intent, then to call for complete rewrites. There have been no complaints about the quality of Penelope's implementation. The programmers have been surprised at how easily they have extended and modified one another's work. For example, an editor for constructing proofs was implemented by a programmer who then left the project. The programmer who took over the job of maintaining the proof constructor read the program in two hours and found herself well prepared to change the code. We do not ascribe Penelope's success purely to literate programming; other factors contributed. We began implementation with a clearly defined goal and worked from detailed, sometimes formal, specifications. We had time to design the system carefully and used a declarative programming language. We did not have to develop a user interface but used the one provided by the Synthesizer Generator~\cite{reps:synthesizer:89}. We will continue to use literate programming for Penelope and for future projects. {\tt WEB}'s problems are such that we believe it will be cost-effective for future projects to develop literate programming tools that address some of the criticisms presented here. \section{Acknowledgments} Silvio Levy provided his {\tt CWEB} implementation as a base for the {\tt WEB} used to implement the Penelope editor. The staff of the Ada Verification project at Odyssey Research made possible the experience with Penelope on which this paper is based. This paper has been much improved by comments from David Hanson and from the anonymous referees. Stuart Feldman commented on this paper and discussed ideas for better tools. \bibliographystyle{unsrt} \bibliography{web,ada,cs,ramsey} %\newpage %\tableofcontents \end{document} % 1