RELFUN

The next transformation step takes all deterministic clauses totally apart: an internal representation, called , is created, in which variables are associated with expressions ( stands for environment because this data structure strongly resembles the sort of environments used for unification in PROLOG interpreters). The return value is represented by .

This structure is needed for several reasons:

• all arguments of subqueries have to be ground; this often requires reordering of premises
• unification has to be done at compile time (static unification), resulting in assignments and equality tests
• in LL, the arguments of a function have to be distinct variables and cannot be arbitrary terms as in PROLOG
• common subexpressions are (statically) unified, e.g. if X is f(Z) and Y is f(Z) occur in a clause, then X is unified with Y, e.g. by replacing Y by X everywhere in the clause (this is allowed because predicates with side effects and non-deterministic predicates are not considered)

For our example, looks like this:

Note that in a variable need not be associated with a unique expression, e.g. in 2a, X is associated with three and Y with two expressions. As will be shown in the following subsection, exactly one of the expressions associated with a variable is used to bind the variable (single assignment); the remaining expressions are only compared with the variable (if one of the expressions a variable is associated with is a constant, then the variable is not needed: it is sufficient to compare all remaining expressions with the constant, e.g. V3 and V4).

was created by (local) abstract interpretation of each clause using the following techniques:

• normalizing heads: all head terms are moved into the body, leaving Arg# as the only head terms
• normalizing lists and structures: all lists and structures are transformed into the LL constructors, selectors, and test predicates (cons, car, struct, etc.)
• static unification: all unification is translated into environment entries in just as a concrete PROLOG interpreter would do: in clause 2a, s[A, B] is s[X, Y] has been used to unify A with X and B with Y
• unification of common subexpressions: static unification is not only used for explicit unification (is) but also for common subexpressions: the output value of clause 2a, V1, is built using the original input argument Arg#1 without re-creating s[X,Y] and s[A,B]: V1 = struct(u, Arg#1, Arg#1)