| << Prev | - Up - | Next >> |
Prolog was the first reasonably successful attempt to make a logic programming language. Underlying logic programming is a simple (and seductive) vision: the task of the programmer is simply to describe problems. The programmer should write down (in the language of logic) a declarative specification (that is: a knowledge base), which describes the situation of interest. The programmer shouldn't have to tell the computer what to do. To get information, he or she simply asks the questions. It's up to the logic programming system to figure out how to get the answer.
Well, that's the idea, and it should be clear that Prolog has taken some interesting steps in this direction. But Prolog is not, repeat not, a full logic programming language. If you only think about the declarative meaning of a Prolog program, you are in for a very tough time. As we learned in the previous lecture, Prolog has a very specific way of working out the answer to queries: it searches the knowledge base from top to bottom, clauses from left to right, and uses backtracking to recover from bad choices. These procedural aspects have an important influence on what actually happens when you make a query. We have already seen a dramatic example of a mismatch between procedural and declarative meaning of a knowledge base (remember the p:- p program?), and as we shall now see, it is easy to define knowledge bases with the same declarative meaning, but very different procedural meanings.
Recall our earlier descendant program (let's call it descend1.pl):
child(martha,charlotte).
child(charlotte,caroline).
child(caroline,laura).
child(laura,rose).
descend(X,Y) :- child(X,Y).
descend(X,Y) :- child(X,Z),
descend(Z,Y). We'll make two changes to it, and call the result descend2.pl:
child(martha,charlotte).
child(charlotte,caroline).
child(caroline,laura).
child(laura,rose).
descend(X,Y) :- descend(Z,Y),
child(X,Z).
descend(X,Y) :- child(X,Y).
From a declarative perspective, what we have done is very simple: we have merely reversed the order of the two rules, and reversed the order of the two goals in the recursive clause. So, viewed as a purely logical definition, nothing has changed. We have not changed the declarative meaning of the program.
But the procedural meaning has changed dramatically. For example, if you pose the query
descend(martha,rose). you will get an error message (`out of local stack', or something similar). Prolog is looping. Why? Well, to satisfy the query descend(martha,rose). Prolog uses the first rule. This means that its next goal will be to satisfy the query
descend(W1,rose) for some new variable W1. But to satisfy this new goal, Prolog again has to use the first rule, and this means that its next goal is going to be
descend(W2,rose) for some new variable W2. And of course, this in turn means that its next goal is going to be descend(W3,rose) and then descend(W4,rose), and so on.
In short, descend1.pl and descend2.pl are Prolog knowledge bases with the same declarative meaning but different procedural meanings: from a purely logical perspective they are identical, but they behave very differently.
Let's look at another example. Recall out earlier successor program (let's call it numeral1.pl):
numeral(0).
numeral(succ(X)) :- numeral(X). Let's simply swap the order of the two clauses, and call the result numeral2.pl:
numeral(succ(X)) :- numeral(X).
numeral(0).Clearly the declarative, or logical, content of this program is exactly the same as the earlier version. But what about its behavior?
Ok, if we pose a query about specific numerals, numeral2.pl will terminate with the answer we expect. For example, if we ask:
numeral(succ(succ(succ(0)))).we will get the answer `yes'. But if we try to generate numerals, that is, if we give it the query
numeral(X).the program won't halt. Make sure you understand why not. Once again, we have two knowledge bases with the same declarative meaning but different procedural meanings.
Because the declarative and procedural meanings of a Prolog program can differ, when writing Prolog programs you need to bear both aspects in mind. Often you can get the overall idea (`the big picture') of how to write the program by thinking declaratively, that is, by thinking simply in terms of describing the problem accurately. But then you need to think about how Prolog will actually evaluate queries. Are the rule orderings sensible? How will the program actually run? Learning to flip back and forth between procedural and declarative questions is an important part of learning to program in Prolog.
| << Prev | - Up - | Next >> |