| 2 |
7u83 |
1 |
<!-- Crown Copyright (c) 1998 -->
|
|
|
2 |
<HTML>
|
|
|
3 |
<HEAD>
|
|
|
4 |
<TITLE>SORTs and TOKENs</TITLE>
|
|
|
5 |
</HEAD>
|
|
|
6 |
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000FF" VLINK="#400080" ALINK="#FF0000">
|
|
|
7 |
<A NAME=S3>
|
|
|
8 |
<H1>TDF Guide, Issue 4.0 </H1>
|
|
|
9 |
<H3>January 1998</H3>
|
|
|
10 |
<A HREF="guide5.html"><IMG SRC="../images/next.gif" ALT="next section">
|
|
|
11 |
</A> <A HREF="guide1.html">
|
|
|
12 |
<IMG SRC="../images/prev.gif" ALT="previous section"></A>
|
|
|
13 |
<A HREF="guide1.html"><IMG SRC="../images/top.gif" ALT="current document"></A>
|
|
|
14 |
<A HREF="../index.html"><IMG SRC="../images/home.gif" ALT="TenDRA home page">
|
|
|
15 |
</A>
|
|
|
16 |
<IMG SRC="../images/no_index.gif" ALT="document index"><P>
|
|
|
17 |
<HR>
|
|
|
18 |
<DL>
|
|
|
19 |
<DT><A HREF="#S4"><B>2.1 </B> - Token applications and first-class
|
|
|
20 |
SORTs</A><DD>
|
|
|
21 |
<DT><A HREF="#S5"><B>2.2 </B> - Token definitions and declarations</A><DD>
|
|
|
22 |
<DT><A HREF="#S6"><B>2.3 </B> - A simple use of a TOKEN</A><DD>
|
|
|
23 |
<DT><A HREF="#S7"><B>2.4 </B> - Second class SORTs</A><DD>
|
|
|
24 |
</DL>
|
|
|
25 |
<HR>
|
|
|
26 |
<H1>2 SORTs and TOKENs</H1>
|
|
|
27 |
In the syntax of language like C or Pascal, we find various syntactic
|
|
|
28 |
units like <Expression>, <Identifier> etc. A SORT bears
|
|
|
29 |
the same relation to TDF as these syntactic units bear to the language;
|
|
|
30 |
roughly speaking, the syntactic unit <Expression> corresponds
|
|
|
31 |
to the SORT EXP and <Identifier> to TAG . However, instead of
|
|
|
32 |
using BNF to compose syntactic units from others, TDF uses explicit
|
|
|
33 |
constructors to compose its SORTs; each constructor uses other pieces
|
|
|
34 |
of TDF of specified SORTs to make a piece of its result SORT. For
|
|
|
35 |
example, the constructor plus uses an ERROR_TREATMENT and two EXPs
|
|
|
36 |
to make another EXP.<P>
|
|
|
37 |
At the moment, there are 58 different SORTS, from ACCESS to VARIETY
|
|
|
38 |
given in tables 1 and 2. Some of these have familiar analogues in
|
|
|
39 |
standard language construction as with EXP and TAG above. Others will
|
|
|
40 |
be less familiar since TDF must concern itself with issues not normally
|
|
|
41 |
addressed in language definitions. For example, the process of linking
|
|
|
42 |
together TDF programs is at the root of the architecture neutrality
|
|
|
43 |
of TDF and so must form an integral part of its definition. On the
|
|
|
44 |
other hand, TDF is not meant to be a language readily accessible to
|
|
|
45 |
the human reader or writer; computers handle it much more easily.
|
|
|
46 |
Thus a great many choices have been made in the definition which would
|
|
|
47 |
be intolerable in a standard language definition for the human programmer
|
|
|
48 |
but which, paradoxically enough, make it much simpler for a computer
|
|
|
49 |
to produce and analyse TDF<P>
|
|
|
50 |
The SORTs and constructors in effect form a multi-sorted algebra.
|
|
|
51 |
There were two principal reasons for choosing this algebraic form
|
|
|
52 |
of definition. First, it is easy to extend - a new operation on existing
|
|
|
53 |
constructs simply requires a new constructor. Secondly, the algebraic
|
|
|
54 |
form is highly amenable to the automatic construction of programs.
|
|
|
55 |
Large parts of both TDF producers and TDF translators have been created
|
|
|
56 |
by automatic transformation of the text of the specification document
|
|
|
57 |
itself, by extracting the algebraic signature and constructing C program
|
|
|
58 |
which can read or produce TDF. To this extent, one can regard the
|
|
|
59 |
specification document as a formal description of the free algebra
|
|
|
60 |
of TDF SORTs and constructors. Of course, most of the interesting
|
|
|
61 |
parts of the definition of TDF lies in the equivalences of parts of
|
|
|
62 |
TDF, so this formality only covers the easy bit.<P>
|
|
|
63 |
Another distinction between the TDF definition and language syntactic
|
|
|
64 |
description is that TDF is to some extent conscious of its own SORTs
|
|
|
65 |
so that it can specify a new construction of a given SORT. The analogy
|
|
|
66 |
in normal languages would be that one could define a new construction
|
|
|
67 |
with new syntax and say this is an example of an <Expression>,
|
|
|
68 |
for example; I don't know of any standard language which permits this,
|
|
|
69 |
although those of you with a historical bent might remember Algol-N
|
|
|
70 |
which made a valiant attempt at it. Of course, the algebraic method
|
|
|
71 |
of description makes it much easier to specify, rather than having
|
|
|
72 |
to give syntax to provide the syntax for the new construction in a
|
|
|
73 |
language.<P>
|
|
|
74 |
<A NAME=S4>
|
|
|
75 |
<HR><H2>2.1. Token applications and first-class SORTs</H2>
|
|
|
76 |
A new construction is introduced by the SORT TOKEN; the constructors
|
|
|
77 |
involving TOKENs allow one to give an expansion for the TOKEN in terms
|
|
|
78 |
of other pieces of TDF, possibly including parameters. We can encapsulate
|
|
|
79 |
a (possibly parameterised) fragment of TDF of a suitable SORT by giving
|
|
|
80 |
it a TOKEN as identification. Not all of the SORTs are available for
|
|
|
81 |
this kind of encapsulation - only those which have a SORTNAME constructor
|
|
|
82 |
(from access to variety). These are the "first-class" SORTs
|
|
|
83 |
given in table 1 on page 8</A>. Each of these have an appropriate
|
|
|
84 |
_apply_token constructor (e.g. exp_apply_token ) give the expansion.
|
|
|
85 |
Most of these also have _cond constructors (e.g.see exp_cond in
|
|
|
86 |
<A HREF="guide11.html#1">section 9.1 on page 43</A>) which allows
|
|
|
87 |
translate time conditional expansion of the SORT.<P>
|
|
|
88 |
<P>
|
|
|
89 |
<BR><IMG SRC="table6.gif"><BR>
|
|
|
90 |
<P>
|
|
|
91 |
Every TOKEN has a result SORT, i.e. the SORT of its resulting expansion
|
|
|
92 |
and before it can be expanded, one must have its parameter SORTs.
|
|
|
93 |
Thus, you can regard a TOKEN as having a type defined by its result
|
|
|
94 |
and parameter SORTs and the _apply_token as the operator which expands
|
|
|
95 |
the encapsulation and substitutes the parameters. <P>
|
|
|
96 |
However, if we look at the signature of exp_apply_token:<P>
|
|
|
97 |
<PRE>
|
|
|
98 |
<I>token_value</I>: TOKEN
|
|
|
99 |
<I>token_args</I>: BITSTREAM <I>param_sorts(token_value)</I>
|
|
|
100 |
-> EXP <I>x</I>
|
|
|
101 |
<I></I>
|
|
|
102 |
</PRE>
|
|
|
103 |
we are confronted by the mysterious BITSTREAM where one might expect
|
|
|
104 |
to find the actual parameters of the TOKEN.<P>
|
|
|
105 |
To explain BITSTREAMs requires a diversion into the bit-encoding of
|
|
|
106 |
TDF. Constructors for a particular SORT are represented in a number
|
|
|
107 |
of bits depending on the number of constructors for that SORT; the
|
|
|
108 |
context will determine the SORT required, so no more bits are required.
|
|
|
109 |
Thus since there is only one constructor for UNITs, no bits are required
|
|
|
110 |
to represent make_unit; there are about 120 different constructors
|
|
|
111 |
for EXPs so 7 bits are required to cover all the EXPs. The parameters
|
|
|
112 |
of each constructor have known SORTs and so their representations
|
|
|
113 |
are just concatenated after the representation of the constructor
|
|
|
114 |
<A NAME=footnote70 HREF="footnote.html#70">*</A>. While this is a
|
|
|
115 |
very compact representation, it suffers from the defect that one must
|
|
|
116 |
decode it even just to skip over it. This is very irksome is some
|
|
|
117 |
applications, notably the TDF linker which is not interested detailed
|
|
|
118 |
expansions. Similarly, in translators there are places where one wishes
|
|
|
119 |
to skip over a token application without knowledge of the SORTs of
|
|
|
120 |
its parameters. Thus a BITSTREAM is just an encoding of some TDF,
|
|
|
121 |
preceded by the number of bits it occupies. Applications can then
|
|
|
122 |
skip over BITSTREAMs trivially. Similar considerations apply to BYTESTREAMs
|
|
|
123 |
used elsewhere; here the encoding is preceded by the number of bytes
|
|
|
124 |
in the encoding and is aligned to a byte boundary to allow fast copying.<P>
|
|
|
125 |
<A NAME=S5>
|
|
|
126 |
<HR><H2>2.2. Token definitions and declarations</H2>
|
|
|
127 |
Thus the <I>token_args</I> parameter of exp_apply_token is just the
|
|
|
128 |
BITSTREAM formed from the actual parameters in the sequence described
|
|
|
129 |
by the definition of the <I>token_valu</I><I>e</I> parameter. This
|
|
|
130 |
will be given in a TOKEN_DEFN somewhere with constructor token_definition:<P>
|
|
|
131 |
<PRE>
|
|
|
132 |
<I>result_sort</I>: SORTNAME
|
|
|
133 |
<I>tok_params</I>: LIST(TOKFORMALS)
|
|
|
134 |
<I>body</I>: <I>result_sort</I>
|
|
|
135 |
-> TOKEN_DEFN
|
|
|
136 |
</PRE>
|
|
|
137 |
The <I>result_sort</I> is the SORT of the construction of <I>body</I>;
|
|
|
138 |
e.g. if <I>result_sort</I> is formed from exp then <I>body</I> would
|
|
|
139 |
be constructed using the EXP constructors and one would use exp_apply_token
|
|
|
140 |
to give the expansion. The list <I>tok_params</I> gives the formal
|
|
|
141 |
parameters of the definition in terms of TOKFORMALS constructed using
|
|
|
142 |
make_tok_formals:<P>
|
|
|
143 |
<PRE>
|
|
|
144 |
<I>sn</I>: SORTNAME
|
|
|
145 |
<I>tk</I>: TDFINT
|
|
|
146 |
-> TOKFORMALS
|
|
|
147 |
</PRE>
|
|
|
148 |
The TDFINT <I>tk</I> will be the integer representation of the formal
|
|
|
149 |
parameter expressed as a TOKEN whose result sort is <I>sn</I> (see
|
|
|
150 |
more about name representation in <A HREF="guide5.html#2">section
|
|
|
151 |
3.1 on page 13</A>). To use the parameter in the body of the TOKEN_DEFN,
|
|
|
152 |
one simply uses the _apply_token appropriate to <I>sn</I>.Note that
|
|
|
153 |
sn may be a TOKEN but the <I>result_sort</I> may not.<P>
|
|
|
154 |
Hence the BITSTREAM <I>param_sorts</I>(<I>token_value</I>) in the
|
|
|
155 |
actual parameter of exp_apply_token above is simply formed by the
|
|
|
156 |
catenation of constructions of the SORTs given by the SORTNAMEs in
|
|
|
157 |
the <I>tok_params</I> of the TOKEN being expanded.<P>
|
|
|
158 |
Usually one gives a name to a TOKEN_DEFN using to form a TOKDEF using
|
|
|
159 |
make_tokdef :<P>
|
|
|
160 |
<PRE>
|
|
|
161 |
<I>tok</I>: TDFINT
|
|
|
162 |
<I>signature</I>: OPTION(STRING)
|
|
|
163 |
<I>def</I>: BITSTREAM TOKEN_DEFN
|
|
|
164 |
-> TOKDEF
|
|
|
165 |
</PRE>
|
|
|
166 |
Here, <I>tok</I> gives the name that will be used to identify the
|
|
|
167 |
TOKEN whose expansion is given by <I>def</I>. Any use of this TOKEN
|
|
|
168 |
(e.g. in exp_apply_token) will be given by make_token(<I>tok
|
|
|
169 |
</I>) . Once again, a BITSTREAM is used to encapsulate the TOKEN_DEFN.
|
|
|
170 |
<P>
|
|
|
171 |
The significance of the signature parameter is discussed in
|
|
|
172 |
<A HREF="guide5.html#37">section 3.2.2 on page 18</A>.<P>
|
|
|
173 |
Often, one wishes a token without giving its definition - the definition
|
|
|
174 |
could, for example, be platform-dependent. A TOKDEC introduces such
|
|
|
175 |
a token using make_tokdec:<P>
|
|
|
176 |
<PRE>
|
|
|
177 |
<I>tok</I>: TDFINT
|
|
|
178 |
<I>signature</I>: OPTION(STRING)
|
|
|
179 |
<I>s</I>: SORTNAME
|
|
|
180 |
-> TOKDEC
|
|
|
181 |
</PRE>
|
|
|
182 |
Here the SORTNAME, <I>s</I>, is given by token:<P>
|
|
|
183 |
<PRE>
|
|
|
184 |
<I>result</I>: SORTNAME
|
|
|
185 |
<I>params</I>: LIST(SORTNAME)
|
|
|
186 |
-> SORTNAME
|
|
|
187 |
</PRE>
|
|
|
188 |
which gives the result and parameter SORTs of <I>tok</I>. <P>
|
|
|
189 |
<P>
|
|
|
190 |
<P>
|
|
|
191 |
One can also use a TOKEN_DEFN in an anonymous fashion by giving it
|
|
|
192 |
as an actual parameter of a TOKEN which itself demands a TOKEN parameter.
|
|
|
193 |
To do this one simply uses use_tokdef :<P>
|
|
|
194 |
<PRE>
|
|
|
195 |
<I>tdef</I>: BITSTREAM TOKEN_DEFN
|
|
|
196 |
-> TOKEN
|
|
|
197 |
</PRE>
|
|
|
198 |
<A NAME=S6>
|
|
|
199 |
<HR><H2>2.3. A simple use of a TOKEN</H2>
|
|
|
200 |
<P>
|
|
|
201 |
The crucial use of TOKENs in TDF is to provide abstractions of APIs
|
|
|
202 |
(see <A HREF="guide12.html#0">section 10 on page 45</A>) but they
|
|
|
203 |
are also used as shorthand for commonly occurring constructions. For
|
|
|
204 |
example, given the TDF constructor plus, mentioned above, we could
|
|
|
205 |
define a plus with only two EXP parameters more suitable to C by using
|
|
|
206 |
the wrap constructor as the ERROR_TREATMENT:<P>
|
|
|
207 |
<PRE>
|
|
|
208 |
make_tokdef (C_plus, empty,
|
|
|
209 |
token_definition(
|
|
|
210 |
exp(),
|
|
|
211 |
(make_tokformals(exp(), l), make_tokformals(exp(), r)),
|
|
|
212 |
plus(wrap(), exp_apply_token(l, ()), exp_apply_token(r,())
|
|
|
213 |
)
|
|
|
214 |
)
|
|
|
215 |
</PRE>
|
|
|
216 |
<A NAME=S7>
|
|
|
217 |
<HR><H2>2.4. Second class SORTs</H2>
|
|
|
218 |
Second class SORTs (given in table 2 on page 11</A>) cannot be TOKENised.
|
|
|
219 |
These are the "syntactic units" of TDF which the user cannot
|
|
|
220 |
extend; he can only produce them using the constructors defined in
|
|
|
221 |
core-TDF.<P>
|
|
|
222 |
Some of these constructors are implicit. For example, there are no
|
|
|
223 |
explicit constructors for LIST or SLIST which are both used to form
|
|
|
224 |
lists of SORTs; their construction is simply part of the encoding
|
|
|
225 |
of TDF. However, it is forseen that LIST constructors would be highly
|
|
|
226 |
desireable and there will probably extensions to TDF to promote LIST
|
|
|
227 |
from a second-class SORT to a first-class one. This will not apply
|
|
|
228 |
to SLIST or to the other SORTs which have implicit constructions.
|
|
|
229 |
These include BITSTREAM, BYTESTREAM, TDFINT, TDFIDENT and TDFSTRING.<BR>
|
|
|
230 |
<P>
|
|
|
231 |
<BR><IMG SRC="table4.gif"><BR>
|
|
|
232 |
<P>
|
|
|
233 |
<P>
|
|
|
234 |
<HR>
|
|
|
235 |
<P><I>Part of the <A HREF="../index.html">TenDRA Web</A>.<BR>Crown
|
|
|
236 |
Copyright © 1998.</I></P>
|
|
|
237 |
</BODY>
|
|
|
238 |
</HTML>
|