SWEB: an SGML Tag Set for Literate Programming

In ‘literate programming’, a programmer constructs documentation for a program together with the program code itself, both kinds of material being included in a single document; by tying the program code intimately to the documentation, literate programming tools make it substantially easier to keep the program and the documentation consistent with each other. It is also more embarrassing if one fails to do so.

In the words of Donald Knuth, who formulated the idea and used it in the construction of his programs TeX and MetaFont:[2]

Let us change our traditional attitude to the construction of programs. Instead of imagining that our main task is to instruct a computer what to do, let us concentrate rather on explaining to human beings what we want a computer to do.

Among the benefits attributed to literate programming by its practitioners and others are: better (and usually fuller) explanation of the program's organization and algorithm, better indexing and cross-indexing of identifiers, easier maintenance, and easier modification of the program by the original author and others.

In Knuth's Web system, and the several similar systems inspired by it, the programmer prepares a single document, called the web, which contains both fragments of program code and prose explanation of the program structure. The code fragments may be introduced in any order suited to their explanation; they do not need to obey the restrictions imposed by the programming language on the sequence of constructs. This freedom of ordering allows global variables to be introduced together with the code which manipulates them, and for the main program and its subroutines to be declared and described in whatever order most clarifies the exposition, even in programming languages which require a rhetorically less effective order for compilation.

The web is processed in two different ways: a weave processor reads the web and produces program documentation (typically in the form of a file in a formatting language such as TeX or troff); a tangle processor rearranges the scraps of program code in the order required by a compiler, expands macros if necessary, and produces a compilable program in the programming language. In some systems, e.g. nuweb, a single program both weaves and tangles the input. Different web systems use different document languages and different programming languages. Knuth's original system used TeX for documentation and Pascal for program code; other systems have been developed for other programming languages and (less frequently) other document languages. In Knuth's system and many others, the weave component typesets the program code; such systems must thus endow weave with knowledge of the programming language being used.

Some newer systems, notably Norman Ramsey's noweb and Preston Briggs's nuweb, are programming-language independent: they have no hard-coded knowledge of the programming languages used, and thus can be used to write literate programs in any programming language, or in several languages. Without knowledge of the programming-language syntax, of course, elaborate typesetting is not feasible; language-independent web systems typically eschew typesetting entirely, reproducing scraps in a monospaced font and following verbatim the layout of the source. Sweb follows the practice of these language-independent systems: it performs no typesetting of the source code and requires no particular programming language.

Like literate programming tools, SGML systems are designed to make it possible to process a single input document in very different ways with different programs. The notion of creating an SGML-based tool for literate programming is thus an obvious one; Sweb is an attempt at such a tool. In discussing Sweb and similar tools, however, it will be useful to distinguish two areas of concern: first, the type of processing to be performed on the SGML-encoded webs, and as a separate issue the markup (i.e. the set of SGML elements) required to make that processing possible.

The processing to be performed has already been described in general terms: the user must be able to weave the web into well-formatted documentation, and to tangle it into executable programs. In the interests of generality, I will abstract away from the details of this processing and where possible formulate our markup language in declarative, rather than procedural terms. That is, I wish to follow the general principle of SGML, which is that process-specific information belongs in a style-sheet or other mechanism for controlling the process, and not in the SGML document.

So, first of all, this document defines an SGML tag set for literate programming. Documents tagged this way can be translated automatically into the specialized markup used by virtually any existing literate-programming tool, or processed directly by SGML-aware application software. They can also be operated upon directly by SGML-aware literate-programming tools.

Documents using these tags can be:

• edited using SGML-aware editors
• validated using SGML parsers
• woven directly into SGML documentation
• tangled directly into programs
• translated automatically into arbitrary web systems

As a secondary matter, this document will also describe some aspects of the processing of documents marked up with these tags. Implementations of software to perform these processes will be described in separate documents; many details of processing will vary from implementation to implementation. At the time of writing, the only implementation is a partial implementation of tangle functionality using yacc and lex; weave functionality is provided by direct display of the Sweb document in an SGML browser such as Panorama or by translation into HTML for delivery on the World Wide Web.

Scraps of code in a document are encoded using the <scrap> element; they are embedded in other scraps using the standard TEI cross-reference elements <ref> and <ptr>:[3]

• <scrap> contains a scrap of program code, in any language. Attributes include:
  • name gives a name to the scrap, to be used as a label for the scrap and in cross-references to it.
  • file names the output file to which this scrap is to be written out; not required if this scrap is embedded by another one elsewhere.
  • prev (i.e. continuation of) gives the SGML identifier of a scrap for which this element is a continuation.
  • version indicates which version(s) of a program this scrap belongs to, when the web defines multiple versions.

By convention, the scrap identified as ‘previous’ should precede its continuations in the document --- but this is not formally required.

Like any TEI element, the <scrap> element can bear the global lang attribute, which in this case records the programming language of the scrap. Since programming languages are not listed in ISO 639, the values for programming languages must be improvised by the author.

For example, here is a scrap of code from Knuth and Levy's rewrite of the Unix utility wc:[4]

<scrap id='wrstat'
       lang='C'
       name='Write statistics for file'>
wc_print(which, char_count,word_count,line_count);
if (file_count)
   printf(" %s\n", *argv); /* not stdin */
else
   printf("\n");           /* stdin */
</scrap>

Scraps can be referred to from other scraps, using the standard TEI elements <ptr> (which uses the SGML identifier of the scrap being embedded as the value of its target attribute) or <ref> (which can use its target attribute, or which can use its content to match the name of the target scrap). Using the SGML ID/IDREF mechanism, Knuth and Levy's rewrite of wc would have the following top-level scrap; it has an empty string as its name value, since they make this top-level scrap anonymous.

<scrap name="">
<ptr target="hdrfiles">
<ptr target="globals">
<ptr target="functns">
<ptr target="main">
</scrap>

The other scraps involved would have the following overall structure:

<scrap id="hdrfiles" name="Header files to include">
#include &lt;stdio.h>
</scrap>

<!-- ... -->

<scrap id="globals">
int status = OK; /* exit status of command, initially OK */
char *prog_name; /* who we are */
</scrap>

<!-- ... -->
<scrap id="functns">  <!-- ... --> </scrap>
<!-- ... -->
<scrap id="main">  <!-- ... --> </scrap>
<!-- ... -->

The formal declaration of <scrap> is as follows: I use the entity model.scrap as the content model for <scrap> element in order to make it easier to customize if desired. It also makes it easier to see that the <scrap> and <recap> elements are declared identically.

Within a code scrap, references to other code scraps serve as cross references or hyperlinks to those other code scraps. In a printed copy of the Sweb document, such cross-references will normally contain the name of the embedded scrap, with a scrap number or page number; by convention these appear together in Roman type enclosed in angle brackets. In an online browser, the cross references should display in much the same way, but should also be live hypertext links: the user should be able to click on the name and traverse the link automatically, so that the embedded scrap appears on the screen for consultation.

The live-link behavior is easy to accomplish if ID/IDREF linking is used, since SGML browsers conventionally interpret ID/IDREF links this way. If string-prefix matching is used, however, very few online browsers will be able to treat scrap references as live hyperlinks. It is desirable, therefore, for a weave process to normalize string-prefix references by transforming them to normal ID/IDREF references. It will simplify the task for formatters and display programs — not to mention later readers of the web — if any abbreviated forms of the name are replaced, at the same time, with the full name. After such normalization, the first example given in the preceding section would look like this:

<!-- top-level scrap refers to 'Program ...' -->
<scrap name="">
<ref target="program">Program to print the first thousand prime numbers
</ref>
</scrap>

<!-- ... -->
<!-- This scrap defines that program. -->
<scrap id="program"
       name='Program to print the first thousand prime numbers'>
  <!-- ... -->
</scrap>

A similar normalization is useful for <ptr> elements. Some SGML browsers have no difficulty in following the pointer, finding the name of the scrap pointed to, and displaying that name as part of the normal rendition of the pointer; such text reflection, however, is beyond the current grasp of other browsers. Such browsers will give better results if text is copied (duplicated) in the source rather than being reflected at display time; in Sweb, this effectively means replacing <ptr> elements with equivalent <ref> elements. The target and all other attributes of the <ref> are the same as those of the <ptr> element; the content of the <ref> is the name value of the <scrap> element being pointed to.

A full Sweb implementation, therefore, performs all of the following normalizations on its input unless the user indicates by means of run-time flags that they should be suppressed:

• String-prefix scrap references are replaced by <ref> elements linked by the SGML ID/IDREF mechanism.
• Scrap references using <ptr> elements are replaced by equivalent references using <ref> elements.
• Each <ref> element is normalized to contain the name of the scrap it points to.

Full Sweb implementations should also identify blind references and unreachable scraps and issue warning messages for them. In cases where blind references are not an error, the warnings can be suppressed by removing the target attribute from the <ref> element in question and processing the file with a flag suppressing string-prefix matching; this will indicate to the weave processor that no target should be sought for the <ref> element. In cases where scraps are known to be unreachable, warnings may be suppressed by giving the value unreachable to the scrap's rend attribute, in effect saying “I know this scrap is unreachable. In this case that is not an error. Don't bother me.” [Is this necessary? Is there a better way?]

The file attribute on the <scrap> element is used to specify that a given scrap is to be written out to the file named. If a scrap tagged with a file name refers to a nested scrap, both scraps will be written out to the same file; a scrap referred to by several others will be written out several times, once for each reference.

Any scrap bearing a value for the file attribute will be written out to the file indicated, together with any scraps it embeds, followed by any continuations. This will happen even if the scrap has already been written out to some other file, or has been referred to by another scrap in the same file. Embedded scraps and continuations should therefore not bear the file attribute, unless it is intended that they appear in the output twice.

If output files are rewritten every time an Sweb document is reprocessed, the resulting changes to the operating system time-stamp on the files are likely to confuse make and similar software development utilities. They rely on the time stamp to indicate the last time changes were made to a file, and will be confused if the time stamp changes even when the file contents do not. (Changes in the Sweb source may have affected only other output files.)

To avoid this problem, full Sweb implementations should replace output files only if the new version will be different from the existing version. The nuweb system demonstrates a simple method of accomplishing this:

• each output file is written as a temporary file
• the temporary file is then compared to the existing file, if any, bearing the name given in the web source
• if the two files are different, the existing file is deleted and the temporary file is renamed with the proper name
• if the two files are the same, the temporary file is deleted and the existing file is left untouched

Other algorithms are possible, but this one seems to work quite well and to have few system dependencies.

As an example, consider the sample input file included in the one-page summary for nuweb, a literate programming tool written by Preston Briggs of Rice University.[6] As a nuweb file, it looks like this:

Here is the overall structure of an example program:

@d Sample Program
@{@<Declarations@>
@<Main Program@>
@<Subroutine@>
@}

Some declarations are always necessary:

@d Declarations
@{Easy things
Real things
Complex things
@| Things Complex declarations
@}

The main program is quite straightforward:

@d Main Program
@{Call @@subroutine
Exit
@}

as is the subroutine

@d Subroutine
@{@<Declarations@>
Useful Job With Things
@}

Finally, write the entire program out to a file:

@o sample.prg -it
@{@<Sample...@>
@}

The files I've generated are:
@f
the macros defined are:
@m
and the terms I've asked to be indexed are:
@u

An SGML user could define many of the special @-sequences as SGML short references for tags, but to make the SGML structure of this example clearer, I will use explicit SGML tags. An Sweb document equivalent to the nuweb document above is:

<p>Here is the overall structure of an example program:

<scrap name='Sample Program'>
<ref>Declarations</>
<ref>Main Program</>
<ref>Subroutine</>
</scrap>

<p>Some declarations are always necessary:

<scrap name='Declarations'>
Easy things
Real things
Complex things
<index level1='Things'>
<index level1='Complex'>
<index level1='declarations'>
@}

The main program is quite straightforward:

<scrap name='Main Program'>
Call @subroutine
Exit
</>

as is the subroutine

<scrap name='Subroutine'>
<ref>Declarations</>
Useful Job With Things
</scrap>

Finally, write the entire program out to a file:

<scrap file='sample.prg' rend='noindent keeptabs'>
<ref>Sample...</>
</scrap>

The files I've generated are:
<divGen type='filenames-index'>
the macros defined are:
<divGen type='scrapnames-index'>
and the terms I've asked to be indexed are:
<divGen type='index'>

When a web defines only one version of a web, a reference to another scrap is interpreted, as described above, as an indication that that scrap belongs logically at the point of reference. When multiple versions are present in the same web, the reference is interpreted as a reference not to one particular scrap, but as a reference to the equivalence class: any scrap in the equivalence class might potentially be substituted for the reference. Which scrap is selected depends on which version is being generated; this in turn is controlled by the user interface to the tangle processor (e.g. by selection from a menu, or by command-line option).

In the simple case, one scrap in the equivalence class identifies itself as belonging to the version being generated (by giving the version identifier on its version attribute); that is the scrap used by tangle. If two scraps in the same equivalence class identify themselves as belonging to the version being generated, it is a fatal error. If no scrap is identified as belonging to the version in question, a fallback must be found.

The fallback information is given by the <version> element, which declares one version of the program or package, and identifies a fallback version to use when necessary. Versions are declared in a <versionList> element, which should normally appear in the front matter or introduction to the document (e.g. in a section that describes which versions of the program exist).

• <versionList> contains a series of <version> elements.
• <version> declares one version of the program, file, or package. Attributes include:
  • id assigns a unique identifier to the version being declared.
  • n gives a name for the version (may be multiple words)
  • fallback identifies the version to use, when no scrap is identified as belonging to the version being declared (normally the version used as the basis for the version being declared).

The fallback version is typically the one from which a new version was derived. If no scrap in an equivalence class identifies itself as belonging to the version being generated, the tangle processor will find the scrap belonging to the fallback version. If there is none, the fallback's fallback will be sought, and so on until there are no further fallbacks, at which point a scrap with no version information at all will be used (which will normally be the first, unmarked version); if none or more than one is found, it is a fatal error.

The formal declaration of the <version> and <versionList> elements is as follows:

For example, Dijkstra's classic article on “Stepwise Program Construction” presents a program to fill an array with the first thousand prime numbers. He presents a scrap of code (scrap 0), which defines the overall program and refers to another scrap (scrap 1), which refines the problem and refers to a third scrap (scrap 2), which does a portion of the work and refers the rest to a fourth scrap (scrap 3). After presenting a first version of scraps 1 and 2, however, Dijkstra observes that they can be made substantially more efficient by only looking at odd numbers when seeking primes greater than 2, and presents alternate versions of these two scraps (scraps 1b and 2b). Further improvements result in versions c and d; and version d is the first to define a scrap 3. A final revision results in scraps 1e, 2e, and 3e, which represent the final form of the program.

The versions of this program can be declared thus:

<versionList>
<version id="A">
<version id="B" fallback="A">
<version id="C" fallback="B">
<version id="D" fallback="C">
<version id="E" fallback="D">
</versionList>

The first few code fragments would look something like this; note that Dijkstra uses the term version in a rather loose sense when labeling his code scraps. The root scrap has no version information, because it is the same for all versions: if we use the ID/IDREF mechanism to match scraps and references to them it will look like this:[12]

<p>We shall now give the coarsest version
of the program, viz.
<scrap id="program" name='version 0'>
begin <ptr target="assign"> end
</scrap>
<p>When this action ...

The first version of scraps 1 and 2 follows:

<p>The first prime number ... we come to

<scrap id="assign"
       n='1a'
       name='assign to the array p
       the prime table as described'
       version="A">
begin integer k, j: k := 1; j := 1;
    while k <= 1000 do
    begin <ptr target="increase">;
         p[k] := j; k := k + 1;
    end
end
</scrap>

<p>Version 1a is a perfect program when ...
With a simple repetitive <kw>repeat until</kw>
clause (which may act upon a sequence of statements)
we come for <q>increase <ident>j</ident> until
the next prime number</q> to

<scrap id="increase"
       n='2a'
       name='increase j until the next prime number'
       version="A">
begin boolean jprime;
    repeat j := j + 1; <ref>give to <ident>jprime</>
         the meaning: <ident>j</> is a
         prime number</ref>;
    until jprime
end
</scrap>

<p>If we substitute version 2a for the appropriate
operation in version 1a our resulting program is
undoubtedly correct. ...

Scrap 2a refers to a scrap (“give to jprime the meaning: j is a prime number”) which is never actually written, because at this point Dijkstra stops and considers an obvious optimization: checking only odd numbers for primality. Since there is no such scrap, there is no SGML ID to point at, and we render the reference using the <ref> element. (This also shows, in passing, how identifiers can be tagged in scrap references; working out the details is left to the reader as an exercise.)[13]

Dijkstra's second cut at scraps 1 and 2 follows:

So we come to

<scrap exclude="assign"
       n='1b'
       name='assign to the array p the
       prime table as described'
       version="B">
begin integer k, j: p[1] := 2; k := 2; j := 1;
    while k <= 1000 do
    begin <ptr target="increase">;
         p[k] := j; k := k + 1;
    end
end
</scrap>

where the analogous elaboration of the
operation between quotes leads to

<scrap exclude="increase"
       n='2b'
       name='increase odd j until the next
       odd prime number'
       version="B">
begin boolean jprime;
    repeat j := j + 2; <ptr target="jprime-odd">;
    until jprime
end
</scrap>

Dijkstra's example raises an important question. Since his scraps 1a and 1b have exactly the same function, as do 2a and 2b, they are shown here as members of the same equivalence class. What should be done, however, with the various versions of the scrap “give to jprime [for odd j] the meaning: j is a prime number”? The variations Dijkstra introduces in its name imply variations in its function; mathematically, as it turns out, this implication is false, in this case, but it is easy to imagine cases where analogous scraps do have different functionality, reflecting different assumptions in the contexts of their use. The rule of Sweb is simple: analogous scraps, called from similar places in equivalent code, which perform mathematically different functions, are not equivalent, and should not be placed in equivalence classes. Instead, they should be treated as different scraps entirely. (It is possible to imagine cases where this will require more verbose encoding of the scraps, but they are all rather far fetched, so this should not be burdensome in practice.) Code called from the same location is normally equivalent and can normally be tagged as a single equivalence class.

[Discussion ... possibly better example, with branching]

Sweb systems normally use a kind of semi-automatic indexing similar to that performed by nuweb. The author of the web can indicate, in the <indexDefs> element, which identifiers are defined or declared in the associated scrap. These identifiers are indexed as being defined in that scrap, and as being used in any other scrap within which their names occur.[18] The author can also indicate, by means of the <divGen> element, where the generated index should be inserted in the output document.

The <indexDefs> element is used to indicate identifiers defined in the current scrap, or more generally to indicate any index strings for which the current scrap should be marked as a primary index entry. The standard TEI elements <index> and <divGen> are used in the normal way to control indexing.

• <indexDefs> contains a list of identifiers to be indexed as being defined in the current scrap; the list may include both simple blank-delimited strings and conventional <index> entries as defined by the TEI core tag set.
• <index> indicates that a specific index entry should be made for the current location (scrap, page, section, ...). Sweb extends the standard TEI <index> element with the attributes target and resp. Attributes include:
  • index identifies, normally by means of a single token, which of several indices should contain the index entry
  • level1 gives the form of the main index entry
  • level2 gives the sub-entry, if any
  • level3 gives the sub-sub-entry, if any
  • level4 gives the fourth-level sub-entry, if any
  • target indicates the SGML element to which the <index> element applies; if omitted, the index element is assumed to apply to the specific location at which it appears.
  • resp indicates who is responsible for the index entry; automatically generated <index> elements will bear the name of the program which generated them as the value of this attribute
• <divGen> indicates the location at which a <div> element of some type is to be generated by a document processor; in particular, an index or table of contents. Attributes include:
  • type indicates the type of <div> element to be generated automatically and inserted in place of the <divGen> element. Suggested values include:
    • table of contents
    • main index; if multiple indices are desired, they may be distinguished by a second token: index identifiers, index filenames, index scrapnames, index names, etc.

All weave processors for Sweb will accept simple blank-delimited strings as input; it is expected, though not required, that they will replace the input strings in their output with equivalent <index> entries. This will allow human editors to use the simpler form for the first cut at an index, and then edit the output from weave if necessary, to get better results.

In normal processing, a weave processor will

• create a primary index entry for each identifier in the list, pointing to the current scrap
• normalize the contents of <indexDefs> by replacing each identifier in the list with an <index> element in which the identifier appears as the level1 attribute value[19]
• seek other occurrences of the identifier in other scraps, and make secondary index references for all the other scraps in which the identifier is found
• insert, at the location indicated by an appropriate <divGen> element, the index of identifiers thus created

For example, one of the scraps of Dijkstra's prime-numbers program might look like this in the first draft of a document, with an index entry specified for jprime:

<scrapInfo>
<head>increase <ident>j</ident> until the next prime number</head>
<scrap id="increase"
       n='2a'
       version="A">
begin boolean jprime;
    repeat j := j + 1; <ref>give to <ident>jprime</>
         the meaning: <ident>j</> is a
         prime number</ref>;
    until jprime
end
</scrap>
<indexDefs>jprime</indexDefs>
</scrapInfo>

After weave processing, the <indexDefs> element would contain <index> elements, not just raw tokens:

<indexDefs>
<index level1='jprime' index='identifiers'>
</indexDefs>

At the end of the document, the identifier index would include an entry something like this:

<item><ident>jprime</ident>:
defined in
<ref target="increase">increase <ident>j</ident>
until the next prime number</ref>,
used in ...
</item>

In some cases, it may be desirable to use the more structured form of an <index> element. If we wanted to use second-level index entries to specify the type of each identifier, for example, we might substitute an <indexDefs> entry like the following:

<indexDefs>
   <index
      level1='jprime'
      level2='(boolean)'
      index='identifiers'
      rend ='defined'
   >
</indexDefs>

In this case, the weave processor would leave the <indexDefs> element alone, and the entry in the identifier index would look something like this:

<item><ident>jprime</ident>
<list type="simple">
<item>(boolean):
defined in
<ref target="increase">increase <ident>j</ident>
until the next prime number</ref>,
used in ...
</item>
</list>
</item>

For further discussion of the back-of-the-book index, see section The Back of the Book Index.

The formal definition of <indexDefs> is as follows:

Automatic index processing can be supressed entirely, to allow the author of the web complete control over the indexing of scraps. Suppression of automatic index processing also allows manual tweaking of the index, after an automatic process has generated a rough draft.

To suppress automatic index generation entirely, it is necessary only to avoid running any of the automatic index generators. Automatic index generation can be suppressed for individual scraps, by setting their index values to manual.

To suppress the normal index processing behavior (as described above in section Normal Indexing), it is necessary to suply an appropriate run-time flag.

Normal index processing produces a full index of identifiers at the location specified by the user by means of a <divGen> element. Its contents are very simple: a <list> of type index. Each index entry is an item; each item consists of the entry form itself, followed by a series of <ref> elements pointing at the scraps in which the identifier in question is defined or used. The point of definition will normally be marked with an asterisk, but this may vary from implementation to implementation.

A fragment of the print index from a literate program might look something like this:[21]

<list type="index">
<!-- ... -->
<item><ident>nactive_heaps</ident> *75c, 76a, 76b </item>
<item><ident>NEQ</ident> *24a </item>
<item><ident>newcell</ident> 41a, 52c, 70a, 84c</item>
<item><ident>nheaps</ident> 19b, 21b, 22b, 62c, 69, 73b, 74, 75c, 76a,
76b </item>
<item><ident>NIL</ident> 16b, 20a, *24a, 31a,
<!-- ... -->
</item>
<!-- ... -->
</list>

A version of this index intended for online use might look slightly different: the page numbers might better be replaced with <ref> elements containing the names of the scraps, with the scrap identifiers in the target attributes:

<list type="index">
<!-- ... -->
<item><ident>nactive_heaps</ident>
<ref target="gcroutines75c">*Define nactive_heaps()</ref>,
<ref target="gc76a">define gc_status()</ref>,
<ref target="gc76b">Define gc_info()</ref>
</item>
<item><ident>NEQ</ident>
<ref target="type-predicates">*Define Lisp type predicates</ref>
</item>
<item><ident>newcell</ident>
<ref target="newcell">Define newcell</ref>,
<ref target="fopen">Define fopen</ref>,
<ref target="gc-for-newcell">Define gc_for_newcell</ref>,
<ref target="lmfuncs">Declare list-management functions</ref>
</item>
<item><ident>nheaps</ident>
<ref target="heapvars">Heap variables</ref>,
<ref target="process-cla">Define process_cla()</ref>,
<ref target="print-hs-1">Define print_hs_1</ref>,
<ref target="init-storage-1">Define init_storage_1</ref>,
<ref target="allocate-aheap">Define allocate_aheap()</ref>,
<ref target="looks-pointerp">Define looks_pointerp</ref>,
<ref target="gcsweek">Define gc_sweep</ref>,
<ref target="gcroutines75c">Define nactive_heaps()</ref>,
<ref target="gc76a">Define gc_status()</ref>,
<ref target="gc76b">Define gc_info()</ref>
</item>
<item><ident>NIL</ident>
<ref target="globals">Declarations for siod.c</ref>,
<ref target="lisp-obj">Lisp objects</ref>,
<ref target="type-predicates">*Define Lisp type predicates</ref>,
<ref target="leval-args">Define leval_args</ref>,
<!-- ... -->
</item>
<!-- ... -->
</list>

The markup and indexing processes described in this document can be used in a variety of ways. In a ‘normal’ case, if any exist, the programmer might index all scraps manually, allowing Sweb to generate an index of identifiers.

In some cases, it might be more convenient to run ScrapIndexer periodically during development, so as to get a rough index automatically. Since ScrapIndexer does not distinguish between definitions and mere uses of variables, the resulting index is not so useful, but it also requires less work to generate. When the program is complete or nearly complete, it would be sensible to run ScrapIndexer (or some other automatic index generator) a final time, and then to edit the results, moving <index> elements as needed into the <indexDefs> element from the <indexRefs> element. The actual index can be generated by the default behavior of Sweb, or the index processing can be set to fully manual operation.

The general rule is simple: use the automatic index generators to generate rough indices during development, and use their output as a rough first draft, to be manually edited and tweaked as the document approaches completion.

Sweb is a single-DTD system, designed to be suitable for handling by a single processor rather than by separate weave and tangle processors. By single-DTD system, I mean a system whose output conforms to the same markup language as the input. This distinguishes it from virtually all of its predecessors, whether single-processor or double-processor systems:[24] they universally produce, as output, files which cannot be read again as input.

In practice, however, a double-DTD system has the undesirable effect that everyone reads the output form of the document and no one ever sees the input form.[25] A single-DTD system eliminates this problem: anyone interested in using the system can imitate the file format they see in the finished products.

The single-DTD system also makes it much easier to do a first sketch of a program or SGML DTD, without the reference material.

A single process which both weaves and tangles the input must:

• tangle the output files
• normalize <ptr> elements into <ref> elements for the sake of browsers which can't reflect text dynamically
• expand <recap> elements inline, ignoring any content they have in the input
• support multiple versions of the code, recognizing equivalence classes and tangling a single version of the output (by default, the last version in the <versionList>; the user may specify another version at run time)
• normalize string-prefix matching scrap references to <ref> elements using ID/IDREF linking, normalizing the content of the <ref> elements at the same time to agree with the full name of the scrap referred to
• generate indices on demand
• generate reference material

These are listed in what seems to me a natural order for gradual implementation.

The tag set declared here functions as a user-supplied extension to the host TEI DTD; apart from being supplied by the user instead of by the TEI, it works the same way the TEI ‘additional tag sets’ work. The formal declarations of the SGML elements will be contained in one file, while the SGML glue needed to integrate the Sweb tags with the native TEI tag sets will be included in another. The system names of these are sweb.dtd and sweb.ent, respectively.

Normally, literate programming documents will use the TEI base tag set for prose (verse and drama would also work, but might seem excessively ‘literate’ and frighten later maintenance programmers who have to work with the web). The tag set described here also requires portions of the additional tag set for linking. The document type declaration for a literate programming document must therefore select the TEI tag sets for prose and linking, and identify the files sweb.dtd and sweb.ent as containing extensions we wish to use. In the simple case, when we are not using any other extensions, the document type declaration can look like this:

  <!DOCTYPE tei.2 SYSTEM 'tei2.dtd' [
    <!ENTITY % TEI.prose   'INCLUDE' >
    <!ENTITY % TEI.linking 'INCLUDE' >
    <!ENTITY % TEI.extensions.dtd SYSTEM 'sweb.dtd' >
    <!ENTITY % TEI.extensions.ent SYSTEM 'sweb.ent' >
  ]>

In the more complex case, we have to combine the Sweb additional tag set with other extensions, for example, those which define TEI Lite. In this case, we need only:

• create a new TEI.extensions.ent file, containing entity declarations for the two extensions' own entity-declaration files. If the two entities modify any of the same TEI entity declarations, then new declarations must be put together by hand for the entities concerned. After this is done, the two extension entity files can be referenced.
• create a new TEI.extensions.dtd file, containing entity declarations for the two extensions' own element-declaration files. If the two entities modify any of the same TEI element or attribute list declarations, then new declarations must be put together by hand for the elements concerned. After this is done, the two extension DTD files can be referenced.

[example needed.]

Some fundamental literate programming facilities can be handled by standard elements and require no specialized tags. It may be necessary, however, for these standard elements to be processed in specialized ways. This section describes the special processing required for standard elements when used in literate programs.

The <ref> element and <ptr> elements are used in program scraps, to indicate embedding of other scraps. Tangle processors should follow the link recursively and embed the other scrap at the location indicated; weave processors should print the name of the other scrap, followed by a module or scrap number, section number, or page number, all enclosed within angle brackets, or using whatever typographic convention is adopted for module references.

The <divGen> element is used to signal that a text-division (<div>) element should be generated, containing an index of a kind specified in the type attribute. Special values which should be recognized by Sweb processors are:

filenames-index

index of files generated

scrap-index

index of scrap names

version-index

index of version names

index

index of identifiers (manually indexed)

[Idea: make two-level convention, so <divGen type='index filenames'> dumps the index created by <index index='filenames' level1='myfile.dat'> and so on. Then it's simple to allow the user to specify whether the identifiers belong in the main index, or in an index of their own. Ditto for everything else: filenames can go in their own index, or they can be put into the main index, depending on one's preferences.]

In order to integrate the tags defined here into the TEI base, we need to include them into the TEI element-class system. I do this by defining some specialized parameter entities:

[This section needs work.]

Knuth's original WEB system, and many of its offshoots, typeset the program code in a readable style, formatting code blocks appropriately (with indentation showing code structure), printing keywords in bold, literals in a monospaced font, and identifiers in italics, and using special characters in the standard TeX fonts for important operators such as assignment, logical-and, and logical-or. This requires substantial knowledge of the programming-language syntax to be hard-coded into the program or located in a table somewhere for consultation by the program.

Hard-coding the program's linguistic knowledge also has the drawback of limiting a web to the language(s) known to the weave and tangle processors; in an attempt to evade this drawback, some tools simply print all program code in a monospaced typewriter font, reserving normal typesetting for module references and comments.

In Sweb, program scraps and inline <code> elements are processed, by default, as verbatim text using a typewriter font. Language-specific processing can be achieved by writing special routines to parse program fragments and insert the proper formatting codes; these special routines should be introduced into the style-sheet controlling the weaving process. In this way, special indexing, etc., can also be introduced.

[Specific examples needed here.]

[N.B. the discussion above is silently assuming that Sweb will be implemented by an SGML-aware filter program driven by a style sheet, or by a pipeline of such filters, implemented with tf, CoST, OmniMark, or similar programs. Since Sweb's output is also an SGML document, then language-specific processors can be run on the Sweb output. They need only distinguish scraps and inline code fragments properly, and identify their language correctly.]

As an aid in understanding the Sweb tag set, and the expected processing, I provide the following partial lists of commmands in some widely used literate programming tools, together with the equivalent in Sweb.

For WEB:

@*

major module: use <div1>

@&#SPACE;

module: use <div2>, <div3>, etc., or <p>.

@p

Pascal program: use <scrap>

@<

module definition: use <scrap>

@<

module reference: use <ref> or <ptr>

@^

index entry (in normal font): use <index> with an appropriate level2 value

@.

index entry (in typewriter font): use <index> with an appropriate level2 value

@>

end of argument: this is handled differently in SGML; mark the end of an SGML element with the appropriate end-tag, the end of an attribute value with a closing quotation mark.

|...|

Pascal-within-text: use <code> or <ident>

@!

mark next identifier as defining occurrence: not implemented

@;

format like Pascal semicolon: not implemented

@d

define a macro: not implemented

N.B. in this version of Sweb, a number of WEB facilities have no SGML analogues; these may eventually be added, but this has not yet been done. In addition to those already mentioned, these constructs without equivalents include:

• facilities for overriding weave's automatic formatting of program text
• ways to force tangle to concatenate adjacent tokens, to manufacture identifiers.
• facilities for octal, decimal, and alphabetic constants

The special markup for overriding the default formatting depends critically upon the specific algorithms used to typeset the program code, and has a very unSGML-like feel to it, so it may never be added; however, it may be essential to really satisfactory results, so it may be necessary to define it in the form of a set of declarative hinting elements for use by any formatter.

For nuweb:

@o filename flags @{ ... @}

write the scrap out to the named file, allowing no page breaks within the scrap: <scrap file="fn" rend="flags"> ... </scrap>

@O file flags @{ ... @}

ditto, but allow page breaks within the scrap: <scrap file="fn" rend='loose flags'> ... </scrap>

@d scrapname @{ ... @}

define a scrap with the name given; allow no page breaks: <scrap name='scrapname'> ... </scrap>

@D scrapname @{ ... @}

define a scrap with the name given; allow page breaks: <scrap name='scrapname' rend='loose'> ... </scrap>

@{ ... @}

delimit a scrap (this should always be preceded by @d or @o): <scrap> ... </scrap>

@< name@>

invokes the scrap named. <ptr target="scrapid"> or <ref>name</ref> or <ref target="scrapid">name</ref>

@f

generate index of filenames created: <divGen type='filenames-index'>

@m

generate index of macro names (scrap names): <divGen type='scraps-index'>

@u

generate index of identifiers or other terms: <divGen type='terms-index'> or <divGen type='index'>