Output type system specification

2. Output type system specification

In this section we document the basic output of calculus. Two forms of the output can be generated - a description of the output specification in terms of the TenDRA #pragma token constructs, and the actual C code which implements these tokens.

In this section the description given will be at the level of the output specification. The more important details of the C implementation are given in the following section.

The output is split among several header files in the specified output directory. The main output is printed into name.h, where name is the overall algebra name. Unless otherwise stated, all the objects specified below are to be found in name.h. However for each union, union, in the algebra certain information associated with the union is printed into union_ops.h. If the union has any maps associated with it then further output is printed to union_map.h and union_hdr.h.

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.

2.4.1. Simple pointer constructs

There are several simple operations on pointers, given as follows:

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

The construct NULL_ptr is used to form the null pointer to t for a type t. This is a constant expression. IS_NULL_ptr can be used to test whether a given pointer expression is a null pointer. Similarly EQ_ptr checks whether two pointers are equal (note that we can only compare pointers to the same type). Finally STEP_ptr can be used to add a scalar value to a pointer.

2.4.2. Unique pointers

There are also constructs for generating and destroying unique pointers:

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

A unique pointer is guaranteed to be different from all other undestroyed pointers. Dereferencing a unique pointer is undefined.

2.4.3. Pointer construction and destruction

The constructs:

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

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

2.4.4. Assignment and dereference constructs

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:

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

where t is the type involved and type is the associated short name.

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:

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

Here the lvalue type qualifier is used to indicate that the statement argument is an assignable lvalue. In this case it should give the location of an object of type t into which the pointer will be dereferenced.

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:

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.

2.5.1. Simple list constructs

There are several simple list constructs:

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

Empty lists may be constructed or tested for. NULL_list 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 car and cdr) 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.

2.5.2. Unique lists

There are also constructs for generating and destroying unique lists:

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

A unique lists is guaranteed to be different from all other undestroyed lists. Taking the head or tail of a unique list is undefined.

2.5.3. List construction and destruction

For each type t there are operations for constructing and deconstructing lists. For the basic types comprising the algebra these take the form:

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

where type is the short type name.

The operation CONS_type 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. UN_CONS_type reverses this process, decomposing a list into its head and its tail. DESTROY_CONS_type is similar, but it also applies the given destructor function to the decomposed list component.

There are also generic list construction and deconstruction operations which apply to lists of pointers (with a ptr suffix), lists of lists (with a list suffix), lists of stacks (with a stack suffix), lists of vectors (with a vec suffix) and lists of pointers to vectors (with a vec_ptr suffix). For example, for lists of pointers these have the form:

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

There is also a generic list destruction construct:

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

which may be used to destroy all the elements in a list.

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.

2.13.1. Union construction operations

Most of the output for the union type t is output into the file union_ops.h. This contains a construct:

unsigned int TAG_union(t);

for extracting the discriminant tag from a union.

For each shared component, comp, of t of type ctype, say, there is an operator:

PTR(ctype) union_comp(t);

which extracts this component from the union.

For each field, field, of the union there are constructs:

unsigned int union_field_tag;
int IS_union_field(t);

giving the (constant) discriminant tag associated with this field, and a test for whether an object of type t has this discriminant.

In addition, for each unshared component, comp, of field of type ctype, say, there is an operator:

PTR(ctype) union_field_comp(t);

which extracts this component from the union.

There are also operations for constructing and deconstructing objects of type t for field field given as follows:

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

The operation MAKE_union_field constructs a value of type t from the various components and assigns it into the last argument. The ctype arguments range over all the components of field, 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 initialiser string or the given operation argument.

DECONS_union_field performs the opposite operation, deconstructing an object of type t into its components for this field. DESTROY_union_field is similar, except that it also applies the given destructor function to the original value. For these two operations ctype ranges over all the components, including those with initialiser strings.

2.13.2. Union field sets

Recall that a number of union field identifiers 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:

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

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 MAKE_union_field_etc takes an extra argument, giving the tag associated with the particular element of the set being constructed. Also the construct MODIFY_union_field_etc is introduced to allow the tag of an existing object to be modified to another value within the same set.

The valid range of union tags for this set can be given by the two constants:

unsigned int union_field_tag;
unsigned int union_field_etc_tag;

A union is a member of this set if its tag is greater than or equal to union_field_tag and strictly less than union_field_etc_tag.

2.13.3. Inheritance in unions

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

btype CONVERT_union_base(t);

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

2.13.4. Union maps

For each map, map, on the union t, we have declared in union_ops.h an operator:

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

where map_ret is the map return type and map_par ranges over the map parameter types. This is except for maps with destructors (i.e. those qualified by a hash symbol) which have the form:

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

These maps are implemented by having one function per field for each map. The output file union_map.h contains tables of these functions. These have the form:

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

where there is one entry per union field.

In order to aid the construction of these functions a set of function headers is provided in union_hdr.h. These take the form:

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

There is also an alternative function header, HDR_map_d_union_field, which calls DESTROY_union_field rather than DECONS_union_field. The destructor function used is destroyer, if this parameter is present, or the default destructor, destroy_name, otherwise.