Subversion Repositories tendra.SVN

<?xml version="1.0" standalone="no"?>

<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.4//EN"

  "http://www.oasis-open.org/docbook/xml/4.4/docbookx.dtd">

<!--

  $Id$

-->

<book>

  <bookinfo>

    <title>Calculus Users' Guide</title>

    <corpauthor>The TenDRA Project</corpauthor>

    <author>

      <firstname>Jeroen</firstname>

      <surname>Ruigrok van der Werven</surname>

    </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 id="introduction">

    <title>Introduction</title>

    <para>This document describes a tool, <command>calculus</command>, 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><command>calculus</command> 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

      <link linkend="diskoutput">disk reading and writing routines</link>

      described below are an example of this.</para>

    <sect1 id="options">

      <title>Using calculus</title>

      <para>The general form for invoking <command>calculus</command> 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

        <link linkend="module">otherwise specified</link> it is the last file

        which is used to generate the output.</para>

      <para>The form in which the

        <link linkend="textinput">input type systems</link>

        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

        <ulink url="tcpplus.html#token"><code>#pragma token</code></ulink>

        statements describing the type system specification are output.  This

        <link linkend="tokenoutput">specification</link> is given below, with

        some of the more important

        <link linkend="coutput">implementation details</link> being described

        in the following section.</para>

      <para>Note that it is necessary to check any program written using

        <command>calculus</command> 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

        <link linkend="coutputsupport">basic functions</link>) may be

        dependent upon the implementation, and so not be suitable for this

        form of checking.</para>

    </sect1>

    <sect1 id="example">

      <title>Example program</title>

      <para>The program <command>calculus</command> itself was written using a

        type system specified using the <command>calculus</command> 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 id="textinput">

    <title>Input syntax</title>

    <para>The overall input file format is as follows:

      <programlisting>

algebra:

        ALGEBRA identifier version<subscript>opt</subscript>: item-list<subscript>opt</subscript>

version:

        (integer.integer)

item-list:

        item

        item-list item

item:

        primitive

        identity

        enumeration

        structure

        union

      </programlisting></para>

      <para>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 <literal>identifier</literal> has the same meaning as in C.

        The only other significant lexical units are

        <literal>integer</literal>, which consists of a sequence of decimal

        digits, and <literal>string</literal>, 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>Primitives</title>

      <para>Primitives form the basic components from which the other types in

        the algebra are built up. They are described as follows:

        <programlisting>

primitive:

        object-identifier = quoted-type;

        </programlisting>

        where the primitive identifier is given by:

        <programlisting>

object-identifier:

        #<subscript>opt</subscript>:<subscript>opt</subscript> identifier

        #<subscript>opt</subscript>:<subscript>opt</subscript> identifier(identifier)

        </programlisting>

        and the primitive definition is a string which gives the C type

        corresponding to this primitive:

        <programlisting>

quoted-type:

        string

        </programlisting></para>

      <para>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>

      <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>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>

identity:

        object-identifier = type;

        </programlisting>

        where the definition type, <literal>type</literal>, is as described

        <link linkend="inputtype">below</link>.</para>

    </sect1>

    <sect1 id="inputenum">

      <title>Enumerations</title>

      <para>Enumerations are used to define types which can only take values

        from some finite set. They are described as follows:

      <programlisting>

enumeration:

        enum !<subscript>opt</subscript> object-identifier = { enumerator-list };

        enum !<subscript>opt</subscript> object-identifier = base-enumeration + { enumerator-list };

      </programlisting>

      where:

      <programlisting>

base-enumeration:

        identifier

      </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>

enumerator:

        identifier

        identifier = enumerator-value

enumerator-list:

        enumerator

        enumerator-list, enumerator

        </programlisting></para>

      <para>Each enumerator is assigned a value in an ascending sequence,

        starting at zero. The next value to be assigned can be set using an

        <literal>enumerator-value</literal>. This is an expression formed from

        <literal>integer</literal>s, <literal>identifier</literal>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 <literal>enumerator-value</literal>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>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>

structure:

        struct object-identifier = component-group;

        struct object-identifier = base-structure + component-group;

        </programlisting>

        where:

        <programlisting>

base-structure:

        identifier

        </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>

component-group:

        { component-list<subscript>opt</subscript> }

component-list:

        component-declarations;

        component-list component-declarations;

component-declarations:

        type component-declarators

component-declarators:

        component-declarator

        component-declarators, component-declarator

component-declarator:

        identifier component-initialiser<subscript>opt</subscript>

component-initialiser:

        = string

        </programlisting></para>

      <para>The optional <link linkend="outputstruct">component initialiser

        strings</link> 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>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>

union:

        union object-identifier = component-group + field-group map-group<subscript>opt</subscript>;

        union object-identifier = base-union + field-group map-group<subscript>opt</subscript>;

        </programlisting>

        where:

        <programlisting>

base-union:

        identifier

        </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 <literal>component-group</literal> gives a set of components

        which are common to all the different union cases. The cases

        themselves are described as follows:

        <programlisting>

field-group:

        { field-list }

field:

        #<subscript>opt</subscript> #<subscript>opt</subscript> field-identifier-list-&gt;component-group

        #<subscript>opt</subscript> #<subscript>opt</subscript> field-identifier-list-&gt;base-field + component-group

base-field:

        identifier

field-list:

        field

        field-list, field

field-identifier:

        identifier

field-identifier-list:

        field-identifier

        field-identifier-list, field-identifier

        </programlisting></para>

      <para>The optional one or two hashes which may be used to qualify a list

        of field identifiers are used to indicate

        <link linkend="diskalias">aliasing</link> in the disk reading and

        writing routines.  The <literal>base-field</literal> 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>

map-group:

        :[map-list<subscript>opt</subscript>]

map:

        extended-type #<subscript>opt</subscript> identifier(parameter-list<subscript>opt</subscript>)

map-list:

        map

        map-list map

        </programlisting>

        where:

        <programlisting>

parameter-list:

        parameter-declarations

        parameter-list; parameter-declarations

parameter-declarations:

        extended-type parameter-declarators

parameter-declarators:

        identifier

        parameter-declarators, identifier

        </programlisting></para>

      <para>Note that the map parameter and return types are given by:

        <programlisting>

          extended-type:

                  type

                  quoted-type

        </programlisting></para>

      <para>In addition to the

        <link linkend="inputtype">types derived from the algebra</link> 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

        <link linkend="outputunionmaps">destructor function</link> as a

        parameter.</para>

    </sect1>

    <sect1 id="inputtype">

      <title>Type constructors</title>

      <para>The types derived from the algebra may be described as follows:

        <programlisting>

type:

        identifier

        PTR type

        LIST type

        STACK type

        VEC type

        VEC_PTR type

        </programlisting></para>

      <para>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>Relations between algebras</title>

      <para>As <link linkend="options">mentioned above</link>, more than one

        input algebra may be specified to <command>calculus</command>. 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>

import:

        IMPORT identifier;

        IMPORT identifier::identifier;

        </programlisting>

        which fit into the main syntax as an <literal>item</literal>. The

        first form imports all the types from the algebra given by

        <literal>identifier</literal> into the current algebra. The second

        imports a single type, given by the second

        <literal>identifier</literal> from the algebra given by the first

        <literal>identifier</literal>.</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 <literal>import</literal> commands can be used to express

        subalgebras in a simple fashion.</para>

    </sect1>

  </chapter>

  <chapter id="tokenoutput">

    <title>Output type system specification</title>

    <para>In this section we document the basic output of

      <command>calculus</command>. 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

      <link linkend="coutput">C implementation</link> 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 <literal>name</literal> is the

      overall algebra name. Unless otherwise stated, all the objects specified

      below are to be found in <literal>name</literal><code>.h</code>. However

      for each union, <literal>union</literal>, in the algebra certain

      information associated with the union is printed into

      <literal>union</literal><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>Version information</title>

      <para>Certain basic information about the input algebra is included in

        <literal>name</literal><code>.h</code>. <literal>name</literal>

        <code>_NAME</code> is a string literal giving the overall algebra

        name.  <literal>name</literal><code>_VERSION</code> is a string

        literal giving the algebra version number.

        <literal>name</literal><code>_SPECIFICATION</code> and

        <literal>name</literal><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>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 t);

TYPE LIST(TYPE t);

TYPE STACK(TYPE t);

TYPE VEC(TYPE t);

TYPE VEC_PTR(TYPE t);

TYPE SIZE(TYPE t);

        </programlisting></para>

      <para>These represent a pointer to an object of type

        <literal>t</literal>, a list of objects of type <literal>t</literal>,

        a stack of objects of type <literal>t</literal>, a vector of objects

        of type <literal>t</literal>, a pointer into a vector of objects of

        type <literal>t</literal>, and an allocation block size for type

        <literal>t</literal> 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

        <command>calculus</command>. 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 name_dim;

        </programlisting>

        is specified, where <literal>name</literal> 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_name();

void dummy_destroy_name();

        </programlisting>

        where <literal>name</literal> is as above.

        <code>destroy_</code><literal>name</literal> is the default

        destructor, whereas <code>dummy_destroy_</code><literal>name</literal>

        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>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

        <link linkend="outputptr">pointer stepping construct</link>

        <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 ( t ) SIZE_type;

        </programlisting>

        where <literal>t</literal> denotes the type itself, and

        <literal>type</literal> is the associated type name.</para>

      <para>For the five other type constructors

        <link linkend="outputbasic">described above</link> there are constant

        expressions:

        <programlisting>

SIZE(PTR(t))      SIZE_ptr(TYPE t);

SIZE(LIST(t))     SIZE_list(TYPE t);

SIZE(STACK(t))    SIZE_stack(TYPE t);

SIZE(VEC(t))      SIZE_vec(TYPE t);

SIZE(VEC_PTR(t))  SIZE_vec_ptr(TYPE t);

      </programlisting>

      for any type <literal>t</literal>.</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(t) SCALE(SIZE(t), INT_TYPE itype);

        </programlisting>

        for any type <literal>t</literal> and any integral type

        <literal>itype</literal>.</para>

    </sect1>

    <sect1 id="outputptr">

      <title>Operations on pointers</title>

      <para>The <code>PTR</code> type constructor is used to represent a

        pointer to an object of type <literal>t</literal>. It should be

        emphasised that this construct is not in general implemented by means

        of the C pointer construct.</para>

      <sect2 id="simple-pointer-constructs">

        <title>Simple pointer constructs</title>

        <para>There are several simple operations on pointers, given as

          follows:

          <programlisting>

PTR(t) NULL_ptr(TYPE t);

int IS_NULL_ptr(PTR (t));

int EQ_ptr(PTR(t), PTR(t));

PTR(t) STEP_ptr(PTR(t), SIZE(t));

          </programlisting></para>

        <para>The construct <code>NULL_ptr</code> is used to form the null

          pointer to <literal>t</literal> for a type <literal>t</literal>.

          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 id="unique-pointers">

        <title>Unique pointers</title>

        <para>There are also constructs for generating and destroying unique

          pointers:

          <programlisting>

PTR(t) UNIQ_ptr(TYPE t);

void DESTROY_UNIQ_ptr(PTR(t));

          </programlisting></para>

        <para>A unique pointer is guaranteed to be different from all other

          undestroyed pointers. Dereferencing a unique pointer is

          undefined.</para>

      </sect2>

      <sect2 id="pointer-construction-destruction">

        <title>Pointer construction and destruction</title>

        <para>The constructs:

          <programlisting>

PTR(t) MAKE_ptr(SIZE(t));

void DESTROY_ptr(PTR(t), SIZE(t));

          </programlisting>

          are used to respectively create and destroy a pointer to a given

          type.</para>

      </sect2>

      <sect2 id="construct-assignment-dereference">

        <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_type(PTR(t), t);

t DEREF_type(PTR(t));

          </programlisting>

          where <literal>t</literal> is the type involved and

          <literal>type</literal> 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_type(PTR(t), t);

STATEMENT DEREF_type(PTR(t), lvalue t);

          </programlisting></para>

        <para>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

          <literal>t</literal> 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(t)), PTR(t));

PTR(t) DEREF_ptr(PTR (PTR (t)));

void COPY_list(PTR(LIST(t)), LIST(t));

LIST(t) DEREF_list(PTR(LIST(t)));

void COPY_stack(PTR(STACK(t)), STACK(t));

STACK(t) DEREF_stack(PTR(STACK(t)));

STATEMENT COPY_vec(PTR(VEC(t)), VEC(t));

STATEMENT DEREF_vec(PTR(VEC(t)), lvalue VEC(t));

STATEMENT COPY_vec_ptr(PTR(VEC_PTR(t)), VEC_PTR(t));

STATEMENT DEREF_vec_ptr(PTR(VEC_PTR(t)), lvalue VEC_PTR(t));

          </programlisting></para>

      </sect2>

    </sect1>

    <sect1 id="outputlist">

      <title>Operations on lists</title>

      <para>The <code>LIST</code> type constructor is used to represent a list

        of objects of type <literal>t</literal>.</para>

      <sect2 id="simple-list-constructs">

        <title>Simple list constructs</title>

        <para>There are several simple list constructs:

          <programlisting>

LIST(t) NULL_list(TYPE t);

int IS_NULL_list(LIST(t));

int EQ_list(LIST(t), LIST(t));

unsigned LENGTH_list(LIST(t));

PTR(t) HEAD_list(LIST(t));

LIST(t) TAIL_list(LIST(t));

PTR(LIST(t)) PTR_TAIL_list(LIST(t));

LIST(t) END_list(LIST(t));

LIST(t) REVERSE_list(LIST(t));

LIST(t) APPEND_list(LST(t), LIST(t));

          </programlisting></para>

        <para>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 id="unique-lists">

        <title>Unique lists</title>

        <para>There are also constructs for generating and destroying unique

          lists:

          <programlisting>

LIST(t) UNIQ_list(TYPE t);

void DESTROY_UNIQ_list(LIST(t));

          </programlisting></para>

        <para>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 id="list-construction-destruction">

        <title>List construction and destruction</title>

        <para>For each type <literal>t</literal> there are operations for

          constructing and deconstructing lists. For the basic types

          comprising the algebra these take the form:

          <programlisting>

STATEMENT CONS_type(t, LIST(t), lvalue LIST(t));

STATEMENT UN_CONS_type(lvalue t, lvalue LIST(t), LIST(t)) ;

STATEMENT DESTROY_CONS_type(DESTROYER, lvalue t, lvalue LIST(t), LIST(t));

          </programlisting>

          where <literal>type</literal> is the short type name.</para>

        <para>The operation <code>CONS_</code><literal>type</literal> 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><literal>type</literal> reverses this process,

          decomposing a list into its head and its tail.

          <code>DESTROY_CONS_</code><literal>type</literal> 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(t), LIST(PTR(t)), lvalue LIST(PTR(t))) ;

STATEMENT UN_CONS_ptr(lvalue PTR(t), lvalue LIST(PTR(t)), LIST(PTR(t)));

STATEMENT DESTROY_CONS_ptr(DESTROYER, lvalue PTR(t), lvalue LIST(PTR(t)), LIST(PTR(t)));

          </programlisting></para>

        <para>There is also a generic list destruction construct:

          <programlisting>

          STATEMENT DESTROY_list(LIST(t), SIZE(t));

          </programlisting>

          which may be used to destroy all the elements in a list.</para>

      </sect2>

    </sect1>

    <sect1 id="outputstack">

      <title>Operations on stacks</title>

      <para>The <code>STACK</code> type constructor is used to represent

        stacks of objects of type <literal>t</literal>. Empty stacks can be

        created and tested for:

        <programlisting>

STACK(t) NULL_stack(TYPE t);

int IS_NULL_stack(STACK(t));

        </programlisting></para>

      <para>For each type <literal>t</literal> 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_type(t, lvalue STACK(t));

STATEMENT POP_type(lvalue t, lvalue STACK(t));

        </programlisting>

        where <literal>type</literal> is the short type name. There are also

        generic constructs, such as <code>PUSH_ptr</code> for pushing any

        pointer type, similar to the

        <link linkend="outputlist">generic list constructors</link>

        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(t) LIST_stack(STACK(t));

STACK(t) STACK_list(LIST(t));

        </programlisting>

        for explicitly converting between lists and stacks.</para>

    </sect1>

    <sect1 id="outputvec">

      <title>Operations on vectors</title>

      <para>The <code>VEC</code> type constructor is used to represent vectors

        of objects of type <literal>t</literal>. There are a number of simple

        operations on vectors:

        <programlisting>

VEC(t) NULL_vec(TYPE t);

name_dim DIM_vec(VEC(t));

name_dim DIM_ptr_vec(PTR(VEC(t)));

PTR(t) PTR_ptr_vec(PTR(VEC(t)));

        </programlisting></para>

      <para>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

        <literal>name</literal><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(t), name_dim, lvalue VEC(t));

STATEMENT DESTROY_vec(VEC(t), SIZE(t));

        </programlisting></para>

      <para>Finally a vector can be trimmed using:

        <programlisting>

STATEMENT TRIM_vec(VEC(t), SIZE(t), int, int, lvalue VEC(t));

        </programlisting>

        the two integral arguments giving the lower and upper bounds for the

        trimming operation.</para>

    </sect1>

    <sect1 id="outputvecptr">

      <title>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

        <literal>t</literal>.  Apart from the basic constructors already

        mentioned, there are only two operations on vector pointers:

        <programlisting>

VEC_PTR(t) VEC_PTR_vec(VEC(t));

PTR(t) PTR_vec_ptr(VEC_PTR(t));

        </programlisting></para>

      <para>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>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>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>Operations on enumerations</title>

      <para>Each enumeration specified within the algebra maps onto an

        unsigned integral type in the output file. The 

        <link linkend="outputprim">basic operations</link>

        listed above are always generated unless it has been indicated that

        <link linkend="inputenum">no lists of this type will be formed</link>,

        when <code>CONS_</code><literal>type</literal> 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>

t enum_member;

        </programlisting>

        where <literal>t</literal> is the enumeration type,

        <literal>enum</literal> is the short type name, and

        <literal>member</literal> 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_enum;