Prolog stands for Programmable Logic. It is a computer programming
language that is used for solving problems involving objects and
the relationships between those objects. Programming in Prolog
typically consists of:
Note that the query tall(napoleon) is not false (from Prolog's point of view) because of the fact short(napoleon) It is merely the case that Prolog can't find the fact tall(napoleon) If we like, we could enter both tall(napoleon) and short(napoleon) as facts into Prolog, and it wouldn't see any contradiction between them. This is because Prolog only knows what you enter in as facts and predicates. You could enter a relationship between the tall and short predicates, but we'll get to that later. First, consider a different type of query. So far, all of the questions asked could be answered with a yes or a no. What about questions like these:
Who is tall?
Who is Mary's sister?
Who plays what instrument?
In these questions, there is some unknown element which we are
expecting to be the response; filled by the who or
what in the sentences. These could be restated like this
in Prolog:
tall(Who).
sister(Who,mary).
plays(Who,Instrument).
In the Prolog versions of the queries, the unknown element is
filled in with a variable. Any term that starts with an upper
case letter in Prolog is a variable. In the three queries above,
All 3 uses of Who and the term Instrument are all
variables. The term mary is still a constant, since it
is lower case. predicate names (in this case tall,
sister, and plays) must always start with a lower
case letter. You can't make a query like
AnyRelation(susan,mary).
Prolog's response to a query with one or more variables is somewhat different than its response to yes/no questions:
| ?- tall(Who).
Who = dan ?
At this point, Prolog pauses to ask if Dan is an acceptible
answer. As the user, you have two choices. You can
either type a carriage return, in which case your query predicate will
exit with success. Or you can type in a semi-colon and a carriage
return, and Prolog will fail the current set of variable bindings
and attempt to resolve the query with different variables.
| ?- tall(Who).
Who = dan ?
yes
| ?- tall(Who).
Who = dan ? ;
no
In this case, since we only have one person being defined as tall
in the fact set, Prolog fails on the re-try. Note that my choice
of the variable "Who" is arbitrary. It has no meaning, other than
the fact that the upper case starting letter makes it a variable.
I could as easily have used "Why" or "Checkers" or "X" and gotten
a similar response:
| ?- tall(X).
X = dan ?
yes
In answering this type of question, Prolog shows a bit more of
its matching process. Prolog is trying to find some way to
unify variables and constants so that the query matches
some fact in the data set. In this case Prolog is able to unify
the query tall(X) with the fact tall(dan) from the
data set by assigning dan to the variable X. When
it finds this match, it shows us a list of the variable bindings
which will allow the query to succeed.
When we typed a semi-colon before, we told Prolog to fail that unification. In other words, we told it to throw away those variable bindings and try to find a different solution. Here are some other examples of Wh-type queries:
| ?- sister(Who,mary).
Who = susan ?
yes
| ?- plays(Who,WhatInstrument).
Who = charlie_parker,
WhatInstrument = saxophone ? ;
no
| ?-
The last example illustrates another facet of Prolog's processing.
When I asked for an alternate answer, it couldn't find one. There is
another "plays" clause in my data set, but it has three arguments
while the query only has two, so it doesn't match. To summarize,
Prolog's method for trying to match up queries with facts is this:
At this point, let's set up a new set of facts to deal with, and try some queries that have more than one possible match.
| ?- consult(user).
| sister(gertrude,wilbur).
| sister(sally,mary).
| sister(susan,mary).
| {user consulted, 0 msec 0 bytes}
yes
| ?- sister(Who,mary).
Who = sally ? ;
Who = susan ? ;
no
Here I've just found both of Mary's sisters with the query. A
common mistake people make at first is to accidently capitalize a
proper name when trying to make a query. Another common error is
forgetting to capitalize something that's supposed to be a
variable. Here are examples of both of these errors:
| ?- sister(Who,Mary).
Who = gertrude,
Mary = wilbur ?
yes
| ?- sister(who,mary).
no
In the first example, I entered the variable Mary rather
than the constant mary. The error should be apparent when
I see that I'm getting back one more variable binding than I
expected. In the second example, I forgot to capitalize the
variable who, so Prolog couldn't find the fact
sister(who,mary).
Part II - Multi-clause QueriesSometimes a query involves more than one relation. For example, suppose I have the original data set and I want to know who plays an instrument. I could make a query like this:
plays(Person,X), instrument(X).
Here I've asked Prolog to find "a person who plays something"
and then verify that that "something" is an instrument. This
is called a conjunctive query, because it's the conjunction
of two clauses. The important point is that the X in the
plays predicate is the same X as in the instrument
predicate.
Prolog will evaluate this query by first trying to match the first predicate, plays(Person,X). Assuming it has the first set of facts that I suggested here, then it will match this with plays(charlie_parker,saxophone). This will bind the variable Person to the value charlie_parker, and the variable X to the value saxophone. Prolog will then try to match the second predicate, but since X is already bound, what it tries to match will be instrument(saxophone). Since that exact predicate is in the set of facts we entered, Prolog succeeds, and tells us the bindings of the variables that were in the query:
| ?- plays(Person,X), instrument(X).
X = saxophone,
Person = charlie_parker ?
yes
| ?-
You could make a more complicated query by asking, "Which of Mary's
siblings plays an instrument?" Now there are 3 clauses involved:
sister(S,mary), plays(S,X), instrument(X).In this case the query would fail, as charlie_parker is the only person currently in our data set who plays an instrument, and Mary's not his sister (at least as far as Prolog knows). This is an important point. What Prolog knows is only what you tell it. So something can only be true if you have provided it as a fact in the data set, or you have provided a combination of facts and rules from which Prolog can prove it. This is known as the Closed World Assumption. If you can't prove it, then it must be false. Obviously this isn't always a nice assumption, as there will always be many things that are true but can't be proven (you'd have to have an awfully big computer to hold all the facts that are true). In the previous example, note that the order of the clauses is mostly irrelevant. You would get the same result[s] if you did any of these searches:
The original form I gave for the query is actually the best of all, since it starts out with its first clause, sister(S,mary), being partially restricted. Then it passes the binding of S from the first clause to the second clause, so the second step in the search is partially restricted as well. Finally, it passes the binding of X from the plays clause to the instrument clause, so the last step is just to test if the clause is there or not. I should point out that there's you can do a conjunctive query with totally unrelated clauses, just as you can ask "What's the time and what year were you born?" On the other hand, there's no advantage to asking them as a conjunctive query rather than two separate queries.
Part III - Defining RulesFrom my discussion so far, you might get the impression that you need to state every individual fact in order to make Prolog do anything useful. Actually there is a way to state a relationship that doesn't require you to state every possible detail of the relationship. You can do it with a rule.For example, suppose I want to assert the fact that anyone who is a tall person plays basketball. If I have a data set that has 200 people listed as tall, I could add 200 clauses for the same people that indicates that each one plays basketball, or I could write the following rule:
plays(X,basketball) :- tall(X).
You could read this as "X plays basketball on the condition
that X is tall." Now if I want to find out if Dan plays
basketball, and this is my data set:
short(john). tall(dan). tall(joe). thin(joe). plays(X,basketball) :- tall(X). plays(X,piano) :- short(X).then here's how Prolog will work:
plays(X,basketball) :- tall(X), thin(X).
Now when Prolog matches the head of this query, it has to
succeed on each of the clauses in the right hand side for
the overall match to succeed. If I now want to ask Prolog
"who plays basketball?" using the same data set, then here's
how Prolog will work:
| ?- plays(Who,basketball).
Who = joe ?
yes
| ?-
If you want to see the details of what clauses Prolog is
trying out in a search, you can turn on trace by calling
the trace predicate. Here's what a trace of the previous
query looks like:
| ?- trace.
{The debugger will first creep -- showing everything (trace)}
yes
{trace}
| ?- plays(Who,basketball).
1 1 Call: plays(_187,basketball) ?
2 2 Call: tall(_187) ?
2 2 Exit: tall(dan) ?
3 2 Call: thin(dan) ?
3 2 Fail: thin(dan) ?
2 2 Redo: tall(dan) ?
2 2 Exit: tall(joe) ?
3 2 Call: thin(joe) ?
3 2 Exit: thin(joe) ?
1 1 Exit: plays(joe,basketball) ?
Who = joe ?
yes
{trace}
| ?-
For more examples of defining rules, see my
genealogy example.
Part IV - Lists in PrologProlog has a very nice format for dealing with lists. Unlike the non-intuitive expressions (CAR L) and (CDR L), Prolog represents the head (the equivalent of the CAR in Lisp) and the tail (the equavalent of the CDR) like this:
[Head|Tail]
Notice that I've got both Head and Tail capitalized, so they're
both variables in this case. Of course, they could be constants,
or terms containing variables, like these:
[a|Tail]
[X|[a,b,c]]
[drove(john,car)|OtherFacts]
[implies(X,Y)|OtherFacts]
For the last two examples here, think of the problem where you're
storing some set of facts, but within some sub-context. For
example, recall the Encyclopedia Brown problems. You need to be
able to distinguish things that someone says happened from things
that are observed to happen. if you just define it all as
facts in Prolog, then you can't tell what's real from what's a
lie. Thus, you can keep two lists, one of real facts and one of
"facts" stated by the person who Encyclopedia accuses. Then you
search for something in the "facts" that contradicts something in
the real facts.
As in Lisp, there is a special symbol for the null list, but instead of ( ), it's [ ]. You may remember that in Lisp, the (CAR ( )) is ( ) and the (CDR ( )) is ( ). This is not the case in Prolog, where you can't pull the head or tail off of a null list. If you try to match [ ] with [H|T], it won't match. One other notation is worth mentioning here. If you don't care what the value of some variable is, you can use an _ for the variable name. For example, if you have a rule that only cares about the head of a list, you could start the rule like this:
process_head([Head|_]) :- ...
On the other hand, if you don't care about the head, but
you only plan on dealing with the tail of the list, you could
do it this way:
process_tail([_|Tail]) :- ...
The benefit of this is that if Prolog knows that you don't
care about a value, it doesn't try to store its variable binding
on the stack, so you save space. It'll become clear where you
could do this in the next section.
Part V - Prolog ProgrammingNow that we've got all the building blocks covered, let's consider how to program a simple function in Prolog. One of the first functions you learned to write in lisp was the member function, which takes an element and a list as arguments and returns true if the element is contained somewhere in the list. In case you've forgotten it, the code looked something like this
(defun member (E L)
(cond ((null L) 'F)
((equal E (CAR L)) 'T)
('T (member E (CDR L)))))
The first condition checks if the list is ( ), and if so it
fails. The second condition checks if the element is at the
head of the list, and the last condition recurses to check if
the element is in the tail. The definition of this function
in Prolog is very similar:
member(H,[H|T]).
member(X,[H|T]) :- member(X,T).
The first statement here is like the second condition of the
Lisp code. It says that the first argument (the element) is
a member of the second argument (the list) if it is the head
of the list. The second statement is like the
recursive call in the Lisp code. It says that the element is
a member of the list on the condition that it is a member of
the tail.
The only thing missing here that was in the Lisp code is the first condition, which checked for the null list. Remember from the last section that the null list in Prolog can never match a [H|T] type representation. Thus, the extra check for the null list isn't needed in Prolog. To see how this works, suppose I call this function with the query member(2,[1,2,3]). Here's how Prolog handles it:
One neat thing about Prolog functions is that they usually don't distinguish what's an input and what's an output. Thus I could call the member function like this:
member(X,[a,b,c]).
In this case, Prolog would succeed in matching my query to the
first statement and return "X = a". If I asked for more results
by typing in a ";", Prolog would first give me "X = b", then
"X = c", then it would fail and say "no".
One more thing to notice here is that the first statement member(H,[H|T]), doesn't really do anything with the tail. Thus this would be a good place to use the _ to indicate we don't care about its value. Similarly, the second statement doesn't really use the head, so we could use it again there. Here's the revised code:
member(H,[H|_]).
member(X,[_|T]) :- member(X,T).
Another simple function on lists can be implemented simply
in Prolog as well; namely, the append function. If we
were implementing append in Lisp, we would do it something
like this:
(defun append (L1 L2)
(cond ((null L1) L2)
(t (cons (car L1) (append (cdr L1) L2)))
)
)
The processing here works the following way. If the
first list is ( ), then you just return the second list.
Otherwise, you take the car of the first list,
and put it back on to the front of the result you get
when you append the cdr of the first list to the
second list. When this is executed in Lisp, it'll take
elements off the first list one by one until it's ( ),
then it'll go back and put them back on one by one with
the cons.
A Prolog implementation works exactly the same way:
append([],L,L).
append([H|T1],L,[H|T2]) :- append(T1,L,T2).
The symmetry between the two functions is obvious: the first
line of the Prolog program is equivalent to the first condition
of the Lisp program, and the second line is equivalent to the
second condition. The only differences are 1) the way lists
and their manipulation are represented, and 2)that the result is
returned as the third argument instead of as a return value
for the function (since Prolog functions can only return yes
or no).
In case it's not clear, let me change the variable names to represent what they are in the Lisp code
append([],L2,L2).
append([CarL1|CdrL1],L2,[CarL1|RecursiveAppendResult]) :-
append(CdrL1,L2,RecursiveAppendResult).
|