Determinism in Relational Languages

Before describing the algorithms for determinism transformation, determinism in relational languages is defined. The definition presented in this work was designed to cover as many deterministic predicates as possible since in the context of a transformation into LL, the gain in efficiency grows directly with the number of transformed deterministic predicates.

In this work, determinism is defined via SLD resolution trees:

As this definition states, all goals appearing as first elements in the nodes of an SLD resolution tree are activated subgoals. This is due to PROLOG's computation rule which always selects the leftmost goal in a goal sequence.

Now the fundamental definition of determinism in PROLOG can be given:

This definition specifies a predicate to be deterministic if for all possible queries all activated subgoals with as predicate either

1. have exactly one solution,
   
2. fail, or
   
3. enter a non-terminating branch (before computing a first solution)
   

There are other possibilities to define determinism in PROLOG. In the following, examples motivating our definition and modifications that make it tractable and more powerful are given.

In definition 4.5, a predicate is deterministic w.r.t. to a given program and a given set of queries . A definition of determinism in PROLOG that does not consider an entire program and a set of queries but only the clauses of a single predicate will not be fruitful: only very few PROLOG predicates are deterministic as such, and - as already mentioned - as many predicates as possible should be covered in order to gain efficiency by transforming them into LL.

Example 4.2 shows that it is important to consider all queries for a given program. Otherwise, predicates that are always used deterministically are not detected and thus compiled into inefficient code.

This definition complies with the concept of partial evaluation (or partial deduction in the field of logic programming). As pointed out in [\protect\citeauthoryearNilsson1993], partial evaluation is, at least from a principal point of view, a simple form of program transformation by which a program, given some partial input data, can be specialized to solve a particular problem more efficiently than the more general program. The origin of the field is due to Kleene [\protect\citeauthoryearKleene1952], but the application to programming languages is primarily due to Futamara [\protect\citeauthoryearFutamura1971], Haraldsson [\protect\citeauthoryearHaraldsson1977], Ershov [\protect\citeauthoryearErshov1980], and Jones [\protect\citeauthoryearJones et al.1989].

As the following example shows, non-trivial deterministic predicates can be detected without partial evaluation.

The next example shows that it is not sufficient for a predicate to have at most one solution for all activated subgoals to be easily replaced by an efficient deterministic procedure.

The problem with this program is that although p is deterministic w.r.t. and , q, which is called in p, is non-deterministic w.r.t. and = {q(1,Z)}:

In order to be able to replace each deterministic predicate by a simple and directly obtainable procedure or function specified in a deterministic imperative or functional language, all predicates called in the execution of deterministic predicates must themselves be deterministic: internal backtracking in the execution of a deterministic predicate is not allowed.

This leads to the following definition of deep determinism:

An algorithm detecting deeply deterministic predicates (for a special case of query sets) is described in section 4.2.3.

The following example motivates a further modification of the concept of deterministic predicates:

This example shows that due to PROLOG's computation rule the set of deterministic predicates in a program can change if the program is transformed into a logically equivalent program. This motivates a slight modification of definitions 4.5 and 4.6: in order to obtain more (or more interesting, e.g. more often used) deterministic predicates, reordering of premises should be allowed.

Reordering of premises is potentially dangerous in PROLOG for several reasons:

1. the termination behaviour may change
   
2. solutions may be computed in a different order
   
3. side effects may be executed in the wrong order

The transformation algorithms described in this work will only reorder premises in respective benevolent cases:

1. by reordering premises, in PROLOG non-terminating relations are sometimes transformed into terminating ones, but never the other way around
2. only premises of deeply deterministic predicates are reordered, which does not change the order of the computed solutions because deeply deterministic predicates have at most one solution
3. the transformations are not applied to programs with side effects