Bottom-up evaluation
The standard strategy of evaluation of logic programs is top-down and depth-first: from the goal, a number of clauses are identified as being possibly able to prove the goal, and recursion over the literals of their bodies is performed. An alternative strategy is to start from the facts and use clauses to derive new facts; this strategy is called bottom-up. It is considered better than the top-down one when the aim is that of producing all consequences of a given program, rather than proving a single goal. In particular, finding all consequences of a program in the standard top-down and depth-first manner may not terminate while the bottom-up evaluation strategy terminates.
The bottom-up evaluation strategy maintains the set of facts proved so far during evalution. This set is initially empty. At each step, it is added new facts derived from the facts already in the set using a single clause in the program. For example, the bottom up evaluation of the following program requires two steps:
A(q). B(X):-A(X).
The set of consequences is initially empty. At the first step, A(q) is the only clause whose body can be proved (because it is empty), and A(q) is therefore added to the current set of consequences. At the second step, since A(q) is proved, the second clause can be used and B(q) is added to the consequences. Since no other consequence can be proved from {A(q),B(q)}, execution terminates.
The advantage of the bottom-up evaluation over the top-down one is that cycles of derivations do not produce an infinite loop. This is because adding a consequence to the current set of consequences that already contains it has no effect. As an example, adding a third clause to the above program generates a cycle of derivations in the top-down evaluation:
A(q). B(X):-A(X). A(X):-B(X).
For example, while evaluating all answers to the goal A(X), the top-down strategy would produce the following derivations:
A(q) A(q):-B(q), B(q):-A(q), A(q) A(q):-B(q), B(q):-A(q), A(q):-B(q), B(q):-A(q), A(q)
In other words, the only consequence A(q) is produced first, but then the algorithm cycles over derivations that do not produce any other answer. More generally, the top-down evaluation strategy may cycle over possible derivations, possibly when other ones exist.
The bottom-up strategy does not have the same drawback, as consequences that were already derived has no effect. On the above program, the bottom-up strategy starts adding A(q) to the set of consequences; in the second step, B(X):-A(X) is used to derive B(q); in the third step, the only facts that can be derived from the current consequences are A(q) and B(q), which are however already in the set of consequences. As a result, the algorithm stops.
In the above example, the only used facts were ground literals. In general, every clause that only contains constraints in the body is considered a fact. For example, a clause A(X):-X>0,X<10 is considered a fact as well. For this extended definition of facts, some facts may be equivalent while not syntactically equal. For example, A(q) is equivalent to A(X):-X=q and both are equivalent to A(X):-X=Y, Y=a. To solve this problem, facts are translated into a normal form in which the head contains a tuple of all-different variables; two facts are then equivalent if their bodies are equivalent on the variables of the head, that is, their sets of solutions are the same when restricted to these variables.