Blame | Last modification | View Log | RSS feed
<!-- Crown Copyright (c) 1998 -->
<HTML>
<HEAD>
<TITLE>
calculus users' guide
</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000FF" VLINK="#400080" ALINK="#FF0000">
<H1>calculus Users' Guide</H1>
<H3>January 1998</H3>
<IMG SRC="../images/no_next.gif" ALT="next section">
<IMG SRC="../images/no_prev.gif" ALT="previous section">
<IMG SRC="../images/no_top.gif" ALT="current document">
<A HREF="../index.html"><IMG SRC="../images/home.gif" ALT="TenDRA home page">
</A>
<IMG SRC="../images/no_index.gif" ALT="document index"><P>
<HR>
<DL>
<DT><A HREF="#Intro"><B>1</B> - Introduction</A><DD>
<DL>
<DT><A HREF="#Options"><B>1.1</B> - Using calculus</A><DD>
<DT><A HREF="#Example"><B>1.2</B> - Example program</A><DD>
</DL>
<DT><A HREF="#TextInput"><B>2</B> - Input syntax</A><DD>
<DL>
<DT><A HREF="#InputPrim"><B>2.1</B> - Primitives</A><DD>
<DT><A HREF="#InputIdent"><B>2.2</B> - Identities</A><DD>
<DT><A HREF="#InputEnum"><B>2.3</B> - Enumerations</A><DD>
<DT><A HREF="#InputStruct"><B>2.4</B> - Structures</A><DD>
<DT><A HREF="#InputUnion"><B>2.5</B> - Unions</A><DD>
<DT><A HREF="#InputType"><B>2.6</B> - Type constructors</A><DD>
<DT><A HREF="#Module"><B>2.7</B> - Relations between algebras</A><DD>
</DL>
<DT><A HREF="#TokenOutput"><B>3</B> - Output type system specification</A><DD>
<DL>
<DT><A HREF="#OutputInfo"><B>3.1</B> - Version information</A><DD>
<DT><A HREF="#OutputBasic"><B>3.2</B> - Basic types</A><DD>
<DT><A HREF="#OutputSize"><B>3.3</B> - Operations on sizes</A><DD>
<DT><A HREF="#OutputPtr"><B>3.4</B> - Operations on pointers</A><DD>
<DT><A HREF="#OutputList"><B>3.5</B> - Operations on lists</A><DD>
<DT><A HREF="#OutputStack"><B>3.6</B> - Operations on stacks</A><DD>
<DT><A HREF="#OutputVec"><B>3.7</B> - Operations on vectors</A><DD>
<DT><A HREF="#OutputVecPtr"><B>3.8</B> - Operations on vector pointers</A><DD>
<DT><A HREF="#OutputPrim"><B>3.9</B> - Operations on primitives</A><DD>
<DT><A HREF="#OutputIdent"><B>3.10</B> - Operations on identities</A><DD>
<DT><A HREF="#OutputEnum"><B>3.11</B> - Operations on enumerations</A><DD>
<DT><A HREF="#OutputStruct"><B>3.12</B> - Operations on structures</A><DD>
<DT><A HREF="#OutputUnion"><B>3.13</B> - Operations on unions</A><DD>
</DL>
<DT><A HREF="#COutput"><B>4</B> - Implementation details</A><DD>
<DL>
<DT><A HREF="#COutputTypes"><B>4.1</B> - Implementation of types</A><DD>
<DT><A HREF="#COutputSupport"><B>4.2</B> - Support routines</A><DD>
<DT><A HREF="#COutputAssert"><B>4.3</B> - Run-time checking</A><DD>
</DL>
<DT><A HREF="#DiskOutput"><B>5</B> - Disk reading and writing</A><DD>
<DL>
<DT><A HREF="#DiskWrite"><B>5.1</B> - Disk writing routines</A><DD>
<DT><A HREF="#DiskRead"><B>5.2</B> - Disk reading routines</A><DD>
<DT><A HREF="#DiskPrint"><B>5.3</B> - Object printing routines</A><DD>
<DT><A HREF="#DiskAlias"><B>5.4</B> - Aliasing</A><DD>
<DT><A HREF="#Application"><B>5.5</B> - Application to calculus</A><DD>
</DL>
<DT><A HREF="#Templates"><B>6</B> - Template files</A><DD>
</DL>
<HR>
<H2><A NAME="Intro">1. Introduction</A></H2>
<P>
This document describes a tool, <CODE>calculus</CODE>, 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.
</P>
<P>
<CODE>calculus</CODE> 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.
</P>
<P>
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.
</P>
<P>
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.
</P>
<H3><A NAME="Options">1.1. Using calculus</A></H3>
<P>
The general form for invoking <CODE>calculus</CODE> is as follows:
<PRE>
calculus [ <I>options</I> ] <I>input</I> .... [ <I>output</I> ]
</PRE>
where <I>input</I> is a file containing the input type system description
and <I>output</I> is the directory where the files implementing this
system are to be output. This directory must already exist. If no
<I>output</I>
argument is given then the current working directory is assumed.
Note that several <I>input</I> files can be given. Unless
<A HREF="#Module">otherwise specified</A> it is the last file which
is used to generate the output.
</P>
<P>
The form in which the <A HREF="#TextInput">input type systems</A>
are expressed is described below. The form of the output depends
on
<I>options</I>. By default, the C implementation of the type system
is output. If the <CODE>-t</CODE> option is passed to <CODE>calculus</CODE>
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.
</P>
<P>
Note that it is necessary to check any program written using
<CODE>calculus</CODE> 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.
</P>
<H3><A NAME="Example">1.2. Example program</A></H3>
<P>
The program <CODE>calculus</CODE> itself was written using a type
system specified using the <CODE>calculus</CODE> 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.
</P>
<HR>
<H2><A NAME="TextInput">2. Input syntax</A></H2>
<P>
The overall input file format is as follows:
<PRE>
<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>
</PRE>
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.
</P>
<P>
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.
</P>
<H3><A NAME="InputPrim">2.1. Primitives</A></H3>
<P>
Primitives form the basic components from which the other types in
the algebra are built up. They are described as follows:
<PRE>
<I>primitive</I> :
<I>object-identifier</I> = <I>quoted-type</I> ;
</PRE>
where the primitive identifier is given by:
<PRE>
<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> )
</PRE>
and the primitive definition is a string which gives the C type corresponding
to this primitive:
<PRE>
<I>quoted-type</I> :
<I>string</I>
</PRE>
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.
</P>
<P>
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.
</P>
<H3><A NAME="InputIdent">2.2. Identities</A></H3>
<P>
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:
<PRE>
<I>identity</I> :
<I>object-identifier</I> = <I>type</I> ;
</PRE>
where the definition type, <I>type</I>, is as described
<A HREF="#InputType">below</A>.
</P>
<H3><A NAME="InputEnum">2.3. Enumerations</A></H3>
<P>
Enumerations are used to define types which can only take values from
some finite set. They are described as follows:
<PRE>
<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> } ;
</PRE>
where:
<PRE>
<I>base-enumeration</I> :
<I>identifier</I>
</PRE>
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.
</P>
<P>
The enumeration constants themselves are defined as follows:
<PRE>
<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>
</PRE>
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.
</P>
<P>
Enumerations thus correspond to enumeration types in C, except that
they are genuinely distinct types.
</P>
<H3><A NAME="InputStruct">2.4. Structures</A></H3>
<P>
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:
<PRE>
<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> ;
</PRE>
where:
<PRE>
<I>base-structure</I> :
<I>identifier</I>
</PRE>
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.
</P>
<P>
The structure components themselves are defined as follows:
<PRE>
<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>
</PRE>
The optional <A HREF="#OutputStruct">component initialiser strings</A>
are explained below.
</P>
<P>
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.
</P>
<H3><A NAME="InputUnion">2.5. Unions</A></H3>
<P>
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:
<PRE>
<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> ;
</PRE>
where:
<PRE>
<I>base-union</I> :
<I>identifier</I>
</PRE>
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.
</P>
<P>
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:
<PRE>
<I>field-group</I> :
{ <I>field-list</I> }
<I>field</I> :
#<I><SUB>opt</SUB></I> #<I><SUB>opt</SUB> field-identifier-list</I> -> <I>component-group
</I>
#<I><SUB>opt</SUB></I> #<I><SUB>opt</SUB> field-identifier-list</I> -> <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>
</PRE>
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.
</P>
<P>
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.
</P>
<P>
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:
<PRE>
<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>
</PRE>
where:
<PRE>
<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>
</PRE>
Note that the map parameter and return types are given by:
<PRE>
<I>extended-type</I> :
<I>type</I>
<I>quoted-type</I>
</PRE>
In addition to the <A HREF="#InputType">types derived from the algebra</A>
it is possible to use quoted C types in this context.
</P>
<P>
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.
</P>
<H3><A NAME="InputType">2.6. Type constructors</A></H3>
<P>
The types derived from the algebra may be described as follows:
<PRE>
<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>
</PRE>
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.
</P>
<P>
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.
</P>
<H3><A NAME="Module">2.7. Relations between algebras</A></H3>
<P>
As <A HREF="#Options">mentioned above</A>, more than one input algebra
may be specified to <CODE>calculus</CODE>. 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 <CODE>-A</CODE><I>name</I>, where <I>name</I>
is the name of the algebra to be used for output.
</P>
<P>
Types may be imported from one algebra to another by means of commands
of the form:
<PRE>
<I>import</I> :
IMPORT <I>identifier</I> ;
IMPORT <I>identifier</I> :: <I>identifier</I> ;
</PRE>
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>.
</P>
<P>
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.
</P>
<HR>
<H2><A NAME="TokenOutput">3. Output type system specification</A></H2>
<P>
In this section we document the basic output of <CODE>calculus</CODE>.
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.
</P>
<P>
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.
</P>
<P>
The output is split among several header files in the specified output
directory. The main output is printed into <I>name</I><CODE>.h</CODE>,
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 <I>union</I><CODE>_map.h</CODE> and <I>union</I><CODE>_hdr.h</CODE>.
</P>
<H3><A NAME="OutputInfo">3.1. Version information</A></H3>
<P>
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.
</P>
<H3><A NAME="OutputBasic">3.2. Basic types</A></H3>
<P>
Six abstract type operators, each taking a type as argument and returning
a type, are specified as follows:
<PRE>
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> ) ;
</PRE>
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 <CODE>calculus</CODE>. Similarly <CODE>STACK</CODE> constructs
may be suppressed using <CODE>-z</CODE>.)
</P>
<P>
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:
<PRE>
LIST ( PTR ( int ) )
</PRE>
representing a list of pointers to <CODE>int</CODE>.
</P>
<P>
An integral type:
<PRE>
INT_TYPE <I>name</I>_dim ;
</PRE>
is specified, where <I>name</I> is the overall algebra name. This
type is used to represent the sizes of vectors.
</P>
<P>
A function pointer type:
<PRE>
typedef void ( *DESTROYER ) () ;
</PRE>
is specified, which represents a destructor function. Two destructor
functions are specified:
<PRE>
void destroy_<I>name</I> () ;
void dummy_destroy_<I>name</I> () ;
</PRE>
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.
</P>
<H3><A NAME="OutputSize">3.3. Operations on sizes</A></H3>
<P>
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.
</P>
<P>
For each basic type in the algebra (a primitive, a structure or a
union), there is a constant expression:
<PRE>
SIZE ( <I>t</I> ) SIZE_<I>type</I> ;
</PRE>
where <I>t</I> denotes the type itself, and <I>type</I> is the associated
type name.
</P>
<P>
For the five other type constructors <A HREF="#OutputBasic">described
above</A> there are constant expressions:
<PRE>
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> ) ;
</PRE>
for any type <I>t</I>.
</P>
<P>
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:
<PRE>
SIZE ( <I>t</I> ) SCALE ( SIZE ( <I>t</I> ), INT_TYPE <I>itype</I> ) ;
</PRE>
for any type <I>t</I> and any integral type <I>itype</I>.
</P>
<H3><A NAME="OutputPtr">3.4. Operations on pointers</A></H3>
<P>
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.
</P>
<H4>Simple pointer constructs</H4>
<P>
There are several simple operations on pointers, given as follows:
<PRE>
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> ) ) ;
</PRE>
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.
</P>
<H4>Unique pointers</H4>
<P>
There are also constructs for generating and destroying unique pointers:
<PRE>
PTR ( <I>t</I> ) UNIQ_ptr ( TYPE <I>t</I> ) ;
void DESTROY_UNIQ_ptr ( PTR ( <I>t</I> ) ) ;
</PRE>
A unique pointer is guaranteed to be different from all other undestroyed
pointers. Dereferencing a unique pointer is undefined.
</P>
<H4>Pointer construction and destruction</H4>
<P>
The constructs:
<PRE>
PTR ( <I>t</I> ) MAKE_ptr ( SIZE ( <I>t</I> ) ) ;
void DESTROY_ptr ( PTR ( <I>t</I> ), SIZE ( <I>t</I> ) ) ;
</PRE>
are used to respectively create and destroy a pointer to a given type.
</P>
<H4>Assignment and dereference constructs</H4>
<P>
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:
<PRE>
void COPY_<I>type</I> ( PTR ( <I>t</I> ), <I>t</I> ) ;
<I>t</I> DEREF_<I>type</I> ( PTR ( <I>t</I> ) ) ;
</PRE>
where <I>t</I> is the type involved and <I>type</I> is the associated
short name.
</P>
<P>
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:
<PRE>
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> ) ;
</PRE>
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.
</P>
<P>
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:
<PRE>
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> ) ) ;
</PRE>
</P>
<H3><A NAME="OutputList">3.5. Operations on lists</A></H3>
<P>
The <CODE>LIST</CODE> type constructor is used to represent a list
of objects of type <I>t</I>.
</P>
<H4>Simple list constructs</H4>
<P>
There are several simple list constructs:
<PRE>
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> ) ) ;
</PRE>
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.
</P>
<H4>Unique lists</H4>
<P>
There are also constructs for generating and destroying unique lists:
<PRE>
LIST ( <I>t</I> ) UNIQ_list ( TYPE <I>t</I> ) ;
void DESTROY_UNIQ_list ( LIST ( <I>t</I> ) ) ;
</PRE>
A unique lists is guaranteed to be different from all other undestroyed
lists. Taking the head or tail of a unique list is undefined.
</P>
<H4>List construction and destruction</H4>
<P>
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:
<PRE>
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> ) ) ;
</PRE>
where <I>type</I> is the short type name.
</P>
<P>
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.
</P>
<P>
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:
<PRE>
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> ) ) ) ;
</PRE>
There is also a generic list destruction construct:
<PRE>
STATEMENT DESTROY_list ( LIST ( <I>t</I> ), SIZE ( <I>t</I> ) ) ;
</PRE>
which may be used to destroy all the elements in a list.
</P>
<H3><A NAME="OutputStack">3.6. Operations on stacks</A></H3>
<P>
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:
<PRE>
STACK ( <I>t</I> ) NULL_stack ( TYPE <I>t</I> ) ;
int IS_NULL_stack ( STACK ( <I>t</I> ) ) ;
</PRE>
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:
<PRE>
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> ) ) ;
</PRE>
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.
</P>
<P>
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:
<PRE>
LIST ( <I>t</I> ) LIST_stack ( STACK ( <I>t</I> ) ) ;
STACK ( <I>t</I> ) STACK_list ( LIST ( <I>t</I> ) ) ;
</PRE>
for explicitly converting between lists and stacks.
</P>
<H3><A NAME="OutputVec">3.7. Operations on vectors</A></H3>
<P>
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:
<PRE>
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> ) ) ) ;
</PRE>
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.
</P>
<P>
In general a vector may be created or destroyed using the operators:
<PRE>
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> ) ) ;
</PRE>
Finally a vector can be trimmed using:
<PRE>
STATEMENT TRIM_vec ( VEC ( <I>t</I> ), SIZE ( <I>t</I> ), int, int, lvalue VEC (
<I>t</I> ) ) ;
</PRE>
the two integral arguments giving the lower and upper bounds for the
trimming operation.
</P>
<H3><A NAME="OutputVecPtr">3.8. Operations on vector pointers</A></H3>
<P>
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:
<PRE>
VEC_PTR ( <I>t</I> ) VEC_PTR_vec ( VEC ( <I>t</I> ) ) ;
PTR ( <I>t</I> ) PTR_vec_ptr ( VEC_PTR ( <I>t</I> ) ) ;
</PRE>
The first transforms a vector into a vector pointer (pointing to its
first argument). The second transforms a vector pointer into a normal
pointer.
</P>
<H3><A NAME="OutputPrim">3.9. Operations on primitives</A></H3>
<P>
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.
</P>
<H3><A NAME="OutputIdent">3.10. Operations on identities</A></H3>
<P>
Each identity specified within the algebra maps onto a <CODE>typedef</CODE>
in the output file. There are no operations on identities.
</P>
<H3><A NAME="OutputEnum">3.11. Operations on enumerations</A></H3>
<P>
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:
<PRE>
<I>t enum_member</I> ;
</PRE>
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:
<PRE>
unsigned long ORDER_<I>enum</I> ;
</PRE>
giving one more than the maximum enumerator in the enumeration.
</P>
<H3><A NAME="OutputStruct">3.12. Operations on structures</A></H3>
<P>
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.
</P>
<P>
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:
<PRE>
PTR ( <I>ctype</I> ) <I>struct_comp</I> ( PTR ( <I>t</I> ) ) ;
</PRE>
which transforms a pointer to the structure into a pointer to the
component. There is also an operation:
<PRE>
STATEMENT MAKE_<I>struct</I> ( <I>ctype</I>, ...., PTR ( <I>t</I> ) ) ;
</PRE>
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>.
</P>
<P>
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:
<PRE>
PTR ( <I>btype</I> ) CONVERT_<I>struct_base</I> ( PTR ( <I>t</I> ) ) ;
</PRE>
where <I>struct</I> and <I>base</I> are the short names of <I>t</I>
and
<I>btype</I> respectively.
</P>
<H3><A NAME="OutputUnion">3.13. Operations on unions</A></H3>
<P>
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:
<PRE>
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> ) ;
</PRE>
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.
</P>
<H4>Union construction operations</H4>
<P>
Most of the output for the union type <I>t</I> is output into the
file
<I>union</I><CODE>_ops.h</CODE>. This contains a construct:
<PRE>
unsigned int TAG_<I>union</I> ( <I>t</I> ) ;
</PRE>
for extracting the discriminant tag from a union.
</P>
<P>
For each shared component, <I>comp</I>, of <I>t</I> of type <I>ctype</I>,
say, there is an operator:
<PRE>
PTR ( <I>ctype</I> ) <I>union_comp</I> ( <I>t</I> ) ;
</PRE>
which extracts this component from the union.
</P>
<P>
For each field, <I>field</I>, of the union there are constructs:
<PRE>
unsigned int <I>union_field</I>_tag ;
int IS_<I>union_field</I> ( <I>t</I> ) ;
</PRE>
giving the (constant) discriminant tag associated with this field,
and a test for whether an object of type <I>t</I> has this discriminant.
</P>
<P>
In addition, for each unshared component, <I>comp</I>, of <I>field</I>
of type <I>ctype</I>, say, there is an operator:
<PRE>
PTR ( <I>ctype</I> ) <I>union_field_comp</I> ( <I>t</I> ) ;
</PRE>
which extracts this component from the union.
</P>
<P>
There are also operations for constructing and deconstructing objects
of type <I>t</I> for field <I>field</I> given as follows:
<PRE>
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> ) ;
</PRE>
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.
</P>
<P>
<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.
</P>
<H4>Union field sets</H4>
<P>
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:
<PRE>
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> ) ;
</PRE>
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.
</P>
<P>
The valid range of union tags for this set can be given by the two
constants:
<PRE>
unsigned int <I>union_field</I>_tag ;
unsigned int <I>union_field</I>_etc_tag ;
</PRE>
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>.
</P>
<H4>Inheritance in unions</H4>
<P>
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:
<PRE>
<I>btype</I> CONVERT_<I>union_base</I> ( <I>t</I> ) ;
</PRE>
where <I>union</I> and <I>base</I> are the short names of <I>t</I>
and
<I>btype</I> respectively.
</P>
<H4><A NAME="OutputUnionMaps">Union maps</A></H4>
<P>
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:
<PRE>
<I>map_ret map_union</I> ( <I>t</I>, <I>map_par</I>, .... ) ;
</PRE>
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:
<PRE>
<I>map_ret map_union</I> ( <I>t</I>, DESTROYER, <I>map_par</I>, .... ) ;
</PRE>
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:
<PRE>
<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>,
....
} ;
</PRE>
where there is one entry per union field.
</P>
<P>
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:
<PRE>
#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> ) ;
</PRE>
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.
</P>
<HR>
<H2><A NAME="COutput">4. Implementation details</A></H2>
<H3><A NAME="COutputTypes">4.1. Implementation of types</A></H3>
<P>
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:
<PRE>
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> ;
</PRE>
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:
<CENTER>
<IMG SRC="../images/calc.gif" ALT="Packing of types">
</CENTER>
</P>
<P>
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.
</P>
<P>
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>.
</P>
<P>
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.
</P>
<P>
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.
</P>
<P>
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.
</P>
<P>
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.
</P>
<P>
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.
</P>
<P>
Stack types are identical to list types, with the head of the list
corresponding to the top of the stack.
</P>
<P>
Vector pointer and vector types are all implemented by structures
defined as follows:
<PRE>
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 ;
</PRE>
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.
</P>
<P>
All size types are implemented as <CODE>int</CODE>.
</P>
<H3><A NAME="COutputSupport">4.2. Support routines</A></H3>
<P>
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:
<PRE>
<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 ) ;
</PRE>
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.
</P>
<P>
Certain generic list functions must also be provided, namely:
<PRE>
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> * ) ;
</PRE>
which implement the constructs <CODE>DESTROY_list</CODE>,
<CODE>REVERSE_list</CODE>, <CODE>APPEND_list</CODE> and
<CODE>END_list</CODE> respectively.
</P>
<P>
Finally a dummy empty vector:
<PRE>
<I>name</I>_VEC empty_<I>name</I>_vec ;
</PRE>
needs to be defined.
</P>
<P>
Examples of these support routines can be found in the
<A HREF="#Example"><CODE>calculus</CODE> program</A> itself.
</P>
<H3><A NAME="COutputAssert">4.3. Run-time checking</A></H3>
<P>
The type checking facilities supported by <CODE>calculus</CODE> 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 <CODE>calculus</CODE> 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.
</P>
<P>
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.
</P>
<P>
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.
</P>
<HR>
<H2><A NAME="DiskOutput">5. Disk reading and writing</A></H2>
<P>
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.
</P>
<P>
The disk reading and writing routines are output into the files
<CODE>read_def.h</CODE> and <CODE>write_def.h</CODE> respectively
if the
<CODE>-d</CODE> command-line option is passed to <CODE>calculus</CODE>.
The object printing routines are output if the <CODE>-p</CODE> option
is given, with additional code designed for use with run-time debuggers
being added if the <CODE>-a</CODE> option is also given.
</P>
<P>
All of these routines use extra constructs output in the main output
files (<I>name</I><CODE>.h</CODE> and <I>union</I><CODE>_ops.h</CODE>),
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.
</P>
<H3><A NAME="DiskWrite">5.1. Disk writing routines</A></H3>
<P>
The disk writing routines output in <CODE>write_def.h</CODE> consist
of a function:
<PRE>
static void WRITE_<I>type</I> ( <I>t</I> ) ;
</PRE>
for each type <I>t</I> mentioned within the algebra description, which
writes an object of that type to disk.
</P>
<P>
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:
<PRE>
LIST ( <I>t</I> ) -> list_<I>type</I>
PTR ( <I>t</I> ) -> ptr_<I>type</I>
STACK ( <I>t</I> ) -> stack_<I>type</I>
VEC ( <I>t</I> ) -> vec_<I>type</I>
VEC_PTR ( <I>t</I> ) -> vptr_<I>type</I>
</PRE>
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.
</P>
<P>
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:
<PRE>
<I>extra</I> :
<I>type-list<SUB>opt</SUB></I>
<I>type-list</I> :
<I>type</I> ;
<I>type-list type</I> ;
</PRE>
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):
<PRE>
void WRITE_BITS ( int, unsigned int ) ;
void WRITE_DIM ( <I>name</I>_dim ) ;
void WRITE_ALIAS ( unsigned int ) ;
</PRE>
for writing a number of bits to disk, writing a vector dimension and
writing an <A HREF="#DiskAlias">object alias</A>.
</P>
<P>
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.
</P>
<H3><A NAME="DiskRead">5.2. Disk reading routines</A></H3>
<P>
The disk reading routines output in <CODE>read_def.h</CODE> are exactly
analogous to the disk writing routines. For each type <I>t</I> (except
primitives) there is a function or macro:
<PRE>
static <I>t</I> READ_<I>type</I> ( void ) ;
</PRE>
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:
<PRE>
unsigned int READ_BITS ( int ) ;
<I>name</I>_dim READ_DIM ( void ) ;
unsigned int READ_ALIAS ( void ) ;
</PRE>
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.
</P>
<H3><A NAME="DiskPrint">5.3. Object printing routines</A></H3>
<P>
The object printing routines output in <CODE>print_def.h</CODE> consist
of a function or macro:
<PRE>
static void PRINT_<I>type</I> ( FILE *, <I>t</I>, char *, int ) ;
</PRE>
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:
<PRE>
void OUTPUT_<I>type</I> ( FILE *, <I>t</I> ) ;
</PRE>
for each primitive type. The <CODE>PRINT_</CODE><I>type</I> functions
may be overridden by means of macros as before.
</P>
<P>
The printing routines are under the control of three variables defined
as follows:
<PRE>
static int print_indent_step = 4 ;
static int print_ptr_depth = 1 ;
static int print_list_expand = 0 ;
</PRE>
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.
</P>
<P>
One application of these object printing routines is to aid debugging
programs written using the <CODE>calculus</CODE> 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
<CODE>calculus</CODE> will generate functions:
<PRE>
void DEBUG_<I>type</I> ( <I>t</I> ) ;
</PRE>
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:
<PRE>
void DEBUG_<I>type</I> ( <I>t</I> * ) ;
</PRE>
These debugging routines are only defined conditionally, if the macro
<CODE>DEBUG</CODE> is defined.
</P>
<H3><A NAME="DiskAlias">5.4. Aliasing</A></H3>
<P>
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 <CODE>calculus</CODE> 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.
</P>
<P>
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.
</P>
<P>
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.
</P>
<P>
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:
<PRE>
ALIAS_<I>union_field</I> ( <I>comp</I>, ...., <I>x</I> ) ;
</PRE>
(where <I>comp</I> ranges over all the union components) is called
prior to writing the object components to disk.
</P>
<P>
Similarly in the disk reading case, the object being read, <I>x</I>,
is initialised by calling the user-defined routine:
<PRE>
UNALIAS_<I>union_field</I> ( <I>x</I> ) ;
</PRE>
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:
<PRE>
UNIFY_<I>union_field</I> ( <I>comp</I>, ...., <I>x</I> ) ;
</PRE>
(where <I>comp</I> ranges over all the union components) is called
to assign these values to <I>x</I> before returning.
</P>
<P>
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.
</P>
<P>
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:
<PRE>
void clear_<I>name</I>_alias ( void ) ;
</PRE>
to clear all aliases.
</P>
<P>
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:
<PRE>
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 ) ;
</PRE>
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"><CODE>calculus</CODE> program</A> itself.
</P>
<H3><A NAME="Application">5.5. Application to calculus</A></H3>
<P>
As <A HREF="#Example">mentioned above</A>, the <CODE>calculus</CODE>
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.
</P>
<P>
If the <CODE>-w</CODE> command-line option is specified to
<CODE>calculus</CODE> 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 <CODE>calculus</CODE> if the <CODE>-r</CODE>
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 <CODE>-o</CODE> option.
</P>
<HR>
<H2><A NAME="Templates">6. Template files</A></H2>
<P>
It is possible to use <CODE>calculus</CODE> to generate an output
file from a template input file, <I>template</I>, using the syntax:
<PRE>
calculus [ <I>options</I> ] <I>input</I> .... -T<I>template output</I>
</PRE>
The template file consists of a list of either template directives
or source lines containing escape sequences which are expanded by
<CODE>calculus</CODE>. 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.
</P>
<P>
There are two template directives; loops take the form:
<PRE>
@loop <I>control</I>
....
@end
</PRE>
and conditionals take the form:
<PRE>
@if <I>condition</I>
....
@else
....
@endif
</PRE>
or:
<PRE>
@if <I>condition</I>
....
@endif
</PRE>
where <CODE>....</CODE> stands for any sequence of template directives
or source lines.
</P>
<P>
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.
</P>
<P>
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.
</P>
<P>
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
<CODE>calculus</CODE> 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.
</P>
<P>
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.
</P>
<P>
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.
</P>
<P>
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.
</P>
<P>
Within a <CODE>struct</CODE> loop, <CODE>%SN</CODE> gives the structure
name and <CODE>%SM</CODE> gives the short structure name.
</P>
<P>
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.
</P>
<P>
As an example, the following template file gives a simple algebra
pretty printer:
<PRE>
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 -> {
@loop union.field.comp
%CT %CN ;
@end
} ;
@end
} ;
@end
</PRE>
</P>
<HR>
<P><I>Part of the <A HREF="../index.html">TenDRA Web</A>.<BR>Crown
Copyright © 1998.</I></P>
</BODY>
</HTML>