Subversion Repositories tendra.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 7u83 1 
<!-- Crown Copyright (c) 1998 -->
2 
<HTML>
3 
<HEAD>
4 
<TITLE>Notes</TITLE>
5 
</HEAD>
6 
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000FF" VLINK="#400080" ALINK="#FF0000">
7 
<H1><A NAME=S382>TDF Specification, Issue 4.0</A></H1>
8 
<H3>January 1998</H3>
9 
<A HREF="spec11.html"><IMG SRC="../images/next.gif" ALT="next section"></A>
10 
<A HREF="spec9.html"><IMG SRC="../images/prev.gif" ALT="previous section"></A>
11 
<A HREF="spec1.html"><IMG SRC="../images/top.gif" ALT="current document"></A>
12 
<A HREF="../index.html"><IMG SRC="../images/home.gif" ALT="TenDRA home page">
13 
</A>
14 
<A HREF="spec12.html"><IMG SRC="../images/index.gif" ALT="document index"></A>
15 
<P>
16 
<HR>
17 
<DL>
18 
<DT><A HREF="#S383"><B>7.1</B> - Binding</A><DD>
19 
<DT><A HREF="#S384"><B>7.2</B> - Character codes</A><DD>
20 
<DT><A HREF="#S385"><B>7.3</B> - Constant evaluation</A><DD>
21 
<DT><A HREF="#S386"><B>7.4</B> - Division and modulus</A><DD>
22 
<DT><A HREF="#S387"><B>7.5</B> - Equality of EXPs</A><DD>
23 
<DT><A HREF="#S388"><B>7.6</B> - Equality of SHAPEs</A><DD>
24 
<DT><A HREF="#S389"><B>7.7</B> - Equality of ALIGNMENTS</A><DD>
25 
<DT><A HREF="#S390"><B>7.8</B> - Exceptions and jumps</A><DD>
26 
<DT><A HREF="#S391"><B>7.9</B> - Procedures</A><DD>
27 
<DT><A HREF="#S392"><B>7.10</B> - Frames</A><DD>
28 
<DT><A HREF="#S393"><B>7.11</B> - Lifetimes</A><DD>
29 
<DT><A HREF="#S394"><B>7.12</B> - Alloca</A><DD>
30 
<DT><A HREF="#S395"><B>7.13</B> - Memory Model</A><DD>
31 
<DL>
32 
<DT><A HREF="#S396"><B>7.13.1</B> - Simple model</A><DD>
33 
<DT><A HREF="#S397"><B>7.13.2</B> - Comparison of pointers and offsets</A><DD>
34 
<DT><A HREF="#S398"><B>7.13.3</B> - Circular types in languages</A><DD>
35 
<DT><A HREF="#S399"><B>7.13.4</B> - Special alignments</A><DD>
36 
<DT><A HREF="#S400"><B>7.13.5</B> - Atomic assignment</A><DD>
37 
</DL>
38 
<DT><A HREF="#S401"><B>7.14</B> - Order of evaluation</A><DD>
39 
<DT><A HREF="#S402"><B>7.15</B> - Original pointers</A><DD>
40 
<DT><A HREF="#S403"><B>7.16</B> - Overlapping</A><DD>
41 
<DT><A HREF="#S404"><B>7.17</B> - Incomplete assignment</A><DD>
42 
<DT><A HREF="#S405"><B>7.18</B> - Representing integers</A><DD>
43 
<DT><A HREF="#S406"><B>7.19</B> - Overflow and Integers</A><DD>
44 
<DT><A HREF="#S407"><B>7.20</B> - Representing floating point</A><DD>
45 
<DT><A HREF="#S408"><B>7.21</B> - Floating point errors</A><DD>
46 
<DT><A HREF="#S409"><B>7.22</B> - Rounding and floating point</A><DD>
47 
<DT><A HREF="#S410"><B>7.23</B> - Floating point accuracy</A><DD>
48 
<DT><A HREF="#S411"><B>7.24</B> - Representing bitfields</A><DD>
49 
<DT><A HREF="#S412"><B>7.25</B> - Permitted limits</A><DD>
50 
<DT><A HREF="#S413"><B>7.26</B> - Least Upper Bound</A><DD>
51 
<DT><A HREF="#S414"><B>7.27</B> - Read-only areas</A><DD>
52 
<DT><A HREF="#S415"><B>7.28</B> - Tag and Token signatures</A><DD>
53 
<DT><A HREF="#S416"><B>7.29</B> - Dynamic initialisation</A><DD>
54 
</DL>
55 
<HR>
56 
<H1>7. Notes</H1>
57 
<A NAME=S383>
58 
 
59 
<HR>
60 
<H2>7.1. Binding</H2>
61 
<A NAME=M1><A NAME=M2>The following constructions introduce
62 
<CODE>TAG</CODE>s: <I>identify</I>, <I>variable</I>, <I>make_proc</I>,
63 
<I>make_general_proc</I>, <I>make_id_tagdec</I>, <I>make_var_tagdec</I>,
64 
<I>common_tagdec</I>.
65 
<P>
66 
During the evaluation of <I>identify</I> and <I>variable</I> a value,
67 
<I>v</I>, is produced which is bound to the <CODE>TAG</CODE> during
68 
the evaluation of an <CODE>EXP</CODE> or <CODE>EXP</CODE>s. The
69 
<CODE>TAG</CODE> is &quot;in scope&quot; for these <CODE>EXP</CODE>s.
70 
This means that in the <CODE>EXP</CODE> a use of the <CODE>TAG</CODE>
71 
is permissible and will refer to the declaration.
72 
<P>
73 
The <I>make_proc</I> and <I>make_general_proc</I> construction introduces
74 
<CODE>TAG</CODE>s which are bound to the actual parameters on each
75 
call of the procedure. These <CODE>TAG</CODE>s are &quot;in scope&quot;
76 
for the body of the procedure.
77 
<P>
78 
If a <I>make_proc</I> or <I>make_general_proc</I> construction occurs
79 
in the body of another <I>make_proc</I> or <I>make_general_proc</I>,
80 
the <CODE>TAG</CODE>s of the inner procedure are not in scope in the
81 
outer procedure, nor are the <CODE>TAG</CODE>s of the outer in scope
82 
in the inner.
83 
<P>
84 
The <I>apply_general_proc</I> construction permits the introduction
85 
of
86 
<CODE>TAG</CODE>s whose scope is the <I>postlude</I> argument. These
87 
are bound to the values of caller parameters after the evaluation
88 
of the body of the procedure.
89 
<P>
90 
The <I>make_id_tagdec</I>, <I>make_var_tagdec</I> and <I>common_tagdec</I>
91 
constructions introduce <CODE>TAG</CODE>s which are &quot;in scope&quot;
92 
throughout all the <I>tagdef</I> <CODE>UNIT</CODE>s. These <CODE>TAG</CODE>s
93 
may have values defined for them in the <I>tagdef</I> <CODE>UNIT</CODE>s,
94 
or values may be supplied by linking.
95 
<P>
96 
<A NAME=M3><A NAME=M4><A NAME=M5>The following constructions introduce
97 
<CODE>LABEL</CODE>s: <I>conditional</I>,
98 
<I>repeat</I>, <I>labelled</I>.
99 
<P>
100 
The construction themselves define <CODE>EXP</CODE>s for which these
101 
<CODE>LABEL</CODE>s are &quot;in scope&quot;. This means that in the
102 
<CODE>EXP</CODE>s a use of the <CODE>LABEL</CODE> is permissible and
103 
will refer to the introducing construction.
104 
<P>
105 
<CODE>TAG</CODE>s, <CODE>LABEL</CODE>s and <CODE>TOKEN</CODE>s (as
106 
<CODE>TOKEN</CODE> parameters) introduced in the body of a
107 
<CODE>TOKEN</CODE> definition are systematically renamed in their
108 
scope each time the <CODE>TOKEN</CODE> definition is applied. The
109 
scope will be completely included by the <CODE>TOKEN</CODE> definition.
110 
<P>
111 
Each of the values introduced in a <CODE>UNIT</CODE> will be named
112 
by a different <CODE>TAG</CODE>, and the labelling constructions will
113 
use different labels, so no visibility rules are needed. The set of
114 
<CODE>TAG</CODE>s and <CODE>LABEL</CODE>s used in a simple
115 
<CODE>UNIT</CODE> are considered separately from those in another
116 
simple
117 
<CODE>UNIT</CODE>, so no question of visibility arises. The compound
118 
and link <CODE>UNIT</CODE>s provide a method of relating the items
119 
in one simple <CODE>UNIT</CODE> to those in another, but this is through
120 
the intermediary of another set of <CODE>TAG</CODE>s and <CODE>TOKEN</CODE>s
121 
at the <CODE>CAPSULE</CODE> level.
122 
<P>
123 
<A NAME=S384>
124 
 
125 
<HR>
126 
<H2>7.2. Character codes</H2>
127 
<A NAME=M6>TDF does not have a concept of characters. It transmits
128 
integers of various sizes. So if a producer wishes to communicate
129 
characters to an installer, it will usually have to do so by encoding
130 
them in some way as integers.
131 
<P>
132 
An ANSI C producer sending a TDF program to a set of normal C environments
133 
may well choose to encode its characters using the ASCII codes, an
134 
EBCDIC based producer transmitting to a known set of EBCDIC environments
135 
might use the code directly, and a wide character producer might likewise
136 
choose a specific encoding. For some programs this way of proceeding
137 
is necessary, because the codes are used both to represent characters
138 
and for arithmetic, so the particular encoding is enforced. In these
139 
cases it will not be possible to translate the characters to another
140 
encoding because the character codes will be used in the TDF as ordinary
141 
integers, which must not be translated.
142 
<P>
143 
Some producers may wish to transmit true characters, in the sense
144 
that something is needed to represent particular printing shapes and
145 
nothing else. These representations will have to be transformed into
146 
the correct character encoding on the target machine.
147 
<P>
148 
Probably the best way to do this is to use <CODE>TOKEN</CODE>s. A
149 
fixed representation for the printing marks could be chosen in terms
150 
of integers and <CODE>TOKEN</CODE>s introduced to represent the translation
151 
from these integers to local character codes, and from strings of
152 
integers to strings of local character codes. These definitions could
153 
be bound on the target machine and the installer should be capable
154 
of translating these constructions into efficient machine code. To
155 
make this a standard, unique <CODE>TOKEN</CODE>s should be used.
156 
<P>
157 
But this raises the question, who chooses the fixed representation
158 
and the unique <CODE>TOKEN</CODE>s and their specification? Clearly
159 
TDF provides a mechanism for performing the standardisation without
160 
itself defining a standard.
161 
<P>
162 
Here TDF gives rise to the need for extra standards, especially in
163 
the specification of globally named unique <CODE>TOKEN</CODE>s.
164 
<P>
165 
<A NAME=S385>
166 
 
167 
<HR>
168 
<H2>7.3. <A NAME=7>Constant evaluation</H2>
169 
<A NAME=M8><A NAME=M9>Some constructions require an
170 
<CODE>EXP</CODE> argument which is &quot;constant at install time&quot;.
171 
For an <CODE>EXP</CODE> to satisfy this condition it must be constructed
172 
according to the following rules after substitution of token definitions
173 
and selection of <I>exp_cond</I> branches.
174 
<P>
175 
If it contains <I>obtain_tag</I> then the tag will be introduced within
176 
the <CODE>EXP</CODE>, or defined with <I>make_id_tagdef</I> within
177 
the current capsule.
178 
<P>
179 
It may not contain any of the following constructions: <I>apply_proc,
180 
apply_general_proc, assign_with_mode</I>, <I>contents_with_mode</I>,
181 
<I>continue</I>, <I>current_env</I>, <I>error_jump</I>,
182 
<I>goto_local_lv</I>, <I>make_local_lv</I>, <I>move_some</I>,
183 
<I>repeat</I>, <I>round_as_state</I>.
184 
<P>
185 
Unless it is the <CODE>EXP</CODE> argument of a <CODE>TAGDEF</CODE>,
186 
a &quot;constant at install time&quot; may not contain <I>env_offset</I>
187 
or <I>env_size</I>.
188 
<P>
189 
Any use of <I>contents</I> or <I>assign</I> will be applied only to
190 
<CODE>POINTER</CODE>s derived from <I>variable</I> constructions.
191 
<P>
192 
If it contains <I>labelled</I> there will only be jumps to the
193 
<CODE>LABEL</CODE>s from within <I>starter</I>, not from within any
194 
of the <I>places</I>.
195 
<P>
196 
Any use of <I>obtain_tag</I> defined with <I>make_id_tagdef</I> will
197 
occur after the end of the <I>make_id_tagdef</I>.
198 
<P>
199 
Note specifically that a constant <CODE>EXP</CODE> forming the defining
200 
value of a <CODE>TAGDEF</CODE> construct may contain <I>env_offset</I>
201 
and/or <I>env_size</I>.
202 
<P>
203 
<A NAME=S386>
204 
 
205 
<HR>
206 
<H2>7.4. <A NAME=10>Division and modulus</H2>
207 
<A NAME=M11><A NAME=M12>Two classes of division (D) and remainder
208 
(M) construct are defined. The two classes have the same definition
209 
if both operands have the same sign. Neither is defined if the second
210 
argument is zero.
211 
<P><B>Class 1</B>:
212 
<PRE>
213 
	<I>p</I> D1 <I>q</I> = <I>n</I>
214 
</PRE>
215 
where:
216 
<PRE>
217 
	<I>p</I> = <I>n</I>*<I>q</I> + (<I>p</I> M1 <I>q</I>)
218 
	sign(<I>p</I> M1 <I>q</I>) = sign(<I>q</I>)
219 
 
220 
</PRE>
221 
<P><B>Class 2</B>:
222 
<PRE>
223 
	<I>p</I> D2 <I>q</I> = <I>n</I>
224 
</PRE>
225 
where:
226 
<PRE>
227 
	<I>p</I> = <I>n</I>*<I>q</I> + (<I>p</I> M2 <I>q</I>)
228 
	sign(<I>p</I> M2 <I>q</I>) = sign(<I>p</I>)
229 
 
230 
</PRE>
231 
<P>
232 
<A NAME=S387>
233 
 
234 
<HR>
235 
<H2>7.5. Equality of EXPs</H2>
236 
<A NAME=M13>A definition of equality of <CODE>EXP</CODE>s would be
237 
a considerable part of a formal specification of TDF, and is not given
238 
here.
239 
<P>
240 
<A NAME=S388>
241 
 
242 
<HR>
243 
<H2>7.6. Equality of SHAPEs</H2>
244 
<A NAME=M14>Equality of <CODE>SHAPE</CODE>s is defined recursively:
245 
<UL>
246 
<LI>Two <CODE>SHAPE</CODE>s are equal if they are both <CODE>BOTTOM</CODE>,
247 
or both <CODE>TOP</CODE> or both <CODE>PROC</CODE>.<P>
248 
<LI>Two <CODE>SHAPE</CODE>s are equal if they are both <I>integer</I>
249 
or both <I>floating</I>, or both <I>bitfield</I>, and the corresponding
250 
parameters are equal.<P>
251 
<LI>Two <CODE>SHAPE</CODE>s are equal if they are both <CODE>NOF</CODE>,
252 
the numbers of items are equal and the <CODE>SHAPE</CODE> parameters
253 
are equal.<P>
254 
<LI>Two <CODE>OFFSET</CODE>s or two <CODE>POINTER</CODE>s are equal
255 
if their <CODE>ALIGNMENT</CODE> parameters are pairwise equal.<P>
256 
<LI>Two <CODE>COMPOUND</CODE>s are equal if their <CODE>OFFSET</CODE>
257 
<CODE>EXP</CODE>s are equal.<P>
258 
<LI>No other pairs of <CODE>SHAPE</CODE>s are equal.
259 
</UL>
260 
<P>
261 
<A NAME=S389>
262 
 
263 
<HR>
264 
<H2>7.7. <A NAME=15>Equality of ALIGNMENTs</H2>
265 
<A NAME=M16>Two <CODE>ALIGNMENT</CODE>s are equal if and only if they
266 
are equal sets.
267 
<P>
268 
<A NAME=S390>
269 
 
270 
<HR>
271 
<H2>7.8. <A NAME=17>Exceptions and jumps</H2>
272 
TDF allows simply for labels and jumps within a procedure, by means
273 
of the <I>conditional</I>, <I>labelled</I> and <I>repeat</I> constructions,
274 
and the <I>goto</I>, <I>case</I> and various <I>test</I> constructions.
275 
But there are two more complex jumping situations.
276 
<P>
277 
First there is the jump, known to stay within a procedure, but to
278 
a computed destination. Many languages have discouraged this kind
279 
of construction, but it is still available in Cobol (implicitly),
280 
and it can be used to provide other facilities (see below). TDF allows
281 
it by means of the <CODE>POINTER(</CODE>{<I>code</I><CODE>})</CODE>.
282 
TDF is arranged so that this can usually be implemented as the address
283 
of the label. The <I>goto_local_lv</I> construction just jumps to
284 
the label.
285 
<P>
286 
The other kind of construction needed is the jump out of a procedure
287 
to a label which is still active, restoring the environment of the
288 
destination procedure: the long jump. Related to this is the notion
289 
of exception. Unfortunately long jumps and exceptions do not co-exist
290 
well. Exceptions are commonly organised so that any necessary destruction
291 
operations are performed as the stack of frames is traversed; long
292 
jumps commonly go directly to the destination. TDF must provide some
293 
facility which can express both of these concepts. Furthermore exceptions
294 
come in several different versions, according to how the exception
295 
handlers are discriminated and whether exception handling is initiated
296 
if there is no handler which will catch the exception.
297 
<P>
298 
Fortunately the normal implementations of these concepts provide a
299 
suggestion as to how they can be introduced into TDF. The local label
300 
value provides the destination address, the environment (produced
301 
by <I>current_env</I>) provides the stack frame for the destination,
302 
and the stack re-setting needed by the local label jumps themselves
303 
provides the necessary stack information. If more information is needed,
304 
such as which exception handlers are active, this can be created by
305 
producing the appropriate TDF.
306 
<P>
307 
So TDF takes the long jump as the basic construction, and its parameters
308 
are a local label value and an environment. Everything else can be
309 
built in terms of these.
310 
<P>
311 
The TDF arithmetic constructions allows one to specify a <CODE>LABEL</CODE>
312 
as destination if the result of the operation is exceptional. This
313 
is sufficient for the kind of explicit exception handling found in
314 
C++ and, in principle, could also be used to implement the kind of
315 
&quot;automatic&quot; exception detection and handling found in Ada,
316 
for example.
317 
<P>
318 
However many architectures have facilities for automatically trapping
319 
on exceptions without explicit testing. To take advantage of this,
320 
there is a <I>trap</I> <CODE>ERROR_TREATMENT</CODE> with associated
321 
<CODE>ERROR_CODE</CODE>s. The action taken on an exception with
322 
<I>trap</I> <CODE>ERROR_TREATMENT</CODE> will be to &quot;throw&quot;
323 
the
324 
<CODE>ERROR_CODE</CODE>.  Since each language has its own idea of
325 
how to interpret the <CODE>ERROR_CODE</CODE> and handle exceptions,
326 
the onus is on the producer writer to describe how to throw an
327 
<CODE>ERROR_CODE</CODE>.
328 
<P>
329 
The producer writer must give a definition of a <CODE>TOKEN</CODE>
330 
<I>~Throw</I> : <CODE>NAT</CODE> -&gt; <CODE>EXP</CODE> where the
331 
<CODE>NAT</CODE> will be the <I>error_val</I> of some <CODE>ERROR_CODE</CODE>.
332 
The expansion of this token will be consistent with the interpretation
333 
of the relevant <CODE>ERROR_CODE</CODE> and the method of handling
334 
exceptions.  Usually this will consist of decoding the
335 
<CODE>ERROR_CODE</CODE> and doing a long_jump on some globals set
336 
up by the procedure in which the exception handling takes place.
337 
<P>
338 
The translator writer will provide a parameterless <CODE>EXP TOKEN</CODE>,
339 
<I>~Set_signal_handler</I>.  This <CODE>TOKEN</CODE> will use <I>~Throw</I>
340 
and must be applied before any possible exceptions. This implies that
341 
the definition of both <I>~Throw</I> and
342 
<I>~Set_signal_handler</I> must be bound before translation of any
343 
<CODE>CAPSULE</CODE> which uses them, presumeably by linking with
344 
some TDF libraries.
345 
<P>
346 
These tokens are specified in more detail in the companion document,
347 
<A HREF="register.html">TDF Token Register</A>.
348 
<P>
349 
<A NAME=S391>
350 
 
351 
<HR>
352 
<H2>7.9. <A NAME=18>Procedures</H2>
353 
The <I>var_intro</I> of a <I>make_proc</I>, if present, may be used
354 
under one of two different circumstances. In one circumstance, the
355 
<CODE>POINTER TAG</CODE> provided by the <I>var_intro</I> is used
356 
to access the actual <I>var_param</I> of an <I>apply_proc</I>. If
357 
this is the case, all uses of <I>apply_proc</I> which have the effect
358 
of calling this procedure will have the <I>var_param</I> option present,
359 
and they will all have precisely the same number of <I>params</I>
360 
as
361 
<I>params_intro</I> in the <I>make_proc</I>. The body of the
362 
<I>make_proc</I> can access elements of the <I>var_param</I> by using
363 
<CODE>OFFSET</CODE> arithmetic relative to the <CODE>POINTER TAG</CODE>.
364 
This provides a method of supplying a variable number of parameters,
365 
by composing them into a compound value which is supplied as the
366 
<I>var_param</I>.
367 
<P>
368 
However, this has proved to be unsatisfactory for the implementation
369 
of variable number of parameters in C - one cannot choose the
370 
<CODE>POINTER</CODE> alignment of the <CODE>TAG</CODE> a priori in
371 
non-prototype calls.
372 
<P>
373 
An alternative circumstance for using <I>var_intro</I> is where all
374 
uses of <I>apply_proc</I> which have the effect of calling this procedure
375 
may have more <I>params</I> present than the number of <I>params_intro</I>,
376 
and none of them will have their <I>var_param</I> option present.
377 
The body of the <I>make_proc</I> can access the additional params
378 
by using installer-defined <CODE>TOKEN</CODE>s specified in the companion
379 
document <A HREF="register.html">TDF Token Register</A>, analogous
380 
to the use of variable argument lists in C. A local variable <I>v</I>
381 
of shape <I>~va_list</I> must be initialised to <I>~__va_start</I>(<I>p</I>),
382 
where <I>p</I> is the
383 
<CODE>POINTER</CODE> obtained from the <I>var_intro</I>. Successive
384 
elements of the <I>params</I> list can then be obtained by successive
385 
applications of <I>~va_arg</I>(<I>v</I>,<I>s</I>) where <I>s</I> is
386 
the
387 
<CODE>SHAPE</CODE> of element obtained. Finally,
388 
<I>~va_end</I>(<I>v</I>) completes the use of <I>v</I>.
389 
<P>
390 
The definition of caller parameters in general procedures addesses
391 
this difficulty in a different way, by describing the layout of caller
392 
parameters qualified by <CODE>PROCPROPS</CODE> <I>var_callers</I>.
393 
This allows both the call and the body to have closely associated
394 
views of the <CODE>OFFSET</CODE>s within a parameter set, regardless
395 
of whether or not the particular parameter has been named. The installer-defined
396 
<CODE>TOKEN</CODE> <I>~next_caller_offset</I> provides access to successive
397 
caller parameters, by using <CODE>OFFSET</CODE>s relative to the current
398 
frame pointer <I>current_env</I>, adjusting for any differences there
399 
may be between the closely associated views.  The
400 
<I>caller_intro</I> list of the <I>make_general_proc</I> must not
401 
be empty, then the sequence of <CODE>OFFSET</CODE>s can start with
402 
an appropriate <I>env_offset</I>. Similar consideration applies to
403 
accessing within the callee parameters, using the installer-defined
404 
<CODE>TOKEN</CODE> <I>~next_callee_offset</I>.
405 
<P>
406 
All uses of <I>return</I>, <I>untidy_return</I> and <I>tail_call</I>
407 
in a procedure will return values of the same <CODE>SHAPE</CODE>,
408 
and this will be the <I>result_shape</I> specified in all uses of
409 
<I>apply_proc</I> or <I>apply_general_proc</I> calling the procedure.
410 
<P>
411 
The use of <I>untidy_return</I> gives a generalisation of
412 
<I>local_alloc</I>.  It extends the validity of pointers allocated
413 
by
414 
<I>local_alloc</I> within the immediatly enclosing procedure into
415 
the calling procedure.  The original space of these pointers may be
416 
invalidated by <I>local_free</I> just as if it had been generated
417 
by
418 
<I>local_alloc</I> in the calling procedure.
419 
<P>
420 
The <CODE>PROCPROPS</CODE> <I>check_stack</I> may be used to check
421 
that limit set by set_stack_limit is not exceeded by the allocation
422 
of the static locals of a procedure body to be obeyed. If it is exceeded
423 
then the producer-defined <CODE>TOKEN</CODE> <I>~Throw</I>: <CODE>NAT</CODE>
424 
-&gt; <CODE>EXP</CODE> will be invoked as
425 
<I>~Throw</I>(<I>error_val</I>(<I>stack_overflow</I>)).  Note that
426 
this will not include any space generated by <CODE>local_alloc</CODE>;
427 
an explicit test is required to do check these.
428 
<P>
429 
Any <CODE>SHAPE</CODE> is permitted as the <I>result_shape</I> in
430 
an <I>apply_proc</I> or <I>apply_general_proc</I>.
431 
<P>
432 
<A NAME=S392>
433 
 
434 
<HR>
435 
<H2>7.10. <A NAME=19>Frames</H2>
436 
<A NAME=M20>TDF states that while a particular procedure activation
437 
is current, it is possible to create a <CODE>POINTER</CODE>, by using
438 
<I>current_env</I>, which gives access to all the declared variables
439 
and identifications of the activation which are alive and which have
440 
been marked as <I>visible</I>. The construction
441 
<I>env_offset</I> gives the <CODE>OFFSET</CODE> of one of these relative
442 
to such a <CODE>POINTER</CODE>.  These constructions may serve for
443 
several purposes.
444 
<P>
445 
One significant purpose is to implement such languages as Pascal which
446 
have procedures declared inside other procedures. One way of implementing
447 
this is by means of a &quot;display&quot;, that is, a tuple of frame
448 
pointers of active procedures.
449 
<P>
450 
Another purpose is to find active variables satisfying some criterion
451 
in all the procedure activations. This is commonly required for garbage
452 
collection. TDF does not force the installer to implement a frame
453 
pointer register, since some machines do not work best in this way.
454 
Instead, a frame pointer is created only if required by <I>current_env</I>.
455 
The implication of this is that this sort of garbage collection needs
456 
the collaboration of the producer to create TDF which makes the correct
457 
calls on <I>current_env</I> and <I>env_offset</I> and place suitable
458 
values in known positions.
459 
<P>
460 
Programs compiled especially to provide good diagnostic information
461 
can also use these operations.
462 
<P>
463 
In general any program which wishes to manipulate the frames of procedures
464 
other than the current one can use <I>current_env</I> and <I>env_offset</I>
465 
to do so.
466 
<P>
467 
A frame consists of three components, the caller parameters, callee
468 
parameters and locals of the procedure involved. Since each component
469 
may have different internal methods of access within the frame, each
470 
has a different special frame alignment associated with pointers within
471 
them. These are <I>callers_alignment</I>, <I>callees_alignment</I>
472 
and
473 
<I>locals_alignment</I>. The <CODE>POINTER</CODE> produced by
474 
<I>current_env</I> will be some union of these special alignments
475 
depending on how the procedure was defined.
476 
<P>
477 
Each of these frame alignments are considered to contain any
478 
<CODE>ALIGNMENT</CODE> produced by <I>alignment</I> from any
479 
<CODE>SHAPE</CODE>. Note that this does not say that they are the
480 
set union of all such <CODE>ALIGNMENT</CODE>s. This is because the
481 
interpretation of pointer and offset operations (notably
482 
<I>add_to_pointer</I>) may be different depending on the implementation
483 
of the frames; they may involve extra indirections.
484 
<P>
485 
Accordingly, because of the constraints on <I>add_to_ptr</I>, an
486 
<CODE>OFFSET</CODE> produced by <I>env_offset</I> can only be added
487 
to a
488 
<CODE>POINTER</CODE> produced by <I>current_env</I>. It is a further
489 
constraint that such an <CODE>OFFSET</CODE> will only be added to
490 
a
491 
<CODE>POINTER</CODE> produced from <I>current_env</I> used on the
492 
procedure which declared the <CODE>TAG</CODE>.
493 
<P>
494 
<A NAME=S393>
495 
 
496 
<HR>
497 
<H2>7.11. Lifetimes</H2>
498 
<A NAME=M21><CODE>TAG</CODE>s are bound to values during the evaluation
499 
of <CODE>EXP</CODE>s, which are specified by the construction which
500 
introduces the <CODE>TAG</CODE>. The evaluation of these
501 
<CODE>EXP</CODE>s is called the lifetime of the activation of the
502 
<CODE>TAG</CODE>.
503 
<P>
504 
Note that lifetime is a different concept from that of scope. For
505 
example, if the <CODE>EXP</CODE> contains the application of a procedure,
506 
the evaluation of the body of the procedure is within the lifetime
507 
of the <CODE>TAG</CODE>, but the <CODE>TAG</CODE> will not be in scope.
508 
<P>
509 
A similar concept applies to <CODE>LABEL</CODE>s.
510 
<P>
511 
<A NAME=S394>
512 
 
513 
<HR>
514 
<H2>7.12. <A NAME=22>Alloca</H2>
515 
<A NAME=M23>The constructions involving <I>alloca</I>
516 
(<I>last_local</I>, <I>local_alloc</I>, <I>local_free</I>,
517 
<I>local_free_all</I>) as well as the <I>untidy_return</I> construction
518 
imply a stack-like implementation which is related to procedure calls.
519 
They may be implemented using the same stack as the procedure frames,
520 
if there is such a stack, or it may be more convenient to implement
521 
them separately. However note that if the <I>alloca</I> mechanism
522 
is implemented as a stack, this may be an upward or a downward growing
523 
stack.
524 
<P>
525 
The state of this notional stack is referred to here as the <I>alloca</I>
526 
state. The construction <I>local_alloc</I> creates a new space on
527 
the <I>alloca</I> stack, the size of this space being given by an
528 
<CODE>OFFSET</CODE>. In the special case that this <CODE>OFFSET</CODE>
529 
is zero, <I>local_alloc</I> in effect gives the current <I>alloca</I>
530 
state (normally a <CODE>POINTER</CODE> to the top of the stack).
531 
<P>
532 
A use of <I>local_free_all</I> returns the <I>alloca</I> state to
533 
what it was on entry to the current procedure.
534 
<P>
535 
The construction <I>last_local</I> gives a <CODE>POINTER</CODE> to
536 
the top item on the stack, but it is necessary to give the size of
537 
this (as an <CODE>OFFSET</CODE>) because this cannot be deduced if
538 
the stack is upward growing. This top item will be the whole of an
539 
item previously allocated with <I>local_alloc</I>.
540 
<P>
541 
The construction <I>local_free</I> returns the state of the <I>alloca</I>
542 
machine to what it was when its parameter <CODE>POINTER</CODE> was
543 
allocated. The <CODE>OFFSET</CODE> parameter will be the same value
544 
as that with which the <CODE>POINTER</CODE> was allocated.
545 
<P>
546 
The <CODE>ALIGNMENT</CODE> of the <CODE>POINTER</CODE> delivered by
547 
<I>local_alloc</I> is <I>alloca_alignment</I>. This shall include
548 
the set union of all the <CODE>ALIGNMENT</CODE>s which can be produced
549 
by <I>alignment</I> from any <CODE>SHAPE</CODE>.
550 
<P>
551 
<A NAME=M24><A NAME=M25>The use of <I>alloca_alignment</I>
552 
arises so that the <I>alloca</I> stack can hold any kind of value.
553 
The sizes of spaces allocated must be rounded up to the appropriate
554 
<CODE>ALIGNMENT</CODE>. Since this includes all value
555 
<CODE>ALIGNMENT</CODE>s a value of any <CODE>ALIGNMENT</CODE> can
556 
be assigned into this space.  Note that there is no necessary relation
557 
with the special frame alignments (see <A HREF="#19">section 7.10</A>)
558 
though they must both contain all the <CODE>ALIGNMENT</CODE>s which
559 
can be produced by <I>alignment</I> from any <CODE>SHAPE</CODE>.
560 
<P>
561 
Stack pushing is <I>local_alloc</I>. Stack popping can be performed
562 
by use of <I>last_local</I> and <I>local_free</I>. Remembering the
563 
state of the <I>alloca</I> stack and returning to it can be performed
564 
by using
565 
<I>local_alloc</I> with a zero <CODE>OFFSET</CODE> and
566 
<I>local_free</I>.
567 
<P>
568 
Note that stack pushing can also be achieved by the use of a procedure
569 
call with <I>untidy_return</I>.
570 
<P>
571 
A transfer of control to a local label by means of <I>goto</I>,
572 
<I>goto_local_lv</I>, any <I>test</I> construction or any
573 
<I>error_jump</I> will not change the <I>alloca</I> stack.
574 
<P>
575 
<I>If an installer implements identify and variable by creating space
576 
on a stack when they come into existence, rather than doing the allocation
577 
for identify and variable at the start of a procedure activation,
578 
then it may have to consider making the alloca stack into a second
579 
stack.</I>
580 
<P>
581 
<A NAME=S395>
582 
 
583 
<HR>
584 
<H2>7.13. <A NAME=26>Memory Model</H2>
585 
<A NAME=M27><A NAME=M28><A NAME=M29>The layout of data in memory is
586 
entirely determined by the calculation of
587 
<CODE>OFFSET</CODE>s relative to <CODE>POINTER</CODE>s. That is, it
588 
is determined by <CODE>OFFSET</CODE> arithmetic and the <I>add_to_ptr</I>
589 
construction.
590 
<P>
591 
A <CODE>POINTER</CODE> is parameterised by the <CODE>ALIGNMENT</CODE>
592 
of the data indicated. An <CODE>ALIGNMENT</CODE> is a set of all the
593 
different kinds of basic value which can be indicated by a
594 
<CODE>POINTER</CODE>.  That is, it is a set chosen from all
595 
<CODE>VARIETY</CODE>s, all <CODE>FLOATING_VARIETY</CODE>s, <I>all</I>
596 
<CODE>BITFIELD_VARIETY</CODE>s<I>, proc</I>, <I>code</I>,
597 
<I>pointer</I> and <I>offset</I>. There are also three special
598 
<CODE>ALIGNMENT</CODE>s, <I>frame_alignment</I>, <I>alloca_alignment</I>
599 
and <I>var_param_alignment</I>.
600 
<P>
601 
The parameter of a <CODE>POINTER</CODE> will not consist entirely
602 
of <CODE>BITFIELD_VARIETY</CODE>s.
603 
<P>
604 
The implication of this is that the <CODE>ALIGNMENT</CODE> of all
605 
procedures is the same, the <CODE>ALIGNMENT</CODE> of all
606 
<CODE>POINTER</CODE>s is the same and the <CODE>ALIGNMENT</CODE> of
607 
all
608 
<CODE>OFFSET</CODE>s is the same.
609 
<P>
610 
At present this corresponds to the state of affairs for all machines.
611 
But it is certainly possible that, for example, 64-bit pointers might
612 
be aligned on 64-bit boundaries while 32-bit pointers are aligned
613 
on 32-bit boundaries. In this case it will become necessary to add
614 
different kinds of pointer to TDF. This will not present a problem,
615 
because, to use such pointers, similar changes will have to be made
616 
in languages to distinguish the kinds of pointer if they are to be
617 
mixed.
618 
<P>
619 
The difference between two <CODE>POINTER</CODE>s is measured by an
620 
<CODE>OFFSET</CODE>. Hence an <CODE>OFFSET</CODE> is parameterised
621 
by two <CODE>ALIGNMENT</CODE>s, that of the starting <CODE>POINTER</CODE>
622 
and that of the end <CODE>POINTER</CODE>. The <CODE>ALIGNMENT</CODE>
623 
set of the first must include the <CODE>ALIGNMENT</CODE> set of the
624 
second.
625 
<P>
626 
The parameters of an <CODE>OFFSET</CODE> may consist entirely of
627 
<CODE>BITFIELD_VARIETY</CODE>s.
628 
<P>
629 
The operations on <CODE>OFFSET</CODE>s are subject to various constraints
630 
on <CODE>ALIGNMENT</CODE>s. It is important not to read into offset
631 
arithmetic what is not there. Accordingly some rules of the algebra
632 
of <CODE>OFFSET</CODE>s are given below.
633 
<UL>
634 
<LI><I>offset_add</I> is associative.<P>
635 
<LI><I>offset_mult</I> corresponds to repeated offset_addition.<P>
636 
<LI><I>offset_max</I> is commutative, associative and idempotent.<P>
637 
<LI><I>offset_add</I> distributes over <I>offset_max</I> where they
638 
form legal expressions.<P>
639 
<LI><I>offset_test</I>(<I>prob</I>, &gt;= , <I>a</I>, <I>b</I>) continues
640 
if <I>offset_max</I>(<I>a</I>,<I>b</I>) = <I>a</I>.<P>
641 
</UL>
642 
<P>
643 
<A NAME=S396>
644 
<H3>7.13.1. Simple model</H3>
645 
<A NAME=M30>An example of the representation of <CODE>OFFSET</CODE>
646 
arithmetic is given below. This is not a definition, but only an example.
647 
In order to make this clear a machine with bit addressing is hypothesized.
648 
This machine is referred to as the simple model.
649 
<P>
650 
In this machine <CODE>ALIGNMENT</CODE>s will be represented by the
651 
number by which the bit address of data must be divisible. For example,
652 
8-bit bytes might have an <CODE>ALIGNMENT</CODE> of 8, longs of 32
653 
and doubles of 64. <CODE>OFFSET</CODE>s will be represented by the
654 
displacement in bits from a <CODE>POINTER</CODE>. <CODE>POINTER</CODE>s
655 
will be represented by the bit address of the data. Only one memory
656 
space will exist. Then in this example a possible conforming implementation
657 
would be as follows.
658 
<UL>
659 
<LI><I>add_to_ptr</I> is addition.<P>
660 
<LI><I>offset_add</I> is addition.<P>
661 
<LI><I>offset_div</I> and <I>offset_div_by_int</I> are exact division.<P>
662 
<LI><I>offset_max</I> is maximum.<P>
663 
<LI><I>offset_mult</I> is multiply.<P>
664 
<LI><I>offset_negate</I> is negate.<P>
665 
<LI><I>offset_pad</I>(<I>a</I>, <I>x</I>) is ((<I>x</I> + <I>a</I>
666 
- 1) / <I>a</I>) * <I>a</I><P>
667 
<LI><I>offset_subtract</I> is subtract.<P>
668 
<LI><I>offset_test</I> is <I>integer_test</I>.<P>
669 
<LI><I>offset_zero</I> is 0.<P>
670 
<LI><I>shape_offset</I>(<I>s</I>) is the minimum number of bits needed
671 
to be moved to move a value of <CODE>SHAPE</CODE> <I>s</I>.
672 
</UL>
673 
<P>
674 
Note that these operations only exist where the constraints on the
675 
parameters are satisfied. Elsewhere the operations are undefined.
676 
<P>
677 
All the computations in this representation are obvious, but there
678 
is one point to make concerning <I>offset_max</I>, which has the following
679 
arguments and result.
680 
<P>
681 
<PRE>
682 
	<I>arg1</I>:		EXP OFFSET(<I>x</I>, <I>y</I>)
683 
	<I>arg2</I>:		EXP OFFSET(<I>z</I>, <I>y</I>)
684 
		   -&gt; EXP OFFSET(<I>unite_alignments</I>(<I>x</I>, <I>z</I>), <I>y</I>)
685 
</PRE>
686 
The <CODE>SHAPE</CODE>s could have been chosen to be:<P>
687 
<PRE>
688 
	<I>arg1</I>:		EXP OFFSET(<I>x</I>, <I>y</I>)
689 
	<I>arg2</I>:		EXP OFFSET(<I>z</I>, <I>t</I>)
690 
		   -&gt; EXP OFFSET(<I>unite_alignments</I>(<I>x</I>, <I>z</I>),
691 
				 <I>intersect_alignments</I>(<I>y</I>, <I>t</I>))
692 
</PRE>
693 
where <I>unite_alignments</I> is set union and
694 
<I>intersect_alignments</I> is set intersection. This would have expressed
695 
the most general reality.  The representation of
696 
<I>unite_alignments</I>(<I>x</I>, <I>z</I>) is the maximum of the
697 
representations of <I>x</I> and <I>z</I> in the simple model. Unfortunately
698 
the representation of
699 
<I>intersect_alignments</I>(<I>y</I>, <I>t</I>) is not the minimum
700 
of the representations of <I>y</I> and <I>t</I>. In other words the
701 
simple model representation is not a homomorphism if
702 
<I>intersect_alignments</I> is used. Because the choice of representation
703 
in the installer is an important consideration the actual definition
704 
was chosen instead. It seems unlikely that this will affect practical
705 
programs significantly.
706 
<P>
707 
<A NAME=S397>
708 
<H3>7.13.2. <A NAME=31>Comparison of pointers and offsets</H3>
709 
Two <CODE>POINTER</CODE>s to the same <CODE>ALIGNMENT</CODE>, <I>a</I>,
710 
are equal if and only if the result of <I>subtract_ptrs</I> applied
711 
to them is equal to <I>offset_zero</I>(<I>a</I>).
712 
<P>
713 
The comparison of <CODE>OFFSET</CODE>s is reduced to the definition
714 
of <I>offset_max</I> and the equality of <CODE>OFFSET</CODE>s by the
715 
note in <A HREF="spec8.html#M172">offset_test</A>.
716 
<P>
717 
<A NAME=S398>
718 
<H3>7.13.3. <A NAME=32>Circular types in languages</H3>
719 
<A NAME=M33>It is assumed that circular types in programming languages
720 
will always involve the <CODE>SHAPE</CODE>s <CODE>PROC</CODE>
721 
or <CODE>POINTER</CODE>(<I>x</I>) on the circular path in their TDF
722 
representation. Since the <CODE>ALIGNMENT</CODE> of <CODE>POINTER</CODE>
723 
is {<I>pointer</I>} and does not involve the <CODE>ALIGNMENT</CODE>
724 
of the thing pointed at, circular <CODE>SHAPE</CODE>s are not needed.
725 
The circularity is always broken in <CODE>ALIGNMENT</CODE> (or
726 
<CODE>PROC</CODE>).
727 
<P>
728 
<A NAME=S399>
729 
<H3>7.13.4. <A NAME=34>Special alignments</H3>
730 
<A NAME=M35><A NAME=M36><A NAME=M37>
731 
<A NAME=M38>There are seven special <CODE>ALIGNMENT</CODE>s. One of
732 
these is <I>code_alignment</I>, the <CODE>ALIGNMENT</CODE> of the
733 
<CODE>POINTER</CODE> delivered by <I>make_local_lv</I>.
734 
<P>
735 
The <CODE>ALIGNMENT</CODE> of a parameter of <CODE>SHAPE</CODE> <I>s</I>
736 
is given by <I>parameter_alignment</I>(<I>s</I>) which will always
737 
contain
738 
<I>alignment</I>(<I>s</I>).
739 
<P>
740 
The other five special <CODE>ALIGNMENT</CODE>s are <I>alloca_alignment</I>,
741 
<I>callees_alignment, callers_alignment, locals_alignment</I> and
742 
<I>var_param_alignment</I>. Each of these contains the set union of
743 
all the <CODE>ALIGNMENT</CODE>s which can be produced by <I>alignment</I>
744 
from any <CODE>SHAPE</CODE>. But they need not be equal to that set
745 
union, nor need there be any relation between them.
746 
<P>
747 
In particular they are not equal (in the sense of <A HREF="#15">Equality
748 
of <CODE>ALIGNMENT</CODE>s</A>).
749 
<P>
750 
Each of these five refer to alignments of various components of a
751 
frame.
752 
<P>
753 
Notice that pointers and offsets such as
754 
<CODE>POINTER</CODE>(<I>callees_alignment</I>(true)) and
755 
<CODE>OFFSET</CODE>(<I>callees_alignment</I>(true), <I>x</I>) etc.
756 
can have some special representation and that <I>add_to_ptr</I> and
757 
<I>offset_add</I> can operate correctly on these representations.
758 
However it is necessary that
759 
<PRE>
760 
	<I>alignment</I>(POINTER(<I>A</I>))={<I>pointer</I>}
761 
</PRE>
762 
for any <CODE>ALIGNMENT</CODE> <I>A</I>.<P>
763 
<A NAME=S400>
764 
<H3>7.13.5. Atomic assignment</H3>
765 
<A NAME=M39><A NAME=M40>At least one <CODE>VARIETY</CODE>
766 
shall exist such that <I>assign</I> and <I>assign_with_mode</I> are
767 
atomic operations. This <CODE>VARIETY</CODE> shall be specified as
768 
part of the installer specification. It shall be capable of representing
769 
the numbers 0 to 127.
770 
<P>
771 
<I>Note that it is not necessary for this to be the same
772 
<CODE>VARIETY</CODE> on each machine. Normal practice will be to use
773 
a
774 
<CODE>TOKEN</CODE> for this <CODE>VARIETY</CODE> and choose the definition
775 
of the <CODE>TOKEN</CODE> on the target machine.</I>
776 
<P>
777 
<A NAME=S401>
778 
 
779 
<HR>
780 
<H2>7.14. <A NAME=41>Order of evaluation</H2>
781 
<A NAME=M42><A NAME=M43>The order of evaluation is specified in certain
782 
constructions in terms of equivalent effect with a canonical order
783 
of evaluation. These constructions are
784 
<I>conditional</I>, <I>identify</I>, <I>labelled</I>, <I>repeat</I>,
785 
<I>sequence</I> and <I>variable</I>.  Let these be called the order-specifying
786 
constructions.
787 
<P>
788 
The constructions which change control also specify a canonical order.
789 
These are <I>apply_proc</I>, <I>apply_general_proc</I>, <I>case</I>,
790 
<I>goto</I>, <I>goto_local_lv</I>, <I>long_jump</I>, <I>return</I>,
791 
u<I>ntidy_return, return_to_label, tail_call,</I> the <I>test</I>
792 
constructions and all instructions containing the <I>error_jump</I>
793 
and <I>trap</I> <CODE>ERROR_TREATMENT</CODE>s.
794 
<P>
795 
The order of evaluation of the components of other constructions is
796 
as follows. The components may be evaluated in any order and with
797 
their components - down to the TDF leaf level - interleaved in any
798 
order. The constituents of the order specifying constructions may
799 
also be interleaved in any order, but the order of the operations
800 
within an order specifying operation shall be equivalent in effect
801 
to a canonical order.
802 
<P>
803 
Note that the rule specifying when error_jumps or traps are to be
804 
taken (<A HREF="spec8.html#M68"><I>error_jump</I></A>) relaxes the
805 
strict rule that everything has to be &quot;as if&quot; completed
806 
by the end of certain constructions. Without this rule pipelines would
807 
have to stop at such points, in order to be sure of processing any
808 
errors. Since this is not normally needed, it would be an expensive
809 
requirement. Hence this rule. However a construction will be required
810 
to force errors to be processed in the cases where this is important.
811 
<P>
812 
<A NAME=S402>
813 
 
814 
<HR>
815 
<H2>7.15. <A NAME=44>Original pointers</H2>
816 
<A NAME=M45><A NAME=M46>Certain constructions are specified as producing
817 
original pointers. They allocate space to hold values and produce
818 
pointers indicating that new space. All other pointer values are derived
819 
pointers, which are produced from original pointers by a sequence
820 
of <I>add_to_ptr</I> operations. Counting original pointers as being
821 
derived from themselves, every pointer is derived from just one original
822 
pointer.
823 
<P>
824 
A null pointer is counted as an original pointer.
825 
<P>
826 
<A NAME=M47>If procedures are called which come from outside the TDF
827 
world (such as <I>calloc</I>) it is part of their interface with TDF
828 
to state if they produce original pointers, and what is the lifetime
829 
of the pointer.
830 
<P>
831 
As a special case, original pointers can be produced by using <I>current_env</I>
832 
and <I>env_offset</I> (see <A HREF="spec8.html#M101"><I>current_env</I></A>).
833 
<P>
834 
Note that:
835 
<PRE>
836 
	<I>add_to_ptr(p, offset_add(q, r))</I>
837 
</PRE>
838 
is equivalent to:
839 
<PRE>
840 
	<I>add_to_ptr(add_to_ptr(p, q), r)</I>
841 
</PRE>
842 
In the case that <I>p</I> is the result of <I>current_env</I> and
843 
<I>q</I> is the result of <I>env_offset</I>:
844 
<PRE>
845 
	<I>add_to_ptr(p, q)</I>
846 
</PRE>
847 
is defined to be an original pointer. For any such expression <I>q</I>
848 
will be produced by <I>env_offset</I> applied to a <CODE>TAG</CODE>
849 
introduced in the procedure in which <I>current_env</I> was used to
850 
make <I>p</I>.
851 
<P>
852 
<A NAME=S403>
853 
 
854 
<HR>
855 
<H2>7.16. <A NAME=48>Overlapping</H2>
856 
<A NAME=M49>In the case of <I>move_some</I>, or <I>assign</I>
857 
or <I>assign_with_mode</I> in which <I>arg2</I> is a <I>contents</I>
858 
or <I>contents_with_mode</I>, it is possible that the source and destination
859 
of the transfer might overlap.
860 
<P>
861 
In this case, if the operation is <I>move_some</I> or
862 
<I>assign_with_mode</I> and the <CODE>TRANSFER_MODE</CODE> contains
863 
<I>overlap</I>, then the transfer shall be performed correctly, that
864 
is, as if the data were copied from the source to an independent place
865 
and then to the destination.
866 
<P>
867 
In all cases, if the source and destination do not overlap the transfer
868 
shall be performed correctly.
869 
<P>
870 
Otherwise the effect is undefined.
871 
<P>
872 
<A NAME=S404>
873 
 
874 
<HR>
875 
<H2>7.17. <A NAME=50>Incomplete assignment</H2>
876 
If the <I>arg2</I> component of an <I>assign</I> or <I>assign_with_mode</I>
877 
operation is left by means of a jump, the question arises as to what
878 
value is in the destination of the transfer.
879 
<P>
880 
If the <CODE>TRANSFER_MODE</CODE> <I>complete</I> is used, the destination
881 
shall be left unchanged if the <I>arg2</I> component is left by means
882 
of a jump. If <I>complete</I> is not used and <I>arg2</I> is left
883 
by a jump, the destination may be affected in any way.
884 
<P>
885 
<A NAME=S405>
886 
 
887 
<HR>
888 
<H2>7.18. <A NAME=51>Representing integers</H2>
889 
<A NAME=M52><A NAME=M53>Integer <CODE>VARIETY</CODE>s shall be represented
890 
by a range of integers which includes those specified by the given
891 
bounds. This representation shall be twos-complement.
892 
<P>
893 
If the lower bound of the <CODE>VARIETY</CODE> is non-negative, the
894 
representing range shall be from 0 to 2<SUP><I>8n</I></SUP>-1 for
895 
some
896 
<I>n</I>.
897 
<I>n</I> is called the number of bytes in the representation. The
898 
number of bits in the representation is 8<I>n</I>.
899 
<P>
900 
If the lower bound of the <CODE>VARIETY</CODE> is negative the representing
901 
range shall be from -2<SUP><I>8n-1</I></SUP> to 2<SUP><I>8n-1</I></SUP>-1
902 
for some <I>n</I>.
903 
<I>n</I> is called the number of bytes in the representation. The
904 
number of bits in the representation is 8<I>n</I><P>
905 
Installers may limit the size of <CODE>VARIETY</CODE> that they implement.
906 
A statement of such limits shall be part of the specification of the
907 
installer. In no case may such limits be less than 64 bits, signed
908 
or unsigned.
909 
<P>
910 
<I>It is intended that there should be no upper limit allowed at some
911 
future date.</I>
912 
<P>
913 
Operations are performed in the representing <CODE>VARIETY</CODE>.
914 
If the result of an operation does not lie within the bounds of the
915 
stated
916 
<CODE>VARIETY</CODE>, but does lie in the representation, the value
917 
produced in that representation shall be as if the <CODE>VARIETY</CODE>
918 
had the lower and upper bounds of the representation. The implication
919 
of this is usually that a number in a <CODE>VARIETY</CODE> is represented
920 
by that same number in the representation.
921 
<P>
922 
If the bounds of a <CODE>VARIETY</CODE>, <I>v</I>, include those of
923 
a
924 
<CODE>VARIETY</CODE>, <I>w</I>, the representing <CODE>VARIETY</CODE>
925 
for <I>v</I> shall include or be equal to the representing
926 
<CODE>VARIETY</CODE> for <I>w</I>.
927 
<P>
928 
The representations of two <CODE>VARIETY</CODE>s of the form
929 
<I>var_limits</I>(0, 2<SUP><I>n</I></SUP>-1) and
930 
<I>var_limits</I>(-2<SUP><I>n-1</I></SUP>, 2<SUP><I>n-1</I></SUP>-1)
931 
shall have the same number of bits and the mapping of their
932 
<CODE>ALIGNMENT</CODE>s into the target alignment shall be the same.
933 
<P>
934 
<A NAME=S406>
935 
 
936 
<HR>
937 
<H2>7.19. <A NAME=54>Overflow and Integers</H2>
938 
<A NAME=M55><A NAME=M56>It is necessary first to define what overflow
939 
means for integer operations and second to specify what happens when
940 
it occurs. The intention of TDF is to permit the simplest possible
941 
implementation of common constructions on all common machines while
942 
allowing precise effects to be achieved, if necessary at extra cost.
943 
<P>
944 
Integer varieties may be represented in the computer by a range of
945 
integers which includes the bounds given for the variety. An arithmetic
946 
operation may therefore yield a result which is within the stated
947 
variety, or outside the stated variety but inside the range of representing
948 
values, or outside that range. Most machines provide instructions
949 
to detect the latter case; testing for the second case is possible
950 
but a little more costly.
951 
<P>
952 
In the first two cases the result is defined to be the value in the
953 
representation. Overflow occurs only in the third case.
954 
<P>
955 
If the <CODE>ERROR_TREATMENT</CODE> is <I>impossible</I> overflow
956 
will not occur. If it should happen to do so the effect of the operation
957 
is undefined.
958 
<P>
959 
If the <CODE>ERROR_TREATMENT</CODE> is <I>error_jump</I> a
960 
<CODE>LABEL</CODE> is provided to jump to if overflow occurs.
961 
<P>
962 
If the <CODE>ERROR_TREATMENT</CODE> is <I>trap(overflow),</I> a producer-defined
963 
<CODE>TOKEN</CODE> <I>~Throw</I>: <CODE>NAT</CODE>
964 
-&gt; <CODE>EXP</CODE> must be provided.  On an overflow, the installer
965 
will arrange that <I>~Throw</I>(<I>error_val</I>(<I>overflow</I>))
966 
is evaluated.
967 
<P>
968 
The <I>wrap</I> <CODE>ERROR_TREATMENT</CODE> is provided so that a
969 
useful defined result may be produced in certain cases where it is
970 
usually easily available on most machines. This result is available
971 
on the assumption that machines use binary arithmetic for integers.
972 
This is certainly so at present, and there is no close prospect of
973 
other bases being used.
974 
<P>
975 
If a precise result is required further arithmetic and testing may
976 
be needed which the installer may be able to optimise away if the
977 
word lengths happen to suit the problem. In extreme cases it may be
978 
necessary to use a larger variety.
979 
<P>
980 
<A NAME=S407>
981 
 
982 
<HR>
983 
<H2>7.20. <A NAME=57>Representing floating point</H2>
984 
<A NAME=M58><A NAME=M59><CODE>FLOATING_VARIETY</CODE>s shall be implemented
985 
by a representation which has at least the properties specified.
986 
<P>
987 
Installers may limit the size of <CODE>FLOATING_VARIETY</CODE> which
988 
they implement. A statement of such limits shall be part of the specification
989 
of an installer.
990 
<P>
991 
The limit may also permit or exclude infinities.
992 
<P>
993 
Any installer shall implement at least one <CODE>FLOATING_VARIETY</CODE>
994 
with the following properties (c.f. IEEE doubles):
995 
<UL>
996 
<LI><I>mantissa_digs</I> shall not be less than 53.
997 
<LI><I>min_exponent</I> shall not be less than 1023.
998 
<LI><I>max_exponent</I> shall not be less than 1022.
999 
</UL>
1000 
Operations are performed and overflows detected in the representing
1001 
<CODE>FLOATING_VARIETY</CODE>.
1002 
<P>
1003 
There shall be at least two <CODE>FLOATING_VARIETY</CODE>s, one occupying
1004 
the same number of bytes and having the same alignment as a
1005 
<CODE>VARIETY</CODE> representation, and one occupying twice as many
1006 
bytes.
1007 
<P>
1008 
<A NAME=S408>
1009 
 
1010 
<HR>
1011 
<H2>7.21. <A NAME=60>Floating point errors</H2>
1012 
<A NAME=M61><A NAME=M62>The only permitted
1013 
<CODE>ERROR_TREATMENT</CODE>s for operations delivering
1014 
<CODE>FLOATING_VARIETY</CODE>s are <I>impossible, error_jump</I> and
1015 
<I>trap</I> (overflow).
1016 
<P>
1017 
The kinds of floating point error which can occur depend on the machine
1018 
architecture (especially whether it has IEEE floating point) and on
1019 
the definitions in the ABI being obeyed.
1020 
<P>
1021 
Possible floating point errors depend on the state of the machine
1022 
and may include overflow, divide by zero, underflow, invalid operation
1023 
and inexact. The setting of this state is performed outside TDF (at
1024 
present).
1025 
<P>
1026 
If an <I>error_jump</I> or <I>trap</I> is taken as the result of a
1027 
floating point error the operations to test what kind of error it
1028 
was are outside the TDF definition (at present).
1029 
<P>
1030 
<A NAME=S409>
1031 
 
1032 
<HR>
1033 
<H2>7.22. Rounding and floating point</H2>
1034 
<A NAME=M63>Each machine has a rounding state which shall be one of
1035 
<I>to_nearest</I>, <I>toward_larger</I>, <I>toward_smaller</I>,
1036 
<I>toward_zero</I>. For each operation delivering a
1037 
<CODE>FLOATING_VARIETY</CODE>, except for <I>make_floating</I>, any
1038 
rounding necessary shall be performed according to the rounding state.
1039 
<P>
1040 
<A NAME=S410>
1041 
 
1042 
<HR>
1043 
<H2>7.23. <A NAME=64>Floating point accuracy</H2>
1044 
While it is understood that most implementations will use IEEE floating
1045 
arithmetic operations, there are machines which use other formats
1046 
and operations. It is intended that they should not be excluded from
1047 
having TDF implementations.
1048 
<P>
1049 
For TDF to have reasonably consistent semantics across many platforms,
1050 
one must have some <I>minimum</I> requirements on the accuracies of
1051 
the results of the floating point operations defined in TDF. The provisional
1052 
requirements sketched below would certainly be satisfied by an IEEE
1053 
implementation.
1054 
<P>
1055 
Let <I>@</I>  be some primitive dyadic arithmetic operator and <I>@'</I>
1056 
be its TDF floating-point implementation. Let <I>F</I> be some non-complex
1057 
<CODE>FLOATING_VARIETY</CODE> and <I>F'</I> be a representational
1058 
variety of <I>F</I>.
1059 
<P>
1060 
<B>Condition 1</B>:<P>
1061 
If <I>a</I>, <I>b</I> and <I>a @ b</I> can all be represented exactly
1062 
in <I>F</I>, then they will also be represented exactly in <I>F'</I>.
1063 
Extending the '-notation in the obvious manner:
1064 
<PRE>
1065 
	<I>(a @ b)' = (a' @' b')</I>
1066 
</PRE>
1067 
This equality will also hold using the TDF equality test, i.e.:
1068 
<PRE>
1069 
	<I>(a @ b)' =' (a' @' b')</I>
1070 
</PRE>
1071 
<P>
1072 
<B>Condition 2</B>:<P>
1073 
The operator <I>@'</I> is monotonic in the sense apposite to the operator
1074 
<I>@</I>. For example, consider the operator +; if <I>x</I> is any
1075 
number and
1076 
<I>a</I> and <I>b</I> are as above:
1077 
<PRE>
1078 
	<I>(x &gt; b) =&gt; ((a' +' x') &gt;=  (a + b)')</I>
1079 
</PRE>
1080 
and:
1081 
<PRE>
1082 
	<I>(x &lt; b) =&gt;  ((a' +' x') &lt;= (a + b)')</I>
1083 
</PRE>
1084 
and so on, reflecting the weakening of the ordering after the operation
1085 
from &gt; to &gt;=  and &lt; to &lt;=.  Once again, the inequalities
1086 
will hold for their TDF equivalents e.g., &gt;=' and &gt;'.
1087 
<P>
1088 
Similar conditions can be expressed for the monadic operations.
1089 
<P>
1090 
For the floating-point test operation, there are obvious analogues
1091 
to both conditions. The weakening of the ordering in the monotonicity
1092 
condition, however, may lead to surprising results, arising mainly
1093 
from the uncertainty of the result of equality between floating numbers
1094 
which cannot be represented exactly in <I>F</I>.
1095 
<P>
1096 
Accuracy requirements for complex <CODE>FLOATING_VARIETY</CODE>s could
1097 
follow directly by considering the above conditions applied to real
1098 
and imaginary parts independently. The following proviso is added
1099 
for some complex operations however, to allow for possible intermediate
1100 
error conditions.  With <I>floating_div</I>, <I>floating_mult</I>
1101 
and
1102 
<I>floating_power</I> for complex <CODE>FLOATING_VARIETY</CODE>s,
1103 
errors are guaranteed not to occur only if the square of the modulus
1104 
of each argument is representable and the square of the modulus of
1105 
the result is representable. Whenever these additional constraints
1106 
are not met, the operation will either complete with the accuracy
1107 
conditions above applying, or it will complete according to the
1108 
<CODE>ERROR_TREATMENT</CODE> specified.
1109 
<P>
1110 
<A NAME=S411>
1111 
 
1112 
<HR>
1113 
<H2>7.24. <A NAME=66><A NAME=66>Representing bitfields</H2>
1114 
<A NAME=M67><CODE>BITFIELD_VARIETY</CODE>s specify a number of bits
1115 
and shall be represented by exactly that number of bits in twos-complement
1116 
notation. Producers may expect them to be packed as closely as possible.
1117 
<P>
1118 
Installers may limit the number of bits permitted in
1119 
<CODE>BITFIELD_VARIETY</CODE>s.  Such a limit shall be not less than
1120 
32 bits, signed or unsigned.
1121 
<P>
1122 
<I>It is intended that there should be no upper limit allowed at some
1123 
future date.</I>
1124 
<P>
1125 
Some offsets of which the second parameter contains a <CODE>BITFIELD</CODE>
1126 
alignment are subject to a constraint defined below. This constraint
1127 
is referred to as <I>variety_enclosed.</I><P>
1128 
The intent of this constraint is to force <CODE>BITFIELD</CODE>s to
1129 
be implemented (in memory) as being included in some properly aligned
1130 
<CODE>VARIETY</CODE> value.  The constraint applies to:
1131 
<PRE>
1132 
	<I>x</I>: <I>offset</I>(<I>p</I>, <I>b</I>)
1133 
</PRE>
1134 
and to:
1135 
<PRE>
1136 
	<I>sh = bitfield</I>(<I>bfvar_bits(s, n)</I>)
1137 
</PRE>
1138 
where  <I>alignment(sh)</I> is included in <I>b</I>. The constraint
1139 
is as follows:<P>
1140 
There will exist a <CODE>VARIETY</CODE>, <I>v</I>, and
1141 
<I>r</I>: <I>offset</I>(<I>p</I>, <I>q</I>) where <I>v</I> is in <I>q</I>.
1142 
<PRE>
1143 
	<I>offset_pad</I>(<I>b, r</I>) &lt;= <I>x</I>
1144 
</PRE>
1145 
and:
1146 
<PRE>
1147 
	<I>offset_pad</I>(<I>b, r</I> + <I>sz</I>(<I>v</I>)) &gt;= <I>offset_pad</I>( <I>b</I>, <I>x</I> + <I>sz</I>(<I>sh</I>))
1148 
</PRE>
1149 
where the comparisons are in the sense of <I>offset_test</I>, + is
1150 
<I>offset_add</I> and <I>sz</I> is <I>shape_offset</I>.
1151 
<P>
1152 
<A NAME=S412>
1153 
 
1154 
<HR>
1155 
<H2>7.25. <A NAME=68>Permitted limits</H2>
1156 
<A NAME=69>An installer may specify limits on the sizes of some of
1157 
the data <CODE>SHAPE</CODE>s which it implements. In each case there
1158 
is a minimum set of limits such that all installers shall implement
1159 
at least the specified <CODE>SHAPE</CODE>s. Part of the description
1160 
of an installer shall be the limits it imposes. Installers are encouraged
1161 
not to impose limits if possible, though it is not expected that this
1162 
will be feasible for floating point numbers.
1163 
<P>
1164 
<A NAME=S413>
1165 
 
1166 
<HR>
1167 
<H2>7.26. <A NAME=70>Least Upper Bound</H2>
1168 
<A NAME=71>The LUB of two <CODE>SHAPE</CODE>s, <I>a</I> and <I>b</I>
1169 
is defined as follows:
1170 
<UL>
1171 
<LI>If <I>a</I> and <I>b</I> are equal shapes, then <I>a</I>.
1172 
<LI>If <I>a</I> is <CODE>BOTTOM</CODE> then <I>b</I>.
1173 
<LI>If <I>b</I> is <CODE>BOTTOM</CODE> then <I>a</I>.
1174 
<LI>Otherwise <CODE>TOP</CODE>.
1175 
</UL>
1176 
<P>
1177 
<A NAME=S414>
1178 
 
1179 
<HR>
1180 
<H2>7.27. Read-only areas</H2>
1181 
Consider three scenarios in increasingly static order:
1182 
<UL>
1183 
<LI>Dynamic loading. A new module is loaded, initialising procedures
1184 
are obeyed and the results of these are then marked as read-only.<P>
1185 
<LI>Normal loading. An <I>ld</I> program is obeyed which produces
1186 
various (possibly circular) structures which are put into an area
1187 
which will be read-only when the program is obeyed.<P>
1188 
<LI>Using ROM. Data structures are created (again possibly circular)
1189 
and burnt into ROM for use by a separate program.
1190 
</UL>
1191 
In each case program is obeyed to create a structure, which is then
1192 
frozen. The special case when the data is, say, just a string is not
1193 
sufficiently general.
1194 
<P>
1195 
This TDF specification takes the attitude that the use of read-only
1196 
areas is a property of how TDF is used - a part of the installation
1197 
process - and there should not be TDF constructions to say that some
1198 
values in a <CODE>CAPSULE</CODE> are read-only. Such constructions
1199 
could not be sufficiently general.
1200 
<P>
1201 
<A NAME=S415>
1202 
 
1203 
<HR>
1204 
<H2>7.28. <A NAME=72>Tag and Token signatures</H2>
1205 
In a TDF program there will usually be references to <CODE>TAG</CODE>s
1206 
which are not defined in TDF; their definitions are intended to be
1207 
supplied by a host system in system specific libraries.
1208 
<P>
1209 
These <CODE>TAG</CODE>s will be declared (but not defined) in a TDF
1210 
<CODE>CAPSULE</CODE> and will be specified by external linkages of
1211 
the
1212 
<CODE>CAPSULE</CODE> with <CODE>EXTERNAL</CODE>s containg either
1213 
<CODE>TDFIDENT</CODE>s or <CODE>UNIQUE</CODE>s. In previous versions
1214 
of TDF, the external names required by system linking could only be
1215 
derived from those <CODE>EXTERNAL</CODE>s.
1216 
<P>
1217 
Version 4.0 gives an alternative method of constructing extra-TDF
1218 
names. Each global <CODE>TAG</CODE> declaration can now contain a
1219 
<CODE>STRING</CODE> signature field which may be used to derive the
1220 
external name required by the system.
1221 
<P>
1222 
This addition is principally motivated by the various &quot;name mangling&quot;
1223 
schemes of C++. The <CODE>STRING</CODE> signature can be constructed
1224 
by concatenations and token expansions. Suitable usages of
1225 
<CODE>TOKEN</CODE>s can ensure that the particular form of name-mangling
1226 
can be deferred to installation time and hence allow, at least conceptually,
1227 
linking with different C++ libraries.
1228 
<P>
1229 
As well as <CODE>TAG</CODE> declarations, <CODE>TAG</CODE> definitions
1230 
are allowed to have signatures.  The restriction that the signature
1231 
(if present) of a <CODE>TAG</CODE> definition being identical to its
1232 
corresponding definition could allow type checking across seperately
1233 
compiled <CODE>CAPSULE</CODE>s.
1234 
<P>
1235 
Similar considerations apply to <CODE>TOKEN</CODE>s; although token
1236 
names are totally internal to TDF, it would allow one to check that
1237 
a token declared in one <CODE>CAPSULE</CODE> has the same &quot;type&quot;
1238 
as its definition in another.
1239 
<P>
1240 
<P>
1241 
<A NAME=S416>
1242 
 
1243 
<HR>
1244 
<H2>7.29. <A NAME=73>Dynamic initialisation</H2>
1245 
The dynamic initialisation of global variables is required for languages
1246 
like C++. Previous to version 4.0, the only initialisations permissable
1247 
were load-time ones; in particular no procedure calls were allowed
1248 
in forming the initialising value. Version 4.0 introduces the constructor
1249 
<I>initial_value</I> to remedy this situation.
1250 
<P>
1251 
Several different implementation strategies could be considered for
1252 
this. Basically, one must ensure that all the initial_value expressions
1253 
are transformed into assignments to globals in some procedure. One
1254 
might expect that there would be one such procedure invented for each
1255 
<CODE>CAPSULE</CODE> and that somehow this procedure is called before
1256 
the main program.
1257 
<P>
1258 
This raises problems on how we can name this procedure so that it
1259 
can be identified as being a special initialising procedure. Some
1260 
UNIX linkers reserve a name like <I>__init</I> specially so that all
1261 
instances of it from different modules can be called before the main
1262 
procedure. Other cases may require a pre-pass on the <I>.o</I> files
1263 
prior to system linking.
1264 
<P>
1265 
<HR>
1266 
<P><I>Part of the <A HREF="../index.html">TenDRA Web</A>.<BR>Crown
1267 
Copyright &copy; 1998.</I></P>
1268 
</BODY>
1269 
</HTML>