Commits

Jeroen Ruigrok van der Werven committed 0c26fa7

Add directories, Makefile, and selected initial DocBook/XML conversions.

Comments (0)

Files changed (5)

+# $Id$
+
+XSLTPROC= xsltproc
+
+DBSRCS=	calculus/calculus.xml diagnostic/diagnostic.xml tcpplus/tcpplus.xml\
+	tspec/tspec.xml
+
+DBXSL=	/usr/local/share/xsl/docbook/xhtml/docbook.xsl
+
+all:
+.for i in ${DBSRCS}
+	${XSLTPROC} -o ${i:C/xml/html/} --xinclude ${DBXSL} ${i}
+.endfor
+
+clean:
+.for i in ${DBSRCS}
+. if exists(${i:C/xml/html/})
+	rm ${i:C/xml/html/}
+. endif
+.endfor

doc/calculus/calculus.xml

+<?xml version="1.0" standalone="no"?>
+<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.3//EN"
+  "http://www.oasis-open.org/docbook/xml/4.3/docbookx.dtd">
+
+<book>
+  <bookinfo>
+    <title>Calculus Users' Guide</title>
+
+    <corpauthor>The TenDRA Project</corpauthor>
+
+    <author>Jeroen Ruigrok van der Werven</author>
+    <authorinitials>JRvdW</authorinitials>
+    <pubdate>2004</pubdate>
+
+    <copyright>
+      <year>2004</year>
+      <year>2005</year>
+
+      <holder>The TenDRA Project</holder>
+    </copyright>
+
+    <copyright>
+      <year>1998</year>
+
+      <holder>DERA</holder>
+    </copyright>
+  </bookinfo>
+
+  <chapter>
+    <title>Introduction</title>
+  
+    <para>This document describes a tool, <productname>calculus</productname>,
+      which allows complex type systems to be described in a simple algebraic
+      format, and transforms this into a system of C types which implements
+      this algebra.</para>
+  
+    <para><productname>calculus</productname> was initially written as a
+      design tool for use with the TenDRA C and C++ producers. The producers'
+      internal datatypes reflect the highly complex interdependencies between
+      the C and C++ language concepts (types, expressions and so on) which
+      they were designed to represent. A tool for managing this complexity and
+      allowing changes to the internal datatypes to be made with confidence
+      was therefore seen to be an absolute necessity. The tool can also be
+      applied in similar situations where a complex type system needs to be
+      described.</para>
+  
+    <para>The tool also provides for a separation between the specification of
+      the type system and its implementation in terms of actual C types. This
+      separation has a number of advantages.  The advantages of maintaining a
+      level of abstraction in the specification are obvious. It is possible to
+      apply extremely rigorous type checking to any program written using the
+      tool, thereby allowing many potential errors to be detected at compile
+      time. It is also possible to restrict access to the types to certain
+      well-specified constructs, thereby increasing the maintainability of
+      code written using the tool.</para>
+  
+    <para>This separation also has beneficial effects on the implementation of
+      the type system. By leaving all the type checking aspects at the
+      specification level, it is possible to impose an extremely homogeneous
+      underlying implementation. This means, for example, that a single memory
+      management system can be applied to all the types within the system. It
+      also opens the possibility of writing operations which apply to all
+      types within the system in a straightforward manner. The
+      <a href="#DiskOutput">disk reading and writing routines</a> described
+      below are an example of this.</para>
+  
+    <sect1 id="Options">
+      <title>1.1. Using calculus</title>
+  
+      <para>The general form for invoking <productname>calculus</productname>
+        is as follows:
+        <command>calculus<optional><option>options</option></optional>
+        <option>input</option> ....
+        <optional><option>output</option></optional></command>
+        where <option>input</option> is a file containing the input type
+        system description and <option>output</option> is the directory where
+        the files implementing this system are to be output. This directory
+        must already exist. If no <option>output</option> argument is given
+        then the current working directory is assumed. Note that several
+        <option>input</option> files can be given.  Unless
+        <a href="#Module">otherwise specified</a> it is the last file which is
+        used to generate the output.</para>
+  
+      <para>The form in which the <a href="#TextInput">input type systems</a>
+        are expressed is described below. The form of the output depends on
+        <option>options</option>. By default, the C implementation of the type system is
+        output. If the <option>-t</option> option is passed to
+        <command>calculus</command> then <a
+        href="../tcpplus/token.html"><code>#pragma token</code></a> statements
+        describing the type system specification are output.  This <a
+        href="#TokenOutput">specification</a> is given below, with some of the
+        more important <a href="#COutput">implementation details</a> being
+        described in the following section.</para>
+  
+      <para>Note that it is necessary to check any program written using
+        <productname>calculus</productname> against the <code>#pragma
+        token</code> version of the specification in order to get the full
+        benefits of the rigorous type checking provided by the tool. Some
+        sections of the program (if only the <a href="#COutputSupport">basic
+        functions</a>) may be dependent upon the implementation, and so not be
+        suitable for this form of checking.</para>
+    </sect1>
+
+    <sect1 id="Example">
+      <title>1.2. Example program</title>
+
+      <para>The program <productname>calculus</productname> itself was written
+        using a type system specified using the
+        <productname>calculus</productname> tool. It is designed to provide an
+        example of its own application, with some features not strictly
+        necessary for the functionality of the program being added for
+        illustrative purposes.</para>
+    </sect1>
+  </chapter>
+  
+  <chapter>
+    <title>Input syntax</title>
+  
+    <para>The overall input file format is as follows:
+      <programlisting>
+          <i>algebra</i> :
+                  ALGEBRA <i>identifier version<sub>opt</sub></i> : <i>item-list<sub>opt</sub>
+  </i>
+  
+          <i>version</i> :
+                  ( <i>integer</i> . <i>integer</i> )
+  
+          <i>item-list</i> :
+                  <i>item</i>
+                  <i>item-list item</i>
+  
+          <i>item</i> :
+                  <i>primitive</i>
+                  <i>identity</i>
+                  <i>enumeration</i>
+                  <i>structure</i>
+                  <i>union</i>
+      </programlisting>
+        The initial identifier gives the overall name of the algebra.  A
+        version number may also be associated with the algebra (if this is
+        omitted the version is assumed to be 1.0). The main body of the
+        algebra definition consists of a list of items describing the
+        primitives, the identities, the enumerations, the structures and the
+        unions comprising the algebra.</para>
+  
+      <para>Here <i>identifier</i> has the same meaning as in C. The only
+        other significant lexical units are <i>integer</i>, which consists of
+        a sequence of decimal digits, and <i>string</i>, which consists of any
+        number of characters enclosed in double quotes. There are no escape
+        sequences in strings. C style comments may be used anywhere in the
+        input. White space is not significant.</para>
+
+    <sect1 id="InputPrim">
+    
+      <title>2.1. Primitives</title>
+  
+      <para>Primitives form the basic components from which the other types in
+        the algebra are built up. They are described as follows:</para>
+      <programlisting>
+          <i>primitive</i> :
+                  <i>object-identifier</i> = <i>quoted-type</i> ;
+  </programlisting>where the primitive identifier is given by:
+    <programlisting>
+          <i>object-identifier</i> :
+                  #<i><sub>opt</sub></i> :<i><sub>opt</sub> identifier</i>
+                  #<i><sub>opt</sub></i> :<i><sub>opt</sub> identifier</i> ( <i>identifier</i> )
+  </programlisting>and the primitive definition is a string which gives the C
+  type corresponding to this primitive:
+    <programlisting>
+          <i>quoted-type</i> :
+                  <i>string</i>
+      </programlisting>Note that each primitive (and also each identity, each
+        enumeration, each structure and each union) has two names associated
+        with it. The second name is optional; if it is not given then it is
+        assumed to be the same as the first name. The first name is that which
+        will be given to the corresponding type in the output file. The second
+        is a short form of this name which will be used in forming constructor
+        names etc. in the output.
+  
+      <para>The optional hash and colon which may be used to qualify an object
+        identifier are provided for backwards compatibility only and are not
+        used in the output routines.</para>
+    </sect1>
+
+    <sect1 id="InputIdent">
+      <title>2.2. Identities</title>
+  
+      <para>Identities are used to associate a name with a particular type in
+        the algebra. In this they correspond to <code>typedef</code>s in C.
+        They are described as follows:
+        <programlisting>
+          <i>identity</i> :
+                  <i>object-identifier</i> = <i>type</i> ;
+        </programlisting>where the definition type, <i>type</i>, is as
+        described <a href="#InputType">below</a>.</para>
+    </sect1>
+
+    <sect1 id="InputEnum">
+      <title>2.3. Enumerations</title>
+  
+      <para>Enumerations are used to define types which can only take values
+        from some finite set. They are described as follows:
+      <programlisting>
+          <i>enumeration</i> :
+                  enum !<i><sub>opt</sub> object-identifier</i> = { <i>enumerator-list</i> } ;
+                  enum !<i><sub>opt</sub> object-identifier</i> = <i>base-enumeration</i> + { 
+  <i>enumerator-list</i> } ;
+      </programlisting>
+      where:
+      <programlisting>
+          <i>base-enumeration</i> :
+                  <i>identifier</i>
+      </programlisting>is the name of a previously defined enumeration type.
+      The latter form is used to express extension enumeration types. An
+      enumeration type may be qualified by an exclamation mark to indicate
+      that no lists of this type will be constructed.</para>
+  
+      <para>The enumeration constants themselves are defined as
+        follows:
+        <programlisting>
+          <i>enumerator</i> :
+                  <i>identifier</i>
+                  <i>identifier</i> = <i>enumerator-value</i>
+  
+          <i>enumerator-list</i> :
+                  <i>enumerator</i>
+                  <i>enumerator-list</i> , <i>enumerator</i>
+        </programlisting>
+        Each enumerator is assigned a value in an ascending sequence, starting
+        at zero. The next value to be assigned can be set using an
+        <i>enumerator-value</i>. This is an expression formed from
+        <i>integer</i>s, <i>identifier</i>s representing previous enumerators
+        from the same enumeration, and the question mark character which
+        stands for the previous enumeration value. The normal C arithmetic
+        operations can be applied to build up more complex
+        <i>enumerator-value</i>s. All enumerator evaluation is done in the
+        <code>unsigned long</code> type of the host machine. Values containing
+        more than 32 bits are not portable.</para>
+  
+      <para>Enumerations thus correspond to enumeration types in C, except
+        that they are genuinely distinct types.</para>
+    </sect1>
+
+    <sect1 id="InputStruct">
+      <title>2.4. Structures</title>
+  
+      <para>Structures are used to build up composite types from other types
+        in the algebra. They correspond to structures in C. They are described
+        as follows:
+        <programlisting>
+          <i>structure</i> :
+                  struct <i>object-identifier</i> = <i>component-group</i> ;
+                  struct <i>object-identifier</i> = <i>base-structure</i> + <i>component-group
+  </i> ;
+        </programlisting>
+        where:
+        <programlisting>
+          <i>base-structure</i> :
+                  <i>identifier</i>
+        </programlisting>is the name of a previously defined structure type.
+        The latter form is used to express (single) inheritance of structures.
+        All components of the base structure also become components of the
+        derived structure.</para>
+  
+      <para>The structure components themselves are defined as follows:
+        <programlisting>
+          <i>component-group</i> :
+                  { <i>component-list<sub>opt</sub></i> }
+  
+          <i>component-list</i> :
+                  <i>component-declarations</i> ;
+                  <i>component-list component-declarations</i> ;
+  
+          <i>component-declarations</i> :
+                  <i>type component-declarators</i>
+  
+          <i>component-declarators</i> :
+                  <i>component-declarator</i>
+                  <i>component-declarators</i> , <i>component-declarator</i>
+  
+          <i>component-declarator</i> :
+                  <i>identifier component-initialiser<sub>opt</sub></i>
+  
+          <i>component-initialiser</i> :
+                  = <i>string</i>
+      </programlisting>The optional <a href="#OutputStruct">component
+        initialiser strings</a> are explained below.</para>
+  
+      <para>Structures are the only algebra construct which prevent the input
+        from being a general graph. Unions may be defined in terms of
+        themselves, but (as in C) pointers must be used to define structures
+        in terms of themselves.</para>
+    </sect1>
+
+    <sect1 id="InputUnion">
+      <title>2.5. Unions</title>
+  
+      <para>Unions are used to build up types which can hold a variety of
+        information. They differ from C unions in that they are discriminated.
+        They are described as follows:
+        <programlisting>
+          <i>union</i> :
+                  union <i>object-identifier</i> = <i>component-group</i> + <i>field-group map-group
+  <sub>opt</sub></i> ;
+                  union <i>object-identifier</i> = <i>base-union</i> + <i>field-group map-group
+  <sub>opt</sub></i> ;
+        </programlisting>
+        where:
+        <programlisting>
+          <i>base-union</i> :
+                  <i>identifier</i>
+        </programlisting>is the name of a previously defined union type. The
+        latter form is used to express (single) inheritance of unions. All
+        components, fields and maps of the base union also become components
+        of the derived union. Note that only new fields and maps can be added
+        in the derived union.</para>
+  
+      <para>The <i>component-group</i> gives a set of components which are
+        common to all the different union cases. The cases themselves are
+        described as follows:
+        <programlisting>
+          <i>field-group</i> :
+                  { <i>field-list</i> }
+  
+          <i>field</i> :
+                  #<i><sub>opt</sub></i> #<i><sub>opt</sub> field-identifier-list</i> -&gt; <i>component-group
+  </i>
+                  #<i><sub>opt</sub></i> #<i><sub>opt</sub> field-identifier-list</i> -&gt; <i>base-field
+  </i> + <i>component-group</i>
+  
+          <i>base-field</i> :
+                  <i>identifier</i>
+  
+          <i>field-list</i> :
+                  <i>field</i>
+                  <i>field-list</i> , <i>field</i>
+  
+          <i>field-identifier</i> :
+                  <i>identifier</i>
+  
+          <i>field-identifier-list</i> :
+                  <i>field-identifier</i>
+                  <i>field-identifier-list</i> , <i>field-identifier</i>
+        </programlisting>
+        The optional one or two hashes which may be used to
+        qualify a list of field identifiers are used to indicate
+        <a href="#DiskAlias">aliasing</a> in the disk reading and writing
+        routines.  The <i>base-field</i> case is a notational convenience
+        which allows one field in a union to inherit all the components of
+        another field.</para>
+  
+      <para>Note that a number of field identifiers may be associated with the
+        same set of field components. Any such list containing more than one
+        identifier forms a field identifier set, named after the first field
+        identifier.</para>
+  
+      <para>In addition a number of maps may be associated with a union.
+        These maps correspond to functions which take the union, plus a number
+        of other map parameter types, and return the map return type. They are
+        described as follows:
+        <programlisting>
+          <i>map-group</i> :
+                  : [ <i>map-list<sub>opt</sub></i> ]
+  
+          <i>map</i> :
+                  <i>extended-type</i> #<i><sub>opt</sub> identifier</i> ( <i>parameter-list
+  <sub>opt</sub></i> )
+  
+          <i>map-list</i> :
+                  <i>map</i>
+                  <i>map-list map</i>
+        </programlisting>where:
+        <programlisting>
+          <i>parameter-list</i> :
+                  <i>parameter-declarations</i>
+                  <i>parameter-list</i> ; <i>parameter-declarations</i>
+  
+          <i>parameter-declarations</i> :
+                  <i>extended-type parameter-declarators</i>
+  
+          <i>parameter-declarators</i> :
+                  <i>identifier</i>
+                  <i>parameter-declarators</i> , <i>identifier</i>
+        </programlisting>Note that the map parameter and return types are
+        given by:
+        <programlisting>
+          <i>extended-type</i> :
+                  <i>type</i>
+                  <i>quoted-type</i>
+        </programlisting>In addition to the <a href="#InputType">types derived
+        from the algebra</a> it is possible to use quoted C types in this
+        context.</para>
+  
+      <para>A map may be qualified by means of a hash. This means that the
+        associated function also takes a
+        <a href="#OutputUnionMaps">destructor function</a>
+        as a parameter.</para>
+    </sect1>
+
+    <sect1 id="InputType">
+      <title>2.6. Type constructors</title>
+  
+      <para>The types derived from the algebra may be described as follows:
+        <programlisting>
+          <i>type</i> :
+                  <i>identifier</i>
+                  PTR <i>type</i>
+                  LIST <i>type</i>
+                  STACK <i>type</i>
+                  VEC <i>type</i>
+                  VEC_PTR <i>type</i>
+        </programlisting>The simple types correspond to primitive, identity,
+        enumeration, structure or union names. It is possible for a type to be
+        used before it is defined, but it must be defined at some
+        point.</para>
+  
+      <para>The derived type constructors correspond to pointers, lists,
+        stacks, vectors and pointers into vectors. They may be used to build
+        up further types from the basic algebra types.</para>
+    </sect1>
+
+    <sect1 id="Module">
+      <title>2.7. Relations between algebras</title>
+  
+      <para>As <a href="#Options">mentioned above</a>, more than one input
+        algebra may be specified to <productname>calculus</productname>. Each
+        is processed separately, and output is generated for only one. By
+        default this is the last algebra processed, however a specific algebra
+        can be specified using the command-line option
+        <option>-A</option><option>name</option>, where <option>name</option>
+        is the name of the algebra to be used for output.</para>
+  
+      <para>Types may be imported from one algebra to another by means of
+        commands of the form:
+        <programlisting>
+          <i>import</i> :
+                  IMPORT <i>identifier</i> ;
+                  IMPORT <i>identifier</i> :: <i>identifier</i> ;
+        </programlisting>which fit into the main syntax as an <i>item</i>. The
+        first form imports all the types from the algebra given by
+        <i>identifier</i> into the current algebra. The second imports a
+        single type, given by the second <i>identifier</i> from the algebra
+        given by the first <i>identifier</i>.</para>
+  
+      <para>Note that importing a type in this way also imports all the types
+        used in its construction. This includes such things as structure
+        components and union fields and maps. Thus an algebra consisting just
+        of <i>import</i> commands can be used to express subalgebras in a
+        simple fashion.</para>
+    </sect1>
+  </chapter>
+  
+  <chapter>
+    <title>Output type system specification</title>
+  
+    <para>In this section we document the basic output of
+      <productname>calculus</productname>. Two forms of the output can be
+      generated - a description of the output specification in terms of the
+      TenDRA <code>#pragma token</code> constructs, and the actual C code
+      which implements these tokens.</para>
+  
+    <para>In this section the description given will be at the level of the
+      output specification. The more important details of the
+      <a href="#COutput">C implementation</a> are given in the following
+      section.</para>
+  
+    <para>The output is split among several header files in the specified
+      output directory. The main output is printed into
+      <filename>name.h</filename>, where <i>name</i> is the overall algebra
+      name. Unless otherwise stated, all the objects specified below are to be
+      found in <i>name</i><code>.h</code>. However for each union,
+      <i>union</i>, in the algebra certain information associated with the
+      union is printed into <i>union</i><code>_ops.h</code>. If the union has
+      any maps associated with it then further output is printed to
+      <filename>union_map.h</filename> and <filename>union_hdr.h</filename>.
+      </para>
+
+    <sect1 id="OutputInfo">
+      <title>3.1. Version information</title>
+  
+      <para>Certain basic information about the input algebra is included in
+        <i>name</i><code>.h</code>. <i>name</i><code>_NAME</code> is a string
+        literal giving the overall algebra name.
+        <i>name</i><code>_VERSION</code> is a string literal giving the
+        algebra version number. <i>name</i><code>_SPECIFICATION</code> and
+        <i>name</i><code>_IMPLEMENTATION</code> are flags which take the
+        values 0 or 1 depending on whether the specification of the type
+        system in terms of <code>#pragma token</code> statements or the C
+        implementation is included.</para>
+    </sect1>
+
+    <sect1 id="OutputBasic">
+      <title>3.2. Basic types</title>
+  
+      <para>Six abstract type operators, each taking a type as argument and
+        returning a type, are specified as follows:
+        <programlisting>
+          TYPE PTR ( TYPE <i>t</i> );
+          TYPE LIST ( TYPE <i>t</i> ) ;
+          TYPE STACK ( TYPE <i>t</i> ) ;
+          TYPE VEC ( TYPE <i>t</i> ) ;
+          TYPE VEC_PTR ( TYPE <i>t</i> ) ;
+          TYPE SIZE ( TYPE <i>t</i> ) ;
+        </programlisting>These represent a pointer to an object of type
+        <i>t</i>, a list of objects of type <i>t</i>, a stack of objects of
+        type <i>t</i>, a vector of objects of type <i>t</i>, a pointer into a
+        vector of objects of type <i>t</i>, and an allocation block size for
+        type <i>t</i> respectively. (It is possible to suppress all constructs
+        involving <code>VEC</code> or <code>VEC_PTR</code> by passing the
+        <code>-x</code> command-line option to
+        <productname>calculus</productname>. Similarly <code>STACK</code>
+        constructs may be suppressed using <code>-z</code>.)</para>
+  
+      <para>These constructors can be applied to any type, although in
+        practice they are only applied to the types specified in the algebra
+        and those derived from them. For example, we may form the type:
+        <programlisting>
+          LIST ( PTR ( int ) )
+        </programlisting>representing a list of pointers to
+        <code>int</code>.</para>
+  
+      <para>An integral type:
+        <programlisting>
+          INT_TYPE <i>name</i>_dim ;
+        </programlisting>is specified, where <i>name</i> is the overall
+        algebra name.  This type is used to represent the sizes of
+        vectors.</para>
+  
+      <para>A function pointer type:
+        <programlisting>
+          typedef void ( *DESTROYER ) () ;
+        </programlisting>is specified, which represents a destructor function.
+        Two destructor functions are specified:
+        <programlisting>
+          void destroy_<i>name</i> () ;
+          void dummy_destroy_<i>name</i> () ;
+        </programlisting>where <i>name</i> is as above.
+        <code>destroy_</code><i>name</i> is the default destructor, whereas
+        <code>dummy_destroy_</code><i>name</i> is a dummy destructor which has
+        no effect. The details of the arguments passed to the destructors and
+        so on are implementation dependent.</para>
+    </sect1>
+
+    <sect1 id="OutputSize">
+      <title>3.3. Operations on sizes</title>
+  
+      <para>The <code>SIZE</code> type constructor is used to represent a
+        multiple of the size of a type. It is used, for example, in the <a
+        href="#OutputPtr">pointer stepping construct</a> <code>STEP_ptr</code>
+        to specify the number of units the pointer is to be increased by.
+        Having a separate abstract type for the size of each type greatly
+        increases the scope for type checking of memory allocation, and other,
+        functions.</para>
+  
+      <para>For each basic type in the algebra (a primitive, a structure or a
+        union), there is a constant expression:
+        <programlisting>
+          SIZE ( <i>t</i> ) SIZE_<i>type</i> ;
+        </programlisting>
+        where <i>t</i> denotes the type itself, and <i>type</i> is the
+        associated type name.</para>
+  
+      <para>For the five other type constructors
+        <a href="#OutputBasic">described above</a> there are constant
+        expressions:
+        <programlisting>
+          SIZE ( PTR ( <i>t</i> ) ) SIZE_ptr ( TYPE <i>t</i> ) ;
+          SIZE ( LIST ( <i>t</i> ) ) SIZE_list ( TYPE <i>t</i> ) ;
+          SIZE ( STACK ( <i>t</i> ) ) SIZE_stack ( TYPE <i>t</i> ) ;
+          SIZE ( VEC ( <i>t</i> ) ) SIZE_vec ( TYPE <i>t</i> ) ;
+          SIZE ( VEC_PTR ( <i>t</i> ) ) SIZE_vec_ptr ( TYPE <i>t</i> ) ;
+        </programlisting>for any type <i>t</i>.</para>
+  
+      <para>These constructs allow the size of any type derived from the
+        algebra to be built up. There is also a construct which corresponds to
+        multiplying the size of a type by a constant. This takes the
+        form:
+        <programlisting>
+          SIZE ( <i>t</i> ) SCALE ( SIZE ( <i>t</i> ), INT_TYPE <i>itype</i> ) ;
+        </programlisting>
+        for any type <i>t</i> and any integral type <i>itype</i>.</para>
+    </sect1>  
+
+    <sect1 id="OutputPtr">
+      <title>3.4. Operations on pointers</title>
+  
+      <para>The <code>PTR</code> type constructor is used to represent a
+        pointer to an object of type <i>t</i>. It should be emphasised that
+        this construct is not in general implemented by means of the C pointer
+        construct.</para>
+  
+      <sect2>
+        <title>Simple pointer constructs</title>
+  
+        <para>There are several simple operations on pointers, given as
+          follows:
+          <programlisting>
+          PTR ( <i>t</i> ) NULL_ptr ( TYPE <i>t</i> ) ;
+          int IS_NULL_ptr ( PTR ( <i>t</i> ) ) ;
+          int EQ_ptr ( PTR ( <i>t</i> ), PTR ( <i>t</i> ) ) ;
+          PTR ( <i>t</i> ) STEP_ptr ( PTR ( <i>t</i> ), SIZE ( <i>t</i> ) ) ;
+          </programlisting>
+          The construct <code>NULL_ptr</code> is used to form the null pointer
+          to <i>t</i> for a type <i>t</i>. This is a constant expression.
+          <code>IS_NULL_ptr</code> can be used to test whether a given pointer
+          expression is a null pointer. Similarly <code>EQ_ptr</code> checks
+          whether two pointers are equal (note that we can only compare
+          pointers to the same type). Finally <code> STEP_ptr</code> can be
+          used to add a scalar value to a pointer.</para>
+      </sect2>
+  
+      <sect2>
+        <title>Unique pointers</title>
+  
+        <para>There are also constructs for generating and destroying unique
+          pointers:
+          <programlisting>
+          PTR ( <i>t</i> ) UNIQ_ptr ( TYPE <i>t</i> ) ;
+          void DESTROY_UNIQ_ptr ( PTR ( <i>t</i> ) ) ;
+          </programlisting>A unique pointer is guaranteed to be different from
+          all other undestroyed pointers. Dereferencing a unique pointer is
+          undefined.</para>
+      </sect2>
+  
+      <sect2>
+        <title>Pointer construction and destruction</title>
+  
+        <para>The constructs:
+          <programlisting>
+          PTR ( <i>t</i> ) MAKE_ptr ( SIZE ( <i>t</i> ) ) ;
+          void DESTROY_ptr ( PTR ( <i>t</i> ), SIZE ( <i>t</i> ) ) ;
+          </programlisting>
+          are used to respectively create and destroy a pointer to a given
+          type.</para>
+      </sect2>
+  
+      <sect2>
+        <title>Assignment and dereference constructs</title>
+  
+        <para>The constructs for assigning and dereferencing pointers have one
+          of two forms depending on the complexity of the type pointed to. For
+          simple types, including primitive, enumeration and union types, they
+          have the form:
+        <programlisting>
+          void COPY_<i>type</i> ( PTR ( <i>t</i> ), <i>t</i> ) ;
+          <i>t</i> DEREF_<i>type</i> ( PTR ( <i>t</i> ) ) ;
+        </programlisting>
+        where <i>t</i> is the type involved and <i>type</i> is the associated
+        short name.</para>
+  
+        <para>For more complex types, including structures, the assignment or
+          dereference cannot be done in a single expression, so the constructs
+          are specified to be statements as follows:
+          <programlisting>
+          STATEMENT COPY_<i>type</i> ( PTR ( <i>t</i> ), <i>t</i> ) ;
+          STATEMENT DEREF_<i>type</i> ( PTR ( <i>t</i> ), lvalue <i>t</i> ) ;
+          </programlisting>
+          Here the <code>lvalue</code> type qualifier is used to indicate that
+          the statement argument is an assignable <code>lvalue</code>. In this
+          case it should give the location of an object of type <i>t</i> into
+          which the pointer will be dereferenced.</para>
+  
+        <para>The appropriate assignment and dereference constructs are
+          generated for each of the basic algebra types (primitives,
+          enumerations, structures and unions). In addition there are generic
+          assignment and dereference constructs for pointer types, list types,
+          stack types, vector types and vector pointer types.  The first three
+          are of the first form above, whereas the second two have the second
+          form, as follows:
+          <programlisting>
+          void COPY_ptr ( PTR ( PTR ( <i>t</i> ) ), PTR ( <i>t</i> ) ) ;
+          PTR ( <i>t</i> ) DEREF_ptr ( PTR ( PTR ( <i>t</i> ) ) ) ;
+          void COPY_list ( PTR ( LIST ( <i>t</i> ) ), LIST ( <i>t</i> ) ) ;
+          LIST ( <i>t</i> ) DEREF_list ( PTR ( LIST ( <i>t</i> ) ) ) ;
+          void COPY_stack ( PTR ( STACK ( <i>t</i> ) ), STACK ( <i>t</i> ) ) ;
+          STACK ( <i>t</i> ) DEREF_stack ( PTR ( STACK ( <i>t</i> ) ) ) ;
+          STATEMENT COPY_vec ( PTR ( VEC ( <i>t</i> ) ), VEC ( <i>t</i> ) ) ;
+          STATEMENT DEREF_vec ( PTR ( VEC ( <i>t</i> ) ), lvalue VEC ( <i>t</i> ) ) ;
+          STATEMENT COPY_vec_ptr ( PTR ( VEC_PTR ( <i>t</i> ) ), VEC_PTR ( <i>t</i> ) ) ;
+          STATEMENT DEREF_vec_ptr ( PTR ( VEC_PTR ( <i>t</i> ) ), lvalue VEC_PTR ( <i>t
+  </i> ) ) ;
+          </programlisting>
+        </para>
+      </sect2>
+    </sect1>
+
+    <sect1 id="OutputList">
+      <title>3.5. Operations on lists</title>
+  
+      <para>The <code>LIST</code> type constructor is used to represent a list
+        of objects of type <i>t</i>.</para>
+  
+      <sect2>
+        <title>Simple list constructs</title>
+  
+        <para>There are several simple list constructs:
+          <programlisting>
+          LIST ( <i>t</i> ) NULL_list ( TYPE <i>t</i> ) ;
+          int IS_NULL_list ( LIST ( <i>t</i> ) ) ;
+          int EQ_list ( LIST ( <i>t</i> ), LIST ( <i>t</i> ) ) ;
+          unsigned LENGTH_list ( LIST ( <i>t</i> ) ) ;
+          PTR ( <i>t</i> ) HEAD_list ( LIST ( <i>t</i> ) ) ;
+          LIST ( <i>t</i> ) TAIL_list ( LIST ( <i>t</i> ) ) ;
+          PTR ( LIST ( <i>t</i> ) ) PTR_TAIL_list ( LIST ( <i>t</i> ) ) ;
+          LIST ( <i>t</i> ) END_list ( LIST ( <i>t</i> ) ) ;
+          LIST ( <i>t</i> ) REVERSE_list ( LIST ( <i>t</i> ) ) ;
+          LIST ( <i>t</i> ) APPEND_list ( LIST ( <i>t</i> ), LIST ( <i>t</i> ) ) ;
+          </programlisting>
+          Empty lists may be constructed or tested for.
+          <code>NULL_list</code> is a constant expression. Two lists may be
+          checked for equality (note that this is equality of lists, rather
+          than element-wise equality).  The number of elements in a list can
+          be found. The head or tail (or <code>car</code> and
+          <code>cdr</code>) of a list may be formed. The end element of a list
+          may be selected. The order of the elements in a list can be
+          reversed. One list can be appended to another.</para>
+      </sect2>
+  
+      <sect2>
+        <title>Unique lists</title>
+  
+        <para>There are also constructs for generating and destroying unique
+          lists:
+          <programlisting>
+          LIST ( <i>t</i> ) UNIQ_list ( TYPE <i>t</i> ) ;
+          void DESTROY_UNIQ_list ( LIST ( <i>t</i> ) ) ;
+          </programlisting>
+          A unique lists is guaranteed to be different from all other
+          undestroyed lists. Taking the head or tail of a unique list is
+          undefined.</para>
+      </sect2>
+  
+      <sect2>
+        <title>List construction and destruction</title>
+  
+        <para>For each type <i>t</i> there are operations for constructing and
+          deconstructing lists. For the basic types comprising the algebra
+          these take the form:
+          <programlisting>
+          STATEMENT CONS_<i>type</i> ( <i>t</i>, LIST ( <i>t</i> ), lvalue LIST ( <i>t
+  </i> ) ) ;
+          STATEMENT UN_CONS_<i>type</i> ( lvalue <i>t</i>, lvalue LIST ( <i>t</i> ), LIST ( 
+  <i>t</i> ) ) ;
+          STATEMENT DESTROY_CONS_<i>type</i> ( DESTROYER, lvalue <i>t</i>, lvalue LIST ( 
+  <i>t</i> ), LIST ( <i>t</i> ) ) ;
+          </programlisting>
+          where <i>type</i> is the short type name.</para>
+  
+        <para>The operation <code>CONS_</code><i>type</i> is used to build a
+          list whose head is the first argument and whose tail is the second
+          argument. This is assigned to the third argument.
+          <code>UN_CONS_</code><i>type</i> reverses this process, decomposing
+          a list into its head and its tail.
+          <code>DESTROY_CONS_</code><i>type</i> is similar, but it also
+          applies the given destructor function to the decomposed list
+          component.</para>
+  
+        <para>There are also generic list construction and deconstruction
+          operations which apply to lists of pointers (with a <code>ptr</code>
+          suffix), lists of lists (with a <code>list</code> suffix), lists of
+          stacks (with a <code>stack</code> suffix), lists of vectors (with a
+          <code>vec</code> suffix) and lists of pointers to vectors (with a
+          <code>vec_ptr</code> suffix). For example, for lists of pointers
+          these have the form:
+          <programlisting>
+          STATEMENT CONS_ptr ( PTR ( <i>t</i> ), LIST ( PTR ( <i>t</i> ) ), lvalue LIST ( PTR ( 
+  <i>t</i> ) ) ) ;
+          STATEMENT UN_CONS_ptr ( lvalue PTR ( <i>t</i> ), lvalue LIST ( PTR ( <i>t</i> ) ), LIST ( PTR ( 
+  <i>t</i> ) ) ) ;
+          STATEMENT DESTROY_CONS_ptr ( DESTROYER, lvalue PTR ( <i>t</i> ), lvalue LIST ( PTR ( 
+  <i>t</i> ) ), LIST ( PTR ( <i>t</i> ) ) ) ;
+          </programlisting>
+          There is also a generic list destruction construct:
+          <programlisting>
+          STATEMENT DESTROY_list ( LIST ( <i>t</i> ), SIZE ( <i>t</i> ) ) ;
+          </programlisting>
+          which may be used to destroy all the elements in a list.</para>
+      </sect2>
+    </sect1>
+
+    <sect1 id="OutputStack">
+      <title>3.6. Operations on stacks</title>
+  
+      <para>The <code>STACK</code> type constructor is used to represent
+        stacks of objects of type <i>t</i>. Empty stacks can be created and
+        tested for:
+        <programlisting>
+          STACK ( <i>t</i> ) NULL_stack ( TYPE <i>t</i> ) ;
+          int IS_NULL_stack ( STACK ( <i>t</i> ) ) ;
+        </programlisting>
+        For each type <i>t</i> there are operations for pushing objects onto a
+        stack and for popping elements off. For the basic types comprising the
+        algebra these take the form:
+        <programlisting>
+          STATEMENT PUSH_<i>type</i> ( <i>t</i>, lvalue STACK ( <i>t</i> ) ) ;
+          STATEMENT POP_<i>type</i> ( lvalue <i>t</i>, lvalue STACK ( <i>t</i> ) ) ;
+        </programlisting>
+        where <i>type</i> is the short type name. There are also generic
+        constructs, such as <code>PUSH_ptr</code> for pushing any pointer
+        type, similar to the <a href="#OutputList">generic list
+        constructors</a> above.</para>
+  
+      <para>Stacks are in fact just modified lists with pushing corresponding
+        adding an element to the start of a list, and popping to removing the
+        first element. There are constructs:
+        <programlisting>
+          LIST ( <i>t</i> ) LIST_stack ( STACK ( <i>t</i> ) ) ;
+          STACK ( <i>t</i> ) STACK_list ( LIST ( <i>t</i> ) ) ;
+        </programlisting>
+        for explicitly converting between lists and stacks.</para>
+    </sect1>
+
+    <sect1 id="OutputVec">
+      <title>3.7. Operations on vectors</title>
+  
+      <para>The <code>VEC</code> type constructor is used to represent vectors
+        of objects of type <i>t</i>. There are a number of simple operations
+        on vectors:
+        <programlisting>
+          VEC ( <i>t</i> ) NULL_vec ( TYPE <i>t</i> ) ;
+          <i>name</i>_dim DIM_vec ( VEC ( <i>t</i> ) ) ;
+          <i>name</i>_dim DIM_ptr_vec ( PTR ( VEC ( <i>t</i> ) ) ) ;
+          PTR ( <i>t</i> ) PTR_ptr_vec ( PTR ( VEC ( <i>t</i> ) ) ) ;
+        </programlisting>
+        An empty vector can be constructed (note that, unlike null pointers
+        and null lists, this is not a constant expression). The number of
+        elements in a vector (or in a vector given by a pointer) can be
+        determined (note how the type <i>name</i><code>_dim</code> is used to
+        represent vector sizes). A pointer to a vector can be transformed into
+        a pointer to the elements of the vector.</para>
+  
+      <para>In general a vector may be created or destroyed using the
+        operators:
+        <programlisting>
+          STATEMENT MAKE_vec ( SIZE ( <i>t</i> ), <i>name</i>_dim, lvalue VEC ( <i>t</i> ) ) ;
+          STATEMENT DESTROY_vec ( VEC ( <i>t</i> ), SIZE ( <i>t</i> ) ) ;
+        </programlisting>
+        Finally a vector can be trimmed using:
+        <programlisting>
+          STATEMENT TRIM_vec ( VEC ( <i>t</i> ), SIZE ( <i>t</i> ), int, int, lvalue VEC ( 
+  <i>t</i> ) ) ;
+        </programlisting>
+        the two integral arguments giving the lower and upper bounds for the
+        trimming operation.</para>
+    </sect1>
+
+    <sect1 id="OutputVecPtr">
+      <title>3.8. Operations on vector pointers</title>
+  
+      <para>The <code>VEC_PTR</code> type constructor is used to represent a
+        pointer to an element of a vector of objects of type <i>t</i>.  Apart
+        from the basic constructors already mentioned, there are only two
+        operations on vector pointers:
+        <programlisting>
+          VEC_PTR ( <i>t</i> ) VEC_PTR_vec ( VEC ( <i>t</i> ) ) ;
+          PTR ( <i>t</i> ) PTR_vec_ptr ( VEC_PTR ( <i>t</i> ) ) ;
+        </programlisting>
+        The first transforms a vector into a vector pointer (pointing to its
+        first argument). The second transforms a vector pointer into a normal
+        pointer.</para>
+    </sect1>
+
+    <sect1 id="OutputPrim">
+      <title>3.9. Operations on primitives</title>
+  
+      <para>Each primitive specified within the algebra maps onto a
+        <code>typedef</code> defining the type in terms of its given
+        definition.  The only operations on primitives are those listed above
+        - the size constructs, the pointer assignment and dereference
+        operations, the list construction and deconstruction operations and
+        the stack push and pop operations.</para>
+    </sect1>
+
+    <sect1 id="OutputIdent">
+      <title>3.10. Operations on identities</title>
+  
+      <para>Each identity specified within the algebra maps onto a
+        <code>typedef</code> in the output file. There are no operations on
+        identities.</para>
+    </sect1>
+
+    <sect1 id="OutputEnum">
+      <title>3.11. Operations on enumerations</title>
+  
+      <para>Each enumeration specified within the algebra maps onto an
+        unsigned integral type in the output file. The
+        <a href="#OutputPrim">basic operations</a> listed above are always
+        generated unless it has been indicated that
+        <a href="#InputEnum">no lists of this type will be formed</a>, when
+        <code>CONS_</code><i>type</i> and the other list and stack operators
+        are suppressed. In addition each enumerator which is a member of this
+        enumeration maps onto a constant expression:
+        <programlisting>
+          <i>t enum_member</i> ;
+        </programlisting>
+        where <i>t</i> is the enumeration type, <i>enum</i> is the short type
+        name, and <i>member</i> is the enumerator name. It is guaranteed that
+        the first enumerator will have value 0, the second 1, and so on,
+        unless the value of the enumerator is explicitly given (as in C).
+        There is also a constant expression:
+        <programlisting>
+          unsigned long ORDER_<i>enum</i> ;
+        </programlisting>
+        giving one more than the maximum enumerator in the enumeration.</para>
+    </sect1>
+
+    <sect1 id="OutputStruct">
+      <title>3.12. Operations on structures</title>
+  
+      <para>Each structure specified within the algebra maps onto a
+        <code>typedef</code> defining the type to be the C structure with the
+        given components. In addition to the <a href= "#OutputPrim">basic
+        operations</a> listed above there are also field selectors
+        defined.</para>
+  
+      <para>Suppose that <i>t</i> is a structure type with short name
+        <i>struct</i>, and that <i>comp</i> is a component of <i>t</i> of type
+        <i>ctype</i>. Then there is an operation:
+        <programlisting>
+          PTR ( <i>ctype</i> ) <i>struct_comp</i> ( PTR ( <i>t</i> ) ) ;
+        </programlisting>
+        which transforms a pointer to the structure into a pointer to the
+        component. There is also an operation:
+        <programlisting>
+          STATEMENT MAKE_<i>struct</i> ( <i>ctype</i>, ...., PTR ( <i>t</i> ) ) ;
+        </programlisting>
+        where <i>ctype</i> ranges over all the component types which do not
+        have a component initialiser string in the structure definition. This
+        is used to assign values to all the components of a structure. If a
+        component has an initialiser string then this is used as an expression
+        giving the initial value, otherwise the given operation argument is
+        used. The initialiser strings are evaluated in the context of the
+        <code>MAKE_</code><i>struct</i> statement.  The parameters to the
+        operation may be referred to by the corresponding component name
+        followed by <code>_</code>. The partially initialised object may be
+        referred to by the special character sequence <code>%0</code>. Any
+        remainder operations should be written as <code>%%</code> rather than
+        <code>%</code>.</para>
+  
+      <para>Inheritance in structures is handled as follows: if <i>t</i> is a
+        derived structure with base structure <i>btype</i> then there is an
+        operation:
+        <programlisting>
+          PTR ( <i>btype</i> ) CONVERT_<i>struct_base</i> ( PTR ( <i>t</i> ) ) ;
+        </programlisting>
+        where <i>struct</i> and <i>base</i> are the short names of <i>t</i>
+        and <i>btype</i> respectively.</para>
+    </sect1>
+    
+    <sect1 id="OutputUnion">
+      <title>3.13. Operations on unions</title>
+  
+      <para>Each union specified within the algebra maps onto an opaque type
+        in the output file. In addition to the <a href= "#OutputPrim">basic
+        operations</a> listed above there are a number of other constructs
+        output into <i>name</i><code>.h</code>, namely:
+        <programlisting>
+          unsigned int ORDER_<i>union</i> ;
+          <i>t</i> NULL_<i>union</i> ;
+          int IS_NULL_<i>union</i> ( <i>t</i> ) ;
+          int EQ_<i>union</i> ( <i>t</i>, <i>t</i> ) ;
+        </programlisting>
+        where <i>t</i> denotes the union type, and <i>union</i> is the short
+        type name. <code>ORDER_</code><i>union</i> is a constant value giving
+        the number of union fields.  <code>NULL_</code><i>union</i> is a
+        distinguished constant value of type <i>t</i>. Values of type <i>t</i>
+        may be compared against this distinguished value, or against each
+        other.</para>
+  
+      <sect2>
+        <title>Union construction operations</title>
+  
+        <para>Most of the output for the union type <i>t</i> is output into
+          the file <filename>union_ops.h</filename>. This contains a
+          construct:
+          <programlisting>
+          unsigned int TAG_<i>union</i> ( <i>t</i> ) ;
+          </programlisting>
+          for extracting the discriminant tag from a union.</para>
+  
+        <para>For each shared component, <i>comp</i>, of <i>t</i> of type
+          <i>ctype</i>, say, there is an operator:
+          <programlisting>
+          PTR ( <i>ctype</i> ) <i>union_comp</i> ( <i>t</i> ) ;
+          </programlisting>
+          which extracts this component from the union.</para>
+  
+        <para>For each field, <i>field</i>, of the union there are
+          constructs:
+          <programlisting>
+          unsigned int <i>union_field</i>_tag ;
+          int IS_<i>union_field</i> ( <i>t</i> ) ;
+          </programlisting>
+          giving the (constant) discriminant tag associated with this field,
+          and a test for whether an object of type <i>t</i> has this
+          discriminant.</para>
+  
+        <para>In addition, for each unshared component, <i>comp</i>, of
+          <i>field</i> of type <i>ctype</i>, say, there is an operator:
+          <programlisting>
+          PTR ( <i>ctype</i> ) <i>union_field_comp</i> ( <i>t</i> ) ;
+          </programlisting>
+          which extracts this component from the union.</para>
+  
+        <para>There are also operations for constructing and deconstructing
+          objects of type <i>t</i> for field <i>field</i> given as
+          follows:
+          <programlisting>
+          STATEMENT MAKE_<i>union_field</i> ( <i>ctype</i>, ...., lvalue <i>t</i> ) ;
+          STATEMENT DECONS_<i>union_field</i> ( lvalue <i>ctype</i>, ...., <i>t</i> ) ;
+          STATEMENT DESTROY_<i>union_field</i> ( DESTROYER, lvalue <i>ctype</i>, ...., 
+  <i>t</i> ) ;
+          </programlisting>
+          The operation <code>MAKE_</code><i>union_field</i> constructs a
+          value of type <i>t</i> from the various components and assigns it
+          into the last argument. The <i>ctype</i> arguments range over all
+          the components of <i>field</i>, both the shared components and the
+          unshared components, which do not have a component initialiser
+          string in the definition. The union component are initialised either
+          using the <a href="#OutputStruct">initialiser string</a> or the
+          given operation argument.</para>
+  
+        <para><code>DECONS_</code><i>union_field</i> performs the opposite
+          operation, deconstructing an object of type <i>t</i> into its
+          components for this field.  <code>DESTROY_</code><i>union_field</i>
+          is similar, except that it also applies the given destructor
+          function to the original value. For these two operations
+          <i>ctype</i> ranges over all the components, including those with
+          initialiser strings.</para>
+      </sect2>
+  
+      <sect2>
+        <title>Union field sets</title>
+  
+        <para>Recall that <a href="#InputUnion">a number of union field
+          identifiers</a> may be associated with the same set of components.
+          In this case these fields form a union field set named after the
+          first element of the set. There are operations:
+          <programlisting>
+          int IS_<i>union_field</i>_etc ( <i>t</i> ) ;
+          PTR ( <i>ctype</i> ) <i>union_field</i>_etc_<i>comp</i> ( <i>t</i> ) ;
+          STATEMENT MAKE_<i>union_field</i>_etc ( unsigned int, <i>ctype</i>, ...., lvalue 
+  <i>t</i> ) ;
+          STATEMENT MODIFY_<i>union_field</i>_etc ( unsigned int, <i>t</i> ) ;
+          STATEMENT DECONS_<i>union_field</i>_etc ( lvalue <i>ctype</i>, ...., <i>t</i> ) ;
+          STATEMENT DESTROY_<i>union_field</i>_etc ( DESTROYER, lvalue <i>ctype</i>, ...., 
+  <i>t</i> ) ;
+          </programlisting>
+          defined on these sets. These are exactly analogous to the single
+          field operations except that they work for any field in the set.
+          Note that <code>MAKE_</code><i>union_field</i><code>_etc</code>
+          takes an extra argument, giving the tag associated with the
+          particular element of the set being constructed. Also the construct
+          <code>MODIFY_</code><i>union_field</i><code>_etc</code> is
+          introduced to allow the tag of an existing object to be modified to
+          another value within the same set.</para>
+  
+        <para>The valid range of union tags for this set can be given by the
+          two constants:
+          <programlisting>
+          unsigned int <i>union_field</i>_tag ;
+          unsigned int <i>union_field</i>_etc_tag ;
+          </programlisting>
+          A union is a member of this set if its tag is greater than or equal
+          to <i>union_field</i><code>_tag</code> and strictly less than
+          <i>union_field</i><code>_etc_tag</code>.</para>
+      </sect2>
+  
+      <sect2>
+        <title>Inheritance in unions</title>
+  
+        <para>Inheritance in unions is handled as follows: if <i>t</i> is a
+          derived union with base union <i>btype</i> then there is an
+          operation:
+          <programlisting>
+          <i>btype</i> CONVERT_<i>union_base</i> ( <i>t</i> ) ;
+          </programlisting>
+          where <i>union</i> and <i>base</i> are the short names of <i>t</i>
+          and <i>btype</i> respectively.</para>
+      </sect2>
+  
+      <sect2 id="OutputUnionMaps">
+        <title>Union maps</title>
+
+        <para>For each map, <i>map</i>, on the union <i>t</i>, we have
+          declared in <i>union</i><code>_ops.h</code> an operator:
+          <programlisting>
+          <i>map_ret map_union</i> ( <i>t</i>, <i>map_par</i>, .... ) ;
+          </programlisting>
+          where <i>map_ret</i> is the map return type and <i>map_par</i>
+          ranges over the map parameter types. This is except for maps with
+          destructors (i.e. those qualified by a <a href= "#InputUnion">hash
+          symbol</a>) which have the form:
+          <programlisting>
+          <i>map_ret map_union</i> ( <i>t</i>, DESTROYER, <i>map_par</i>, .... ) ;
+          </programlisting>
+          These maps are implemented by having one function per field for each
+          map. The output file <i>union</i><code>_map.h</code> contains tables
+          of these functions. These have the form:
+          <programlisting>
+          <i>map_ret</i> ( *<i>map_union</i>_table [ ORDER_<i>union</i> ] ) ( <i>t</i>, 
+  <i>map_par</i>, .... ) = {
+                  ....
+                  <i>map_union_field</i>,
+                  ....
+          } ;
+          </programlisting>
+          where there is one entry per union field.</para>
+  
+        <para>In order to aid the construction of these functions a set of
+          function headers is provided in <i>union</i><code>_hdr.h</code>.
+          These take the form:
+          <programlisting>
+          #define HDR_<i>map_union_field</i>\
+                  <i>map_ret map_union_field</i> ( <i>name_union</i>, <i>destroyer</i>, <i>par
+  </i>, .... )\
+                  <i>t name_union</i> ;\
+                  DESTROYER <i>destroyer</i> ; /* if required */\
+                  <i>map_par par</i> ;\
+                  ....\
+                  {\
+                          <i>ctype comp</i> ;\
+                          ....\
+                          DECONS_<i>union_field</i> ( <i>comp</i>, ...., <i>name_union</i> ) ;
+          </programlisting>
+          There is also an alternative function header,
+          <code>HDR_</code><i>map</i>_d_<i>union_field</i>, which calls
+          <code>DESTROY_</code><i>union_field</i> rather than
+          <code>DECONS_</code><i>union_field</i>. The destructor function used
+          is <i>destroyer</i>, if this parameter is present, or the default
+          destructor, <code>destroy_</code><i>name</i>, otherwise.</para>
+      </sect2>
+    </sect1>
+  </chapter>
+  
+  <chapter>
+    <title>Implementation details</title>
+
+    <sect1 id="COutputTypes">
+      <title>4.1. Implementation of types</title>
+  
+      <para>The C implementation of the type system
+        <a href="#TokenOutput">specified above</a> is based on a single type,
+        <i>name</i>, with the same name as the input algebra. This is defined
+        as follows:
+        <programlisting>
+          typedef union <i>name</i>_tag {
+                  unsigned int ag_tag ;
+                  union <i>name</i>_tag *ag_ptr ;
+                  unsigned ag_enum ;
+                  unsigned long ag_long_enum ;
+                  <i>name</i>_dim ag_dim ;
+                  <i>t</i> ag_prim_<i>type</i> ;
+                  ....
+          } <i>name</i> ;
+        </programlisting>
+        where <i>t</i> runs over all the primitive types. All of the types in
+        the algebra can be packed into a block of cells of type <i>name</i>.
+        The following paragraphs describe the implementation of each type,
+        together with how they are packed as blocks of cells.  This is
+        illustrated by the following diagram:
+  
+      <img src="../images/calc.gif" alt="Packing of types" />
+        </para>
+  
+      <para>Primitive types are implemented by a <code>typedef</code> defining
+        the type in terms of its <a href="#OutputPrim">given definition</a>. A
+        primitive type can be packed into a single cell using the appropriate
+        <code>ag_prim_</code><i>type</i> field of the union.</para>
+  
+      <para>Identity types are implemented by a <code>typedef</code> defining
+        the type as being equal to another <a href="#OutputIdent">type from
+        the algebra</a>.</para>
+    
+      <para>Enumeration types are all implemented as <code>unsigned int</code>
+        if all its values fit into 16 bits, or <code>unsigned long</code>
+        otherwise. An enumeration type can be packed into a single cell using
+        the <code>ag_enum</code> or <code>ag_long_enum</code> field of the
+        union.</para>
+    
+      <para>Structure types are implemented by a <code>typedef</code> defining
+        the type to be the C structure with the <a href="#OutputStruct">given
+        components</a>. A structure type may be packed into a block of cells
+        by packing each of the components in turn.</para>
+    
+      <para>Union types are all implemented by a pointer to <i>name</i>.  This
+        pointer references a block of cells. The null pointer represents
+        <code>NULL_</code><i>union</i>, otherwise the first cell contains the
+        union discriminant tag (in the <code>ag_tag</code> field), with the
+        subsequent cells containing the packed field components (shared
+        components first, then unshared components). If the union has only one
+        field then the discriminant can be omitted. The union itself can be
+        packed into a single cell using the <code>ag_ptr</code> field of the
+        union.</para>
+  
+      <para>Pointer types are all implemented by a pointer to <i>name</i>.
+        Null pointers represent <code>NULL_ptr</code>, otherwise the pointer
+        references a single cell. This cell contains a pointer to the packed
+        version of the object being pointed to in its <code>ag_ptr</code>
+        field. A pointer type itself can be packed into a single cell using
+        the <code>ag_ptr</code> field of the union.</para>
+    
+      <para>List types are all implemented by a pointer to <i>name</i>.  Null
+        pointers represent <code>NULL_list</code>, otherwise the pointer
+        references a block of two cells. The first cell gives the tail of the
+        list in its <code>ag_ptr</code> field; the second cell contains a
+        pointer to the packed version of the head of the list in its
+        <code>ag_ptr</code> field. A list type itself can be packed into a
+        single cell using the <code>ag_ptr</code> field of the union.</para>
+    
+      <para>Stack types are identical to list types, with the head of the list
+        corresponding to the top of the stack.</para>
+    
+      <para>Vector pointer and vector types are all implemented by structures
+        defined as follows:
+        <programlisting>
+          typedef unsigned int <i>name</i>_dim ;
+  
+          typedef struct {
+                  <i>name</i> *vec ;
+                  <i>name</i> *ptr ;
+          } <i>name</i>_VEC_PTR ;
+  
+          typedef struct {
+                  <i>name</i>_dim dim ;
+                  <i>name</i>_VEC_PTR elems ;
+          } <i>name</i>_VEC ;
+        </programlisting>
+        The <code>vec</code> field of a vector pointer contains a pointer to a
+        block of cells containing the packed versions of the elements of the
+        vector. The <code>ptr</code> field is a pointer to the current element
+        of this block. A vector type also has a field giving the vector size.
+        A vector pointer type can be packed into a block of two cells, using
+        the <code>ag_ptr</code> field of each to hold its two components. A
+        vector type can similarly be packed into a block of three cells, the
+        first holding the vector size in its <code>ag_dim</code> field.</para>
+  
+      <para>All size types are implemented as <code>int</code>.</para>
+    </sect1>  
+
+    <sect1 id="COutputSupport">
+      <title>4.2. Support routines</title>
+  
+      <para>The implementation requires the user to provide certain support
+        functions. Most fundamental are the routines for allocating and
+        deallocating the blocks of cells which are used to store the types.
+        These are specified as follows:
+        <programlisting>
+          <i>name</i> *gen_<i>name</i> ( unsigned int ) ;
+          void destroy_<i>name</i> ( <i>name</i> *, unsigned int ) ;
+          void dummy_destroy_<i>name</i> ( <i>name</i> *, unsigned int ) ;
+        </programlisting>
+        where <code>gen_</code><i>name</i> allocates a block of cells of the
+        given size, <code>destroy_</code><i>name</i> deallocates the given
+        block, and <code>dummy_destroy_</code><i>name</i> has <a
+        href="#OutputBasic">no effect</a>. The precise details of how the
+        memory management is to be handled are left to the user.</para>
+  
+      <para>Certain generic list functions must also be provided, namely:
+        <programlisting>
+          void destroy_<i>name</i>_list ( <i>name</i> *, unsigned int ) ;
+          name *reverse_<i>name</i>_list ( <i>name</i> * ) ;
+          name *append_<i>name</i>_list ( <i>name</i> *, <i>name</i> * ) ;
+          name *end_<i>name</i>_list ( <i>name</i> * ) ;
+        </programlisting>
+        which implement the constructs <code>DESTROY_list</code>,
+        <code>REVERSE_list</code>, <code>APPEND_list</code> and
+        <code>END_list</code> respectively.</para>
+  
+      <para>Finally a dummy empty vector:
+      <programlisting>
+          <i>name</i>_VEC empty_<i>name</i>_vec ;
+      </programlisting>needs to be defined.</para>
+  
+      <para>Examples of these support routines can be found in the
+        <a href="#Example"><productname>calculus</productname> program</a>
+        itself.</para>
+    </sect1>
+
+    <sect1 id="COutputAssert">
+      <title>4.3. Run-time checking</title>
+  
+      <para>The type checking facilities supported by
+        <productname>calculus</productname> allow for compile-time detection
+        of many potential programming errors, however there are many problems,
+        such as dereferencing null pointers, deconstructing empty lists and
+        union tag errors which can only be detected at run-time. For this
+        reason <productname>calculus</productname> can be made to add extra
+        assertions to check for such errors into its output. This is done by
+        specifying the <code>-a</code> command-line option.</para>
+  
+      <para>These assertions are implemented by means of macros. If the macro
+        <code>ASSERTS</code> is defined then these macros expand to give the
+        run-time checks. If not the output is exactly equivalent to that which
+        would have been output if the <code>-a</code> option had not been
+        given.</para>
+  
+      <para>The assertions require certain support functions which are output
+        into a separate file, <code>assert_def.h</code>. These functions need
+        to be compiled into the program when <code>ASSERTS</code> is defined.
+        Note that the functions are implementation specific.</para>
+    </sect1>
+  </chapter>
+  
+  <chapter>
+    <title>Disk reading and writing</title>
+  
+    <para>One of the facilities which the <a href= "#COutputTypes">homogeneous
+      implementation</a> of the type system described above allows for is the
+      addition of persistence.  Persistence in this context means allowing
+      objects to be written to, and read from, disk. Also discussed in this
+      section is the related topic of the object printing routines, which
+      allow a human readable representation of objects of the type system to
+      be output for debugging or other purposes.</para>
+  
+    <para>The disk reading and writing routines are output into the files
+      <filename>read_def.h</filename> and <filename>write_def.h</filename>
+      respectively if the <option>-d</option> command-line option is passed to
+      <productname>calculus</productname>. The object printing routines are
+      output if the <option>-p</option> option is given, with additional code
+      designed for use with run-time debuggers being added if the
+      <option>-a</option> option is also given.</para>
+  
+    <para>All of these routines use extra constructs output in the main output
+      files (<filename>name.h</filename> and
+      <filename>union_ops.h</filename>), but not normally accessible.  The
+      macro <i>name</i><code>_IO_ROUTINES</code> should be defined in order to
+      make these available for the disk reading and writing routines to
+      use.</para>
+
+    <sect1 id="DiskWrite">
+      <title>5.1. Disk writing routines</title>
+  
+      <para>The disk writing routines output in
+        <filename>write_def.h</filename> consist of a function:
+        <programlisting>
+          static void WRITE_<i>type</i> ( <i>t</i> ) ;
+        </programlisting>for each type <i>t</i> mentioned within the algebra
+        description, which writes an object of that type to disk.</para>
+  
+      <para>Note that such routines are output not only for the basic types,
+        such as unions and structures, but also for any composite types, such
+        as pointers and lists, which are used in their definition. The
+        <i>type</i> component of the name <code>WRITE_</code><i>type</i> is
+        derived from basic types <i>t</i> by using the short type name. For
+        composite types it is defined recursively as follows:
+        <programlisting>
+          LIST ( <i>t</i> ) -&gt; list_<i>type</i>
+          PTR ( <i>t</i> ) -&gt; ptr_<i>type</i>
+          STACK ( <i>t</i> ) -&gt; stack_<i>type</i>
+          VEC ( <i>t</i> ) -&gt; vec_<i>type</i>
+          VEC_PTR ( <i>t</i> ) -&gt; vptr_<i>type</i>
+        </programlisting>
+        Such functions are defined for identity types and composite types
+        involving identity types by means of macros which define them in terms
+        of the identity definitions.  <code>WRITE_</code><i>type</i> functions
+        for the primitive types should be provided by the user to form a
+        foundation on which all the other functions may be built.</para>
+  
+      <para>The user may wish to generate <code>WRITE_</code><i>type</i> (or
+        other disk reading and writing) functions for types other than those
+        mentioned in the algebra definition. This can be done by means of a
+        command-line option of the form <code>-E</code><i>input</i> where
+        <i>input</i> is a file containing a list of the extra types required.
+        In the notation <a href="#TextInput">used above</a> the syntax for
+        <i>input</i> is given by:
+        <programlisting>
+          <i>extra</i> :
+                  <i>type-list<sub>opt</sub></i>
+  
+          <i>type-list</i> :
+                  <i>type</i> ;
+                  <i>type-list type</i> ;
+        </programlisting>
+        The <code>WRITE_</code><i>type</i> functions are defined recursively
+        in an obvious fashion. The user needs to provide the writing routines
+        for the primitives already mentioned, plus support routines (or
+        macros):
+        <programlisting>
+          void WRITE_BITS ( int, unsigned int ) ;
+          void WRITE_DIM ( <i>name</i>_dim ) ;
+          void WRITE_ALIAS ( unsigned int ) ;
+        </programlisting>
+        for writing a number of bits to disk, writing a vector dimension and
+        writing an <a href="#DiskAlias">object alias</a>.</para>
+  
+      <para>Any of the <code>WRITE_</code><i>type</i> functions may be
+        overridden by the user by defining a macro
+        <code>WRITE_</code><i>type</i> with the desired effect. Note that the
+        <code>WRITE_</code><i>type</i> function for an identity can be
+        overridden independently of the function for the identity definition.
+        This provides a method for introducing types which are
+        representationally the same, but which are treated differently by the
+        disk reading and writing routines.</para>
+    </sect1>
+
+    <sect1 id="DiskRead">
+      <title>5.2. Disk reading routines</title>
+  
+      <para>The disk reading routines output in
+        <filename>read_def.h</filename> are exactly analogous to the disk
+        writing routines. For each type <i>t</i> (except primitives) there is
+        a function or macro:
+        <programlisting>
+          static <i>t</i> READ_<i>type</i> ( void ) ;
+        </programlisting>
+        which reads an object of that type from disk. The user must provide
+        the <code>READ_</code><i>type</i> functions for the primitive types,
+        plus support routines:
+        <programlisting>
+          unsigned int READ_BITS ( int ) ;
+          <i>name</i>_dim READ_DIM ( void ) ;
+          unsigned int READ_ALIAS ( void ) ;
+        </programlisting>
+        for reading a number of bits from disk, reading a vector dimension and
+        reading an <a href="#DiskAlias">object alias</a>. The
+        <code>READ_</code><i>type</i> functions may be overridden by means of
+        macros as before.</para>
+    </sect1>
+
+    <sect1 id="DiskPrint">
+      <title>5.3. Object printing routines</title>
+  
+      <para>The object printing routines output in
+        <filename>print_def.h</filename> consist of a function or macro:
+        <programlisting>
+          static void PRINT_<i>type</i> ( FILE *, <i>t</i>, char *, int ) ;
+        </programlisting>
+        for each type <i>t</i>, which prints an object of type <i>t</i> to the
+        given file, using the given object name and indentation value. The
+        user needs to provide basic output routines:
+        <programlisting>
+          void OUTPUT_<i>type</i> ( FILE *, <i>t</i> ) ;
+        </programlisting>
+        for each primitive type. The <code>PRINT_</code><i>type</i> functions
+        may be overridden by means of macros as before.</para>
+  
+      <para>The printing routines are under the control of three variables
+        defined as follows:
+        <programlisting>
+          static int print_indent_step = 4 ;
+          static int print_ptr_depth = 1 ;
+          static int print_list_expand = 0 ;
+        </programlisting>
+        These determine the indentation to be used in the output, to what
+        depth pointers are to be dereferenced when printing, and whether lists
+        and stacks are to be fully expanded into a sequence of elements or
+        just split into a head and a tail.</para>
+  
+      <para>One application of these object printing routines is to aid
+        debugging programs written using the
+        <productname>calculus</productname> tool.  The form of the type system
+        implementation means that it is not easy to extract information using
+        run-time debuggers without a detailed knowledge of the structure of
+        this implementation. As a more convenient alternative, if both the
+        <code>-p</code> and <code>-a</code> command-line options are given
+        then <productname>calculus</productname> will generate
+        functions:
+        <programlisting>
+          void DEBUG_<i>type</i> ( <i>t</i> ) ;
+        </programlisting>
+        defined in terms of <code>PRINT_</code><i>type</i>, for printing an
+        object of the given type to the standard output. Many debuggers have
+        problems passing structure arguments, so for structure, vector and
+        vector pointer types <code>DEBUG_</code><i>type</i> takes the form:
+        <programlisting>
+          void DEBUG_<i>type</i> ( <i>t</i> * ) ;
+        </programlisting>
+        These debugging routines are only defined conditionally, if the macro
+        <code>DEBUG</code> is defined.</para>
+    </sect1>
+  
+    <sect1 id="DiskAlias">
+      <title>5.4. Aliasing</title>
+  
+      <para>An important feature of the disk reading and writing routines,
+        namely aliasing, has been mentioned but not yet described. The problem
+        to be faced is that many of the objects built up using type systems
+        defined using <productname>calculus</productname> will be cyclic -
+        they will include references to themselves in their own definitions.
+        Aliasing is a mechanism for breaking such cycles by ensuring that only
+        one copy of an object is ever written to disk, or that only one copy
+        is created when reading from disk. This is done by associating a
+        unique number as an alias for the object.</para>
+  
+      <para>For example, when writing to disk, the first time the object is
+        written the alias definition is set up. Consequently the alias number
+        is written instead of the object it represents. Similarly when reading
+        from disk, an alias may be associated with an object when it is read.
+        When this alias is encountered subsequently it will always refer to
+        this same object.</para>
+  
+      <para>The objects on which aliasing can be specified are the
+        <a href="#InputUnion">union fields</a>. A union field may be qualified
+        by one or two hash symbols to signify that objects of that type should
+        be aliased.</para>
+  
+      <para>The two hash case is used to indicate that the user wishes to gain
+        access to the objects during the aliasing mechanism. In the disk
+        writing case, the object to be written, <i>x</i> say, is split into
+        its components using the appropriate
+        <code>DECONS_</code><i>union_field</i> construct. Then the
+        user-defined routine, or macro:
+        <programlisting>
+          ALIAS_<i>union_field</i> ( <i>comp</i>, ...., <i>x</i> ) ;
+        </programlisting>
+        (where <i>comp</i> ranges over all the union components) is called
+        prior to writing the object components to disk.</para>
+  
+      <para>Similarly in the disk reading case, the object being read,
+        <i>x</i>, is initialised by calling the user-defined routine:
+        <programlisting>
+          UNALIAS_<i>union_field</i> ( <i>x</i> ) ;
+        </programlisting>
+        prior to reading the object components from disk. Each object
+        component is then read into a local variable, <i>comp</i>. Finally the
+        user-defined routine:
+        <programlisting>
+          UNIFY_<i>union_field</i> ( <i>comp</i>, ...., <i>x</i> ) ;
+        </programlisting>
+        (where <i>comp</i> ranges over all the union components) is called to
+        assign these values to <i>x</i> before returning.</para>
+  
+      <para>In the single hash case the object is not processed in this way.
+        It is just written straight to disk, or has its components immediately
+        assigned to it when reading from disk.</para>
+  
+      <para>Note that aliasing is used, not just in the disk reading and
+        writing routines, but also in the object printing functions.  After
+        calling any such function the user should call the routine:
+        <programlisting>
+          void clear_<i>name</i>_alias ( void ) ;
+        </programlisting>
+        to clear all aliases.</para>
+  
+      <para>Aliases are implemented by adding an extra field to the objects to
+        be aliased, which contains the alias number, if this has been
+        assigned, or zero, otherwise. A list of all these extra fields is
+        maintained. In addition to the routine
+        <code>clear_</code><i>name</i>_alias mentioned above, the user should
+        provide support functions and variables:
+        <programlisting>
+          unsigned int crt_<i>name</i>_alias ;
+          void set_<i>name</i>_alias ( <i>name</i> *, unsigned int ) ;
+          <i>name</i> *find_<i>name</i>_alias ( unsigned int ) ;
+        </programlisting>
+        giving the next alias number to be assigned, and routines for adding
+        an alias to the list of all aliases, and looking up an alias in this
+        list. Example implementations of these routines are given in the
+        <a href="#Example"><productname>calculus</productname> program</a>
+        itself.</para>
+    </sect1>
+
+    <sect1 id="Application">
+      <title>5.5. Application to calculus</title>
+  
+      <para>As <a href="#Example">mentioned above</a>, the
+        <productname>calculus</productname> program itself is an example of
+        its own application. It therefore contains routines for reading and
+        writing a representation of an algebra to and from disk, and for
+        pretty-printing the contents of an algebra. These may be accessed
+        using the <a href="#Options">command-line options</a> mentioned
+        above.</para>
+  
+      <para>If the <option>-w</option> command-line option is specified to
+        <productname>calculus</productname> then it reads its input file,
+        <i>input</i>, as normal, but writes a disk representation of the input
+        algebra to <i>output</i>, which in this instance is an output file,
+        rather than an output directory. An output file produced in this way
+        can then be specified as an input file to
+        <productname>calculus</productname> if the <option>-r</option> option
+        is given.  Finally the input algebra may be pretty-printed to an
+        output file (or the standard output if no <i>output</i> argument is
+        given) by specifying the <option>-o</option> option.</para>
+    </sect1>
+  </chapter>
+  
+  <chapter>
+    <title>Template files</title>
+  
+    <para>It is possible to use <productname>calculus</productname> to
+      generate an output file from a template input file, <i>template</i>,
+      using the syntax:
+      <programlisting>
+          calculus [ <i>options</i> ] <i>input</i> .... -T<i>template output</i>
+      </programlisting>
+      The template file consists of a list of either template directives or
+      source lines containing escape sequences which are expanded by
+      <productname>calculus</productname>. Template directive lines are
+      distinguished by having <code>@</code> as their first character.  Escape
+      sequences consist of <code>%</code> following by one or more
+      characters.</para>
+  
+    <para>There are two template directives; loops take the form:
+      <programlisting>
+          @loop <i>control</i>
+          ....
+          @end
+      </programlisting>
+      and conditionals take the form:
+      <programlisting>
+          @if <i>condition</i>
+          ....
+          @else
+          ....
+          @endif
+      </programlisting>
+      or:
+      <programlisting>
+          @if <i>condition</i>
+          ....
+          @endif
+      </programlisting>
+      where <code>....</code> stands for any sequence of template directives
+      or source lines.</para>
+  
+    <para>The <i>control</i> statements in a loop can be
+      <code>primitive</code>, <code>identity</code>, <code>enum</code>,
+      <code>struct</code> or <code>union</code> to loop over all the
+      primitive, identity, enumeration structure or union types within the
+      input algebra. Within an <code>enum</code> loop it is possible to use
+      <code>enum.const</code> to loop over all the enumeration constants of
+      the current enumeration type. Within a <code>struct</code> loop it is
+      possible to use <code>struct.comp</code> to loop over all the components
+      of the current structure. Within a <code>union</code> loop it is
+      possible to use <code>union.comp</code> to loop over all the shared
+      components of the current union, <code>union.field</code> to loop over
+      all the fields of the current union, and <code>union.map</code> to loop
+      over all the maps of the current union. Within a
+      <code>union.field</code> loop it is possible to use
+      <code>union.field.comp</code> to loop over all the components of the
+      current union field. Within a <code>union.map</code> loop it is possible
+      to use <code>union.map.arg</code> to loop over all the arguments of the
+      current union map.</para>
+  
+    <para>The valid <i>condition</i> statements in a conditional are
+      <code>true</code> and <code>false</code>, plus
+      <code>comp.complex</code>, which is true if the current structure or
+      union field component has a complex type (i.e. those for which
+      <code>COPY_</code><i>type</i> and <code>DEREF_</code><i>type</i> require
+      two arguments), and <code>comp.default</code>, which is true if the
+      current structure or union field component has a default initialiser
+      value.</para>
+  
+    <para>A number of escape sequences can be used anywhere.  <code>%ZX</code>
+      and <code>%ZV</code> give the name and version number of the version of
+      <productname>calculus</productname> used.  <code>%Z</code> and
+      <code>%V</code> give the name and version number of the input algebra.
+      <code>%%</code> and <code>%@</code> give <code>%</code> and
+      <code>@</code> respectively, and <code>%</code> as the last character in
+      a line suppresses the following newline character.</para>
+  
+    <para>Within a <code>primitive</code> loop, <code>%PN</code> gives the
+      primitive name, <code>%PM</code> gives the short primitive name and
+      <code>%PD</code> gives the primitive definition.</para>
+  
+    <para>Within an <code>identity</code> loop, <code>%IN</code> gives the
+      identity name, <code>%IM</code> gives the short identity name and
+      <code>%IT</code> gives the identity definition.</para>
+  
+    <para>Within an <code>enum</code> loop, <code>%EN</code> gives the
+      enumeration name, <code>%EM</code> gives the short enumeration name and
+      <code>%EO</code> gives the enumeration order,
+      <code>ORDER_</code><i>enum</i>. Within an <code>enum.const</code> loop,
+      <code>%ES</code> gives the enumeration constant name and
+      <code>%EV</code> gives its value.</para>
+  
+    <para>Within a <code>struct</code> loop, <code>%SN</code> gives the
+      structure name and <code>%SM</code> gives the short structure
+      name.</para>
+  
+    <para>Within a <code>union</code> loop, <code>%UN</code> gives the union
+      name, <code>%UM</code> gives the short union name and <code>%UO</code>
+      gives the union order, <code>ORDER_</code><i>union</i>. Within a
+      <code>union.field</code> loop, <code>%FN</code> gives the field name.
+      Within a <code>struct.comp</code>, <code>union.comp</code> or
+      <code>union.field.comp</code> loop, <code>%CN</code> gives the component
+      name, <code>%CT</code> gives the component type, <code>%CU</code> gives
+      the short form of the component type and <code>%CV</code> gives the
+      default component initialiser value (if <code>comp.default</code> is
+      true). Within a <code>union.map</code> loop, <code>%MN</code> gives the
+      map name and <code>%MR</code> gives the map return type. Within a
+      <code>union.map.arg</code> loop, <code>%AN</code> gives the argument
+      name and <code>%AT</code> gives the argument type.</para>
+  
+    <para>As an example, the following template file gives a simple algebra
+      pretty printer:
+      <programlisting>
+          ALGEBRA %X (%V):
+  
+          /* PRIMITIVE TYPES */
+          @loop primitive
+          %PN (%PM) = "%PD" ;
+          @end
+  
+          /* IDENTITY TYPES */
+          @loop identity
+          %IN (%IM) = %IT ;
+          @end
+  
+          /* ENUMERATION TYPES */
+          @loop enum
+  
+          enum %EN (%EM) = {
+          @loop enum.const
+                  %ES = %EV,
+          @end
+          } ;
+          @end
+  
+          /* STRUCTURE TYPES */
+          @loop struct
+  
+          struct %SN (%SM) = {
+          @loop struct.comp
+                  %CT %CN ;
+          @end
+          } ;
+          @end
+  
+          /* UNION TYPES */
+          @loop union
+  
+          union %UN (%UM) = {
+          @loop union.comp
+                  %CT %CN ;
+          @end
+          } + {
+          @loop union.field
+                  %FN -&gt; {
+          @loop union.field.comp
+                          %CT %CN ;
+          @end
+                  } ;
+          @end
+          } ;
+          @end
+      </programlisting>
+    </para>  
+  </chapter>
+</book>

doc/diagnostic/diagnostic.xml

+<?xml version="1.0"?>
+<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.3//EN"
+  "http://www.oasis-open.org/docbook/xml/4.3/docbookx.dtd">
+
+<book>
+  <bookinfo>
+    <title>TDF Diagnostic Specification, Issue 3.0</title>
+
+    <corpauthor>The TenDRA Project</corpauthor>
+
+    <author>Jeroen Ruigrok van der Werven</author>
+    <authorinitials>JRvdW</authorinitials>
+    <pubdate>2004</pubdate>
+
+    <copyright>
+      <year>2004</year>
+      <year>2005</year>
+
+      <holder>The TenDRA Project</holder>
+    </copyright>
+
+    <copyright>
+      <year>1998</year>
+
+      <holder>DERA</holder>
+    </copyright>
+  </bookinfo>
+  
+  <chapter>
+    <title>TDF Diagnostic Specification, Issue 3.0</title>
+  
+    <sect1 id="intro">
+      <title>Introduction</title>
+      
+      <para>The TDF diagnostic information is intended to convey all that
+        information, used by current source level debuggers, which would
+        conventionally be part of an object file. Any particular installer
+        will only use those parts of this information which its native object
+        format can represent.</para>
+  
+      <para>The version of the diagnostics described here is the first
+        version. It has only been tested with TDF produced from C programs.
+        There are known to be certain deficiencies relative to other languages
+        (in particular to FORTRAN). A later version will correct these
+        deficiencies. The changes already envisaged are detailed in
+        <a href="diag6.html#0">section 4</a>, and would have minimal (if any)
+        impact on C producers.</para>
+  
+      <para>The diagnostic system introduces one new type of TDF linkable
+        entities, and currently adds two new units to the bitstream
+        representation of TDF.</para>
+    
+      <para>Much of the actual annotation of procedure bodies is currently
+        done by reserved <code>TOKEN</code>s, which installers recognize
+        specially. These <code>TOKEN</code>s are described in
+        <a href= "diag5.html#0">section 3</a>.</para>
+    
+      <para>There is a resemblance between the TDF diagnostic information and
+        Unix International's DWARF format. DWARF has similar aims to the TDF
+        diagnostics, and ensuring that complete DWARF information could be
+        generated provided a useful check during the development of the TDF
+        diagnostics. However the TDF diagnostics are intended to be
+        architecture (and format) neutral. No inference should be made about
+        any link (present or future) between DWARF and TDF diagnostics.</para>
+    </sect1>
+  
+    <sect1>
+      <title>2. Diagnostic SORTs</title>
+      
+      <para>As a summary of this section:
+        <itemizedlist>
+          <listitem>
+            <para><code>DIAG_TYPE</code>s describe programming language types
+              (e.g. arrays, structs...). <code>DIAG_TQ</code>s are qualifiers
+              of <code>DIAG_TYPE</code> s used for attributes like volatile
+              and const.</para>
+          </listitem>
+    
+          <listitem>
+            <para><code>FILENAME</code>s and <code>SOURCEMARK</code>s describe
+            source files and locations within them.</para>
+          </listitem>
+    
+          <listitem>
+            <para><code>DIAG_TAG</code>s associate integers with
+              <code>DIAG_TYPE</code>s. They are used in a similar manner to
+              normal TDF <code>TAG</code>s, and are held in a (TDF) linkable
+              unit called a <code>DIAG_TYPE_UNIT</code>.</para>
+          </listitem>
+    
+          <listitem>
+            <para><code>DIAG_UNIT</code>s hold a collection of
+            <code>DIAG_DESCRIPTOR</code>s, used for information outside
+            procedure bodies.</para>
+          </listitem>
+        </itemizedlist>
+      </para>
+  
+      <sect2 id="S5">
+        <title>2.1. DIAG_DESCRIPTOR</title>
+
+        <para>
+        <b>Number of encoding bits</b>: 2
+        <b>Is coding extendable</b>: yes
+        </para>
+  
+        <para><code>DIAG_DESCRIPTOR</code>s are used to associate names in the
+          source program with diagnostic items.</para>
+  
+        <sect3 id="S6">
+          <title>2.1.1. diag_desc_id</title>
+
+          <para>
+          <b>Encoding number</b>: 1
+          <programlisting>
+            <i>src_name</i>:        TDFSTRING<i>(k, n)</i>
+            <i>whence</i>:          SOURCEMARK
+            <i>found_at</i>:        EXP POINTER(<i>al</i>)
+            <i>type</i>:            DIAG_TYPE
+                       -&gt; DIAG_DESCRIPTOR
+    
+            </programlisting>
+            Generates a descriptor for an identifier (of
+            <code>DIAG_TYPE</code> <i>type</i>), whose source name was
+            <i>src_name</i> from source location <i>whence</i>. The
+            <code>EXP</code> <i>found_at</i> describes how to access the
+            value.  Note that the <code>EXP</code> need not be unique (e.g.
+            FORTRAN EQUIVALENCE might be implemented this way).</para>
+        </sect3>
+  
+        <sect3 id="S7">
+          <title>2.1.2. diag_desc_struct</title>
+
+          <para>
+          <b>Encoding number</b>: 2
+
+          <programlisting>
+            <i>src_name</i>:        TDFSTRING<i>(k, n)</i>
+            <i>whence</i>:          SOURCEMARK
+            <i>new_type</i>:        DIAG_TYPE
+                       -&gt; DIAG_DESCRIPTOR
+    
+          </programlisting>
+
+          Generates a descriptor whose source name was <i>src_name</i>.
+          <i>new_type</i> must be either a <code>DIAG_STRUCT</code>,
+          <code>DIAG_UNION</code> or <code>DIAG_ENUM</code>.</para>
+  
+          <para>This construct is obsolete.</para>
+        </sect3>
+  
+        <sect3 id="S8">
+          <title>2.1.3. diag_desc_typedef</title>
+          
+          <para>
+          <b>Encoding number</b>: 3
+          <programlisting>
+            <i>src_name</i>:        TDFSTRING<i>(k, n)</i>
+            <i>whence</i>:          SOURCEMARK
+            <i>new_type</i>:        DIAG_TYPE
+                       -&gt; DIAG_DESCRIPTOR
+    
+          </programlisting>
+          
+          Generates a descriptor for a type <i>new_type</i> whose source name
+          was <i>src_name</i>. Note that <i>diag_desc_typedef</i> is used for
+          associating a name with a type, rather than for any name given in
+          the initial description of the type (e.g. in C this is used for
+          typedef, not for struct/union/enum tags).</para>
+        </sect3>
+      </sect2>
+  
+      <sect2 id="S9">
+        <title>2.2. DIAG_UNIT</title>
+        
+        <para>
+        <b>Number of encoding bits</b>: 0
+        <b>Is coding extendable</b>: no
+        <b>Unit identification</b>: <i>diagdef</i>
+        </para>
+  
+        <para>A <code>DIAG_UNIT</code> is a TDF unit containing
+          <code>DIAG_DESCRIPTOR</code>s. A <code>DIAG_UNIT</code> is used to
+          contain descriptions of items outside procedure bodies (e.g.  global
+          variables, global type definitions).</para>
+  
+        <sect3 id="S10">
+          <title>2.2.1. build_diag_unit</title>
+    
+          <para>
+          <b>Encoding number</b>: 0
+          <programlisting>
+            <i>no_labels</i>:       TDFINT
+            <i>descriptors</i>:     SLIST(DIAG_DESCRIPTOR)
+                       -&gt; DIAG_UNIT
+    
+          </programlisting>
+          Create a <code>DIAG_UNIT</code> containing
+          <code>DIAG_DESCRIPTOR</code>s. <i>no_labels</i> is the number of
+          local labels used in <i>descriptors</i> (for conditionals).</para>
+        </sect3>
+      </sect2>
+  
+      <sect2 id="S11">
+        <title>2.3. DIAG_TAG</title>
+        
+        <para>
+        <b>Number of encoding bits</b>: 1
+        <b>Is coding extendable</b>: yes
+        <b>Linkable entity identification</b>: <i>diagtag</i>
+        </para>
+  
+        <para><code>DIAG_TAG</code>s are used <i>inter alia</i> to break
+          cyclic diagnostic types. They are (TDF) linkable entities. A
+          <code>DIAG_TAG</code> is made from a number, and used in
+          <i>use_diag_tag</i> to obtain the <code>DIAG_TYPE</code> associated
+          with that number by <i>make_diag_tagdef</i>.</para>
+  
+        <sect3 id="S12">
+          <title>2.3.1. make_diag_tag</title>
+          
+          <para>
+          <b>Encoding number</b>: 1
+          <programlisting>
+            <i>num</i>:             TDFINT
+                       -&gt; DIAG_TAG
+    
+          </programlisting>
+          Create a <code>DIAG_TAG</code> from <i>num</i>.
+          </para>
+        </sect3>
+      </sect2>
+  
+      <sect2 id="S13">
+        <title>2.4. DIAG_TAGDEF</title>
+        
+        <para>
+        <b>Number of encoding bits</b>: 1
+        <b>Is coding extendable</b>: yes
+        </para>
+  
+        <para><code>DIAG_TAGDEF</code>s associate <code>DIAG_TAG</code>s with
+          <code>DIAG_TYPE</code> s.</para>
+  
+        <sect3 id="S14">
+          <title>2.4.1. make_diag_tagdef</title>
+          
+          <para>
+          <b>Encoding number</b>: 1
+          <programlisting>
+            <i>tno</i>:             TDFINT
+            <i>dtype</i>:           DIAG_TYPE
+                       -&gt; DIAG_TAGDEF
+    
+          </programlisting>
+          Associates tag number <i>tno</i> with <i>dtype</i>.
+          </para>
+        </sect3>
+      </sect2>
+  
+      <sect2 id="S15">
+        <title>2.5. DIAG_TYPE_UNIT</title>
+        
+        <para>
+        <b>Number of encoding bits</b>: 0
+        <b>Is coding extendable</b>: no
+        <b>Unit identification</b>: <i>diagtype</i>
+        </para>
+  
+        <para>A <code>DIAG_TYPE_UNIT</code> is a TDF unit containing
+          <code>DIAG_TAGDEF</code>s.</para>
+  
+        <sect3 id="S16">
+          <title>2.5.1. build_diagtype_unit</title>
+          
+          <para>
+          <b>Encoding number</b>: 0
+          <programlisting>
+            <i>no_labels</i>:       TDFINT
+            <i>tagdefs</i>: SLIST(DIAG_TAGDEF)
+                       -&gt; DIAG_TYPEUNIT
+    
+          </programlisting>
+          Create a <code>DIAG_TYPEUNIT</code> containing
+          <code>DIAG_TAGDEF</code>s. <i>no_labels</i> is the number of local
+          labels used in <i>tagdefs</i> (for conditionals).</para>
+        </sect3>
+      </sect2>
+  
+      <sect2 id="S17">
+        <title>2.6. DIAG_TYPE</title>
+        
+        <para>
+        <b>Sortname</b>:
+        <i>foreign_sort("diag_type")</i>
+        <b>Number of encoding bits</b>: 4
+        <b>Is coding extendable</b>: yes
+        </para>
+  
+        <para><code>DIAG_TYPE</code>s are used to provide diagnostic
+          information about data types.</para>
+  
+        <sect3 id="S18">
+          <title>2.6.1. diag_type_apply_token</title>
+          
+          <para>
+          <b>Encoding number</b>: 1
+          <programlisting>
+            <i>token_value</i>:     TOKEN
+            <i>token_args</i>:      BITSTREAM
+                       -&gt; DIAG_TYPE
+    
+          </programlisting>
+          The token is applied to the arguments to give a
+          <code>DIAG_TYPE</code>. If there is a definition for
+          <i>token_value</i> in the <code>CAPSULE</code> then
+          <i>token_args</i> is a <code>BITSTREAM</code> encoding of the
+          <code>SORT</code>s of its parameters, in the order specified.</para>
+        </sect3>
+  
+        <sect3 id="S19">
+          <title>2.6.2. diag_array</title>
+          
+          <para>
+          <b>Encoding number</b>: 2