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

- have exactly one solution,

- fail, or

- 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:

- the termination behaviour may change

- solutions may be computed in a different order

- side effects may be executed in the wrong order

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

- by reordering premises, in PROLOG non-terminating relations are sometimes transformed into terminating ones, but never the other way around
- 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
- the transformations are not applied to programs with side effects