12.1. Transformations as definitions

As well being a vehicle for expressing optimisation, TDF transformations can be used as the basis for defining TDF. In principle, if we were to define all of the allowable transformations of the TDF constructions, we would have a complete definition of TDF as the initial model of the TDF algebra. This would be a fairly impracticable project, since the totality of the rules including all the simple constructs would be very unwieldy, difficult to check for inconsistencies and would not add much illumination to the definition. However, knowledge of allowable transformations of TDF can often answer questions of the meaning of diverse constructs by relating them to a single construct. What follows is an alphabet of generic transformations which can often help to answer knotty questions. Here, E[X \ Y] denotes an EXP E with all internal occurrences of X replaced by Y.

If F is any non order-specifying ^[i] EXP constructor and E is one of the EXP operands of F, then:

F(..., E, ...) xde identify(empty, newtag, E, F(..., obtain_tag(newtag), ...))

If E is a non side-effecting ^[j] EXP and none of the variables used in E are assigned to in B: identify(v, tag, E, B) xde B[obtain_tag(tag) \ E]

If all uses of tg in B are of the form contents(shape(E), obtain_tag(tg)):

variable(v, tg, E, B) xde identify(v, nt, E, B[contents(shape(E), obtain_tag(tg)) \ obtain_tag(nt)])
sequence((S1, ..., Sn),
         sequence((P1, ..., Pm), R) xdb
         sequence((S1, ..., Sn, P1, ..., Pm), R)

If S_i = sequence((P₁, ..., P_m), R):

sequence((S1, ..., Sn), T) xdb
         sequence((S1, ...,
                  Si-1, P1, ..., Pm, R,
                  Si+1, ..., Sn), T) E xdb sequence((), E)

If D is either identify or variable:

D(v, tag, sequence((S1, ..., Sn), R), B) xde
                   sequence((S1, ..., Sn), D(v, tag, R, B))

If S_i is an EXP BOTTOM, then:

sequence((S1, S2, ... Sn), R) xde
sequence((S1, ...  Si - 1), Si)

If E is an EXP BOTTOM, and if D is either identify or variable:

D(v, tag, E, B) xde E

If S_i is make_top(), then:

sequence((S1,
S2, ...  Sn), R) xdb
sequence((S1, ...  Si - 1,
Si + 1, ...Sn), R)

If S_n is an EXP TOP:

sequence((S1, ...
          Sn), make_top()) xdb sequence((S1, ...,
          Sn - 1), Sn)

If E is an EXP TOP and E is not side-effecting then:

E xde make_top()

If C is some non order-specifying and non side-effecting constructor, and S_i is C(P₁,..., P_m) where P_1..m are the EXP operands of C:

sequence((S1, ..., Sn), R) xde
sequence((S1, ..., Si - 1, P1,
          ..., Pm, Si + 1, ..., Sn), R)

If none of the S_i use the label L:

conditional(L,
            sequence((S1, ..., Sn), R), A) xde
            sequence((S1, ..., Sn), conditional(L, R, A))

If there are no uses of L in X: ^[k]

conditional(L, X, Y) xde X conditional(L, E, goto(Z)) xde E[L \ Z]

If EXP X contains no use of the LABEL L:

conditional(L, conditional(M, X, Y), Z) xde conditional(M, X, conditional(L, Y, Z))
repeat(L, I, E) xde sequence((I), repeat(L, make_top(), E))
repeat(L, make_top(), E) xde conditional(Z, E[L \ Z], repeat(L, make_top(), E))

If there are no uses of L in E:

repeat(L, make_top(), sequence((S, E), make_top())) xde
conditional(Z, S[L \ Z], repeat(L, make_top(), sequence((E, S), make_top())))

If f is a procedure defined ^[l] as:

make_proc(rshape, formal1 .. n, vtg,
          B(return R1, ..., return Rm))

where:

formali = make_tagshacc(si, vi, tgi)

and B is an EXP with all of its internal return constructors indicated parametrically then:

if Ai has SHAPE si apply_proc(rshape, f, (A1, ..., An), V) xde
variable(empty, newtag, make_value((rshape=BOTTOM) ?  TOP : rshape),
         labelled((L), variable(v1, tg1, A1, ...,
                  variable(vn, tgn, An,
                  variable(empty, vtg, V,
                  B(sequence(assign(obtain_tag(newtag), R1), goto(L)),
                    ...,
                    sequence(assign(obtain_tag(newtag), Rm), goto(L))))),
                  contents(rshape, obtain_tag(newtag))))
assign(E, make_top()) xde sequence((E), make_top())
contents(TOP, E) xde sequence((E), make_top())
make_value(TOP) xde make_top()
component(s, contents(COMPOUND(S), E), D) xde contents(s, add_to_ptr(E, D))
make_compound(S, ((E1, D1), ..., (En, Dn))) xde variable(empty, nt, make_value(COMPOUND(S)),
    sequence((assign(add_to_ptr(obtain_tag(nt), D1), E1), ...,
              assign(add_to_ptr(obtain_tag(nt), Dn), En)),
             contents(S, obtain_tag(nt))))

12.2. Examples of transformations

Any of these transformations may be performed by the TDF translators. The most important is probably {A} which allows one to reduce all of the EXP operands of suitable constructors to obtain_tags. The expansion rules for identification, {G}, {H} and {I}, gives definition to complicated operands as well as strangely formed ones, e.g. return(... return(X)...). Rule {A} also illustrates neatly the lack of ordering constraints on the evaluation of operands. For example, mult(et, exp1, exp2) could be expanded by applications of {A} to either:

identify(empty, t1, exp1, identify(empty, t2, exp2, mult(et, obtain_tag(t1), obtain_tag(t2))))

or:

identify(empty, t2, exp2, identify(empty, t1, exp1, mult(et, obtain_tag(t1), obtain_tag(t2))))

Both orderings of the evaluations of exp1 and exp2 are acceptable, regardless of any side-effects in them. There is no requirement that both expansions should produce the same answer for the multiplications; the only person who can say whether either result is "wrong" is the person who specified the program.

Many of these transformations often only come into play when some previous transformation reveals some otherwise hidden information. For example, after procedure in-lining given by {U} or loop un-rolling given by {S}, a translator can often deduce the behaviour of a _test constructor, replacing it by either a make_top or a goto. This may allow one to apply either {J} or {H} to eliminate dead code in sequences and in turn {N} or {P} to eliminate entire conditions and so on.

Application of transformations can also give expansions which are rather pathological in the sense that a producer is very unlikely to form them. For example, a procedure which returns no result would have result statements of the form return(make_top()). In-lining such a procedure by {U} would have a form like:

variable(empty, nt, make_shape(TOP),
         labelled((L),
         ... sequence((assign(obtain_tag(nt), make_top())),
goto(L)) ...
         contents(TOP, obtain_tag(nt))
         )
)

The rules {V}, {W} and {X} allow this to be replaced by:

variable(empty, nt, make_top(),
         labelled((L),
         ... sequence((obtain_tag(nt)), goto(L)) ...
         sequence((obtain_tag(nt)), make_top())
         )
)

The obtain_tags can be eliminated by rule {M} and then the sequences by {F}. Sucessive applications of {C} and {B} then give:

labelled((L),
         ... goto(L) ...
         make_top()
        )

12.3. Programs with undefined values

The definitions of most of the constructors in the TDF specification are predicated by some conditions; if these conditions are not met the effect and result of the constructor is not defined for all possible platforms. ^[m] Any value which is dependent on the effect or result of an undefined construction is also undefined. This is not the same as saying that a program is undefined if it can construct an undefined value - the dynamics of the program might be such that the offending construction is never obeyed.