Prolog
Language constructs
Facts, rules, queries through examples
Horn clauses
Goal-oriented semantics
Procedural semantics
How computation is performed?
Comparison to logic programming
1
Prolog, CS314 Fall 2007 BGRyder/Borgida
Logic Programming vs Prolog
Logic programming languages are neither
procedural or functional.
Based on predicate calculus -- represent using
predicates/relations:
class Student extends Person {int year; float gpa; major}
can be represented, among others, as
student(_), person(_), inYear(_,_), hasGpa(_,_),...
person(X):- student(X).
student(jane).
%% jane = new Student();
inYear(jane,3).
%% jane.year = 3;
2
Prolog, CS314 Fall 2007 BGRyder/Borgida
Logic Programming vs Prolog
Separate logic from control:
Separate the What (logic) from the How
(control)
Programmer declares what facts and relations
are true
System determines how to use facts to solve
problems
State relationships and query them as in logic
3
Prolog, CS314 Fall 2007 BGRyder/Borgida
Logic Programming
Computation engine: theorem-proving
Uses unification, resolution, backward chaining,
backtracking
Programming style: uses recursion, like
functional paradigm
Problem description is higher-level than
imperative languages
4
Prolog, CS314 Fall 2007 BGRyder/Borgida
Prolog
As database management
Start with program as a database of facts
Simple queries with constants and variables
(binding), conjunctions and disjunctions
Add to program rules to derive additional facts
Two interpretations
Declarative: based on logic
Procedural: searching for answers to queries
Search trees and rule firings can be traced
5
Prolog, CS314 Fall 2007 BGRyder/Borgida
Facts
likes(eve, pie).
likes(al, eve).
likes(eve, tom).
likes(eve, eve).
predicates
food(pie).
food(apple).
person(tom).
constants
6
Prolog, CS314 Fall 2007 BGRyder/Borgida
Queries (Asking Questions)
likes(eve, pie).
likes(al, eve).
likes(eve, tom).
likes(eve, eve).
?-likes(al,eve).
yes
query
?-likes(al, pie)
no
answer
?-likes(eve,al).
no
?-likes(person,food).
no
Prolog, CS314 Fall 2007 BGRyder/Borgida
food(pie).
food(apple).
person(tom).
variable
?-likes(al,Who).
Who=eve
?-likes(eve,W).
W=pie ;
answer with
W=tom ;
variable binding
W=eve ;
no
force search for
more answers 7
Harder Queries
likes(eve, pie).
likes(al, eve).
likes(eve, tom).
likes(eve, eve).
food(pie).
food(apple).
person(tom).
?-likes(A,B).
A=eve,B=pie ; A=al,B=eve ;
?-likes(D,D).
and
D=eve ; no
?-likes(eve,W), person(W).
W=tom
?-likes(al,V), likes(eve,V).
V=eve ; no
Prolog, CS314 Fall 2007 BGRyder/Borgida
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 ; no
?-likes(eve,W),\+likes(al,W).
W=pie ; W=tom ; no
Prolog, CS314 Fall 2007 BGRyder/Borgida
not
Rules
likes(eve, pie).
likes(al, eve).
likes(eve, tom).
likes(eve, eve).
food(pie).
food(apple).
person(tom).
What if you want to ask the same question
often? Add a rule to the database:
rule1:-likes(eve,V),person(V).
?-rule1.
yes
10
Prolog, CS314 Fall 2007 BGRyder/Borgida
Rules
likes(eve, pie).
food(pie).
likes(al, eve).
food(apple).
likes(eve, tom).
person(tom).
likes(eve, eve).
rule1:-likes(eve,V),person(V).
rule2(V):-likes(eve,V),person(V).
?-rule2(H).
H=tom ; no
?-rule2(pie).
no
Note rule1 and rule2 are just like any other predicate!
11
Prolog, CS314 Fall 2007 BGRyder/Borgida
Queen Victoria Example
male(albert).
a fact
cf Clocksin
female(alice). Facts are put in a file.
male(edward).
and Mellish
female(victoria).
parents(edward,victoria,albert).
parents(alice,victoria,albert).
?- [family].
loads file
yes
?- male(albert).
a query
yes
?- male(alice).
no
?- parents(edward,victoria,albert).
yes
?- parents(bullwinkle,victoria,albert).
no
12
Prolog, CS314 Fall 2007 BGRyder/Borgida
Queen Victoria Example, cont.
Problem: facts alone do not make interesting
programs possible. Need variables and deductive
rules.
?-female(X).
a query or proposed fact
X = alice
;
; asks for more answers
X = victoria ;
if user types <return> then
no more answers given
no
when no more answers left, return no
Variable X has been unified to all possible values
that make female(X) true.
Performed by pattern match search
Variables are capitalized, predicates and constants
are lower case
13
Prolog, CS314 Fall 2007 BGRyder/Borgida
Queen Victoria Example, cont.
sister_of(X,Y):female(X),parents(X,M,F),parents(Y,M,F).
a rule
?- sister_of(alice,Y).
Y = edward
?- sister_of(alice, victoria).
no
14
Prolog, CS314 Fall 2007 BGRyder/Borgida
Horn Clauses
(logical foundations)
A Horn Clause is: c h1^ h2 ^ h3 ^ ^hn
Antecedents(hs): conjunction of zero or more
conditions which are atomic formulae in predicate
logic
Consequent(c): an atomic formula in predicate logic
Meaning of a Horn clause:
The consequent is true if the antecedents are all true
c is true if h1, h2 , h3 , . . . , and hn are all true
likes(calvin,hobbes)
tiger(hobbes), child(calvin).
15
Prolog, CS314 Fall 2007 BGRyder/Borgida
Horn Clauses
In Prolog, a Horn clause c h1 ^ ^hn
is written c :- h1 , ... , hn.
Horn Clause is a Clause
Consequent is a Goal or a Head
Antecedents are Subgoals or Tail
Horn Clause with No Tail is a Fact
male(edward). dependent on no other conditions
Horn Clause with Tail is a Rule
father(albert,edward) :male(edward),parents(edward,M,albert).
16
Prolog, CS314 Fall 2007 BGRyder/Borgida
Horn Clauses
Variables may appear in the antecedents and
consequent of a Horn clause:
c(X1,. . . ,Xn) :- h(X1 ,.. . ,Xn,Y1 ,.. . ,Yk).
For all values of X1 ,.. . ,Xn , the formula
c(X1,. . . ,Xn) is true if there exist values
of Y1,. . . ,Yk such that the formula
h(X1 ,. . . ,Xn,Y1 ,.. . ,Yk) is true
Call Yi an auxiliary variable. Its value will be
bound to make consequent true, but not reported
by Prolog, because it doesnt appear in the
consequent.
17
Prolog, CS314 Fall 2007 BGRyder/Borgida
Declarative Semantics
Prolog program consists of facts and rules
Rules like
sister_of(X,Y):female(X),parents(X,M,F),parents(Y,M,F).
correspond to logical formulas
X,Y . sister_of(X,Y)
M,F . female(X), parents(X,M,F), parents(Y,M,F).
/* X is the sister of Y, if X is female, and there are M and F who are Xs
parents, and Ys parents */
Note that variables not in head are existentially
quantified
18
Prolog, CS314 Fall 2007 BGRyder/Borgida
Declarative Semantics
A query is a conjunction of atoms, to
be proven
If query has no variables and is provable,
answer is yes
If query has variables, proof process
causes some variables to be bound to
values (called a substitution); these are
reported
19
Prolog, CS314 Fall 2007 BGRyder/Borgida
Example
?-sister_of(X,Y):
female(X),parents(X,M,F),parents(Y,M,F).
?-sister_of(alice,Y). (1)male(albert).
Y = edward
(2)female(alice).
(3)male(edward).
?-sister_of(X,Y).
(4)female(victoria).
X = alice
(5)parents(edward,victoria,albert).
(6)parents(alice,victoria,albert).
Y = edward ;
X = alice
Y = alice ;
Example shows
no
-subgoal order of evaluation
Whats wrong here? -argument invertability
-backtracking
-computation in rule order
20
Prolog, CS314 Fall 2007 BGRyder/Borgida
10
Procedural Semantics
?-sister_of(X,Y):
female(X),parents(X,M,F),parents(Y,M,F).
First find an X to make female(X) true
Second find an M and F to make parents(X,M,F)
true for that X.
Third find a Y to make parents(Y,M,F) true for
those M,F
This algorithm is recursive; each find works on a new
copy of the facts+rules. eventually, each find must
be resolved by appealing to facts.
Process is called backward chaining.
Variables are local;
(every time rule is used, new names for X,Y,M,F)
21
Prolog, CS314 Fall 2007 BGRyder/Borgida
Prolog Rule Ordering and Unification
Rule ordering (from first to last) used in
search
Unification requires all instances of the same
variable in a rule to get the same value
Unification does not require differently
named variables to get different values:
sister_of(alice, alice)
All rules searched if requested by
successive typing of ;
22
Prolog, CS314 Fall 2007 BGRyder/Borgida
11
Example
sis(X,Y):-female(X),parents(X,M,F),
parents(Y,M,F),\+(X==Y).
?-sis(X,Y). last subgoal disallows X,Y to have same
value
X=alice
Y=edward ;
no
= means unifies with
== means same in value
23
Prolog, CS314 Fall 2007 BGRyder/Borgida
Negation as Failure
\+(P) succeeds when P fails
Called negation by failure, defined:
not(X):-X,!,fail.
not(_).
Which means
if X succeeds in first rule, then the rule is
forced to fail by the last subgoal (fail).we
cannot backtrack over the cut (!) in the first
rule, and the cut prevents us from accessing the
second rule.
if X fails, then the second rule succeeds,
because _ (or dont_care) unifies with anything.
24
Prolog, CS314 Fall 2007 BGRyder/Borgida
12
Negation by Failure
Not equivalent to logical not in Prolog
Prolog can only assert that something is
true
Prolog cannot assert that something is
false, but only that it cannot be proven
with the given rules
25
Prolog, CS314 Fall 2007 BGRyder/Borgida
Transitive Relations
Family tree
lee joe
ann mike
mary al
parents(jane,bob,sally).
parents(john,bob,sally).
parents(sally,al,mary).
parents(bob,mike,ann).
parents(mary,joe,lee).
sally bob
ancestor(X,Y) :- parents(X,Y,_).
jane john
ancestor(X,Y) :- parents(X,_,Y).
ancestor(X,Y) :- parents(X,W,_),ancestor(W,Y).
ancestor(X,Y) :- parents(X,_,W), ancestor(W,Y).
?- ancestor(jane,X).
X = bob ;
X = sally ;
X = mike ;
X = ann ;
Prolog, CS314 Fall 2007 BGRyder/Borgida
X= al ;
X = mary ;
X = joe ;
X = lee ;
No
26
13
Logic Programming vs Prolog
Logic Programming: Nondeterministic
Arbitrarily choose rule to expand first
Arbitrarily choose subgoal to explore first
Results don't depend on rule and subgoal ordering
Prolog: Deterministic
Expand first rule first
Explore first(leftmost) subgoal first
Results may depend on rule and subgoal ordering
27
Prolog, CS314 Fall 2007 BGRyder/Borgida
Minimal Prolog Syntax
<rule> ::= (<head> :- <body> .) | <fact> .
<head> ::= <predicate>
<fact> ::= <predicate>
<body> ::= <predicate> { , <predicate> }
<predicate> ::= <functor> (<term> {
,<term>} )
<term> ::= <integer> | <atom> | <variable>|
<predicate>
<query> ::= ?- <predicate>
28
Prolog, CS314 Fall 2007 BGRyder/Borgida
14
