Execution of CLP languages can be seen as a tree traversal, where the nodes of the tree are conjunctions of atoms to be proved (similar to bodies of clauses, which are also conjunctions of atoms). The root of the tree is the initial query posed by the user, and there might be one or several branches starting at every node, each branch corresponding to the clauses with matching heads for the first (leftmost) goal in the conjunction. The tree is explored by selecting the leftmost goal in a conjunction, and the leftmost untried branch (clause) for that goal. The tree can be explored partially or totally; in the latter case, all solutions to the initial query are returned.
Figure 2.2 shows how the execution tree is traversed for the following program and the query ?- grandparent(charles,X).
grandparent(C,G):- parent(C,P), parent(P,G). parent(C,P):- father(C,P). parent(C,P):- mother(C,P). father(charles,philip). father(ana,george). mother(charles,ana).
Execution starts at the toplevel query grandparent(charles, X), which is equated to the first clause of the program. Variables in the body of the clause are substituted by the constants in the query, and the body (with some constants in place of the textual variables) is left to be solved as a conjunction of goals. The execution continues by selecting the first goal in the body (parent(C, P), now rewritten at runtime to parent(charles, P)), and the process continues. There are two matching clauses for parent(charles, P), and the two are tried in textual order: that is the reason why two different subtrees are rooted at this node. The execution proceeds until a node with no atoms to solve is obtained (this is possible because a resolution against a fact, which has no body, removes an atom from the node).
The final result of the query, X = george, is obtained in the leaf labeled (precisely) X = george. This binding for X can be seen as propagated upwards in the tree and communicated to the variable present in the toplevel query, but, in fact, the variable this binding is made to, is the same one which was present in the toplevel query: as atoms were reduced in the execution process, variables in the same position in atoms and clause heads were unified, i.e., equated.
Knowing the operational behavior of the language is necessary for larger programs (especially because it is instrumental for achieving better performance), but for the time being, it is not essential: understanding the declarative semantics (i.e., the grandfather of someone is the father of his/her mother or the father or his father) is far more important at this stage.
