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