Tutorial 1
Contents
- Prolog programming consists of defining relations and making
queries about relations.
- A program consists of clauses of which there are three types:
- A relation is defined in terms of either or both of
- facts, which describe members of the relation explicitly.
- rules, which describe members in terms of other relations.
- A collection of facts and rules is called a database.
- A query asks a question about a relation.
The query succeeds if the database satisfies the query. Otherwise the
query fails.
Here is a simple Prolog database comprising some
facts. Each fact each states a certain pair of individuals are in
the "likes" relation.
likes(john,fish).
likes(john,mary).
likes(mary,book).
likes(john,book).
Note that
- Each fact corresponds to a simple assertion, eg. John
likes fish: more technically, the pair (john,fish) is in the
likes relation.
- Each fact is a clause comprising a functor (the symbol
"likes") and some arguments separated by commas and enclosed
in parentheses.
- The symbol "likes" starts with a lowercase letter. A
lowercase symbol in Prolog is a constant that stands for
itself.
- In general any symbol standing in function position
(called a functor) must start with a lowercase
letter.
- Each clause must be terminated by a period.
Once a database has been written in a file and loaded into
Prolog, the system issues a prompt
?-
and awaits a query.
At this point the user can type in a query terminated with a period. In the
examples below, user input appears in italics.
?- likes(john, fish).
yes
Prolog searches the database for a matching clause. If it finds one,
the query succeeds, as it does here, and as indicated
by the "yes" response. Note that a simple query
is just another kind of clause and has the same general shape as a
fact (that's why it has to be terminated with a period).
If there is no matching clause, the query fails. This is
indicated by the response "no".
?- likes(john, money).
no
Most of the time we issue queries in order to associate values with
variables. Variables are symbols that begin with an uppercase
letter. The next query corresponds to the English question "What does
John like?", or more precisely, "Is there an X such that John likes it?".
When a query contains a variable, Prolog searches the database for
matching clauses, as before. The difference is that when it finds one
it reports the corresponding variable binding. At this point the user
can enter a carriage return (written as [return] below),
whereupon the query succeeds as before.
?- likes(john,X).
X=book [return]
yes
Alternatively, the user can enter a semicolon, thereby instructing
Prolog to continue the search for other matching clause, which, if
it exists, is reported in the same way.
?- likes(john,X).
X=book;
X=fish;
X=mary;
no
Note that
- The very last query (the semicolon after the response "mary") fails:
there are no more answers. Hence the "no" reponse.
- The order of the answers reflects the order of the clauses
in the database: Prolog always searches the database from top to bottom,
Matching Queries Against Facts
Clearly, the success of a query depends upon there being a match
between query and fact. To summarise the above:
- Each matching fact yields a distinct solution.
- A fact matches a query just
in case:
- The query and the fact have the same predicate name.
- The query and the fact have the same number of arguments.
- Corresponding arguments match.
For example, the fact
sum(3,3,6).
is matched by any
of the following queries:
?- sum(X,3,6).
?- sum(X,X,6).
?- sum(X,Y,6).
?- sum(X,Y,Z).
?- sum(3,3,6).
but not by
?- plus(3,3,6).
?- sum(X,3).
?- sum(3,3,7).
?- sum(X,3,X).
So far we have looked at simple queries. A more complex kind of query
can be formed with one or more simple queries separated by a comma, as
shown in the next example, which corresponds to the English question
"Does John like Mary and Mary like John?".
?- likes(john,mary), likes(mary,john).
no
Note
that
- The comma separating the queries acts like a logical
conjunction: both of the constituent queries (or subgoals) must
be satisfied for the query to succeed.
- The subgoals are attempted from left to right.
The latter point is best illustrated by means of the following example:
?- likes(john,X), likes(mary,Y).
X=fish
Y=book;
X=mary
Y=book;
X=book
Y=book;
no
Note carefully the steps followed to yield these solutions:
- Prolog first attempts to satisfy likes(john,X). It finds the first matching
clause with X=fish.
- It then proceeds to likes(mary,Y), which succeeds with Y=book.
- Both subgoals are satisfied and the variable bindings are printed.
- The user types a semicolon. Internally, this initiates a failure and
a subsequent attempt to resatisfy the last goal.
- There is no way to resatisfy likes(mary,Y) so the failure is propagated
backward to the moment when immediately preceding goal left off. Can that
subgoal be successfully resatisfied?
- It can - a second matching clause is found, with X=mary. We have
now succeeded in resatisfying the first subgoal.
- Next Prolog attempts the second subgoal - afresh, since all record
if the previous
attempt was "forgotten" when we went back in time.
- The second subgoal is satisfied - again Y=book.
- The second solution is printed, and the user types a semicolon, provoking
the third solution.
- When the user types a semicolon for the third time, there is no way
to resatisfy the first goal, so the failure is propagated right back to
the user level.
- The failure is reported with "no"
The last example involves the two distinct variables X and Y
whose values are independent of each other. Clearly, the range of
expressible queries is enhanced if we envisage multiple occurrences of
the same variable. For example, the English query "What is it that
John and Mary both like?" can be expressed by
?- likes(john,X), likes(mary,X).
X=book;
no
Note that the mechanics of attempting to satisfy this query is essentially
similar to that of the last example. The only difference is that
the contents of the second goal is now linked to the first through the value
of the variable X. Prolog thus attempts to solve the second goal with
X=fish, X=mary, and X=book (in that order), but it only succeeds with the last of
these.
Contents of this tutorial
Exercise on the contents of this tutorial
How to run Prolog
Tutorial 2
Mike Rosner (mros@cs.um.edu.mt)
Last modified: Wed May 21 16:44:12 MET DST