Programming in Prolog – Unification and Search Strategy
Programming in Prolog
Uni�cation and Search Strategy
Romain Barnoud
Thanks to:
Dr Fariba Sadri
Claudia Schulz
How Prolog works? An informal example
Program
parent(alice, bob).
parent(arthur, bob).
parent(anna, barbara).
parent(bob, charlie).
parent(barbara, charlie).
grandparent(X, Z) :-
parent(X, Y),
parent(Y, Z).
Query
?- grandparent(X, charlie).
Who are the grand-parents of Charlie?
1
Find a rule that matches
granparent(X, charlie)
2
Solve the query
?- parent(X,Y), parent(Y,charlie).
3 Find a rule that matches parent(X,Y)
4
parent(alice, bob) works.
Solve ?- parent(bob, charlie).
5
parent(bob, charlie) is a fact:
we have found a solution, X = alice .
6
Backtrack to point 4 to �nd other
solutions (Arthur and Anna).
Charlie
Bob Barbara
Alice Arthur Anna
Prolog terms
A prolog term is one of the following:
Atom/Constant [starts with lower case letter or anything between quotes]
john computing_MSc x123 ’logic and ai’
Number [integer or �oat]
0 42 -1729 2.718 6.626E-34
Variable [starts with an upper case letter or an underscore]
My_variable X _Anonymous _123 _
Compound term [functor(t1, . . . , tN):
functor (i.e. a constant name) applied to N terms.
N is called the arity of the term (NB: constants are 0-arity terms).]
dob(alice, 1970)
world_record(’100m’, 9.58, date(16, august, 2009))
’long function name 3’(X, cst, _)
A ground term is a term that contains no variable.
Substitutions
De�nition
A substitution θ = {X1 7→ t1,X2 7→ t2, . . . ,Xn 7→ tn} is a mapping from
variables to terms.
Applying a substitution to a term
A substitution θ = {X1 7→ t1,X2 7→ t2, . . . ,Xn 7→ tn} applied to a term t,
written tθ, is a new term s identical to t, where every occurrence of Xi has
been replaced by ti (for all i , simultaneously).
s is called an instance of t.
Examples
f(A,B) {A 7→z, B 7→ y} gives f(z,y)
g(X,f(c,X),Y) {X 7→a, Y 7→ Z} gives g(a,f(c,a),Z)
h(X,Y,Z) {X 7→W, Y 7→ f(W), Z 7→ f(b)} gives h(W,f(W),f(b))
Uni�cation
De�nition
Two terms T1 and T2 unify if
there exists a substitution θ such that T1θ ≡ T2θ.
Do the following terms unify?
If they do, give the instantiation of the variables.
john & john
3
alice & Alice
3
3 & 3.0
7
518 & ’518’
7
_000 & Variable
3
g(a, b, c) & h(a, b, c)
7
p(X, 2) & p(f(g), Y)
3
f(a,X) & f(X, b)
7
p(X, f(Y)) & p(a, X)
7
p(X, f(Y)) & p(f(f(b)), X)
3
p(X, f(Y)) & p(Y, X)
7/3
Uni�cation
De�nition
Two terms T1 and T2 unify if
there exists a substitution θ such that T1θ ≡ T2θ.
Do the following terms unify?
If they do, give the instantiation of the variables.
john & john 3
alice & Alice 3
3 & 3.0 7
518 & ’518’ 7
_000 & Variable 3
g(a, b, c) & h(a, b, c) 7
p(X, 2) & p(f(g), Y) 3
f(a,X) & f(X, b) 7
p(X, f(Y)) & p(a, X) 7
p(X, f(Y)) & p(f(f(b)), X) 3
p(X, f(Y)) & p(Y, X) 7/3
= vs. == vs. is vs. =:=
In the following, S, T and X are terms,
In the following, Expr, Expr1 and Expr2 are arithmetic expressions.
S = T will succeed i� S and T unify
S == T will succeed i� S and T are identical
X is Expr will succeed i�
the evaluation of Expr can be uni�ed with X
Expr1 =:= Expr2 will succeed i�
Expr1 and Expr2 evaluate to the same number
Opposite predicates:
= == is =:=
\= \== undef. =\=
= vs. == vs. is vs. =:=
Let’s practice!
Term 1 Term 2 = == is =:=
james james
yes yes 7 7
X emily
X=emily no 7 7
X Y
X=_0, Y=_0 no 7 7
12 5+7
no no yes yes
X 3*4
X=3*4 no X=12 7
X-Y 15-2*5
X=15, Y=2*5 no no 7
NB: ?- X=Y, X==Y. will succeed
NB:
?- X==Y, X=Y. will not
= vs. == vs. is vs. =:=
Let’s practice!
Term 1 Term 2 = == is =:=
james james yes yes 7 7
X emily X=emily no 7 7
X Y X=_0, Y=_0 no 7 7
12 5+7 no no yes yes
X 3*4 X=3*4 no X=12 7
X-Y 15-2*5 X=15, Y=2*5 no no 7
NB: ?- X=Y, X==Y. will succeed
NB:
?- X==Y, X=Y. will not
Search Strategy: How Prolog answers queries
Prolog queries
A query is a conjunction of goals: ?- G1, G2, …, Gn.
An answer to a query is a substitution θ such that
G1θ, G2θ, . . ., Gnθ are logical consequences of the program.
But how does Prolog �nd this substitution
(or prove that it does not exists)?
Search Strategy: How Prolog answers queries
Prolog Search Startegy
1 To solve a query `?- G1, G2, …, Gn.’
start with solving the �rst goal G1.
2 To solve G1, �nd a fact/clause ‘H :- B1, B2, …, Bm’,
whose head matches G1 (i.e. ∃θ such that G1θ ≡ Hθ).
If more than one clause satisfy the above condition, we have reached a
choice point: in which case, select potential clauses from top to bottom.
3.a If G1 is the only goal in the query (n = 1) and
the selected clause is a fact (`H.’, m = 0)
succeed
3.b If a such clause and substitution exist, solve query
`?- B1θ, B2θ, …, Bmθ, G2θ, …, Gnθ.’
(case 1 )
3.c If no such clause and substitution, backtrack to the last
choice point and pick the next satis�able clause.
(case 2 for
a previous goal)
3.d If there are no more choice points (i.e. all clauses
for all choice points have been tried)
fail
Search Strategy: How Prolog answers queries
Prolog Search Tree
At each step, the applicable clauses represent alternative evaluations
paths (i.e. di�erent branches of the search tree)
Prolog searches this tree, left to right, depth-�rst, to �nd a
successful evaluation paths
A path/branch of the search tree fails if the leaf query has no
applicable clause
A path/branch of the search tree succeeds if the leaf query is an
empty conjunction
Search Strategy: Example 1
Program
p(X) :- q(X,Y), r(Y).
p(X) :- s(X).
q(1,2). q(2,3). q(3,4).
r(3).
s(1). s(2).
Query
?- p(X).
?- p(X).
?- q(X,Y), r(Y).
?- r(2).
X=1,Y=2
?- r(3).
X=2,Y=3
X=2
?- r(4).
X=3,Y=4
Search Strategy: Example 1
Program
p(X) :- q(X,Y), r(Y).
p(X) :- s(X).
q(1,2). q(2,3). q(3,4).
r(3).
s(1). s(2).
Query
?- p(X).
?- p(X).
?- q(X,Y), r(Y).
X=2
?- s(X).
X=1
X=1
X=2
X=2
Search Strategy: Example 1 – Complete tree
?- p(X).
?- q(X,Y), r(Y).
?- r(2).
X=1,Y=2
?- r(3).
X=2,Y=3
X=2
?- r(4).
X=3,Y=4
?- s(X).
X=1
X=1
X=2
X=2
Search Strategy: Example 2
Program
p(2).
p(X) :- s(X).
p(X) :- t.
q(X,X).
q(1,5). q(2,3). q(3,1).
r(2). r(3). r(5).
s(1). s(4).
Query
?- p(X), q(X,Y), r(Y).
?- p(X), q(X,Y), r(Y).
?- q(2,Y), r(Y).
X=2
?- r(2).
Y=2
X=2,Y=2
?- r(3).
Y=3
X=2,Y=3
Search Strategy: Example 2
Program
p(2).
p(X) :- s(X).
p(X) :- t.
q(X,X).
q(1,5). q(2,3). q(3,1).
r(2). r(3). r(5).
s(1). s(4).
Query
?- p(X), q(X,Y), r(Y).
?- p(X), q(X,Y), r(Y).
?- s(X), q(X,Y), r(Y).
?- q(1,Y), r(Y).
X=1
?- r(1).
Y=1
?- r(5).
Y=5
X=1,Y=5
?- q(4,Y), r(Y).
X=4
?- r(4).
Y=4
Search Strategy: Example 2
Program
p(2).
p(X) :- s(X).
p(X) :- t.
q(X,X).
q(1,5). q(2,3). q(3,1).
r(2). r(3). r(5).
s(1). s(4).
Query
?- p(X), q(X,Y), r(Y).
?- p(X), q(X,Y), r(Y).
?- t, q(X,Y), r(Y).
Search Strategy: Example 2 – Complete tree
?- p(X), q(X,Y), r(Y).
?- q(2,Y), r(Y).
X=2
?- r(2).
Y=2
X=2,Y=2
?- r(3).
Y=3
X=2,Y=3
?- s(X), q(X,Y), r(Y).
?- q(1,Y), r(Y).
X=1
?- r(1).
Y=1
?- r(5).
Y=5
X=1,Y=5
?- q(4,Y), r(Y).
X=4
?- r(4).
Y=4
?- t, q(X,Y), r(Y).
What have we learned today?
What is uni�cation and how it works
What algorithm is used by Prolog to generate answers
Why the order of clauses and the order of goals in clauses/queries
matter.