Declarative Programming CS-205 Part II: Logic Programming (Prolog)
Logic Programming (Prolog)
1 / 1
Unification
Basic idea
Two terms unify if
they are identical terms
or if they contain variables that can be consistently instantiated with
terms in such a way that the resulting terms are equal
SOME MORE EXAMPLES
f(a,Y) and f(X,g(Z)) unify with X=a and Y=g(Z)
f(h(a,b),f(U,V)) and f(W,f(a,Z)) unify with
U = a, W = h(a,b), Z = V
f(a,g(b)) and f(a,b) DON’T unify
In Prolog ’=/2’ is used to unify two terms
2 / 1
Unification – Recursive Definition
Two terms T1 and T2 unify
1 If T1 and T2 are atomic, then T1 and T2 unify if they are the same
atom, or the same number
2 If T1 is a variable and T2 is any type of term, then T1 and T2 unify, and
T1 is instantiated to T2 (and vice versa)
3 If T1 and T2 are complex terms then they unify if:
a) They have the same functor and arity,
b) and all their corresponding arguments unify,
c) and the variable instantiations are compatible
(Note atomic means and atom or a number)
3 / 1
Unification – Occurs Check
What happens if we try to launch the goal
X = f(X) ?
Sicstus Prolog will actually make X an infinite term f(f(…))
A standard unification algorithm carries out an occurs check
If it is asked to unify a variable with another term it checks whether the
variable occurs in the term to avoid these possible infinite terms
Prolog doesn’t perform the occurs check for efficiency
If you want to enforce it use unify with occurs check
so unify with occurs check(f(X), X) will fail
4 / 1
Proof Trees
% We will give full proof tree for program:
% the men
man(bill). % fact 1
man(joe). % fact 2
% who’s rich
rich(joe). % fact 3
% married men
married to(bill,jill). % fact 4
married to(joe,ann). % tact 5
% the happy rules
happy(M) :- man(M),married to(M, ). % rule 1
happy(M) :- man(M),rich(M). % rule 2
5 / 1
Proof Trees
The proof of goal happy(X) is
happy(X)
man(X),married(X,W) man(X),rich(X)
married(bill,W)
X=bill
yes
W=jill
married(joe,W)
X=joe
yes
W=ann
rich(bill)
X=bill
no
rich(joe)
X=joe
yes
r1 r2
f1 f2 f1 f2
f4 f5 f3
Figure 1: Proof Tree for goal happy(X)
Shows three ways of proving happy(X) with X = bill; joe; joe
6 / 1
Proof search: How about this example?
interesting(X) :- loop(X);fact.
loop(X) :- loop2(X).
loop2(X) :- loop(X).
fact.
It is recommended that you trace the query ?- interesting(X). with
having set trace on: ?-trace.
7 / 1
Proof search
Prolog is using a depth-first strategy to find its responses.
Advantage: much less memory consumption than breadth-first search.
Disadvantage: Some solutions may not be found. (See previous slide.)
8 / 1