Previous | Table of Contents | Next |
6.2.8.1. An Example
As an example of how Prolog works, consider the query member([a,b], X), X=b. The sequence of calls to solve and solve_clause made during the start of processing of this query is as follows. (Calls to solve_eq are not shown for brevity.)
solve((member([a,b], X), X=b)) solve_clause( member([a,b], X), member([Head|Tail], Head), (X=b) ) solve(([a,b]=[Head|Tail], X=Head, X=b)) solve((a=Head, [b]=Tail, X=Head, X=b)) solve(([b]=Tail, X=a, X=b)) solve((X=a, X=b)) solve((a=b))
At this point, we have reached a dead end. Our initial guess that the first clause of member was the right one to use has matched X to a, which is not equal to b. solve_eq returns redo and this return value gets passed back through all the levels of solve and solve_eq up to the topmost call to solve. We then try the second clause of member, with better results:
solve_clause( member([a,b], X), member([Head|Tail], X) :- member(Tail, X), (X=b) ) solve(([a,b]=[Head|Tail], X=X, member(Tail, X), X=b)) solve((a=Head, [b]=Tail, X=X, member(Tail, X), X=b)) solve(([b]=Tail, X=X, member(Tail, X), X=b)) solve((X=X, member([b], X), X=b)) solve((member([b], X), X=b)) solve_clause( member([b], X), member([Head|Tail], Head), (X=b) ) solve(([b]=[Head|Tail], X=Head, X=b)) solve((b=Head, []=Tail, X=Head, X=b)) solve(([]=Tail, X=b, X=b)) solve((X=b, X=b)) solve((b=b)) solve(())
This last call, asking to solve the empty goal, causes Prolog to report the solution and ask the user if she wants to find more solutions. If the user types ; and then presses Enter, Prolog tries again with the second clause of member and does not find any more solutions; the redo that results percolates up to the top level and causes Prolog to report no as its final verdict on the query. If the user presses Enter at the solutions prompt, exit is returned and Prolog ends up saying yes.
6.2.8.2. Some Terminology
Prolog programmers have developed a language that they use to talk about the execution of queries. Here we look at some of this terminology.
Prolog may succeed or fail to find a satisfying substitution for a query. This success or failure is often viewed as an action of the query itself or of a goal that is encountered during the processing of a query. Thus we say, for example, that the query member([a,b], X), X=b succeeds and that the query member([a,b], c) fails.
You may have noticed, in the execution model, that variables hang around during the processing of a query until a goal comes up that equates the variable to a term. When such a goal does arise, the variable is replaced everywhere by that term. This process of substituting a variable by a term is referred to as instantiating the variable; variables that have not yet been substituted for are referred to as uninstantiated. In fact, a variable, say X, may be replaced by a term that itself has uninstantiated variables in it, say [a,b,Z]. In this case, we say that X is partially instantiated, indicating that some but not all the holes in its pattern have been filled in.
The entire process of equating two termsfor instance, for processing [Head|Tail] = [b] by substituting Head by b and Tail by []is referred to as unification. Many texts present the Prolog unification algorithm as a separate entity; here we look at it as part of the wider algorithm that Prolog uses to execute a query. We say that two terms unify if the execution of an equality query between them does not result in failure. Thus a does not unify with b, but [Head|Tail] does unify with [b].
Previous | Table of Contents | Next |