Subversion Repositories tendra.SVN

<?xml version="1.0" standalone="no"?>

<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.4//EN"

  "http://www.oasis-open.org/docbook/xml/4.4/docbookx.dtd">

<!--

  $Id$

-->

<book>

  <bookinfo>

    <title>A Guide to the TDF Specification, Issue 4.0</title>

    <corpauthor>The TenDRA Project</corpauthor>

    <author>

      <firstname>Jeroen</firstname>

      <surname>Ruigrok van der Werven</surname>

    </author>

    <authorinitials>JRvdW</authorinitials>

    <pubdate>2005</pubdate>

    <copyright>

      <year>2004</year>

      <year>2005</year>

      <holder>The TenDRA Project</holder>

    </copyright>

    <copyright>

      <year>1998</year>

      <holder>DERA</holder>

    </copyright>

  </bookinfo>

  <chapter id="introduction">

    <title>Introduction</title>

    <para>This memo is intended to be a fairly detailed commentary on the

      specification of TDF, a kind of Talmud to the Torah. If it conflicts

      with the specification document, it is wrong. The aim is elucidate the

      various constructions of TDF, giving examples of usages both from the

      point of view of a producer of TDF and how it is used to construct

      programs on particular platforms using various installers or

      translators. In addition, some attempt is made to give the reasons why

      the particular constructions have been chosen. Most of the commentary is

      a distillation of questions and answers raised by people trying to learn

      TDF from the specification document.</para>

    <para>Throughout this document, references like (S5.1) are headings in the

      <ulink url="../tdf/spec1.html">TDF specification, Issue 4.0</ulink>.

      I use the term "compiling" or "producing" to mean the production of TDF

      from some source language and "translating" to mean making a program for

      some specific platform from TDF.</para>

    <para>I use the first person where I am expressing my own opinions or

      preferences; these should not be taken as official opinions of DRA or

      the TenDRA team.</para>

  </chapter>

  <chapter>

    <sect1 id="sorts-and-tokens">

      <title>SORTs and TOKENs</title>

      <para>In the syntax of language like C or Pascal, we find various

        syntactic units like <Expression>, <Identifier> etc. A

        SORT bears the same relation to TDF as these syntactic units bear to

        the language; roughly speaking, the syntactic unit <Expression>

        corresponds to the SORT EXP and <Identifier> to TAG . However,

        instead of using BNF to compose syntactic units from others, TDF uses

        explicit constructors to compose its SORTs; each constructor uses

        other pieces of TDF of specified SORTs to make a piece of its result

        SORT. For example, the constructor plus uses an ERROR_TREATMENT and

        two EXPs to make another EXP.</para>

      <para>At the moment, there are 58 different SORTS, from ACCESS to

        VARIETY given in tables 1 and 2. Some of these have familiar analogues

        in standard language construction as with EXP and TAG above. Others

        will be less familiar since TDF must concern itself with issues not

        normally addressed in language definitions. For example, the process

        of linking together TDF programs is at the root of the architecture

        neutrality of TDF and so must form an integral part of its definition.

        On the other hand, TDF is not meant to be a language readily

        accessible to the human reader or writer; computers handle it much

        more easily. Thus a great many choices have been made in the

        definition which would be intolerable in a standard language

        definition for the human programmer but which, paradoxically enough,

        make it much simpler for a computer to produce and analyse TDF</para>

      <para>The SORTs and constructors in effect form a multi-sorted algebra.

        There were two principal reasons for choosing this algebraic form of

        definition. First, it is easy to extend - a new operation on existing

        constructs simply requires a new constructor.  Secondly, the algebraic

        form is highly amenable to the automatic construction of programs.

        Large parts of both TDF producers and TDF translators have been

        created by automatic transformation of the text of the specification

        document itself, by extracting the algebraic signature and

        constructing C program which can read or produce TDF. To this extent,

        one can regard the specification document as a formal description of

        the free algebra of TDF SORTs and constructors. Of course, most of the

        interesting parts of the definition of TDF lies in the equivalences of

        parts of TDF, so this formality only covers the easy bit.</para>

      <para>Another distinction between the TDF definition and language

        syntactic description is that TDF is to some extent conscious of its

        own SORTs so that it can specify a new construction of a given SORT.

        The analogy in normal languages would be that one could define a new

        construction with new syntax and say this is an example of an

        <Expression>, for example; I don't know of any standard language

        which permits this, although those of you with a historical bent might

        remember Algol-N which made a valiant attempt at it. Of course, the

        algebraic method of description makes it much easier to specify,

        rather than having to give syntax to provide the syntax for the new

        construction in a language.</para>

      <sect2>

        <title>Token applications and first-class SORTs</title>

        <para>A new construction is introduced by the SORT TOKEN; the

          constructors involving TOKENs allow one to give an expansion for the

          TOKEN in terms of other pieces of TDF, possibly including

          parameters. We can encapsulate a (possibly parameterised) fragment

          of TDF of a suitable SORT by giving it a TOKEN as identification.

          Not all of the SORTs are available for this kind of encapsulation

          - only those which have a SORTNAME constructor (from access to

          variety).  These are the "first-class" SORTs given in table 1.  Each

          of these have an appropriate _apply_token constructor (e.g.

          exp_apply_token) give the expansion. Most of these also have _cond

          constructors (e.g.see exp_cond in

          <link linkend="cond-constructors">section 9.1</link>)

          which allows translate time conditional expansion of the

          SORT.</para>

        <mediaobject>

          <imageobject>

            <imagedata fileref="images/guidetable3.png" format="PNG"/>

          </imageobject>

          <textobject>

            <phrase>TBD</phrase>

          </textobject>

          <caption>

            <para>TBD</para>

          </caption>

        </mediaobject>

        <para>Every TOKEN has a result SORT, i.e. the SORT of its resulting

          expansion and before it can be expanded, one must have its parameter

          SORTs. Thus, you can regard a TOKEN as having a type defined by its

          result and parameter SORTs and the _apply_token as the operator

          which expands the encapsulation and substitutes the

          parameters.</para>

        <para>However, if we look at the signature of exp_apply_token:</para>

        <programlisting>

token_value: TOKEN

token_args:  BITSTREAM param_sorts(token_value)

             -> EXP x

        </programlisting>

        <para>we are confronted by the mysterious BITSTREAM where one might

          expect to find the actual parameters of the TOKEN.</para>

        <para>To explain BITSTREAMs requires a diversion into the bit-encoding

          of TDF. Constructors for a particular SORT are represented in a

          number of bits depending on the number of constructors for that

          SORT; the context will determine the SORT required, so no more bits

          are required. Thus since there is only one constructor for UNITs, no

          bits are required to represent make_unit; there are about 120

          different constructors for EXPs so 7 bits are required to cover all

          the EXPs. The parameters of each constructor have known SORTs and so

          their representations are just concatenated after the representation

          of the constructor.

          <footnote><para>There are facilities to allow extensions to the

            number of constructors, so it is not quite as simple as

            this.</para></footnote>

          While this is a very compact representation, it suffers from the

          defect that one must decode it even just to skip over it. This is

          very irksome is some applications, notably the TDF linker which is

          not interested detailed expansions.  Similarly, in translators there

          are places where one wishes to skip over a token application without

          knowledge of the SORTs of its parameters. Thus a BITSTREAM is just

          an encoding of some TDF, preceded by the number of bits it occupies.

          Applications can then skip over BITSTREAMs trivially.  Similar

          considerations apply to BYTESTREAMs used elsewhere; here the

          encoding is preceded by the number of bytes in the encoding and is

          aligned to a byte boundary to allow fast copying.</para>

      </sect2>

      <sect2>

        <title>Token definitions and declarations</title>

        <para>Thus the <parameter>token_args</parameter> parameter of

          exp_apply_token is just the BITSTREAM formed from the actual

          parameters in the sequence described by the definition of the

          <parameter>token_value</parameter> parameter. This will be given in

          a TOKEN_DEFN somewhere with constructor token_definition:</para>

        <programlisting>

result_sort: SORTNAME

tok_params:  LIST(TOKFORMALS)

body:        result_sort

             -> TOKEN_DEFN

        </programlisting>

        <para>The <type>result_sort</type> is the SORT of the construction of

          <type> body</type>; e.g. if <type>result_sort</type> is formed from

          exp then <type>body</type> would be constructed using the EXP

          constructors and one would use exp_apply_token to give the

          expansion. The list <type>tok_params</type> gives the formal

          parameters of the definition in terms of TOKFORMALS constructed

          using make_tok_formals:</para>

        <programlisting>

sn: SORTNAME

tk: TDFINT

    -> TOKFORMALS

        </programlisting>

        <para>The TDFINT <type>tk</type> will be the integer representation of

          the formal parameter expressed as a TOKEN whose result sort is

          <type>sn</type> (see more about name representation in

          <link linkend="make_capsule-and-name-spaces">section 3.1</link>). To

          use the parameter in the body of the TOKEN_DEFN, one simply uses the

          _apply_token appropriate to <type>sn</type>.Note that sn may be a

          TOKEN but the <type>result_sort</type> may not.</para>

        <para>Hence the BITSTREAM

          <type>param_sorts</type>(<parameter>token_value</parameter>) in the

          actual parameter of exp_apply_token above is simply formed by the

          catenation of constructions of the SORTs given by the SORTNAMEs in

          the <type>tok_params</type> of the TOKEN being expanded.</para>

        <para>Usually one gives a name to a TOKEN_DEFN using to form a TOKDEF

          using make_tokdef :</para>

        <programlisting>

tok:       TDFINT

signature: OPTION(STRING)

def:       BITSTREAM TOKEN_DEFN

           -> TOKDEF

        </programlisting>

        <para>Here, <type>tok</type> gives the name that will be used to

          identify the TOKEN whose expansion is given by <type>def</type>. Any

          use of this TOKEN (e.g. in exp_apply_token) will be given by

          make_token(<type>tok</type>). Once again, a BITSTREAM is used to

          encapsulate the TOKEN_DEFN.</para>

        <para>The significance of the signature parameter is discussed in

          <link linkend="declaration-and-definition-signatures">section

            3.2.2</link>.</para>

        <para>Often, one wishes a token without giving its definition - the

          definition could, for example, be platform-dependent. A TOKDEC

          introduces such a token using make_tokdec:</para>

        <programlisting>

tok:       TDFINT

signature: OPTION(STRING)

s:         SORTNAME

           -> TOKDEC

        </programlisting>

        <para>Here the SORTNAME, <type>s</type>, is given by token:</para>

        <programlisting>

result: SORTNAME

params: LIST(SORTNAME)

        -> SORTNAME

        </programlisting>

        <para>which gives the result and parameter SORTs of

          <type>tok</type>.</para>

        <para>One can also use a TOKEN_DEFN in an anonymous fashion by giving

          it as an actual parameter of a TOKEN which itself demands a TOKEN

          parameter. To do this one simply uses use_tokdef:</para>

        <programlisting>

tdef: BITSTREAM TOKEN_DEFN

      -> TOKEN

        </programlisting>

      </sect2>

      <sect2>

        <title>A simple use of a TOKEN</title>

        <para>The crucial use of TOKENs in TDF is to provide abstractions of

          APIs (see <link linkend="tokens-and-apis">section 10</link>) but

          they are also used as shorthand for commonly occurring

          constructions. For example, given the TDF constructor plus,

          mentioned above, we could define a plus with only two EXP parameters

          more suitable to C by using the wrap constructor as the

          ERROR_TREATMENT:</para>

        <programlisting>

make_tokdef(C_plus, empty, token_definition(exp(), (make_tokformals(exp(), l),

                                                    make_tokformals(exp(), r)),

            plus(wrap(), exp_apply_token(l, ()), exp_apply_token(r, ())))

        </programlisting>

      </sect2>

      <sect2>

        <title>Second class SORTs</title>

        <para>Second class SORTs (given in table 2) cannot be

          TOKENised. These are the "syntactic units" of TDF which the user

          cannot extend; he can only produce them using the constructors

          defined in core-TDF.</para>

        <para>Some of these constructors are implicit. For example, there are

          no explicit constructors for LIST or SLIST which are both used to

          form lists of SORTs; their construction is simply part of the

          encoding of TDF. However, it is forseen that LIST constructors would

          be highly desireable and there will probably extensions to TDF to

          promote LIST from a second-class SORT to a first-class one. This

          will not apply to SLIST or to the other SORTs which have implicit

          constructions. These include BITSTREAM, BYTESTREAM, TDFINT, TDFIDENT

          and TDFSTRING.</para>

      </sect2>

    </sect1>

    <sect1>

      <title>CAPSULEs and UNITs</title>

      <para>A CAPSULE is typically the result of a single compilation - one

        could regard it as being the TDF analogue of a Unix .o file. Just as

        with .o files, a set of CAPSULEs can be linked together to form

        another. Similarly, a CAPSULE may be translated to make program for

        some platform, provided certain conditions are met. One of these

        conditions is obviously that a translator exists for the platform, but

        there are others. They basically state that any names that are

        undefined in the CAPSULE can be supplied by the system in which it is

        to be run. For example, the translator could produce assembly code

        with external identifiers which will be supplied by some system

        library.</para>

      <sect2 id="make_capsule-and-name-spaces">

        <title>make_capsule and name-spaces</title>

        <para>The only constructor for a CAPSULE is make_capsule. Its basic

          function is to compose together UNITs which contain the declarations

          and definitions of the program. The signature of make_capsule looks

          rather daunting and is probable best represented graphically.</para>

        <mediaobject>

          <imageobject>

            <imagedata fileref="images/guide2.png" format="PNG"/>

          </imageobject>

          <textobject>

            <phrase>TBD</phrase>

          </textobject>

          <caption>

            <para>TBD</para>

          </caption>

        </mediaobject>

        <para>The diagram gives an example of a CAPSULE using the same

          components as in the following text.</para>

        <para>Each CAPSULE has its own name-space, distinct from all other

          CAPSULEs' name-spaces and also from the name-spaces of its component

          UNITs (see <link linkened="#11">section 3.1.2</link>).  There are

          several different kinds of names in TDF and each name-space is

          further subdivided into one for each kind of name.  The number of

          different kinds of names is potentially unlimited but only three are

          used in core-TDF, namely "tag", "token" and "al_tag". Those names in

          a "tag" name-space generally correspond to identifiers in normal

          programs and I shall use these as the paradigm for the properties of

          them all.</para>

        <para>The actual representations of a "tag" name in a given name-space

          is an integer, described as SORT TDFINT. These integers are drawn

          from a contiguous set starting from 0 up to some limit given by the

          constructor which introduces the name-space. For CAPSULE

          name-spaces, this is given by the <type>capsule_linking</type>

          parameter of make_capsule:</para>

        <programlisting>

capsule_linking: SLIST(CAPSULE_LINK)

        </programlisting>

        <para>In the most general case in core-TDF, there would be three

          entries in the list introducing limits using make_capsule_link for

          each of the "tag", "token" and "al_tag" name-spaces for the CAPSULE.

          Thus if:</para>

        <programlisting>

capsule_linking = (make_capsule_link("tag", 5),

                   make_capsule_link("token", 6),

                   make_capsule_link("al_tag", 7))

        </programlisting>

        <para>there are 5 CAPSULE "tag" names used within the CAPSULE, namely

          0, 1, 2, 3 and 4; similarly there are 6 "token" names and 7 "al_tag"

          names.</para>

        <sect3 id="external-linkages">

          <title>External linkages</title>

          <para>The context of usage will always determine when and how an

            integer is to be interpreted as a name in a particular name-space.

            For example, a TAG in a UNIT is constructed by make_tag applied to

            a TDFINT which will be interpreted as a name from that UNIT's

            "tag" name-space. An integer representing a name in the CAPSULE

            name-space would be found in a LINKEXTERN of the

            <type>external_linkage</type> parameter of make_capsule.</para>

          <programlisting>

external_linkage: SLIST(EXTERN_LINK)

          </programlisting>

          <para>Each EXTERN_LINK is itself formed from an SLIST of LINKEXTERNs

            given by make_extern_link . The order of the EXTERN_LINKs

            determines which name-space one is dealing with; they are in the

            same order as given by the <type>extern_linkage</type> parameter.

            Thus, with the <type>extern_linkage</type> given above, the first

            EXTERN_LINK would deal with the "tag" name-space; Each of its

            component LINKEXTERNs constructed by make_linkextern would be

            identifying a tag number with some name external to the CAPSULE;

            for example one might be:</para>

          <programlisting>

make_linkextern(4, string_extern("printf"))

          </programlisting>

          <para>This would mean: identify the CAPSULE's "tag" 4 with an name

            called "printf", external to the module. The name "printf" would

            be used to linkage external to the CAPSULE; any name required

            outside the CAPSULE would have to be linked like

            this.</para></sect3>

        <sect3 id="units">

          <title>UNITs</title>

          <para>This name "printf", of course, does not necessarily mean the C

            procedure in the system library. This depends both on the system

            context in which the CAPSULE is translated and also the meaning of

            the CAPSULE "tag" name 4 given by the component UNITs of the

            CAPSULE in the <type>groups</type> parameter of

            make_capsule:</para>

          <programlisting>

groups: SLIST(GROUP)

          </programlisting>

          <para>Each GROUP in the <type>groups</type> SLIST will be formed by

            sets of UNITs of the same kind. Once again, there are a

            potentially unlimited number of kinds of UNITs but core-TDF only

            uses those named "tld","al_tagdefs", "tagdecs", "tagdefs",

            "tokdecs" and "tokdefs".

            <footnote><para>The "tld" UNITs gives usage information for names

              to aid the linker, tld, to discover which namess have

              definitions and some usage information. The C producer also

              optionally constructs "diagnostics" UNITs (to give run-time

              diagnostic information).</para></footnote>

            These names will appear (in the same order as in

            <type>groups</type>) in the <type>prop_names</type> parameter of

            make_capsule, one for each kind of UNIT appearing in the

            CAPSULE:</para>

          <programlisting>

prop_names: SLIST(TDFIDENT)

          </programlisting>

          <para>Thus if:</para>

          <programlisting>

prop_names = ("tagdecs", "tagdefs")

          </programlisting>

          <para>then, the first element of <type>groups</type> would contain

            only "tagdecs" UNITs and and the second would contain only

            "tagdefs" UNITs. A "tagdecs" UNIT contains things rather like a

            set of global identifier declarations in C, while a "tagdefs" UNIT

            is like a set of global definitions of identifiers.</para>

        </sect3>

        <sect3 id="make_unit">

          <title>make_unit</title>

          <para>Now we come to the construction of UNITs using make_unit, as

            in the diagram below

            <mediaobject>

              <imageobject>

                <imagedata fileref="images/guide1.png" format="PNG"/>

              </imageobject>

              <textobject>

                <phrase>TBD</phrase>

              </textobject>

              <caption>

                <para>TBD</para>

              </caption>

            </mediaobject>

          </para>

          <para>First we give the limits of the various name-spaces local to

            the UNIT in the <type>local_vars</type> parameter:</para>

          <programlisting>

local_vars: SLIST(TDFINT)

          </programlisting>

          <para>Just in the same way as with <type>external_linkage</type>,

            the numbers in local_vars correspond (in the same order) to the

            spaces indicated in <type>capsule_linking</type> in

            <link linkend="make_capsule-and-name-spaces">section 3.1</link>.

            With our example,the first element of <type>local_vars</type>

            gives the number of "tag" names local to the UNIT, the second

            gives the number of "token" names local to the UNIT etc. These

            will include all the names used in the body of the UNIT. Each

            declaration of a TAG, for example, will use a new number from the

            "tag" name-space; there is no hiding or reuse of names within a

            UNIT.</para>

        </sect3>

        <sect3 id="link">

          <title>LINK</title>

          <para>Connections between the CAPSULE name-spaces and the UNIT

            name-spaces are made by LINKs in the <parameter>lks</parameter>

            parameter of make_unit:</para>

          <programlisting>

lks: SLIST(LINKS)

          </programlisting>

          <para>Once again, <type>lks</type> is effectively indexed by the

            kind of name-space a. Each LINKS is an SLIST of LINKs each of

            which which establish an identity between names in the CAPSULE

            name-space and names in the UNIT name-space. Thus if the first

            element of <type>lks</type> contains:</para>

          <programlisting>

make_link(42, 4)

          </programlisting>

          <para>then, the UNIT "tag" 42 is identical to the CAPSULE "tag"

            4.</para>

          <para>Note that names from the CAPSULE name-space only arise in two

            places, LINKs and LINK_EXTERNs. Every other use of names are

            derived from some UNIT name-space.</para>

        </sect3>

      </sect2>

      <sect2 id="definitions-and-declarations">

        <title>Definitions and declarations</title>

        <para>The encoding in the <type>properties</type>:BYTESTREAM parameter

          of a UNIT is a PROPS, for which there are five constructors

          corresponding to the kinds of UNITs in core-TDF, make_al_tagdefs,

          make_tagdecs, make_tagdefs, make_tokdefs and make_tokdecs. Each of

          these will declare or define names in the appropriate UNIT

          name-space which can be used by make_link in the UNIT's

          <type>lks</type> parameter as well as elsewhere in the

          <type>properties</type> parameter. The distinction between

          "declarations" and "definitions" is rather similar to C usage; a

          declaration provides the "type" of a name, while a definition gives

          its meaning. For tags, the "type" is the SORT SHAPE (see below). For

          tokens, the "type" is a SORTNAME constructed from the SORTNAMEs of

          the parameters and result of the TOKEN using token:

          <programlisting>

params: LIST(SORTNAME)

result: SORTNAME

        -> SORTNAME

          </programlisting>

          Taking make_tagdefs as a paradigm for PROPS, we have:

          <programlisting>

no_labels: TDFINT

tds:       SLIST(TAGDEF)

           -> TAGDEF_PROPS

          </programlisting>

          The <type>no_labels</type> parameter introduces the size of yet

          another name-space local to the PROPS, this time for the LABELs used

          in the TAGDEFs. Each TAGDEF in <type>tds</type> will define a "tag"

          name in the UNIT's name-space. The order of these TAGDEFs is

          immaterial since the initialisations of the tags are values which

          can be solved at translate time, load time or as unordered dynamic

          initialisations.</para>

        <para>There are three constructors for TAGDEFs, each with slightly

          different properties. The simplest is make_id_tagdef:</para>

        <programlisting>

t:         TDFINT

signature: OPTION(STRING)

e:         EXP x

           -> TAGDEF

        </programlisting>

        <para>Here, <type>t</type> is the tag name and the evaluation of

          <type>e</type> will be the value of SHAPE <type>x</type> of an

          obtain_tag(<type>t</type>) in an EXP. Note that t is not a variable;

          the value of obtain_tag(<type>t</type>) will be invariant. The

          <type>signature</type> parameter gives a STRING (see

          <link linkend="sort-string">section 3.2.3</link>) which may be used

          as an name for the tag, external to TDF and also as a check

          introduced by the producer that a tagdef and its corresponding

          tagdec have the same notion of the language-specific type of the

          tag.</para>

        <para>The two other constructors for TAGDEF, make_var_tagdef and

          common_tagdef both define variable tags and have the same

          signature:</para>

        <programlisting>

t:          TDFINT

opt_access: OPTION(ACCESS)

signature:  OPTION(STRING)

e:          EXP x

            -> TAGDEF

        </programlisting>

        <para>Once again <type>t</type> is tag name but now <type>e</type> is

          initialisation of the variable <type>t</type>. A use of

          obtain_tag(<type>t</type>) will give a pointer to the variable (of

          SHAPE POINTER x), rather than its contents.

          <footnote><para>There is a similar distinction between tags

            introduced to be locals of a procedure using identify and variable

            (see <link linkend="identify-variable">section 5.3.1</link>).</para>

          </footnote>

          There can only be one make_var_tagdef of a given tag in a program,

          but there may be more than one common_tagdef, possibly with

          different initialisations; however these initialisations must

          overlap consistently just as in common blocks in FORTRAN.</para>

        <para>The ACCESS parameter gives various properties required for the

          tag being defined and is discussed in

          <link linkend="sort-access">section 5.3.2</link>.</para>

        <para>The initialisation EXPs of TAGDEFs will be evaluated before the

          "main" program is started. An initialiation EXP must either be a

          constant (in the sense of

          <link linkend="constants">section 9</link>) or reduce to (either

          directly or by token or _cond expansions) to an initial_value:

          <programlisting>

init: EXP s

      -> EXP s

          </programlisting>

          The translator will arrange that <type>init</type> will be evaluated

          once only before any procedure application, other than those

          themselves involved in initial_values, but after any constant

          initialisations. The order of evaluation of different initial_values

          is arbitrary.</para>

        <sect3 id="scopes-and-linking">

          <title>Scopes and linking</title>

          <para>Only names introduced by AL_TAGDEFS, TAGDEFS, TAGDECs, TOKDECs

            and TOKDEFs can be used in other UNITs (and then, only via the

            <type>lks</type> parameters of the UNITs involved). You can regard

            them as being similar to C global declarations. Token definitions

            include their declarations implicitly; however this is not true of

            tags. This means that any CAPSULE which uses or defines a tag

            across UNITs must include a TAGDEC for that tag in its "tagdecs"

            UNITs. A TAGDEC is constructed using either make_id_tagdec,

            make_var_tagdec or common_tagdec, all with the same form:

          <programlisting>

t_intro:   TDFINT

acc:       OPTION(ACCESS)

signature: OPTION(STRING)

x:         SHAPE

           -> TAGDEC

          </programlisting>

          Here the tagname is given by <type>t_intro</type>; the SHAPE

          <type>x</type> will defined the space and alignment required for the

          tag (this is analogous to the type in a C declaration). The

          <type>acc</type> field will define certain properties of the tag not

          implicit in its SHAPE; I shall return to the kinds of properties

          envisaged in discussing local declarations in

          <link linkend="defining-and-using-locals">section 5.3</link>.</para>

        <para>Most program will appear in the "tagdefs" UNITs - they will

          include the definitions of the procedures of the program which in

          turn will include local definitions of tags for the locals of the

          procedures.</para>

        <para>The standard TDF linker allows one to link CAPSULEs together

          using the name identifications given in the LINKEXTERNs, perhaps

          hiding some of them in the final CAPSULE. It does this just by

          generating a new CAPSULE name-space, grouping together component

          UNITs of the same kind and replacing their

          <parameter>lks</parameter> parameters with values derived from the

          new CAPSULE name-space without changing the UNITs' name-spaces or

          their <parameter>props</parameter> parameters.  The operation of

          grouping together UNITs is effectively assumed to be associative,

          commutative and idempotent e.g. if the same tag is declared in two

          capsules it is assumed to be the same thing . It also means that

          there is no implied order of evaluation of UNITs or of their

          component TAGDEFs</para>

        <para>Different languages have different conventions for deciding how

          programs are actually run. For example, C requires the presence of a

          suitably defined "main" procedure; this is usually enforced by

          requiring the system ld utility to bind the name "main" along with

          the definitions of any library values required.  Otherwise, the C

          conventions are met by standard TDF linking.  Other languages have

          more stringent requirements. For example, C++ requires dynamic

          initialisation of globals, using initial_value. As the only runnable

          code in TDF is in procedures, C++ would probably require an

          additional linking phase to construct a "main" procedure which calls

          the initialisation procedures of each CAPSULE involved if the system

          linker did not provide suitable C++ linking.</para>

        </sect3>

        <sect3 id="declaration-and-definition-signatures">

          <title>Declaration and definition signatures</title>

          <para>The <type>signature</type> arguments of TAGDEFs and TAGDECs

            are designed to allow a measure of cross-UNIT checking when

            linking independently compiled CAPSULEs. Suppose that we have a

            tag, <type>t</type>, used in one CAPSULE and defined in another;

            the first CAPSULE would have to have a TAGDEC for <type>t</type>

            whose TAGDEF is in the second. The <type>signature</type> STRING

            of both could be arranged to represent the language-specific type

            of <type>t</type> as understood at compilation-time. Clearly, when

            the CAPSULEs are linked the types must be identical and hence

            their STRING representation must be the same - a translator will

            reject any attempt to link definitions and declarations of the

            same object with different signatures.</para>

          <para>Similar considerations apply to TOKDEFs and TOKDECs; the

            "type" of a TOKEN may not have any familiar analogue in most HLLs,

            but the principle remains the same.</para>

        </sect3>

        <sect3 id="sort-string">

          <title>STRING</title>

          <para>The SORT STRING is used in various constructs other than

            declarations and definitions. It is a first-class SORT with

            string_apply_token and string_cond. A primitive STRING is

            constructed from a TDFSTRING(k,n) which is an encoding of n

            integers,each of k bits, using make_string:

            <programlisting>

arg: TDFSTRING(k, n)

     -> STRING(k, n)

            </programlisting>

            STRINGs may be concatenated using concat_string:

            <programlisting>

arg1: STRING(k, n)

arg2: STRING(k,m)

      -> STRING(k, n + m)

            </programlisting>

            Being able to compose strings, including token applications etc,

            means that late-binding is possible in <type>signature</type>

            checking in definitions and declarations. This late-binding means

            that the representation of platform-dependent HLL types need only

            be fully expanded at install-time and hence the types could be

            expressed in their representational form on the specific

            platform.</para>

        </sect3>

      </sect2>

    </sect1>

    <sect1>

      <title>SHAPEs, ALIGNMENTs and OFFSETs.</title>

      <para>In most languages there is some notion of the type of a value.

        This is often an uncomfortable mix of a definition of a representation

        for the value and a means of choosing which operators are applicable

        to the value. The TDF analogue of the type of value is its SHAPE

        (S3.20). A SHAPE is only concerned with the representation of a value,

        being an abstraction of its size and alignment properties.  Clearly an

        architecture-independent representation of a program cannot say, for

        example, that a pointer is 32 bits long; the size of pointers has to

        be abstracted so that translations to particular architectures can

        choose the size that is apposite for the platform.</para>

      <sect2 id="S19">

        <title>Shapes</title>

        <para>There are ten different basic constructors for the SORT SHAPE

          from bitfield to top as shown in table 3.  SHAPEs arising from those

          constructors are used as qualifiers (just using an upper case

          version of the constructor name) to various SORTs in the definition;

          for example, EXP TOP is an expression with top SHAPE. This is just

          used for definitional purposes only; there is no SORT SHAPENAME as

          one has SORTNAME.</para>

        <para>In the TDF specification of EXPs, you will observe that all EXPs

          in constructor signatures are all qualified by the SHAPE name; for

          example, a parameter might be EXP INTEGER(v). This merely means that

          for the construct to be meaningful the parameter must be derived

          from a constructor defined to be an EXP INTEGER(v). You might be

          forgiven for assuming that TDF is hence strongly-typed by its

          SHAPEs. This is not true; the producer must get it right. There are

          some checks in translators, but these are not exhaustive and are

          more for the benefit of translator writers than for the user. A tool

          for testing the SHAPE correctness of a TDF program would be useful

          but has yet to be written.</para>

        <sect3 id="S20">

          <title>TOP, BOTTOM, LUB</title>

          <para>Two of the SHAPE constructions are rather specialised; these

            are TOP and BOTTOM. The result of any expression with a TOP shape

            will always be discarded; examples are those produced by assign

            and integer_test . A BOTTOM SHAPE is produced by an expression

            which will leave the current flow of control e.g. goto . The

            significance of these SHAPEs only really impinges on the

            computation of the shapes of constructs which have alternative

            expressions as results. For example, the result of conditional is

            the result of one of its component expressions. In this case, the

            SHAPE of the result is described as the LUB of the SHAPEs of the

            components. This simply means that if one of the component SHAPEs

            is TOP then the resulting SHAPE is TOP; if one is BOTTOM then the

            resulting SHAPE is the SHAPE of the other; otherwise both

            component SHAPEs must be equal and is the resulting SHAPE. Since

            this operation is associative, commutative and idempotent, we can

            speak quite unambiguously of the LUB of several SHAPEs.</para>

        </sect3>

        <sect3 id="S21">

          <title>INTEGER</title>

          <para>Integer values in TDF have shape INTEGER(v) where v is of SORT

            VARIETY. The constructor for this SHAPE is integer with a VARIETY

            parameter.  The basic constructor for VARIETY is var_limits which

            has a pair of signed natural numbers as parameters giving the

            limits of possible values that the integer can attain. The SHAPE

            required for a 32 bit signed integer would be:

            <programlisting>

integer(var_limits(-2<superscript>31</superscript>, 2<superscript>31</superscript> - 1))

            </programlisting>

            while an unsigned char is:

            <programlisting>

integer(var_limits(0, 255))

            </programlisting>

            A translator should represent each integer variety by an object

            big enough (or bigger) to contain all the possible values with

            limits of the VARIETY. That being said, I must confess that most

            current translators do not handle integers of more than the

            maximum given naturally by the target architecture, but this will

            be rectified in due course.

          <para>The other way of constructing a VARIETY is to specify the

            number of bits required for its 2s-complemennt representation

            using var_width:</para>

            <programlisting>

signed_width: BOOL

width:        NAT

              -> VARIETY

            </programlisting>

          </para>

        </sect3>

        <sect3 id="S22">

          <title>FLOATING and complex</title>

          <para>Similarly, floating point and complex numbers have shape

            FLOATING qualified by a FLOATING_VARIETY.</para>

          <para>A FLOATING_VARIETY for a real number is constructed using

            fvar_parms:</para>

          <programlisting>

base:              NAT

mantissa_digits:   NAT

minimum_exponent:  NAT

maximum_exponent:: NAT

                   -> FLOATING_VARIETY

          </programlisting>

          <para>A FLOATING_VARIETY specifies the base, number of mantissa

            digits, and maximum and minimum exponent. Once again, it is

            intended that the translator will choose a representation which

            will contain all possible values, but in practice only those which

            are included in IEEE float, double and extended are actually

            implemented.</para>

          <para>Complex numbers have a floating variety constructed by

            complex_parms which has the the same signature as fvar_parms. The

            representation of these numbers is likely to be a pair of real

            numbers each defined as if by fvar_parms with the same arguments.

            The real and imaginary parts of of a complex number can be

            extracted using real_part and imaginary_part; these could have

            been injected ito the complex number using make_complex or any of

            the complex operations. Many translators will simply transform

            complex numbers into COMPOUNDs consisting of two floating point

            numbers, transforming the complex operations into floating point

            operations on the fields.</para>

        </sect3>

        <sect3 id="S23">

          <title>BITFIELD</title>

          <para>A number of contiguous bits have shape BITFIELD, qualified by

            a BITFIELD_VARIETY (S3.4) which gives the number of bits involved

            and whether these bits are to be treated as signed or unsigned

            integers. Current translators put a maximum of 32 or 64 on the

            number of bits.</para>

        </sect3>

        <sect3 id="S24">

          <title>PROC</title>

          <para>The representational SHAPEs of procedure values is given by

            PROC with constructor proc . I shall return to this in the

            description of the operations which use it.</para>

        </sect3>

        <sect3 id="S25">

          <title>Non-primitive SHAPEs</title>

          <para>The construction of the other four SHAPEs involves either

            existing SHAPEs or the alignments of existing SHAPEs.  These are

            constructed by compound, nof, offset and pointer.  Before

            describing these, we require a digression into what is meant by

            alignments and offsets.</para>

        </sect3>

      </sect2>

      <sect2>

        <title>Alignments</title>

        <para>In most processor architectures there are limitations on how one

          can address particular kinds of objects in convenient ways. These

          limitations are usually defined as part of the ABI for the

          processor. For example, in the MIPs processor the fastest way to

          access a 32-bit integer is to ensure that the address of the integer

          is aligned on a 4-byte boundary in the address space; obviously one

          can extract a mis-aligned integer but not in one machine

          instruction. Similarly, 16-bit integers should be aligned on a

          2-byte boundary. In principle, each primitive object could have

          similar restrictions for efficient access and these restrictions

          could vary from platform to platform. Hence, the notion of alignment

          has to be abstracted to form part of the architecture independent

          TDF - we cannot assume that any particular alignment regime will

          hold universally.</para>

        <para>The abstraction of alignments clearly has to cover compound

          objects as well as primitive ones like integers. For example, if a

          field of structure in C is to be accessed efficiently, then the

          alignment of the field will influence the alignment of the structure

          as whole; the structure itself could be a component of a larger

          object whose alignment must then depend on the alignment of the

          structure and so on. In general, we find that a compound alignment

          is given by the maximum alignment of its components, regardless of

          the form of the compound object e.g. whether it is a structure,

          union, array or whatever.</para>

        <para>This gives an immediate handle on the abstraction of the

          alignment of a compound object - it is just the set of abstractions

          of the alignments of its components. Since "maximum" is associative,

          commutative and idempotent, the component sets can be combined using

          normal set-union rules. In other words, a compound alignment is

          abstracted as the set of alignments of the primitive objects which

          make up the compound object. Thus the alignment abstraction of a C

          structure with only float fields is the singleton set containing the

          alignment of a float while that of a C union of an int and this

          structure is a pair of the alignments of an int and a float.</para>

        <sect3 id="alignement-constructors">

          <title>ALIGNMENT constructors</title>

          <para>The TDF abstraction of an alignment has SORT ALIGNMENT. The

            constructor, unite_alignments, gives the set-union of its

            ALIGNMENT parameters; this would correspond to taking a maximum of

            two real alignments in the translator.</para>

          <para>The constructor, alignment, gives the ALIGNMENT of a given

            SHAPE according to the rules given in the definition. These rules

            effectively <type>define</type> the primitive ALIGNMENTs as in the

            ALIGNMENT column of table 3. Those for PROC, all OFFSETs and all

            POINTERs are constants regardless of any SHAPE qualifiers. Each of

            the INTERGER VARIETYs, each of the FLOATING VARIETYs and each of

            the BITFIELD VARIETYs have their own ALIGNMENTs. These ALIGNMENTs

            will be bound to values apposite to the particular platform at

            translate-time. The ALIGNMENT of TOP is conventionally taken to be

            the empty set of ALIGNMENTs (corresponding to the minimum

            alignment on the platform).</para>

          <para>The alignment of a procedure parameter clearly has to include

            the alignment of its SHAPE; however, most ABIs will mandate a

            greater alignment for some SHAPEs e.g. the alignment of a byte

            parameter is usually defined to be on a 32-bit rather than an

            8-bit boundary. The constructor, parameter_alignment, gives the

            ALIGNMENT of a parameter of given SHAPE.</para>

        </sect3>

        <sect3 id="S28">