Now that you've read chapters 2, 3, and the first three parts of this chapter, you should have a pretty good understanding of the basics of Prolog programming and using Visual Prolog. Remember, Prolog is a declarative language, which means that you describe a problem in terms of facts and rules and let the computer figure out how to find a solution. Other programming languages--such as Pascal, BASIC, and C--are procedural, which means that you must write subroutines and functions that tell the computer exactly what steps to go through in order to solve the problem.
We're going to back up now and review of some of the material you've just learned about Prolog, but this time we're going to present it from a procedural perspective.
It's easy to think of a Prolog rule as a procedure definition. For instance, the rule
likes(bill,Something):- likes(cindy,Something).
means,
"To prove that Bill likes something, prove that Cindy likes it."
With this in mind, you can see how procedures like
say_hello:- write("Hello"), nl.
and
greet:-
write("Hello, Earthlings!"),
nl.
correspond to subroutines and functions in other programming languages.
You can even think of Prolog facts of as procedures; for instance, the fact
likes(bill, pasta).
means
"To prove that Bill likes pasta, do nothing--and by the way, if the arguments Who and What in your query likes(Who, What) are free variables, you can bind them to bill and pasta, respectively."
Some programming procedures that you might be familiar with from other languages are case statements, boolean tests, goto statements, and computational returns. In the next sections, by reiterating what we've already covered from a different (procedural) point of view, we'll show you how Prolog rules can perform these same functions.
(1) Using Rules Like Case Statements
One big difference between rules in Prolog and procedures in other languages is that Prolog allows you to give multiple alternative definitions of the same procedure. This came up with the "parent" program earlier on page 15; a person can be a parent by being a father or by being a mother, so the definition of "parent" is made up of two rules.
You can use multiple definitions like you use a Pascal case statement by writing a different definition for each argument value (or set of argument values). Prolog will try one rule after another until it finds a rule that matches, then perform the actions that rule specifies, as in Program 13.
/* Program ch04e13.pro */
/* Copyright (c) 1986, '95 by Prolog Development Center */
PREDICATES
nondeterm action(integer)
CLAUSES
action(1):-
nl,
write("You typed 1."),nl.
action(2):-
nl,
write("You typed two."),nl.
action(3):-
nl,
write("Three was what you typed."),nl.
action(N):-
nl,
N<>1, N<>2, N<>3,
write("I don't know that number!").
GOAL
write("Type a number from 1 to 3: "),
readint(Num),
action(Num).
If the user types 1, 2, or 3, action will be called with its argument bound to the appropriate value, and it will match only one of the first three rules.
(2) Performing Tests within the Rule
Look more closely at the fourth clause for action. It will match whatever argument it's called with, binding X to that value. So you have to make sure that it doesn't print I don't know that number unless the number is indeed out of range. That's the purpose of the subgoals
X<>1, X<>2, X<>3
where <> means not equal. In order to print I don't know that number, Prolog must first prove that X is not 1, 2, or 3. If any of these subgoals fail, Prolog will try to back up and find alternatives--but there aren't any alternatives, so the rest of the clause will never be executed.
Notice that action relies on Choice being bound. If you call action with a free variable as an argument, the goal would match all of the clauses. The first three would return alternative solutions, and then the last one would raise an error because you can't test whether an unbound variable is not equal to a number.
(3) The Cut as a GoTo
Program 13 is somewhat wasteful because, after choosing and executing the correct rule, Prolog still keeps looking for alternatives and has to find out the hard way that the last rule doesn't apply.
It would save time and memory if you could tell Prolog to stop looking for alternatives. And you can, by using the cut, which means,
"If you get this far, don't do any backtracking within this rule, and don't look for any alternatives to this rule."
In other words, "Burn your bridges behind you." Backtracking is still possible, but only at a higher level. If the current rule was called by another rule, and the higher rule has alternatives, they can still be tried. But the cut rules out alternatives within, and alternatives to, the present rule.
Using cuts, the program can be rewritten as follows:
/* Program ch04e14.pro */
/* Copyright (c) 1986, '95 by Prolog Development Center */
PREDICATES
action(integer)
CLAUSES
action(1):-!,
nl,
write("You typed 1.").
action(2):-!,
nl,
write("You typed two.").
action(3):-!,
nl,
write("Three was what you typed.").
action(_):-
write("I don't know that number!").
GOAL
write("Type a number from 1 to 3: "),
readint(Num),
action(Num),nl.
The cut has no effect unless it is actually executed. That is, in order to perform a cut, Prolog must actually get into the rule containing the cut and reach the point where the cut is located.
The cut can be preceded by other tests, like this:
action(X) :- X>3, !, write("Too high.").
In this rule, the cut won't have any effect unless the subgoal X>3 succeeds first.
Notice that the order of the rules is now significant. In 13, you could have written the rules in any order; only one of them will match any particular number. But in Program 14 you must make sure that the computer doesn't even try the rule that prints I don't know that number unless all of the preceding rules have been tried (and have not executed their cuts).
The cuts in 14 are what some people call red cuts--cuts that change the logic of the program. If you had kept the tests X<>1, X<>2, and X<>3, changing the program only by inserting a cut in each clause, you would have been using green cuts--cuts that save time in a program that would be equally correct without them. The efficiency gained is not as great, but there is less risk of making an error in the program.
The cut is a powerful, but messy, Prolog operation. In this respect it resembles the goto statement in other programming languages--you can do many things with it, but it can make your program really hard to understand.
(4) Returning Computed Values
As we have seen, a Prolog rule or fact can return information to the goal that called it. This is done by binding arguments that were previously unbound. The fact
likes(bill, cindy).
returns information to the goal
likes(bill, Who).
by binding Who to cindy.
A rule can return the results of a computation the same way. Here's a simple example:
/* Program ch04e15.pro */
/* Copyright (c) 1986, '95 by Prolog Development Center */
PREDICATES
nondeterm classify(integer,symbol)
CLAUSES
classify(0,zero).
classify(X,negative):-
X < 0.
classify(X,positive):-
X > 0.
The first argument of classify must always be either a constant or a bound variable. The second argument can be either bound or unbound; it gets matched with the symbol zero, negative, or positive, depending on the value of the first argument.
Here are some examples of how rules can return values:
You can ask whether 45 is positive by giving the goal:
Goal classify(45, positive).
yes
Because 45 is greater than 0, only the third clause of classify can succeed. In doing so, it matches the second argument with positive. But the second argument is already positive, so the match succeeds, and you get the answer yes.
Conversely, if the match fails, you get no:
Goal classify(45, negative).
no
What happens is this:
Prolog tries the first clause, but the first argument won't match 0 (nor does the second argument match zero).
Then it tries the second clause, binding X to 45, but the test X<0 fails.
So it backs out and tries the third clause, but this time the second arguments don't match.
To get an actual answer, rather than just yes or no, you must call classify with the second argument free:
Goal classify(45, What).
What=positive
1 Solution
Here's what really takes place in this case:
The goal classify(45, What) won't match the head of the first clause, classify(0, zero), because 45 doesn't match 0. So the first clause can't be used.
Again, the goal classify(45, What) matches the head of the second clause, classify(X, negative), binding X to 45 and negative to What. But then the text X<0 fails, because X is 45 and it is not true that 45<0. So Prolog backs out of this clause, undoing the variable bindings just created.
Finally, classify(45, What) matches classify(X, positive), binding X to 45 and What to positive. The test X>0 succeeds. Since this is a successful solution, Prolog doesn't backtrack; it returns to the calling procedure (which in this case is the goal that you typed). And since the variable X belongs to the calling procedure, that procedure can use its binding--in this case, to print out the value automatically.
In this chapter we've introduced unification, backtracking, determinism, the predicates not and fail, and the cut (!), and we've reviewed the important parts of the tutorial information up to this point from a procedural perspective.
Prolog facts and rules receive information by being called with arguments that are constants or bound variables; they return information to the calling procedure by binding variable arguments that were unbound.
Unification is the process of matching two predicates and assigning free variables to make the predicates identical. This mechanism is necessary so Prolog can identify which clauses to call and bind values to variables. These are the major points about matching (unification) presented in this chapter:
When Prolog begins an attempt to satisfy a goal, it starts at the top of the program in search of a match.
When a new call is made, a search for a match to that call also begins at the top of the program.
When a call has found a successful match, the call is said to return, and the next subgoal in turn can be tried.
Once a variable has been bound in a clause, the only way to free that binding is through backtracking.
Backtracking is the mechanism that instructs Prolog where to go to look for solutions to the program. This process gives Prolog the ability to search through all known facts and rules for a solution. These are the four basic principles of backtracking given in this chapter:
Subgoals must be satisfied in order, from top to bottom.
Predicate clauses are tested in the order they appear in the program, from top to bottom.
When a subgoal matches the head of a rule, the body of that rule must be satisfied next. The body of the rule then constitutes a new set of subgoals to be satisfied.
A goal has been satisfied when a matching fact is found for each of the extremities (leaves) of the goal tree.
A call that can produce multiple solutions is non-deterministic, while a call that can produce one and only one solution is deterministic.
Visual Prolog provides three tools for controlling the course of your program's logical search for solutions: these are the two predicates fail and not, and the cut.
The fail predicate always fails; it forces backtracking in order to find alternate solutions.
The not predicate succeeds when its associated subgoal can't be proven true.
The cut prevents backtracking.
It's easy to think of a Prolog rule as a procedure definition. From a procedural perspective, rules can function as case statements, perform boolean tests, act like goto statements (using the cut), and return computed values.