11/5/2009

Prolog
Prolog is a high level declarative programming language based on a subset of predicate logic. It is a logic programming language.

Prolog 1
MSc Computing Fariba Sadri
With thanks to Keith Clark for the use of some of his lecture material

Particularly favoured for applications in AI expert system and computational linguistics. It was developed in the early 1970s through the theoretical studies of Professor Robert Kowalski at Imperial College and Edinburgh Alain Colmerauer in Marseille, France, and the first compiler was written by David H.D. Warren in Edinburgh, Scotland.

Introduction to Prolog

Introduction to Prolog

Example In logic
We will be using Sicstus Prolog and Windows. Program files are saved as plain text.
S (pass_exams(S) pass_cwks(S) pass_projs(S) pass_msc(S)) pass_exams(john) pass_cwks(john) pass_projs(john) L |- pass_msc(john). But it is not the case that L |- pass_msc(mary).
Introduction to Prolog 3 Introduction to Prolog 4

11/5/2009

Example in Prolog
S (pass_msc(S) pass_exams(S) pass_cwks(S) pass_projs(S) pass_exams(john) pass_cwks(john) pass_projs(john)
pass_msc(S) :- pass_exams(S), pass_cwks(S), pass_projs(S). pass_exams(john). pass_cwks(john). pass_projs(john). Query to P Answer Query to P Answer Query to P Answer
Introduction to Prolog 5

: : : : : :

pass_msc(john)? yes pass_msc(mary)? no pass_msc(X)? (who passes the MSc?) X = john

Introduction to Prolog 6

Prolog syntax
Prolog program is a sequence of clauses. A clause has the form: H :- C1,...,Ck. conditional clause or H. unconditional clause A terminating .<space>, .<newline> or .<tab> is essential after each clause.

Prolog syntax cntd.

p(t1,...tn) or p

H :- C1,...,Ck.

H and each Ci is an atomic formula of the form:

Must be NO space between p and the ( p is the predicate or relation name of the atomic formula. t1,...tn are terms. Clause is about the predicate of H. Each Ci is sometimes referred to as a call or condition. Later we will see that we can have more complex conditions.
7 Introduction to Prolog 8

Introduction to Prolog

11/5/2009

Logical reading
A conditional clause H :- C1,...,Ck. is read as: X1 . . . Xm(C1 . . . Ck H) where the Xi are all the variables that occur in the clause, or equivalently: X1 . . . Xi (Xi+1,.. ,Xm(C1 . . Ck) H) where Xi+1,..,Xk are variables that only appear in the conditions of the clause. An unconditional clause H is read as: X1 . . . Xm(H) where the Xi are all the variables that occur in H.
Introduction to Prolog 9

Prolog terms
constants - usually alphanumeric sequence of one or more symbols beginning with a lower case letter e.g. bill, maryJones, elephant67 numbers - usual syntax e.g. 3, -6, 34.89 variable names - alphanumeric sequence of one or more symbols beginning with an upper case letter or _ e.g. X, Apple, _456, _ compound terms - a function name (same syntax as constant) applied to n terms of the form f(t1,..,tn), e.g. fun23(3,apple,98) Predicate names have same syntax as constants. There are three other kinds of terms - quoted constants, strings and lists (we will come to these later).
Introduction to Prolog 10

Facts and Rules

If an unconditional clause: H. contains no variables then the clause is called a fact. E.g. pass_cwks(john). no_of_children(mary, 3). All other Prolog clauses are called rules. E.g. drinks(john) :- anxious(john). anxious(X):- has_driving_test(X). needs(_, water).
Introduction to Prolog 11

Prolog queries
A query is a conjunction of conditions, i.e. ?- C1, . . . , Cn .<newline> Each Ci is a condition/call (as in a clause). ?- is a prompt displayed by Prolog. Terminating .<newline> is needed.

Introduction to Prolog

12

11/5/2009

Prolog queries cntd

?- C1, . . . , Cn .<newline> If it contains variables, the query is a request for a substitution (a set of term values) for the variables of the query such each of the conditions: C1, . . . , Cn is a logical consequence of the program clauses, or for a confirmation that there is no such . Ci is Ci with any variable in Ci (given a value in ) replaced by its assigned value. If no vars in query, it is a request for a report on whether or not the query, as given, is a logical consequence of the program clauses.
Introduction to Prolog 13

Exercise
c -----------------------------------------p(X) {X=john} p(john) q(X,Y) {X=1, Y=2} q(X,Y) {X=1, Y=f(Z)} q(X, f(X)) {X=g(5)}
C
Introduction to Prolog 14

Example query
?- drinks(X) i.e. "Is there someone, X, who drinks?" or "Who drinks? It is a request for an answer ={X=name} such that drinks(X) i.e. drinks(name) follows from the program clauses or for confirmation that there is no such (no such name).
Introduction to Prolog 15

Example Program The Trade Program

sells(usa, grain, mexico). sells(S, P, R) :- produces(S, P), needs(R, P). produces(oman, oil). produces(iraq, oil). produces(japan, cameras). produces(germany, pork). produces(france, wine). needs(britain, cars). needs(japan, cars). needs(france, pork). needs(_, cameras). needs(C, oil) :- needs(C, cars).
Introduction to Prolog 16

11/5/2009

Anonymous Variables
Variables that appear only once in a rule, can be anonymous, i.e. do not have to be named. You can use _ (underscore) to denote such variables. needs(_,cameras). happy(fs) :- likes(_, logic). But be careful! Two or more "_" in the same rule represent different variables. really_happy(fs) :- likes(_, logic), likes(_, prolog). is understood as really_happy(fs) :- likes(X, logic), likes(Y, prolog).

Example Queries and Answers

?-produces(oman, oil) yes yes means it follows from clauses ?-produces(X, oil) X = oman; ; is request for another answer X = iraq; no no means no more answers ?-produces(japan, X) X = cameras; no
Introduction to Prolog 18

Introduction to Prolog

17

Exercise Trade Program

?-produces(X,Y) X = oman, Y= oil; X = iraq, Y= oil; X = japan, Y= cameras; X = germany, Y= pork; X = france, Y= wine; no ?-produces(X, rice) no ?-produces(ussr, cameras) no ?-produces(iraq, Y), needs(britain, Y) Y = oil
Introduction to Prolog 19

Write Prolog Queries for the following: 1. 2. 3. 4. 5. Does Britain sell oil to the USA? Who sells grain to who? Who sells oil to Britain? Who sells what to Hungary? Who sells something to Hungary?

Introduction to Prolog

20

11/5/2009

Exercise Trade Program ctnd.

6. Which two countries have mutual trade with one another? 7. Which two different countries have mutual trade with one another? (X\=Z means X and Z are different from one another.) 8. Express a prolog rule for bilateral_traders(X,Z)such that X and Z are two different countries that have mutual trade with one another. 9. Express the following query in Prolog. Who produces something that is needed by both Britain and Japan? What answer(s) will Prolog give?
Introduction to Prolog 21

Scope of identifiers
The scope of a variable is just the clause or query in which it occurs. The scope of any other name (constant, function name, predicate name) is the whole program and any query.

Introduction to Prolog

22

Example Program Work-Manager

worksIn(bill, sales). worksIn(sally, accounts). deptManager(sales,joan). deptManager(accounts,henry). managerOf(joan, james). managerOf(henry,james). managerOf(james,paul).

Exercise
1. Define colleague/2, such that colleague(W1,W2) holds if W1,W2 are different workers that work in the same department. 2. Add a new clause for managerOf(W,M) to express that M is the manager of W if M is the manager of the department in which W works.
23 Introduction to Prolog 24

Introduction to Prolog

11/5/2009

Recursion
superiorOf(E,S) :superiorOf(E,S):managerOf(E,S). managerOf(E,M), superiorOf(M,S).

Paul james Joan bill

25

superiorOf/2 is a recursive predicate. The first rule for superiorOf/2 is a base case. The second rule for superiorOf/2 is a recursive rule. With earlier facts and rules we get: ?-superiorOf(bill,paul). Yes What are the answers to ?-superiorOf(X,Y). ?
Introduction to Prolog

henry sally

Introduction to Prolog

26

The logical status of yes/no answers

Program P Query Q with no variables: Prolog Answer yes Answer no Logic P |- Q not the case P |- Q

The logical status of variable binding answers

Program P Query Q with variables: Answer displayed by Prolog is (e.g. X = john) : Logic is: P |- X1 . . . Xk(Q ) where X1 . . . Xk are all the variables of Q, if any. X1 . . . Xk(Q ) is called the universal closure of Q . Answer displayed by Prolog is no : Logic is: There is no substitution , such that P |- Q

Introduction to Prolog

27

Introduction to Prolog

28

11/5/2009

More on syntax
Constants, function symbols and predicate symbols can also be any sequence of characters in single quotes, e.g. fs@doc.ic.ac.uk Sam bill green *****
Introduction to Prolog 29

Disjunction in bodies of rules and queries

In Prolog ; is the same as the logical symbol . E.g.

inelligible_to_vote(X) :-under_age(X) ; mentally_ill(X). The Prolog rule p:-c1;c2. has the same meaning as the two rules p:-c1. p:-c2. Exercise: Prove in logic that pc1 c2 (p c1) (p c2).
Introduction to Prolog 30

How does Prolog generate an answers?

Prologs proof strategy: Solve conditions in queries and bodies of rules left to right. Try clauses for a predicate in order they are given (top to bottom). So, the sequencing of query answers depends on the: Order of the clauses in the program Order of the conditions in the rules and the query
Introduction to Prolog 31

Example of order dependence

worksIn(bill, sales). worksIn (sally, accounts). deptManager(accounts, henry). deptManager(sales, joan). with def: managerOf(W,M):- worksIn(W,D), deptManager(D,M). we get: ?-managerOf(W,M). W=bill, M=joan; W=sally, M=henry with def: managerOf(W,M):-deptManager(D,M), worksIn(W,D). we get: ?-managerOf(W,M). W=sally, M=henry; W=bill, M=joan
Introduction to Prolog 32

11/5/2009

How does Prolog generate an answer?

Simple example: p:- q. p:-r. r. Query ?- p. Prologs proof strategy: p q fail r succeed
Introduction to Prolog 33

How does Prolog generate an answer?

Another Example: q(1). r(1,1). r(2,2). r(3,3). Consider a rule p(X,Y) :- q(X), r(X,Y). Compare with p(X,Y) :- r(X,Y), q(X). With a query ?- p(W,Z).
Introduction to Prolog 34

q(1). r(1,1). r(2,2). r(3,3). p(X,Y) :- q(X), r(X,Y). ?- p(W,Z). p(X,Y) :- q(X), r(X,Y). q(W), r(W,Z). {X=W, Y=Z} r(1,Z) {W=1} Succeeds {W=1, Z=1}.
Introduction to Prolog 35

q(1). r(1,1). r(2,2). r(3,3). p(X,Y) :- r(X,Y), q(X). ?- p(W,Z). r(W,Z), q(W) q(1) q(2) q(3) .. succeeds fails fails {W=1,Z=1}
Introduction to Prolog 36

11/5/2009

Unification
There is an algorithm for unifying two atomic formulas and producing the unifying substitution. h(X,a,Y) and h(b,Z,W) unify with: ={X=b, Z=a, Y=W} (or W=Y) both become: h(b,a,W)

How does Prolog generate an answer?

Let us generalize the form of a Prolog query to: {X1=t1, X2=t2, .. ,Xk=tk}-C1,C2..,Cn We interpret this as a request for an answer: {X1=t1, X2=t2 , .. ,Xk=tk } such that the universal closure of: C1 ,C2 ..,Cn is a logical consequence of the program. The universal closure is the conjunction universally quantified wrt all its variables (if any).
37 Introduction to Prolog 38

p(X,Y,h(Y)) p(Z,a,Z) unify with: ={X=h(a), Y=a, Z=h(a)} both become: p(h(a),a,h(a)) Find out more about unification by entering queries using the =/2 unification primitive. Try the query: ?- p(X,Y,h(Y)) = p(Z,a,Z).
Introduction to Prolog

Normal Prolog query

?- C1,C2..,Cn is equivalent to be the generalized query: {X1=X1, X2=X2, .. ,Xk=Xk}-C1,C2..,Cn where X1, X2, .. ,Xk} are all the variables of C1,C2..,Cn. E.g. sells(S,cameras,R) becomes: {S=S,R=R}-sells(S,cameras,R)
Introduction to Prolog 39

Query Evaluation/Reduction step

{X1=t1, X2=t2, .. ,Xk=tk}-C1,C2..,Cn Find first program clause for predicate of C1 H:-B1,..Bk with variables changed to be different from any vars in the query, such that there is a unifying substitution which makes C1 and H identical. This is an applicable clause for the query. Reduce the query to: {X1=t1, X2=t2, .. ,Xk=tk}- B1,..Bk,C2..,Cn or {X1=t1, X2=t2, .. ,Xk=tk} if n=1 (C1 is only cond.) and k=0 (clause is unconditional H). If there is no untried applicable clause for C1 fail and backtrack to the most recent preceding query for which there is an unused applicable clause. Continue by reducing that query using its next unused applicable clause.
Introduction to Prolog 40

10

11/5/2009

Successful Evaluation
Repeat reduction step until {X1=t1, X2=t2, .. ,Xk=tk} is generated This is an answer to the query. To find more answers, backtrack to most recent preceding query for which there is an unused applicable clause. Continue by reducing that query using its next untried applicable clause.
Introduction to Prolog 41

Example evaluation
Program: sells(usa, grain, mexico). sells(S, P, R) :- produces(S, P), needs(R, P). produces(japan, cameras). . needs(_,cameras). Query : 1:{E=E,I=I}-sells(E,cameras,I) 1st (and only) applicable clause is: sells(S,P,R):- produces(S,P),needs(R,P) 1={S=E, P=cameras, R=I} sells(E,cameras,I)1 sells(S,P,R)1 are both: sells(E,cameras,I).

Introduction to Prolog

42

Example evaluation cntd.

Reduced query is: 2: {E=E1,I=I1}-produces(S,P)1, needs(R,P)1 i.e. {E=E,I=I}-produces(E,cameras), needs(I,cameras) 1st (and only) applicable clause is now: produces(japan,cameras) 2 ={E=japan} Reduced query is: 3:{E=japan,I=I}-needs(I,cameras) 1st (and only) applicable clause is now: needs(_1,cameras) 3 = {_1=I}
Introduction to Prolog 43

Example evaluation cntd.

Final reduced query and only answer is: 4:{E=japan,I=I} So (I)sells(japan,cameras,I)

Introduction to Prolog

44

11

11/5/2009

Search Space/Search Tree: Tree of alternative evaluation paths

At each step the applicable clauses represent alternative evaluation paths. Prolog effectively searches this tree, left to right depth first, to find the successful evaluation paths. A path, or branch of the search tree ends in fail if the leaf query has no applicable clauses. It ends in success, if the leaf query has an empty query conjunction
Introduction to Prolog 45

Using recursive rules

parent(bill,mary). parent(jane,henry) parent(mary,jane).

ancestor(C,A):- parent(C,A). ancestor(C,A):- parent(C,P),ancestor(P,A).

Introduction to Prolog

46

1: {X=X}-ancestor(bill,X) using first ancestor/2 clause, ={C=bill,A=X} 2: {X=X}-parent(bill,X) backtrack query 1 using 1st parent/2 fact (only applicable clause) = {X=mary} 3: {X=mary} 1st solution backtrack query 1 retry 1, using second (and last) ancestor/2 clause, = {C=bill,A=X} 4: {X=X}-parent(bill,P),ancestor(P,X) no backtrack query using 1st parent/2 fact (only applicable clause) = {P=mary} 5: {X=X}-ancestor(mary,X) no backtrack query using 1st ancestor/2 clause, = {C=mary,A=X} 6: {X=X}-parent(mary,X) backtrack query 5 using 2nd parent/2 fact (only applicable clause) = {X=jane} 7: {X=jane} 2nd solution backtrack query 5 ..

Introduction to Prolog

47

12