Calculus Users' Guide

ii. Using calculus

The form in which the input type systems are expressed is described below. The form of the output depends on options. By default, the C implementation of the type system is output. If the -t option is passed to calculus then #pragma token statements describing the type system specification are output. This specification is given below, with some of the more important implementation details being described in the following section.

Note that it is necessary to check any program written using calculus against the #pragma token 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 basic functions) may be dependent upon the implementation, and so not be suitable for this form of checking.

iii. Example program

The program calculus itself was written using a type system specified using the calculus 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.

1.1. Primitives

Primitives form the basic components from which the other types in the algebra are built up. They are described as follows:

primitive:
			object-identifier = quoted-type;

where the primitive identifier is given by:

object-identifier:
			#?:? identifier
			#?:? identifier(identifier)

and the primitive definition is a string which gives the C type corresponding to this primitive:

quoted-type:
			string

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.

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.

1.2. Identities

Identities are used to associate a name with a particular type in the algebra. In this they correspond to typedefs in C. They are described as follows:

identity:
			object-identifier = type;

where the definition type, type, is as described below.

1.3. Enumerations

Enumerations are used to define types which can only take values from some finite set. They are described as follows:

enumeration:
			enum !? object-identifier = { enumerator-list };
			enum !? object-identifier = base-enumeration + { enumerator-list };

where:

base-enumeration:
			identifier

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.

The enumeration constants themselves are defined as follows:

enumerator:
			identifier
			identifier = enumerator-value

enumerator-list:
			enumerator
			enumerator-list, enumerator

Each enumerator is assigned a value in an ascending sequence, starting at zero. The next value to be assigned can be set using an enumerator-value. This is an expression formed from integers, identifiers 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 enumerator-values. All enumerator evaluation is done in the unsigned long type of the host machine. Values containing more than 32 bits are not portable.

Enumerations thus correspond to enumeration types in C, except that they are genuinely distinct types.

1.4. Structures

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:

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

where:

base-structure:
			identifier

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.

The structure components themselves are defined as follows:

component-group:
			{ component-list? }

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?

component-initialiser:
			= string

The optional component initialiser strings are explained below.

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.

1.5. Unions

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:

union:
			union object-identifier = component-group + field-group map-group?;
			union object-identifier = base-union + field-group map-group?;

where:

base-union:
			identifier

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.

The component-group gives a set of components which are common to all the different union cases. The cases themselves are described as follows:

field-group:
			{ field-list }

field:
			#? #? field-identifier-list->component-group
			#? #? field-identifier-list->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

The optional one or two hashes which may be used to qualify a list of field identifiers are used to indicate aliasing in the disk reading and writing routines. The base-field case is a notational convenience which allows one field in a union to inherit all the components of another field.

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.

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:

map-group:
			:[map-list?]

map:
			extended-type #? identifier(parameter-list?)

map-list:
			map
			map-list map

where:

parameter-list:
			parameter-declarations
			parameter-list; parameter-declarations

parameter-declarations:
			extended-type parameter-declarators

parameter-declarators:
			identifier
			parameter-declarators, identifier

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

extended-type:
								type
								quoted-type

In addition to the types derived from the algebra it is possible to use quoted C types in this context.

A map may be qualified by means of a hash. This means that the associated function also takes a destructor function as a parameter.

1.6. Type constructors

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

type:
			identifier
			PTR type
			LIST type
			STACK type
			VEC type
			VEC_PTR type

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.

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.

1.7. Relations between algebras

As mentioned above, more than one input algebra may be specified to calculus. 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 -A name, where name is the name of the algebra to be used for output.

Types may be imported from one algebra to another by means of commands of the form:

import:
			IMPORT identifier;
			IMPORT identifier::identifier;

which fit into the main syntax as an item. The first form imports all the types from the algebra given by identifier into the current algebra. The second imports a single type, given by the second identifier from the algebra given by the first identifier.

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 import commands can be used to express subalgebras in a simple fashion.

2.1. Version information

Certain basic information about the input algebra is included in name.h. name _NAME is a string literal giving the overall algebra name. name_VERSION is a string literal giving the algebra version number. name_SPECIFICATION and name_IMPLEMENTATION are flags which take the values 0 or 1 depending on whether the specification of the type system in terms of #pragma token statements or the C implementation is included.

2.2. Basic types

Six abstract type operators, each taking a type as argument and returning a type, are specified as follows:

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

These represent a pointer to an object of type t, a list of objects of type t, a stack of objects of type t, a vector of objects of type t, a pointer into a vector of objects of type t, and an allocation block size for type t respectively. (It is possible to suppress all constructs involving VEC or VEC_PTR by passing the -x command-line option to calculus. Similarly STACK constructs may be suppressed using -z.)

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:

LIST(PTR(int))

representing a list of pointers to int.

An integral type:

INT_TYPE name_dim;

is specified, where name is the overall algebra name. This type is used to represent the sizes of vectors.

A function pointer type:

typedef void (*DESTROYER)();

is specified, which represents a destructor function. Two destructor functions are specified:

void destroy_name();
void dummy_destroy_name();

where name is as above. destroy_name is the default destructor, whereas dummy_destroy_name is a dummy destructor which has no effect. The details of the arguments passed to the destructors and so on are implementation dependent.

2.3. Operations on sizes

The SIZE type constructor is used to represent a multiple of the size of a type. It is used, for example, in the pointer stepping construct STEP_ptr 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.

For each basic type in the algebra (a primitive, a structure or a union), there is a constant expression:

SIZE ( t ) SIZE_type;

where t denotes the type itself, and type is the associated type name.

For the five other type constructors described above there are constant expressions:

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

for any type t.

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:

SIZE(t) SCALE(SIZE(t), INT_TYPE itype);

for any type t and any integral type itype.

2.4. Operations on pointers

The PTR type constructor is used to represent a pointer to an object of type t. It should be emphasised that this construct is not in general implemented by means of the C pointer construct.

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

PTR(t) UNIQ_ptr(TYPE t);
void DESTROY_UNIQ_ptr(PTR(t));

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

void COPY_type(PTR(t), t);
t DEREF_type(PTR(t));

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

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

2.5. Operations on lists

The LIST type constructor is used to represent a list of objects of type t.

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

LIST(t) UNIQ_list(TYPE t);
void DESTROY_UNIQ_list(LIST(t));

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

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

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

2.6. Operations on stacks

The STACK type constructor is used to represent stacks of objects of type t. Empty stacks can be created and tested for:

STACK(t) NULL_stack(TYPE t);
int IS_NULL_stack(STACK(t));

For each type t 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:

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

where type is the short type name. There are also generic constructs, such as PUSH_ptr for pushing any pointer type, similar to the generic list constructors above.

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:

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

for explicitly converting between lists and stacks.

2.7. Operations on vectors

The VEC type constructor is used to represent vectors of objects of type t. There are a number of simple operations on vectors:

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

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 name_dim is used to represent vector sizes). A pointer to a vector can be transformed into a pointer to the elements of the vector.

In general a vector may be created or destroyed using the operators:

STATEMENT MAKE_vec(SIZE(t), name_dim, lvalue VEC(t));
STATEMENT DESTROY_vec(VEC(t), SIZE(t));

Finally a vector can be trimmed using:

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

the two integral arguments giving the lower and upper bounds for the trimming operation.

2.8. Operations on vector pointers

The VEC_PTR type constructor is used to represent a pointer to an element of a vector of objects of type t. Apart from the basic constructors already mentioned, there are only two operations on vector pointers:

VEC_PTR(t) VEC_PTR_vec(VEC(t));
PTR(t) PTR_vec_ptr(VEC_PTR(t));

The first transforms a vector into a vector pointer (pointing to its first argument). The second transforms a vector pointer into a normal pointer.

2.9. Operations on primitives

Each primitive specified within the algebra maps onto a typedef 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.

2.10. Operations on identities

Each identity specified within the algebra maps onto a typedef in the output file. There are no operations on identities.

2.11. Operations on enumerations

Each enumeration specified within the algebra maps onto an unsigned integral type in the output file. The basic operations listed above are always generated unless it has been indicated that no lists of this type will be formed, when CONS_type 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:

t enum_member;

where t is the enumeration type, enum is the short type name, and member 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:

unsigned long ORDER_enum;

giving one more than the maximum enumerator in the enumeration.

2.12. Operations on structures

Each structure specified within the algebra maps onto a typedef defining the type to be the C structure with the given components. In addition to the basic operations listed above there are also field selectors defined.

Suppose that t is a structure type with short name struct, and that comp is a component of t of type ctype. Then there is an operation:

PTR(ctype) struct_comp(PTR(t));

which transforms a pointer to the structure into a pointer to the component. There is also an operation:

STATEMENT MAKE_struct(ctype, ...., PTR(t));

where ctype 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 MAKE_struct statement. The parameters to the operation may be referred to by the corresponding component name followed by _. The partially initialised object may be referred to by the special character sequence %0. Any remainder operations should be written as %% rather than %.

Inheritance in structures is handled as follows: if t is a derived structure with base structure btype then there is an operation:

PTR(btype) CONVERT_struct_base(PTR(t));

where struct and base are the short names of t and btype respectively.

2.13. Operations on unions

Each union specified within the algebra maps onto an opaque type in the output file. In addition to the basic operations listed above there are a number of other constructs output into name.h, namely:

unsigned int ORDER_union;
t NULL_union;
int IS_NULL_union(t);
int EQ_union(t, t);

where t denotes the union type, and union is the short type name. ORDER_union is a constant value giving the number of union fields. NULL_union is a distinguished constant value of type t. Values of type t may be compared against this distinguished value, or against each other.

unsigned int TAG_union(t);

PTR(ctype) union_comp(t);

unsigned int union_field_tag;
int IS_union_field(t);

PTR(ctype) union_field_comp(t);

STATEMENT MAKE_union_field(ctype, ...., lvalue t);
STATEMENT DECONS_union_field(lvalue ctype, ...., t);
STATEMENT DESTROY_union_field(DESTROYER, lvalue ctype, ...., t);

int IS_union_field_etc(t);
PTR(ctype) union_field_etc_comp(t);
STATEMENT MAKE_union_field_etc(unsigned int, ctype, ...., lvalue t);
STATEMENT MODIFY_union_field_etc(unsigned int, t);
STATEMENT DECONS_union_field_etc(lvalue ctype, ...., t);
STATEMENT DESTROY_union_field_etc(DESTROYER, lvalue ctype, ...., t);

unsigned int union_field_tag;
unsigned int union_field_etc_tag;

btype CONVERT_union_base(t);

map_ret map_union(t, map_par, ....);

map_ret map_union(t, DESTROYER, map_par, ....);

map_ret(*map_union_table[ORDER_union])(t, map_par, ....) = {
	....
	map_union_field,
	....
} ;

#define HDR_map_union_field                               \
map_ret map_union_field(name_union, destroyer, par, ....) \
    t name_union;                                         \
    DESTROYER destroyer; /* if required */                \
    map_par par;                                          \
    ....                                                  \
    {                                                     \
        ctype comp;                                       \
        ....                                              \
        DECONS_union_field(comp, ...., name_union);

3.1. Implementation of types

The C implementation of the type system specified above is based on a single type, name, with the same name as the input algebra. This is defined as follows:

typedef union name_tag {
    unsigned int ag_tag;
    union name_tag *ag_ptr;
    unsigned ag_enum;
    unsigned long ag_long_enum;
    name_dim ag_dim;
    t ag_prim_type;
    ....
} name;

where t runs over all the primitive types. All of the types in the algebra can be packed into a block of cells of type name. 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:

Primitive types are implemented by a typedef defining the type in terms of its given definition. A primitive type can be packed into a single cell using the appropriate ag_prim_type field of the union.

Identity types are implemented by a typedef defining the type as being equal to another type from the algebra.

Enumeration types are all implemented as unsigned int if all its values fit into 16 bits, or unsigned long otherwise. An enumeration type can be packed into a single cell using the ag_enum or ag_long_enum field of the union.

Structure types are implemented by a typedef defining the type to be the C structure with the given components. A structure type may be packed into a block of cells by packing each of the components in turn.

Union types are all implemented by a pointer to name. This pointer references a block of cells. The null pointer represents NULL_union, otherwise the first cell contains the union discriminant tag (in the ag_tag 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 ag_ptr field of the union.

Pointer types are all implemented by a pointer to name. Null pointers represent NULL_ptr, otherwise the pointer references a single cell. This cell contains a pointer to the packed version of the object being pointed to in its ag_ptr field. A pointer type itself can be packed into a single cell using the ag_ptr field of the union.

List types are all implemented by a pointer to name. Null pointers represent NULL_list, otherwise the pointer references a block of two cells. The first cell gives the tail of the list in its ag_ptr field; the second cell contains a pointer to the packed version of the head of the list in its ag_ptr field. A list type itself can be packed into a single cell using the ag_ptr field of the union.

Stack types are identical to list types, with the head of the list corresponding to the top of the stack.

Vector pointer and vector types are all implemented by structures defined as follows:

typedef unsigned int name_dim;

typedef struct {
    name *vec;
    name *ptr;
} name_VEC_PTR;

typedef struct {
    name_dim dim;
    name_VEC_PTR elems;
} name_VEC;

The vec field of a vector pointer contains a pointer to a block of cells containing the packed versions of the elements of the vector. The ptr 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 ag_ptr 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 ag_dim field.

All size types are implemented as int.

3.2. Support routines

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:

name *gen_name(unsigned int);
void destroy_name(name *, unsigned int);
void dummy_destroy_name(name *, unsigned int);

where gen_name allocates a block of cells of the given size, destroy_name deallocates the given block, and dummy_destroy_name has no effect. The precise details of how the memory management is to be handled are left to the user.

Certain generic list functions must also be provided, namely:

void destroy_name_list(name *, unsigned int);
name *reverse_name_list(name *);
name *append_name_list(name *, name *);
name *end_name_list(name *);

which implement the constructs DESTROY_list, REVERSE_list, APPEND_list and END_list respectively.

Finally a dummy empty vector:

name_VEC empty_name_vec;

needs to be defined.

Examples of these support routines can be found in the calculus program itself.

3.3. Run-time checking

The type checking facilities supported by calculus 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 calculus can be made to add extra assertions to check for such errors into its output. This is done by specifying the -a command-line option.

These assertions are implemented by means of macros. If the standard macro NDEBUG is not 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 -a option had not been given.

The assertions require certain support functions which are output into a separate file, assert_def.h. These functions need to be compiled into the program when NDEBUG is not defined. Note that the functions are implementation specific.

4.1. Disk writing routines

The disk writing routines output in write_def.h consist of a function:

static void WRITE_type(t);

for each type t mentioned within the algebra description, which writes an object of that type to disk.

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 type component of the name WRITE_type is derived from basic types t by using the short type name. For composite types it is defined recursively as follows:

LIST(t)->list_type PTR(t)->ptr_type STACK(t)->stack_type VEC(t)->vec_type VEC_PTR(t)->vptr_type

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. WRITE_type functions for the primitive types should be provided by the user to form a foundation on which all the other functions may be built.

The user may wish to generate WRITE_type (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 -Einput where input is a file containing a list of the extra types required. In the notation used above the syntax for input is given by:

extra:
			type-list?

type-list:
			type;
			type-list type;

The WRITE_type 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):

void WRITE_BITS(int, unsigned int);
void WRITE_DIM(name_dim);
void WRITE_ALIAS(unsigned int);

for writing a number of bits to disk, writing a vector dimension and writing an object alias.

Any of the WRITE_type functions may be overridden by the user by defining a macro WRITE_type with the desired effect. Note that the WRITE_type 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.

4.2. Disk reading routines

The disk reading routines output in read_def.h are exactly analogous to the disk writing routines. For each type t (except primitives) there is a function or macro:

static t READ_type(void);

which reads an object of that type from disk. The user must provide the READ_type functions for the primitive types, plus support routines:

unsigned int READ_BITS(int);
name_dim READ_DIM(void);
unsigned int READ_ALIAS(void);

for reading a number of bits from disk, reading a vector dimension and reading an object alias. The READ_type functions may be overridden by means of macros as before.

4.3. Object printing routines

The object printing routines output in print_def.h consist of a function or macro:

static void PRINT_type(FILE *, t, char *, int);

for each type t, which prints an object of type t to the given file, using the given object name and indentation value. The user needs to provide basic output routines:

void OUTPUT_type(FILE *, t);

for each primitive type. The PRINT_type functions may be overridden by means of macros as before.

The printing routines are under the control of three variables defined as follows:

static int print_indent_step = 4;
static int print_ptr_depth = 1;
static int print_list_expand = 0;

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.

One application of these object printing routines is to aid debugging programs written using the calculus 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 -p and -a command-line options are given then calculus will generate functions:

void DEBUG_type(t);

defined in terms of PRINT_type, 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 DEBUG_type takes the form:

void DEBUG_type(t *);

These debugging routines are only defined conditionally, if the standard macro NDEBUG is not defined.

4.4. Aliasing

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

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.

The objects on which aliasing can be specified are the union fields. A union field may be qualified by one or two hash symbols to signify that objects of that type should be aliased.

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, x say, is split into its components using the appropriate DECONS_union_field construct. Then the user-defined routine, or macro:

ALIAS_union_field(comp, ...., x);

(where comp ranges over all the union components) is called prior to writing the object components to disk.

Similarly in the disk reading case, the object being read, x, is initialised by calling the user-defined routine:

UNALIAS_union_field(x);

prior to reading the object components from disk. Each object component is then read into a local variable, comp. Finally the user-defined routine:

UNIFY_union_field(comp, ...., x);

(where comp ranges over all the union components) is called to assign these values to x before returning.

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.

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:

void clear_name_alias(void);

to clear all aliases.

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 clear_name_alias mentioned above, the user should provide support functions and variables:

unsigned int crt_name_alias;
void set_name_alias(name *, unsigned int);
name *find_name_alias(unsigned int);

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 calculus program itself.

4.5. Application to calculus

As mentioned above, the calculus 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 command-line options mentioned above.

If the -w command-line option is specified to calculus then it reads its input file, input, as normal, but writes a disk representation of the input algebra to output, 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 calculus if the -r option is given. Finally the input algebra may be pretty-printed to an output file (or the standard output if no output argument is given) by specifying the -o option.