TDF Specification

A separable piece of TDF is called a CAPSULE. A producer generates a CAPSULE; the TDF linker links CAPSULEs together to form a CAPSULE; and the final translation process turns a CAPSULE into an object file.

The structure of capsules is designed so that the process of linking two or more capsules consists almost entirely of copying large byte-aligned sections of the source files into the destination file, without changing or even examining these sections. Only a small amount of interface information has to be modified and this is made easily accessible. The translation process only requires an extra indirection to account for this interface information, so it is also fast. The description of TDF at the capsule level is almost all about the organisation of the interface information.

There are three major kinds of entity which are used inside a capsule to name its constituents. The first are called tags; they are used to name the procedures, functions, values and variables which are the components of the program. The second are called tokens; they identify pieces of TDF which can be used for substitution - a little like macros. The third are the alignment tags, used to name alignments so that circular types can be described. Because these internal names are used for linking pieces of TDF together, they are collectively called linkable entities. The interface information relates these linkable entities to each other and to the world outside the capsule.

The most important part of a capsule, the part which contains the real information, consists of a sequence of groups of units. Each group contains units of the same kind, and all the units of the same kind are in the same group. The groups always occur in the same order, though it is not necessary for each kind to be present.

Figure 1.1. Capsule 4

The order is as follows:

This organisation is imposed to help installers, by ensuring that the information needed to process a unit has been provided before that unit arrives. For example, the token definitions occur before any tag definition, so that, during translation, the tokens may be expanded as the tag definitions are being read (in a capsule which is ready for translation all tokens used must be defined, but this need not apply to an arbitrary capsule).

The tags and tokens in a capsule have to be related to the outside world. For example, there might be a tag standing for printf, used in the appropriate way inside the capsule. When an object file is produced from the capsule the identifier printf must occur in it, so that the system linker can associate it with the correct library procedure. In order to do this, the capsule has a table of tags at the capsule level, and a set of external links which provide external names for some of these tags.

Figure 1.2. Capsule 1

In just the same way, there are tables of tokens and alignment tags at the capsule level, and external links for these as well.

The tags used inside a unit have to be related to these capsule tags, so that they can be properly named. A similar mechanism is used, with a table of tags at the unit level, and links between these and the capsule level tags.

Figure 1.3. Capsule 2

Again the same technique is used for tokens and alignment tags.

It is also necessary for a tag used in one unit to refer to the same thing as a tag in another unit. To do this a tag at the capsule level is used, which may or may not have an external link.

Figure 1.4. Capsule 3

The same technique is used for tokens and alignment tags.

So when the TDF linker is joining two capsules, it has to perform the following tasks:

This can be done without looking into the interior of the units (except for the tld unit), simply copying the units into their new place.

During the process of installation the values associated with the linkable entities can be accessed by indexing into an array followed by one indirection. These are the kinds of object which in a programming language are referred to by using identifiers, which involves using hash tables for access. This is an example of a general principle of the design of TDF; speed is required in the linking and installing processes, if necessary at the expense of time in the production of TDF.

Tokens are used (applied) in the TDF at the point where substitutions are to be made. Token definitions provide the substitutions and usually reside on the target machine and are linked in there.

A typical token definition has parameters from various SORTs and produces a result of a given SORT. As an example of a simple token definition, written here in a C-like notation, consider the following.

EXP ptr_add (EXP par0, EXP par1, SHAPE par2) { add_to_ptr( par0, offset_mult( offset_pad( alignment(par2), shape_offset(par2)), par1)) }

This defines the token, ptr_add, to produce something of SORT EXP. It has three parameters, of SORTs EXP, EXP and SHAPE. The add_to_ptr, offset_mult, offset_pad, alignment and shape_offset constructions are TDF constructions producing respectively an EXP, an EXP, an EXP, an ALIGNMENT and an EXP.

A typical use of this token is:

ptr_add( obtain_tag(tag41), contents(integer(~signed_int), obtain_tag(tag62)), integer(~char))

The effect of this use is to produce the TDF of the definition with par0, par1 and par2 substituted by the actual parameters.

There is no way of obtaining anything like a side-effect. A token without parameters is therefore just a constant.

Tokens can be used for various purposes. They are used to make the TDF shorter by using tokens for commonly used constructions (ptr_add is an example of this use). They are used to make target dependent substitutions (~char in the use of ptr_add is an example of this, since ~char may be signed or unsigned on the target).

A particularly important use is to provide definitions appropriate to the translation of a particular language. Another is to abstract those features which differ from one ABI to another. This kind of use requires that sets of tokens should be standardised for these purposes, since otherwise there will be a proliferation of such definitions.

Tags are used to identify the actual program components. They can be declared or defined. A declaration gives the SHAPE of a tag (a SHAPE is the TDF analogue of a type). A definition gives an EXP for the tag (an EXP describes how the value is to be made up).

TDF can be extended for two major reasons.

First, as part of the evolution of TDF, new features will from time to time be identified. It is highly desirable that these can be added without disturbing the current encoding, so that old TDF can still be installed by systems which recognise the new constructions. Such changes should only be made infrequently and with great care, for stability reasons, but nevertheless they must be allowed for in the design.

Second, it may be required to add extra information to TDF to permit special processing. TDF is a way of describing programs and it clearly may be used for other reasons than portability and distribution. In these uses it may be necessary to add extra information which is closely integrated with the program. Diagnostics and profiling can serve as examples. In these cases the extra kinds of information may not have been allowed for in the TDF encoding.

Some extension mechanisms are described below and related to these reasons:

In this document the behaviour of TDF installers is described in a precise manner. Certain words are used with very specific meanings. These are:

All installers must implement all of the constructions of TDF. There are some constructions where the installers may impose limits on the ranges of values which are implemented. In these cases the description of the installer must specify these limits.

Installers are not expected to check that the TDF they are processing is well-formed, nor that undefined constructs are absent. If the TDF is not well-formed any effect is permitted.

Installers shall only implement optimisations which are correct in all circumstances. This correctness can only be shown by demonstrating the equivalence of the transformed program, from equivalences deducible from this specification or from the ordinary laws of arithmetic. No statements are made in this specification of the form "such and such an optimisation is permitted".

An ACCESS describes properties a variable or identity may have which may constrain or describe the ways in which the variable or identity is used.

Each construction which needs an ACCESS uses it in the form OPTION(ACCESS). If the option is absent the variable or identity has no special properties.

An ACCESS acts like a set of the values constant, long_jump_access, no_other_read, no_other_write, register, out_par, used_as_volatile, and visible. standard_access acts like the empty set. add_accesses is the set union operation.

token_value: TOKEN
token_args:  BITSTREAM param_sorts(token_value)
             → ACCESS

control: EXP INTEGER(v)
e1:      BITSTREAM ACCESS
e2:      BITSTREAM ACCESS
         → ACCESS

a1: ACCESS
a2: ACCESS
    → ACCESS

→ ACCESS

→ ACCESS

→ ACCESS

→ ACCESS

→ ACCESS

→ ACCESS

→ ACCESS

→ ACCESS

→ ACCESS

→ ACCESS

AL_TAGs name ALIGNMENTs. They are used so that circular definitions can be written in TDF. However, because of the definition of alignments, intrinsic circularities cannot occur.

For example, the following equation has a circular form x = alignment(pointer(alignment(x))) and it or a similar equation might occur in TDF. But since alignment(pointer(x)) is {pointer}, this reduces to x = {pointer}.

token_value: TOKEN
token_args:  BITSTREAM param_sorts(token_value)
             → AL_TAG