程序代写代做代考 Answer Set Programming prolog compiler AI asp Prolog

Prolog

Introduction to Prolog 1

Prolog 1

MSc Computing

Fariba Sadri
With thanks to Keith Clark for the use of some of his lecture

material

Introduction to Prolog 2

Prolog

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

Particularly favoured for applications in

• AI

• expert system and

• computational linguistics.

Relevance to courses next term:

• Introduction to Artificial Intelligence: uses Prolog

• Argumentation and Multi-Agent Systems: uses Prolog

• Logic-based Learning course: uses HAIL (Hybrid Abductive Inductive

Learning) and ASP (answer Set Programming)

• We will be using Sicstus Prolog and

Windows. You can use Linux.

• Program files are saved as plain text.

• Prolog tutorials in lab 219 on Thursdays in

week 5 (2 November), and other Thursday

(will be annonced).

Introduction to Prolog 3

• Assessment is by:

– An assessed lab exercise and

– Lab examination in Jan

• Possible Mock test in week 11 (unassessed)

Introduction to Prolog 4

Introduction to Prolog 5

Example:

A very short Prolog program
Recall from Predicate Logic:

/* Anyone passes the MSc if they pass the exams and the project.

S (pass_exams(S)  pass_proj(S)  pass_msc(S))

S (pass_msc(S)  pass_exams(S)  pass_proj(S))

In Prolog:

% A rule:

pass_msc(S) :- pass_exams(S), pass_proj(S).

% Add a condition that S is an MSc student?

% A set of facts:

pass_exams(mary).

pass_proj(mary).

% A rule:

pass_msc(S) :- pass_exams(S), pass_proj(S).

:- corresponds to 

, corresponds to 

Introduction to Prolog 6

Comments in Programs

% This is a comment, ignored by the compiler.

You can use % when the comment is short

and runs on one line only.

Otherwise use /* …. */

/* Anything here is a comment */

Introduction to Prolog 7

How to read the rule

pass_msc(S) :- pass_exams(S),
pass_proj (S).

Declaratively:

Anyone who passes the exams and passes the project
passes the MSc.

Introduction to Prolog 8

Procedurally:

There are two readings:

1.To show that someone passes the MSc:

a) show that they pass the exams, and

b) they pass the project.

2. To find who passes the MSc:

find who passes the exams and the project.

Introduction to Prolog 9

Demo
pass_msc(S) :- pass_exams(S), pass_proj(S).

pass_msc(peter).

pass_exams(john).

pass_exams(mary).

pass_exams(bob).

pass_exams(jill).

pass_proj(john).

pass_proj(mary).

Introduction to Prolog 10

Example Queries to the

Program
| ?- pass_msc(mary).

yes

| ?- pass_msc(X). Who has passed the MSc?

X = john ? ;

X = mary ? ;

X = peter ? ;

Introduction to Prolog 11

| ?- pass_exams(X), + pass_msc(X).

Who has passed the exams but not the MSc?

X = bob ? ;

X = jill ? ;

| ?- pass_msc(john), pass_msc(mary).

Have john and mary both passed the MSc?

yes

Introduction to Prolog 12

Introduction to Prolog 13

Prolog syntax

A Prolog program is a sequence of clauses.

A clause has the form:

H :- C1, …, Ck. conditional clause

or H. unconditional clause

A terminating

‘.’,

‘.’ or

‘.’

is essential after each clause.

Introduction to Prolog 14

Prolog syntax cntd. H :- C1,…,Ck.
H and each Ci is an atomic formula of the form:

p(t1,…, tn) or p

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 p of H.

Each Ci is sometimes referred to as a call or condition.

Later we will see that we can have more complex
conditions.

Introduction to Prolog 15

Logical reading

A conditional clause

H :- C1,…,Ck. is read as:

X1 . . . Xm(H  C1 …  Ck)

where the Xi are all the variables that occur in the clause,

or equivalently:

X1, . . ., Xi ( H  Xi+1, … , Xm (C1  …  Ck))

where Xi+1,..,Xm are variables that only appear in the conditions
of the clause.

(slide 24 of predicate logic part 2 set)

In Predicate Logic:

If X does not occur free in B then

X Y (B  A)  Y(B  X A)

E.g. X,Y(has_criminal_record(Y) 

convicted_for(Y, X))



Y(has_criminal_record(Y) 

X convicted_for(Y, X))

Introduction to Prolog 16

An unconditional clause

H. is read as:

X1 . . . Xm(H)

where the Xi are all the variables that occur in H.

E.G.

beautiful(X). is read as

X beautiful(X)

Introduction to Prolog 17

Introduction to Prolog 18

Prolog terms

• Constants – usually alphanumeric sequence of one or
more symbols beginning with a lower case letter, and
possibly containing _

e.g. bill, maryJones, mary_jones, diamond67

• 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. Suppose we want to represent data on who the winner of our

project prizes are.
We have a lot of choices.

Introduction to Prolog 19

We can use the function names below
name(First_name, Surname)

proj(Department, Degree, Year)
e.g. proj(computing, msc, 2016)

Introduction to Prolog 20

E.g. project prize winners

Using winner/2:

winner(name(alex, jones), proj(computing, msc, 2016)).

Using winner/6:

winner(alex, jones, proj, computing, msc, 2016).

Using winner_proj /5:

winner_proj(alex, jones, computing, msc, 2016).

Using winner_proj /4:

winner_proj(name(alex, jones), computing, msc, 2016).

Introduction to Prolog 21

Predicate names have the same syntax as

constants, i.e.

alphanumeric sequence of one or more symbols

beginning with a lower case letter, and

possibly containing _

E.g. pass_msc

appointed

win2017

Introduction to Prolog 22

Introduction to Prolog 23

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’

’*****’

There are two other kinds of terms,

strings and

lists

(we will look at lists in detail later).

Introduction to Prolog 24

Introduction to Prolog 25

Facts and Rules

If an unconditional clause:

contains no variables then the clause is called a fact.

E.g. pass_exams(mary).

no_of_children(john, 3).

All other Prolog clauses are called rules.

E.g.

drinks(john) :- anxious(john).

anxious(X):- has_driving_test(X).

covers(sky, X).

Introduction to Prolog 26

Prolog queries

A query is a conjunction of conditions, i.e.

?- C1, . . . , Cn .

Each Ci is a condition/call (as in a clause).

?- is a prompt displayed by Prolog.

Terminating . is needed.

Introduction to Prolog 27

Prolog queries cntd

?- C1, . . . , Cn .

If there are no vars in query, then the query is a request for a
report on whether or not the query, as given, is a logical
consequence of the program clauses.

E.g.

?- pass_msc(john).

Has john passed the MSc?

?- no_of_children(john, 3).

Does John have 3 children?

If the query ?- C1, . . . , Cn . 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.

Introduction to Prolog 28

Introduction to Prolog 29

C θ

Cθ

p(X) {X=john} p(john)

q(X,Y) {X=1, Y=2}

q(X,Y) {X=1, Y=f(Z)}

q(X, Y) {X=1, Y=f(X)}

q(X, f(X)) {X=g(5)}

Introduction to Prolog 30

Example query

?- pass_msc(X).

i.e. “Is there someone, X, who has passed the MSc?”

or “Who passed the MSc?

It is a request for an answer

θ ={X=name}

such that

pass_msc(X)θ

i.e. pass_msc(name)

follows from the program clauses or

for confirmation that there is no such θ (no such name).

Program:

pass_exams(mary).

pass_proj(mary).

pass_msc(S) :- pass_exams(S), pass_proj(S).

Query:

?- pass_msc(X).

Answer:

X=mary
Introduction to Prolog 31

Introduction to Prolog 32

Example Program

The Trade Program
sells(usa, grain, japan).

sells(Seller, P, Buyer) :- produces(Seller, P), needs(Buyer, P).

produces(oman, oil).

produces(iraq, oil).

produces(japan, computers).

produces(germany, cars).

produces(france, iron).

needs(germany, iron).

needs(britain, cars).

needs(japan, cars).

needs(_, computers).

needs(Country, oil) :- needs(Country, cars).

Introduction to Prolog 33

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(_, computers).

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).

Introduction to Prolog 34

Demo

?-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 = computers;

Introduction to Prolog 35

?-produces(X,Y).

X = oman, Y= oil;

X = iraq, Y= oil;

X = japan, Y= computers;

X = germany, Y= cars;

X = france, Y= iron;

?-produces(X, rice).

?-produces(britain, cameras).

?-produces(iraq, Y), needs(britain, Y).

Y = oil

| ?- sells(X, Y, britain).

| ?- sells(X, _, britain).

| ?- sells(_,_, britain).

Introduction to Prolog 36

Introduction to Prolog 37

Exercise: Trade Program

Write Prolog Queries for the following:

1. Does Britain sell oil to the USA?

2. Who sells grain to who?

3. Who sells oil to Britain?

4. Who sells what to Germany?

5. Who sells something to Germany?

Introduction to Prolog 38

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 39

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 40

Example Program Work-Manager

% worksIn(Person, Department)

worksIn(bill, sales).

worksIn(sally, accounts).

% deptManager(Department, Manager)

deptManager(sales, joan).

deptManager(accounts, henry).

% managerOf(Worker, Manager)

managerOf(joan, james).

managerOf(henry, james).

managerOf(james, paul).

Introduction to Prolog 41

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.

Introduction to Prolog 42

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) ; in_prison(X).

The Prolog rule

p:-c1;c2.

has the same meaning as the two rules

p:-c1.

p:-c2.

Exercise: Prove in logic that

pc1 c2  (p  c1) (p  c2).

inelligible_to_vote(X) :- under_age(X) ;

in_prison(X).

Can be written as:

inelligible_to_vote(X) :- under_age(X).

inelligible_to_vote(X) :- in_prison(X).

Introduction to Prolog 43

Arithmetic

• is/2 is a primitive Prolog predicate for evaluating arithmetic
expressions.

• The call
X is Exp

where Exp is an arithmetic expression, unifies X with the value of
Exp

• Operators work in the same way as in most languages + – * /

• X can be a number or an unbound variable but not another
expression.

• Note that at the time of evaluation of condition
X is Exp, Exp must be ground, i.e. contain no unbound vars.

• Arithmetic values can be compared using built in relations:

<, =< , >, >=

Arithmatic Examples

• X is 2*4 (unifies/binds X to 8)

• W=4, U is 25*W, X is U/5

(unifies/binds U to 100, and X to 20)

• X is 4, X is X+1 (will fail!)

• X is 4, NewX is X+1

(unifies/binds NewX to 5)

• The difference between is and =.

Try X is 2+1, Y=2+1.

X1 =:= X2

Succeeds if X1 and X2 evaluate to the same

number.

X1 == X2

Succeeds if X1 and X2 do not evaluate to

the same number.

Introduction to Prolog 46

Example: Factorial

The Factorial of a non-negative integer N,

denoted N!,

is the product of N and all the non-negative, non-zero integers
below it.

O! = 1

1! = 1

2! = 2 * 1

3! = 3*2*1

4! = 4*3*2*1

N! = N*(N-1)*(N-2)* …*1 if N>0

N! = N*(N-1)! if N>0

In Prolog

Let fact(N, FN) stand for factorial of N is FN.

Introduction to Prolog 48

O! = 1

fact(0,1).
* we can also write this as:
fact(N, FN):- N=0, FN=1.
*/

N! =

N*(N-1)!
if N>0

fact(N, FN):-
N>0,
X is N-1,

fact(X,FX),
FN is N*FX.

Example Uses

Find the factorial of a number

?- fact(4,X).

X=24

Check the factorial of a number

?- fact(3,6)
yes

Combined in any conjunction

?- fact(4, X), fact(5, Y), Y is 5*X.

X = 24, Y = 120 yes

Cannot use invertibly:

?- fact(X,2).

! Instantiation error in argument 1 of >/2

because the condition: N > 0 needs N to be
known.

trace / notrace

| ?- trace.

% The debugger will first creep — showing everything

(trace)yes% trace

See the difference between:

| ?- fact(2,X).

| ?- fact(X,2).

| ?- notrace.

1 1 Call: fact(2,_523) ?

2 2 Call: 2>0 ?

3 2 Exit: 2>0 ?

3 2 Call: _1162 is 2-1 ?

4 2 Exit: 1 is 2-1 ?

4 2 Call: fact(1,_1172) ?

5 3 Call: 1>0 ?

6 3 Exit: 1>0 ?

6 3 Call: _4519 is 1-1 ?

7 3 Exit: 0 is 1-1 ?

7 3 Call: fact(0,_4529) ?

8 3 Exit: fact(0,1) ?

8 3 Call: _1172 is 1*1 ?

9 3 Exit: 1 is 1*1 ? ?

4 2 Exit: fact(1,1) ?

9 2 Call: _523 is 2*1 ?

10 2 Exit: 2 is 2*1 ? ?

1 1 Exit: fact(2,2) ?

X = 2 ?

Yes

% trace

| ?- notrace.

1 1 Call: notrace ?

% The debugger is switched off

Yes

| ?-

Published by admin

Leave a Reply Cancel reply