Introduction to Prolog

Contents:

Prolog programs as databases

We show below a Prolog program consisting entirely of simple clauses or facts. This set of facts is a database about a family. Note that all the gender facts are grouped together, then all the father facts, then all the mother facts. Many versions of Prolog demand that similar clauses be grouped together. 

/* family.pl - a simple database for a family */
gender(al,male).
gender(anne,female).
gender(arthur,male).
gender(amber,female).
gender(boris,male).
gender(barbara,female).
gender(betty,female).
gender(buck,male).
gender(carla,female).
gender(charles,male).
gender(cora,female).
gender(cuthbert,male).
gender(cecilia,female).
gender(calvin,male).

father(arthur,buck).
father(al,buck).
father(amber,buck).
father(anne,boris).
father(barbara,charles).
father(betty,cuthbert).
father(boris,charles).
father(buck,calvin).

mother(al,barbara).
mother(anne,betty).
mother(arthur,barbara).
mother(amber,barbara).
mother(boris,carla).
mother(barbara,carla).
mother(betty,cora).
mother(buck,cecilia).
We can load this database into a Prolog interpreter. Below we show how to do this using BinProlog 4.00, which is available on our UNIX system scott now and should be available on other systems later. In fact, you can get Windows95 and DOS versions from scott. We named our Prolog database "family.pl". 

scott.astate.edu> bp

BinProlog 4.00 Copyright (C) Paul Tarau 1992-1995
by FTP from:   clement.info.umoncton.ca
E-MAIL to  : binprolog@info.umoncton.ca
(C-ified standalone)
(with heap GC enabled)
Finished loading system C-code (23203 instructions).
Finished loading user C-code (4 instructions).
?- [family].
compiling(to(mem),family.pl,...)
bytes_used(code(2208),strings(122),symbols(152),htable(1536),total(4018))
compile_time(183)
?-
The code to load family.pl was just [family]. Now the interpreter is waiting for us to query it. Every query must end with a period. When we query the interpreter, it will give us the first answer it finds, based on the facts in the database. If we want more answers, we enter a semicolon. If we don't want any more answers to that query, we just enter a carriage return. Thus consider the sequence that follows. 

?- father(X,Y).
X=arthur,
Y=buck;

X=al,
Y=buck;

X=amber,
Y=buck;

X=anne,
Y=boris;

X=barbara,
Y=charles;

X=betty,
Y=cuthbert;

X=boris,
Y=charles;

X=buck,
Y=calvin

no
?-
The "no" simply indicates that there were no more answers. Prolog will answer "yes" or "no" depending on the truth or falsehood of a simple query. Thus: 

?- mother(al,betty).
no
?- mother(al,barbara).
yes
?-
We can build more complex queries like the following, to find a grandmother of al. 

?- mother(al,X),mother(X,Y).
X=barbara,
Y=carla

yes
?-
By now you have observed that identifiers that start with an upper case letter are variables, and those that start with lower case letters are constants.

Rules

We can add some intelligence to our facts by adding a clause that tells how to figure out from the simple clauses whether Y is a parent of X. The rules we add are 

parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).
The symbol ':=' should be read as "if". Now we can query as follows. 

?- parent(al,Y).
Y=buck;

Y=barbara

yes
?-
We can now build a rule that uses the parent rules. 

grandfather(X,Y) :- parent(X,Z),father(Z,Y).
and ask questions like 

?- grandfather(anne,Y).
Y=charles;

Y=cuthbert;

no
?-
The scope of variables is one clause; there is no such thing as a global variable.

Backtracking

When Prolog tries to answer a query, it goes through a matching process. It tries to match the predicates on the right-hand side of the rule from left to right, binding variables when it finds a match. If a match fails, it may be because of the bondings in matches to the left. In that case, the interpreter backtracks - it returns to the nearest previous binding and tries to find a different match. If that fails, it backtracks some more. We can trace what is going on. In the next sequence, we are going to consult our file family.pl instead of compiling it. This will allow the interpreter to see the text of the original rules. 

?- consult(family).
% using compile/1 is MUCH faster
consulting(family.pl)
consulted(family.pl,time(50))
yes
?-
Now we can use the builtin trace predicate to see what happens as one of our rules is matched. 

?- trace(grandfather(al,Daddio)).
Call: grandfather(al,_2409) : -
 !!! dynamic(grandfather/2)
 Call: parent(al,_2959) : -
  !!! dynamic(parent/2)
  Call: father(al,_2959) : -
   !!! dynamic(father/2)
  Exit: father(al,buck)
 Exit: parent(al,buck)
 Call: father(buck,_2409) : -
  !!! dynamic(father/2)
 Exit: father(buck,calvin)
Exit: grandfather(al,calvin)
Daddio=calvin;

Redo: grandfather(al,calvin)
 Redo: father(buck,calvin)
 Fail: father(buck,_2409)
 Redo: parent(al,buck)
  Redo: father(al,buck)
  Fail: father(al,_2959)
  Call: mother(al,_2959) :-
   !!! dynamic(mother/2)
  Exit: mother(al,barbara)
 Exit: parent(al,barbara)
 Call: father(barbara,_2409) : -
  !!! dynamic(father/2)
 Exit: father(barbara,charles)
Exit: grandfather(al,charles)
Daddio=charles;

Redo: grandfather(al,charles)
 Redo: father(barbara,charles)
 Fail: father(barbara,_2409)
 Redo: parent(al,barbara)
  Redo: mother(al,barbara)
  Fail: mother(al,_2959)
 Fail: parent(al,_2959)
Fail: grandfather(al,_2409)
no
?-
Notice in the last sequence that when the interpreter runs out of facts of the form father(barbara,_), it tries to find facts of the form mother(barbara,_) to satisfy the parent predicate. Note that rules in the database are tried in the order they appear in the database.
We can make Prolog print out all the answers to a question by deliberately making it fail, using the fail predicate. 

?- grandfather(X,Y),write('X='),write(X),write(', Y='),write(Y),nl,fail.
X=arthur, Y=calvin
X=al, Y=calvin
X=amber, Y=calvin
X=anne, Y=charles
X=al, Y=charles
X=anne, Y=cuthbert
X=arthur, Y=charles
X=amber, Y=charles
no
?-
You might also try saying 

?- interactive(no).
and then just grandfather(X,Y).

Availability

We currently have two Prolog implementations available.
This page is maintained by: Robert F. Rossa who can be reached at rossa@csm.astate.edu
Last revised on: 12/11/96
Return to Computer Science and Mathematics page
Return to the Computer Science Topics Page