S7CS/CH/Oct., 2002
Prolog
pam tom
bob liz
ann pat
jim
figure 1 A family tree.
Prolog is a programming language for symbolic, non-numeric computations. It is specially well suited for solving problems that involve objects and relation between objects.
First simple Prolog Program
¨ Use an editor to input the following program named family:
parent( pam, bob ).
parent( tom, bob ).
parent( tom, liz ).
parent( bob, ann ).
parent( bob, pat ).
parent( pat, jim ).
¨ The program developed a relation as the family tree in fig. 1.
¨ Enter the IF-Prolog environment, where you can see the prompt ?-, get the Prolog program by enter consult(family).
¨ Then you can have query on the family relation as follows:
?- parent ( bob, pat ).
Answer from Prolog:
yes
?-
¨ Study the following I-O carefully:
Input / Outputparent ( liz, pat ). / no
parent ( tom, ben ). / no
parent ( X, liz). / X = tom
parent ( bob, X ). / X = ann;
X = pat
parent ( X, Y). / X = pam
Y = bob;
X = tom
Y = bob;
X = tom
Y = liz;
...
parent(Y, jim), parent(X, Y) / X = bob
Y = pat
Basic elements of Prolog
¨ Clause.
i. A Prolog program consists of clauses. Each clause terminates with a period (.).
ii. Each of these clauses declares one fact, e.g. the parent-child relation.
iii. In general, a relation is defined as the set of all its instances.
¨ Rules.
i. It specifies things that are true if the same condition is satisfied.
ii. e.g. To formulate the logical statement,
" X and Y, (" means “for all”)
Y is an offspring of X if
X is a parent of Y.
The following Prolog clause is used.
offspring (Y, X) :- parent (X, Y).
iii. Each rule have :
a) condition part (on RHS as body ).
b) conclusion part (on LHS as head ).
¨ Two more examples
i. " X and Y,
X is the mother of Y if
X is a parent of Y and
X is a female.
Formulate the statement by the following PROLOG statements,
mother(X, Y) :- parent(X, Y), female(X).
ii. " X and Y,
X is a sister of Y if
(1) both X and Y have the same parent, and
(2) X is a female.
Formulate the statement by the following PROLOG statements,
sister( X, Y) :-
parent ( Z, X),
parent ( Z, Y),
female ( X).
¨ Recursive rule definition. Defining a rule based on a definition of itself defined before.
e.g. " X and Z,
X is a predecessor of Z if
X is a parent of Z or
$ Y ' ($ means “there exists”, ' means “such that”)
(1) X is a parent of Y, and
(2) Y is a predecessor of Z.
Formulate the logical statement as
predecessor ( X, Z) :-
parent ( X, Z).
predecessor ( X, Z) :-
parent ( X, Y),
predecessor ( Y, Z).
¨ Here is a complete program family:
parent( pam, bob). % Pam is a parent of Bob
parent( tom, bob).
parent( tom, liz).
parent( bob, ann).
parent( bob, pat).
parent( pat, jim).
female( pam). % Pam is female
male( tom). % Tom is male
male( bob).
female( liz).
female( ann).
female( pat).
male( jim).
offspring( Y, X) :- % Y is an offspring of X if
parent( X, Y). % X is a parent of Y
mother( X, Y) :- % X is the mother of Y if
parent( X, Y), % X is a parent of Y and
female( X). % X is female
grandparent( X, Z) :- % X is a grandparent of Z if
parent( X, Y), % X is a parent of Y and
parent( Y, Z). % Y is a parent of Z
sister( X, Y) :- % X is a sister of Y if
parent( Z, X),
parent( Z, Y), % X and Y have the same parent and
female(X), % X is female and
different( X, Y). % X and Y are different
predecessor( X, Z) :- % Rule pr1 : X is predecessor of Z
parent( X, Z).
predecessor( X, Z) :- % Rule pr2 : X is predecessor of Z
parent( X, Y),
predecessor( Y, Z).
How does Prolog answer questions? --- Backtracking
¨ To answer a question, Prolog tries to satisfy all the goals. (‘To satisfy a goal’ means to demonstrate the goal logically follows from the facts and rules in the program.)
¨ Prolog backtracks to the original goal in order to try an alternative way to derive the top goal.
¨ e.g. Given the question for the program family:
?- predecessor ( tom, pat).
1st : X = tom, Z = pat
2nd : Rule 1 not true. Backtrack rule 2.
3rd : Match with parent (tom, bob).
4th : Recursive search for predecessor ( bob, pat).
5th : match with rule 1, i.e. parent ( bob, pat).
** Answer found ----> yes.
¨ The complete execution trace is shown in fig. 2.
predecessor(tom, pat)by rule pr1 / by rule pr2
parent(tom, pat) / parent(tom, Y)
predecessor(Y, pat)
no
figure 2 Execution trace
Declarative and Procedural meaning of programs
¨ The declarative meaning is concerned with the relations defined by the program, i.e. determining WHAT the output of the program is.
¨ The procedural meaning is concerned with the relations actually evaluated by the Prolog system, i.e. determining HOW the output is obtained.
Syntax and Meaning
PROLOG page 7
S7CS/CH/Oct., 2002
Data objects
¨ Constants (i.e. atoms and number)
i. Strings can consist of the following characters:
upper-case letters A, B, ... , Z
lower-case letters a, b, ... , z
digits 0, 1, 2, ... , 9
special characters such as
+ - * / < > = : . & _ ~
data objects
simple objects structure
constants variables
atoms numbers
Figure 3 Data objects in Prolog
PROLOG page 7
S7CS/CH/Oct., 2002
ii. Atoms can be constructed in 3 ways:
Strings of letters. starting with a lower-case letter.
e.g. x___y, miss_Jones
Strings of special characters. without predefined meaning
e.g. the string ‘:-’ cannot be used.
Strings of characters. enclosed in single quotes. e.g. 'Mom', 'Sarah Jones'
iii. Numbers in Prolog
Integer: -16383 to 16383
Real: not used very much, only decimal point form is used
PROLOG page 7
S7CS/CH/Oct., 2002
¨ Variables
i. Starting with an upper-case letter or an underscored character.
ii. e.g. X, Result, _x23
iii. The lexical scope of variable name is one clause, i.e. if the same name occurs in two clauses, it signifies two different variables.
Figure 4 Some simple geometric objects
¨ Structures
4
5
(6, 4)
i. Structured objects are objects that have several components.
2
3
P2 = (2,3)
T
ii. The components themselves can, in turn, be structures.
1
(4, 2)
iii. e.g. date( Day, may, 1983).
1
2
3
4
5
6
7
8
P1 = (1,1)
(7, 1)
iv. The figure in fig. 4 shows the relations of points, segments and triangles.
v. To formulate in Prolog:
P1 = point( 1, 1)
P2 = point( 2, 3)
S = seg( point( 1, 1), point( 2, 3))
T = triangle( point( 4, 2), point( 6, 4), point( 7, 1))
vi. The corresponding tree representation is shown in fig. 5.
P1 = point S = seg
1 1 point point
1 1 2 3
T = triangle
point point point
4 2 6 4 7 1
Figure 5. Tree representation of the objects in Figure 4.
Matching
¨ Given 2 terms, we say that they match if :
i. they are identical, or
ii. the variables in both terms can be instantiated to objects in such a way that after the substitution of variables by these objects the terms become identical.
¨ Thus, matching is a process that takes as input two terms and checks whether they match.
¨ The general rules to decide whether two terms, S and T, match are as follows:
i. If S and T are constants, then S and T match only if they are the same object.
ii. If S is a variable and T is anything, then they match, and S is instantiated to T. Conversely, if T is a variable then T is instantiated to S.
iii. If S and T are structures then they match only if
a) S and T have the same principal functor, and
b) all their corresponding components match.
¨ The resulting instantiation is determined by the matching of the components.
¨ e.g. Defining structures for recognizing horizontal and vertical line segments.
vetical( seg( point( X, Y1), point( X, Y2))).
horizontal( seg( point( X1, Y), point( X2, Y))).
Conjunction and Disjunction
¨ In general, a question to the Prolog system is a list of goals separated by commas.
¨ A comma between goals thus denotes the conjunction of goals (AND)
¨ Prolog also accepts the disjunction of goals (OR). It is lower in order of precedence, and denoted by separated with the semicolon.
¨ e.g. translate( Number, Word) :-
Number = 1, Word = one;
Number = 2, Word = two;
Number = 3, Word = three.
*** Example: monkey and banana
¨ A Monkey is at the door and the banana is hang on from the ceiling the room.
¨ The state of the “world” is determined by
The position of monkey in the room.
Is the monkey on the box or on the floor?
The position of the box.
Does the monkey have the banana?
¨ Four types of movement by the monkey: grasp banana, climb box, push box, walk around
¨ Sample Prolog program to find the solution.
% move( State1, Move State2): making Move in State1 results in State2;
% a state is represented by a term:
% state( MonkeyHorizontal, MonkeyVertical, BoxPosition, HasBanana)
move( state( middle, onbox, middle, hasnot), % Before move
grasp, % Grasp banana
state( middle, onbox, middle, has) ). % After move
move( state( P, onfloor, P, H),
climb, % Climb box
state( P, onbox, P, H) ).
move( state( P1, onfloor, P1, H),
push( P1, P2), % Push box from P1 to P2
state( P2, onfloor, P2, H) ).
move( state( P1, onfloor, B, H),
walk( P1, P2), % Walk from P1 to P2
state( P2, onfloor, B, H) ).
% canget( State): monkey can get banana in State
canget( state( _, _, _, has) ). % can 1 : Monkey already has it
canget( State1) :- % can 2 : Do some work to get it
move( State1, Move, State2), % Do something
canget( State2). % Get it now
¨ Given the initial state to see if there is a solution as follows,
?- canget( state( atdoor, onfloor, atwindow, hasnot)).
state( atdoor, onfloor, atwindow, hasnot)
walk( atdoor, P2)
state( P2, onfloor, atwindow, hasnot)
climb backtrack push( P2, P2’)
P2 = atwindow
state( atwindow, onbox, atwindow, hasnot) state( P2’, onfloor, P2’, hasnot)
No move climb
possible state( P2’, onbox, P2’, hasnot)
grasp
P2’ = middle
state( middle, onbox, middle, has)
Figure 6 The monkey’s search for the banana. The search starts at the top node and proceeds downwards, as indicated. Alternative moves are tried in the left-to-right order. Backtracking occurred once only.
Danger of indefinite looping
¨ Considering the following clause in a program:
p :- p.
The question
?- p.
will cause Prolog entering an indefinite loop .
¨ Another example of indefinite looping
i. Reorder the Monkey and Banana thus the ‘walk’ clause appears first.
ii. Then the execution of our original goal of the previous section,
?- canget( state( atdoor, onfloor, atwindow, hasnot)).
would cause an indefinite looping. (Why? The monkey will only walk around.)
Program variations through reordering of clauses and goals.
¨ Consider the four versions of the predecessor program.
pred1( X, Z) :- pred2( X, Z) :-
parent( X, Z). parent( X, Y),
pred1( X, Z) :- pred2( Y, Z).
parent( X, Y), pred2( X, Z) :-
pred1( Y, Z). parent( X, Z).
pred3( X, Z) :- pred4( X, Z) :-
parent( X, Z). pred4( X, Y),
pred3( X, Z) :- parent( Y, Z).
pred3( X, Y), pred4( X, Z) :-
parent( Y, Z). parent( X, Z).
¨ All pred1, pred2 and pred3 can reach a solution.
¨ The pred4 is hopeless.
List
¨ The list is a simple data structure widely used in non-numeric programming.
¨ e.g. [ann, tennis, tom, skiing]
¨ A list consists of two things
i. the first term, called the head of the list.
ii. the remaining part of the list, called the tail.
¨ The head can be any Prolog object; the tail has to be a list.
¨ In If-Prolog, a list can be regarded as an empty list or a structure whose functor is dot ‘.’, and that has two arguments: the head and the tail.
¨ Thus, the general principle for structuring data objects in Prolog also applies to lists of any length. It can be illustrated by the following example.
¨ e.g.
?- List1 = [a,b,c],
List2 = '.'(a, '.'(b, '.'(c, []))).
List1 = [a,b,c]
List2 = [a,b,c]
?- Hobbies = '.'( tennis, '.'( music, [])),
Hobbies = [ skiing, food],
L = [ ann, [ tennis, music], tom, [skiing, food]].
Hobbies = [ tennis, music]
Hobbies = [ skiing, food]
L = [ ann, [ tennis, music], tom, [skiing, food]]
¨ Prolog provides another notational extension, the vertical bar, which separates the head and the tail. The notation is