Logic Programming and Prolog
Read: Scott, Chapter 12
1
Lecture Outline
n Logic programming n Prolog
n Language constructs: facts, rules, queries
n Search tree, unification, backtracking, backward
chaining
Programming Languages CSCI 4430, A. Milanova 2
Prolog
n Download and install SWI Prolog on laptop! n Write your Prolog program and save in .pl file,
e.g., snowy.pl
n Run swipl (Prolog interpreter) on command line n Load your file: ?– [swnowy].
n Issue query at prompt: ?– snowy(C).
n J.R.Fisher’s Prolog Tutorial: http://www.cpp.edu/~jrfisher/www/prolog_tutorial/contents.html
Programming Languages CSCI 4430, A. Milanova 3
Why Study Prolog?
n Declarative programming and logic programming
n Prolog is useful in a variety of applications n Rule-based reasoning
n Natural-language processing n Database systems
n Prolog and SQL have a lot in common
n Practice of important concepts such as first-
order logic
Programming Languages CSCI 4430, A. Milanova 4
Logic Programming
n Logic programming is declarative programming
n Logic program states what (logic), not how (control)
n Programmer declares axioms n In Prolog, facts and rules
n Programmer states a theorem, or a goal (the what) n In Prolog, a query
n Language implementation determines how to use the axioms to prove the goal
Programming Languages CSCI 4430, A. Milanova 5
Logic Programming
n Logic programming style is characterized by
n Database of facts and rules that represent logical relations. Computation is modeled as search (queries) over this database
n Use of lists and use of recursion, which turns out very similar to the functional programming style
Programming Languages CSCI 4430, A. Milanova 6
Logic Programming Concepts
n A Horn Clause is: H ¬ B1,B2,…,Bn
n Antecedents (B’s): conjunction of zero or more terms in
predicate calculus; this is the body of the horn clause n Consequent (H): a term in predicate calculus
n Resolution principle: if two Horn clauses A ¬ B1,B2,B3 ,…, Bm
C ¬ D1,D2,D3 ,…, Dn
are such that A matches D1,
then we can replace D1 with B1,B2,B3 ,…, Bm
C ¬ B1,B2,B3 ,…, Bm,D2,D3 ,…, Dn
Programming Languages CSCI 4430, A. Milanova 7
Lecture Outline
n Logic programming n Prolog
n Language constructs: facts, rules, queries
n Search tree, unification, backtracking, backward
chaining
Programming Languages CSCI 4430, A. Milanova 8
Horn Clauses in Prolog
n In Prolog, a Horn clause is written h :- b1,…,bn.
n Horn Clause is called clause
n Consequent is called goal or head
n Antecedents are called subgoals or tail
n Horn Clause with no tail is a fact
n E.g., rainy(seattle). Depends on no other conditions
n Horn Clause with a tail is a rule snowy(X) :- rainy(X),cold(X).
Programming Languages CSCI 4430, A. Milanova 9
Horn Clauses in Prolog
n Clause is composed of terms n Constants
n Number, e.g., 123, etc.
n Atoms e.g., seattle, rochester, rainy, foo
In Prolog, atoms begin with a lower-case letter!
n Variables
n X, Foo, My_var, Seattle, Rochester, etc. In Prolog, variables begin with upper-case letter!
n Structures
n E.g., rainy(seattle), snowy(X)
n Consists of an atom, called a functor and a list of arguments
10
Horn Clauses in Prolog
n Variables may appear in the tail and head of a rule:
n c(X) :- h(X,Y).
For all values of X, c(X) is true if there exist a value of Y such that h(X,Y) is true
n Call Y an auxiliary variable. Its value will be bound to make consequent true, but not reported
by Prolog, because it does not appear in the head
Programming Languages CSCI 4430, A. Milanova 11
Prolog
n Program has a database of clauses i.e., facts and rules; the rules help derive more facts
n We add simple queries with constants, variables, conjunctions or disjunctions
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X) :- rainy(X),cold(X).
? – rainy(C).
? – snowy(C).
Programming Languages CSCI 4430, A. Milanova 12
Facts
likes(eve, pie).
likes(al, eve).
likes(eve, tom).
likes(eve, eve).
food(pie).
food(apple).
person(tom).
functors
constants
The combination of the functor and its arity (i.e., its number of arguments) is called a predicate.
Programming Languages CSCI 4430, A. Milanova 13
Queries
likes(eve, pie).
likes(al, eve).
likes(eve, tom).
likes(eve, eve).
query
food(pie).
food(apple).
person(tom).
variable
?-likes(al,eve). ?-likes(al,Who). true. answer Who=eve.
answer with
variable binding
?-likes(al,pie). ?-likes(eve,W).
false. W=pie ;
?-likes(eve,al). W=tom ;
false. W=eve .
force search for
Programming Languages CSCI 4430, A. Milanova more answers 14
Question
likes(eve, pie).
likes(al, eve).
likes(eve, tom).
likes(eve, eve).
food(pie).
food(apple).
person(tom).
?-likes(eve,W). W = pie ;
W = tom ;
W = eve .
Prolog gives us the answer precisely in this order: first W=pie then W=tom and finally W=eve.
Can you guess why?
15
Harder Queries
likes(eve, pie).
likes(al, eve).
likes(eve, tom).
likes(eve, eve).
and
?-likes(al,V) , likes(eve,V). V=eve.
?-likes(eve,W) , person(W). W=tom
?-likes(A,B).
A=eve,B=pie ; A=al,B=eve ; A=eve,B=tom ;
A=eve,B=eve. ?-likes(D,D). D=eve.
food(pie).
food(apple).
person(tom).
16
Harder Queries
likes(eve, pie).
likes(al, eve).
likes(eve, tom).
likes(eve, eve).
food(pie).
food(apple).
person(tom).
same binding
?-likes(eve,W),likes(W,V).
W=eve,V=pie ; W=eve,V=tom ; W=eve,V=eve.
?-likes(eve,W),person(W),food(V).
W=tom,V=pie ; W=tom,V=apple
or
?-likes(eve,V),(person(V);food(V)).
V=pie ; V=tom
Programming Languages CSCI 4430, A. Milanova 17
Rules
likes(eve, pie).
likes(al, eve).
likes(eve, tom).
likes(eve, eve).
food(pie).
food(apple).
person(tom).
Add a rule to the database:
rule1:-likes(eve,V),person(V).
?-rule1.
true
Programming Languages CSCI 4430, A. Milanova 18
Rules
likes(eve, pie).
likes(al, eve).
likes(eve, tom).
likes(eve, eve).
food(pie).
food(apple).
person(tom).
rule1 :- likes(eve,V),person(V).
rule2(V) :- likes(eve,V),person(V).
?-rule2(H).
H=tom
?-rule2(pie).
false.
rule1 and rule2 are just like any other predicate!
Programming Languages CSCI 4430, A. Milanova 19
Queen Victoria Example
male(albert).
male(edward). Put all clauses in file
female(alice). family.pl female(victoria). parents(edward,victoria,albert).
parents(alice,victoria,albert).
?- [family]. Loads file family.pl true.
?- male(albert). A query true.
?- male(alice).
false.
?- parents(edward,victoria,albert).
true.
?- parents(bullwinkle,victoria,albert).
false.
Programming Languages CSCI 4430, A. Milanova 20
cf Clocksin and Mellish
Queen Victoria Example
?-female(X). a query
X = alice ; ; asks for more answers
X = victoria.
n Variable X has been unified to all possible values
that make female(X) true.
n Variables are upper-case, functors (predicates and
constants) are lower-case!
Programming Languages CSCI 4430, A. Milanova 21
Queen Victoria Example
n Facts alone do not make interesting programs. We need variables and deductive rules.
sister_of(X,Y) :- female(X),parents(X,M,F),
parents(Y,M,F).
?- sister_of(alice, Y).
Y = edward
false.
Programming Languages CSCI 4430, A. Milanova 22
Another Prolog Program
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X) :- rainy(X),cold(X).
?- [snowy].
?- rainy(C).
?- snowy(C).
Programming Languages CSCI 4430, A. Milanova 23
Lecture Outline
n Logic programming n Prolog
n Language constructs: facts, rules, queries n Search tree, unification, rule ordering,
backtracking, backward chaining
Programming Languages CSCI 4430, A. Milanova 24
Logical Semantics
n Prolog program consists of facts and rules
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X):-rainy(X),cold(X).
Rules like snowy(X):- rainy(X),cold(X). correspond to logical formulas:
“X[snowy(X) ¬ rainly(X) ^ cold(X)] /* For every X, X is snowy, if X is rainy and X is cold */
Programming Languages CSCI 4430, A. Milanova 25
Logical Semantics
n A query such as ?- rainy(C). triggers resolution. Logical semantics does
not impose restriction in the order of application of resolution rules
C = seattle
C = rochester
C = rochester
C = seattle
Programming Languages CSCI 4430, A. Milanova
26
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X):-rainy(X),cold(X).
Procedural Semantics
?- snowy(C).
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X):-rainy(X),cold(X).
Find the first clause in the database whose head matches the query. In our case this is clause
snowy(X) :- rainy(X),cold(X)
Then, find a binding for X that makes rainy(X) true; then,
check if cold(X) is true with that binding
n If yes, report binding as successful
n Otherwise, backtrack to the binding of X, unbind and consider the next binding
n Prolog’s computation is well-defined procedurally by search tree, rule ordering, unification, backtracking, and backward chaining
27
Question
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X):-rainy(X),cold(X).
snowy(troy).
What does this query yield?
?- snowy(C).
Answer:
C = rochester ;
C = troy.
Programming Languages CSCI 4430, A. Milanova 28
Procedural Semantics
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X) :- rainy(X),cold(X).
snowy(C)
success
snowy(X)
AND
X = rochester
_C = _X
X = seattlerainy(X) OR
cold(seattle)
fails; backtrack.
cold(X)
cold(rochester)
rainy(seattle) rainy(rochester)
Programming Languages CSCI 4430, A. Milanova
29
Prolog Concepts: Search Tree
OR levels:
parent: goal (e.g., rainy(X))
children: heads-of-clauses (rainy(…))
ORDER: from left to right AND levels:
parent: goal (e.g., snowy(X))
children: subgoals (rainy(X), cold(X))
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X):-rainy(X),cold(X).
?- snowy(C).
ORDER: from left to right
snowy(C)
snowy(X)
AND
rainy(X)
OR
rainy(seattle) rainy(rochester)
cold(X)
cold(rochester)
30
Prolog Concepts: Unification
n At OR levels Prolog performs unification
n Unifies parent (goal), with child (head-of-clause) n E.g.,
n snowy(C) = snowy(X) n success, _C = _X
n rainy(X) = rainy(seattle) n success, X = seattle
n parents(alice,M,F) = parents(edward,victoria,albert) n fail
n parents(alice,M,F) = parents(alice,victoria,albert) n success, M = victoria, F = albert
In Prolog, = denotes unification, not assignment!
31
Prolog Concepts: Unification n A constant unifies only with itself
n E.g., alice=alice, but alice=edward fails
n Two structures unify if and only if (i) they have the same functor, (ii) they have the same number of arguments, and (iii) their arguments unify recursively
n E.g., rainy(X) = rainy(seattle)
n A variable unifies with anything. If the other thing has a value, then variable is bound to that value. If the other thing is an unbound variable, then the two variables are associated and if either one gets a value, both do
32
Prolog Concepts: Backtracking If at some point, a goal fails, Prolog backtracks rainy(seattle).
to the last goal (i.e., last unification point) where there is an untried binding, undoes current binding and tries new binding (an
alternative OR branch), etc.
snowy(C)
_C = _X
rainy(rochester).
cold(rochester).
snowy(X):-rainy(X),cold(X).
?- snowy(C).
snowy(X)
AND
cold(seattle)
fails; backtrack.
cold(X)
cold(rochester)
X = seattlerainy(X) OR
rainy(seattle) rainy(rochester)
Programming Languages CSCI 4430, A. Milanova
33
Prolog Concepts: Backward Chaining
n Backwardchaining:starts from goal, towards facts
? – snowy(rochester).
snowy(rochester):-
rainy(rochester),
cold(rochester)
n Forwardchaining:startsfrom facts towards goal
? – snowy(rochester).
rainy(rochester)
snowy(rochester):-
rainy(rochester),
cold(rochester)
rainy(rochester)
———————- —————————–
snowy(rochester):-
cold(rochester)
cold(rochester)
———————- —————————–
snowy(rochester). snowy(rochester).
cold(rochester)
snowy(rochester):-
cold(rochester)
Programming Languages CSCI 4430, A. Milanova 34
Exercise
takes(jane, his).
takes(jane, cs).
takes(ajit, art).
takes(ajit, cs).
classmates(X,Y):-takes(X,Z),takes(Y,Z).
?- classmates(jane,C).
Draw search tree for query.
What are the bindings for C?
Programming Languages CSCI 4430, A. Milanova 35
The End
Programming Languages CSCI 4430, A. Milanova 36