Fig. 2.2
Two predicate definitions that calculate the factorial function are in file 2_2.pl, which the reader can view by clicking on the 'Code' link at the bottom of this page. The first of these definitions is:
factorial(0,1). factorial(N,F) :- N>0, N1 is N-1, factorial(N1,F1), F is N * F1.
This program consists of two clauses. The first clause is a unit clause, having no body. The second is a rule, because it does have a body. The body of the second clause is on the right side of the ':-' which can be read as "if". The body consists of literals separated by commas ',' each of which can be read as "and". The head of a clause is the whole clause if the clause is a unit clause, otherwise the head of a clause is the part appearing to the left of the colon in ':-'. A declarative reading of the first (unit) clause says that "the factorial of 0 is 1" and the second clause declares that "the factorial of N is F if N>0 and N1 is N-1 and the factorial of N1 is F1 and F is N*F1".
The Prolog goal to calculate the factorial of the number 3 responds with a value for W, the goal variable:
?- factorial(3,W). W=6
Consider the following clause tree constructed for the literal 'factorial(3,W)'. As explained in the previous section, the clause tree does not contain any free variables, but instead has instances (values) of variables. Each branching under a node is determined by a clause in the original program, using relevant instances of the variables; the node is determined by some instance of the head of a clause and the body literals of the clause determine the children of the node in the clause tree.
All of the arithmetic leaves are true by evaluation (under the intended interpretation), and the lowest link in the tree corresponds to the very first clause of the program for factorial. That first clause could be written
factorial(0,1) :- true.
and, in fact, ?- true is a Prolog goal that always succeeds (true is built-in). For the sake of brevity, we have not drawn 'true' leaves under the true arithmetic literals.
The program clause tree provides a meaning of the program for the goal at the root of the tree. That is, 'factorial(3,6)' is a consequence of the Prolog program, because there is a clause tree rooted at 'factorial(3,6)' all of whose leaves are true. The literal 'factorial(5,2)' is, on the other hand, not a consequence of the program because there is no clause tree rooted at 'factorial(5,2)' having all true leaves. Thus the meaning of the program for the literal 'factorial(5,2)' is that it is false. In fact,
?- factorial(3,6). yes ?- factorial(5,2). no
as expected. Clause trees are so-called AND-trees, since, in order for the root to be a consequence of the program, each of its subtrees must also be rooted at literals which are themselves consequences of the program. We will have more to say about clause trees later. We have indicated that clause trees provide a meaning or semantics for programs. We will see another approach to program semantics in Chapter 6. Clause trees do provide an intuitive, as well as a correct, approach to program semantics.
We will need to distinguish between the program clause trees and so-called Prolog derivation trees. The clause trees are "static" and can be drawn for a program and goal regardless of the particular procedural goal-satisfaction mechanism. Roughly speaking, the clause trees correspond to the declarative reading of the program.
Derivation trees, on the other hand, take into account the variable-binding mechanism of Prolog and the order that subgoals are considered. Derivation trees are discussed in Section 3.1 (but see the animation below).
A trace of a Prolog execution also shows how variables are bound in order to satisfy goals. The following sample shows how a typical Prolog tracer is turned on and off.
?- trace. % The debugger will first creep -- showing everything (trace). yes [trace] ?- factorial(3,X). (1) 0 Call: factorial(3,_8140) ? (1) 1 Head [2]: factorial(3,_8140) ? (2) 1 Call (built-in): 3>0 ? (2) 1 Done (built-in): 3>0 ? (3) 1 Call (built-in): _8256 is 3-1 ? (3) 1 Done (built-in): 2 is 3-1 ? (4) 1 Call: factorial(2, _8270) ? ... (1) 0 Exit: factorial(3,6) ? X=6 [trace] ?- notrace. % The debugger is switched off yes
The animated tree below gives another look at the derivation tree for the Prolog goal 'factorial(3,X)'. To start (or to restart) the animation, simply click on the "Step" button.
The title of this section referred to two factorial definitions. Here is the other one, with the same predicate name, but using three variables.
factorial(0,F,F).
factorial(N,A,F) :-
N > 0,
A1 is N*A,
N1 is N -1,
factorial(N1,A1,F).
For this version, use the following type of a goal:
?- factorial(5,1,F). F=120
The second parameter in the definition is a so called an accumulating parameter. This version is properly tail recursive. It is very important for the student to complete the following exercises.
Exercise 2.2.1 Using the first factorial program, show explicitly that there cannot possibly be an clause tree rooted at 'factorial(5,2)' having all true leaves.
Exercise 2.2.2 Draw an clause tree for the goal 'factorial(3,1,6)' having all true leaves, in a fashion similar to that done for factorial(3,6) previously. How do the two programs differ with regard to how they compute factorial? Also, trace the goal 'factorial(3,1,6)' using Prolog.