i. Introduction
This document describes a tool, calculus, 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.
calculus 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.
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.
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 disk reading and writing routines described below are an example of this.
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.