A generic version of the algorithm for simplification--applicable
to most of the expressions in the language--is given in Figure
A.5. The algorithm is written as a recursive
function, *simplify*. The main input to this function is an
expression term , which is modified by the function.
Along with the modified version of , the *simplify* function
outputs a sequence of statements,
*INITS*, which declares and initializes any temporaries that
were introduced in the simplification of . It also outputs
``access sets'' for and `INITS`.

The algorithm traverses sub-expressions in *right to left* order.
If a sub-expression must be precomputed, the associated code will have
to be moved in front of sibling sub-expressions currently to its left.
If there are no dependencies between the moved sub-expression and its
left siblings, this is fine. But if there is a dependency, the sibling
expression must also be precomputed, to preserve the original order
of evaluation.

Dependencies are detected using *access sets*. These record uses
and definitions of individual variables, or categories of variables, within
expressions. The *simplify* function computes these access sets on
the fly and returns two of them in the values *ACCESS* and
*INIT_ACCESS*. The set *ACCESS* is the set of program variable
accesses in the translated expression . The set *INIT_ACCESS*
is the set of program variable accesses in the ``precomputation''
code--code for initialization of temporaries defined in *INITS*
(both sets exclude accesses to temporaries themselves).

At the time a subexpression is visited, the variable *INIT_ACCESS*
holds accesses in ``precomputation'' code already generated by
subexpressions *to the right* of the current expression. If a
dependency is discovered between the translated version of the *current* expression and the code we already know must move ``to
the left'', the whole of the current expression must also ``move to
the left'', to be precomputed before the code already scheduled to move.

Multiply referenced values and composite expressions are handled in different parts of the algorithm, but currently they are a treated in exactly the same way.