Transforming Relational Languages into LL

For reasons of simplicity, only the following two kinds of deeply deterministic predicates are supported:

1. 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)
2. 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:

1. :
   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)
2. while do :
   repeat deleting all predicates in if in their definition a predicate in is used until no such predicate in exists
3. 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
4. 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:

1. fac (the factorial function) is used to show how the algorithms work for a simple case.
2. 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.

• REL RELFUN Functions
• RELFUN
• 
• LL
• Examples