Next: REL RELFUN Functions
Up: Determinism Transformation
Previous: Restricting the Query
In this subsection, the determinism analysis and the
transformation steps for deeply deterministic predicates are
described.
For reasons of simplicity, only the following two kinds of deeply
deterministic predicates are supported:
- functional predicates: predicates which for a given
set of ground input arguments compute a ground set of output
arguments, i.e. they always compute exactly one solution
and never fail (total functions)
- test predicates: predicates which when called with all
arguments ground either fail or succeed exactly once;
these test predicates are used as guards
For a program , in which the predicates are defined,
and a set of mode declarations ,
deeply deterministic functional or test predicates
are detected by the following algorithm:
- :
construct a set of candidates consisting of all
predicates with at least one ground argument (if all
arguments are ground, the predicate is assumed to be a test
predicate, otherwise it is assumed to be a functional predicate)
- while do
:
repeat deleting all predicates in if in their definition
a predicate in is used
until no such predicate in exists
- try to transform all predicates in into LL (with the
algorithms described in the following subsections); remove all
predicates from which could not be thus transformed
- same as 2.
In the transformation steps, several intermediate representations
are used:
The following REL example will be used to demonstrate the various
transformations and intermediate representations. It consists
of two deeply deterministic functional predicates:
This example was chosen for the following reasons:
- fac (the factorial function) is
used to show how the algorithms work for a simple case.
- f is a rather artificial function using fac. It
is used to show how the algorithms handle non-standard cases:
- the definition of f cannot be evaluated by REL
(the arithmetical builtin - is called with free
variables),
- the expression A is -(B,A) is cyclic,
- the unification in s[A,B] is s[X,Y]
has to be handled
at compile time (static unification),
- lists and structures are transformed into LL constructors,
selectors, and test predicates, and
- subexpressions in the output value can be shared with
the input value.
Next: REL RELFUN Functions
Up: Determinism Transformation
Previous: Restricting the Query
Harold Boley & Michael Sintek (sintek@dfki.uni-kl.de)