LL

In the final step, all clauses for a predicate are collected into a single LL function definition, where the clauses are connected by a cascade of if and let statements.

This transformation is only allowed if the following conditions are satisfied:

1. for deeply deterministic functional predicates:
   1. all (REL input) clauses but the last must contain a quasi-final cut, i.e. all guards (test predicates and test builtins) come before the cut
   2. the last clause must be a catch-all clause, i.e. a clause without any guards
2. for deeply deterministic test predicates: all clauses but the last either
   1. contain a quasi-final cut or
   2. their head is disjoint from all following clause heads (disjointness is established via non-unifyability)

These conditions ensure that all deeply deterministic functional predicates have exactly one solution and all deeply deterministic test predicates have at most one solution.

For a typed relational language, these conditions could be relaxed in a very desirable way: clauses often do not have to contain cuts, which at least by logic-programming purists are disliked for various reasons, and catch-all clauses can in most cases be avoided, since guards together with type declarations can be used to prove all clauses of a predicate to be disjoint (and total) w.r.t. the mode and type declaration.

In example 4.6, both predicates satisfy the conditions, i.e. clauses 1a and 2a contain final cuts and clauses 1b and 2b are catch-all clauses. The following LL function definitions result:

(defun fac/2-1 (arg#1)
  (if (equal 0 arg#1)
      1
      (* arg#1 (fac/2-1 (- arg#1 1)))))

(defun f/2-1 (arg#1)
  (if (and (structp arg#1)
           (equal 's (functor arg#1))
           (equal 2 (arity arg#1)))
      (let ((x (elt arg#1 0)))
           (if (equal x (fac/2-1 x))
               (let ((y (elt arg#1 1)))
                    (if (and (equal x (- y x)) (equal y (fac/2-1 y)))
                        (struct 'u arg#1 arg#1)
                        (cons arg#1 (cons arg#1 nil))))
               (cons arg#1 (cons arg#1 nil))))
      (cons arg#1 (cons arg#1 nil))))

In case of the fac function, exactly the definition a human programmer would have chosen has been created.

The function definition for f is extremely operational: the sequence of unifications of the original REL definition has been transformed into a very precise operational definition mainly consisting of assignments and equality tests. This is consistent with recent insights that PROLOG programs should be compiled into much simpler and more specialized instructions than the WAM instructions (see [\protect\citeauthoryearVan Roy1994][\protect\citeauthoryearTaylor1990]).

The three copies of (cons arg#1 (cons arg#1 nil)) cannot be avoided in a purely functional specification. These copies, which do not cause any efficiency disadvantages, can be removed on the abstract machine level by code sharing.