CSE2AIF/CSE4002

Artificial Intelligence
Fundamentals

Lecture 5 and 6
Automated Reasoning -
PROLOG
PROLOG
The most commonly used programming languages in AI.

PROLOG stands for PROgramming in LOGic; A declarative

language.

Invented by Alain Colmerauer at the University of Aix-

Marseille in 1971. Implemented in 1972.
PROLOG

PROLOG facilitates
◼ Propositional logic reasoning

◼ First order logic reasoning

◼ Higher order logic reasoning

SWI-PROLOG is a PROLOG executor, which can be

downloaded from (http://www.swi-prolog.org/)

The website (http://www.swi-prolog.org/) also provides

PROLOG tutorials, SWI-PROLOG reference manual and other
support.
An Example
There were seven people in a family reunion - Anna, Samantha,
Rebecca, Elizabeth, Michael, Jack and Tom. Each individual
provides some information about the family relations.
Rebecca said: " Samantha is my daughter."
Michael stated: " Jack is my son."
" I am Michael's daughter." Samantha said
Anna mentioned, " Rebecca is one of my parents."
Elizabeth declared, " I am one of Michael's parents."
" Rebecca is my daughter.“ Tom told.
Finally, Jack mentioned "Rebecca, Samantha, Anna and
Elizabeth are female and Michael, Tom and I are male. "
An Example

Based on the statements, one can easily deduce facts such as

“Michael is Samantha’s father”
“Rebecca is Anna’s mother”
or even
“Elizabeth is a grandmother of jack”
etc.

The inference can also be conducted by using a computer.

PROLOG is designed to solve problems of this type.
An Example

A logic program can be written in PROLOG to reflect the

statements

Firstly, a number of predicates which will be used in the PROLOG

program, need to be defined as below.

daughter(X, Y) X is a daughter of Y
son(X, Y) X is a son of Y
parent(X, Y) X is a parent of Y
mother (X, Y) X is the mother of Y
father(X, Y) X is father of Y
male(X) X is male
An Example

Then the logic program can be written in PROLOG to reflect the

statements as below

daughter(samantha, rebecca). Rebecca said: " Samantha is my daughter."

son(jack, michael). Michael stated: " Jack is my son."

daughter(samantha, michael). “ I am Michael's daughter." Samantha said
parent(rebecca, anna). Anna mentioned, " Rebecca is one of my parents."
parent(elizabeth, michael).
Elizabeth declared, " I am one of Michael's
daughter(rebecca, tom). parents."
male(tom). "Rebecca is my daughter.“ Tom told.
male(michael).
Finally, Jack mentioned "Rebecca, Samantha,
male(jack). Anna and Elizabeth are female and Michael, Tom
and I are male. "
An Example
parent(X, Y) :- daughter(Y, X).
parent(X, Y) :- son(Y, X).
mother(X, Y) :- parent(X, Y), not(male(X)).
father(X, Y) :- parent(X, Y), male(X).

Assume that the program above is saved as familyRelation.pl

and is loaded into the PROLOG executor.
An Example
We can obtain/derive new information from the program by
entering a query into the PROLOG executor.

For example, for the query

?_ father(michael, samantha).
the PROLOG executor will answer “true" which means the fact
“Michael is Samantha’s father” can be derived from the program.

For the query

?_ mother(rebecca, jack).
the PROLOG executor will answer “false". This means that
“Rebecca is Jack’s mother” can not be derived from the program.
An Example
For the query
?_ parent(X, samantha).
the PROLOG executor will provide answer :
X = michael
X = rebecca

This means that

“Michael is a parent of Samantha”
and
“Rebecca is a parent of Samantha”
can be derived from the program.
An Example
We can add extra rules such as

grandMother(X, Y) :- mother(X, Z), parent(Z, Y).

grandFather(X, Y) :- father(X, Z), parent(Z, Y).

into our PROLOG program, so that queries such as

?_ grandMother(X, samantha).
?_ grandFather(X, Y).

can be answered.
Constants, Variables, Terms,
Predicates and Atoms
In PROLOG, datatypes are not defined, though numerical calculations
are supported.

1 Constants
A constant in PROLOG is a value which can never be changed.
A constant can be a value of an integer, a decimal number, a sequence
of symbols, a string, a list or a structure.
In PROLOG, a constant may/may not have an identifier. The
identifier of a constant may contain letters, digits, underscores, and
should start with a lower-case letter.

Example
a12_3, xY, 50, 3.1415926, pi, samantha and jack are constants.
_a, Mary, _50 are not constants.
Constants, Variables, Terms,
Predicates and Atoms
2 Variables

A variable in PROLOG represents a value which can vary.

A variable always has an identifier. A valid identifier may
contain letters, digits and underscores and it starts with a
capital letter or an underscore.

Example
_X, Mary, Z100
are valid variable identifiers/names.
x, 10XY, ???
are invalid variable names.
Constants, Variables, Terms,
Predicates and Atoms
3 Terms

A term is either a variable or a constant.

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 14

Constants, Variables, Terms,
Predicates and Atoms
4 Predicates

In logic, a predicate is a function with only two possible values

“true” and “false”.

A predicate may be unary (takes only one parameter) or multi-

ary (takes more than one parameter). A predicate takes n
parameters is a n-ary predicate.

In PROLOG, the identifier of a predicate may contain letters,

digits, underscores and should start with a lower-case letter.
Constants, Variables, Terms,
Predicates and Atoms
Example
greater_than, positive, parent
are valid predicate names.

_greater_than, ?positive, Parent

are invalid predicate names.

greater_than, positive and parent can also be written as

greater_than/2, positive/1 and parent/2 to indicate the number of
parameters each predicate takes. ie. greater_than/2 and
parent/2 take two parameters. positive/1 takes one parameter.
Constants, Variables, Terms,
Predicates and Atoms

If p is an n-ary predicate and t1, ..., tn are terms, then

p(t1, ..., tn) is called an atom.

Example
greater_than(1, 5), greater_than(a, b), positive(1), positive(b) and
parent(micheal, jack) are atoms.
Logical Connectives

In PROLOG, logical connectives are represented as follows.

Logic PROLOG

 conjunction ,

 disjunction ;
 implication :-
 negation not
Logical Connectives
Example
In the previous PROLOG program,

parent(X, Y) :- daughter(Y, X).

mother(X, Y) :- parent(X, Y), not(male(X)).

are equivalent to

parent(X, Y)  daughter(Y, X)
mother(X, Y)  parent(X, Y) male(X)
Logic Program
1. Logic Program

A logic program is a set of program clauses. A program clause

can be a fact, a rule or a goal.
Logic Program
2. Fact
A fact represents a statement which is true.

In PROLOG, a fact normally takes the form of an atom.

p(a1, a2, ..., an).
where a1, a2, ..., an are terms and p is a predicate.

Example
daughter(samantha, rebecca).
parent(rebecca, anna).
parent(elizabeth, michael).
are facts.
Logic Program
3. Rule

A rule indicates a relation of implication (if ... then ...).

In Prolog, a rule normally takes the form :

B :- A1, A2, ..., Ak.
where B is an atom and A1, A2, ..., Ak are atoms or negation of
atoms.

B is the head(consequent) of the rule and A1, A2, ..., Ak is the

body(premise) of the rule.
Logic Programs
Example
parent(X, Y) :- daughter(Y, X).
father(X, Y) :- parent(X, Y), male(X).
are two rules.

In the rule father(X, Y) :- parent(X, Y), male(X).

father(X, Y) is the head.
parent(X, Y), male(X) is the body.
Logic Program
4. Goal

A goal is an atom or the conjunction of a number of atoms that

we want to prove.

Example
?_ mother(rebecca, jack).
is a goal.

?_ parent(X, samantha), mother(rebecca, jack).

is also a goal.
Arithmetic Calculations

PROLOG maintains some simple arithmetic calculations.

1 Arithmetic Operators

◼ “+”, “-”, “*”, “/” and “mod” are arithmetic operators.

◼ Calculation starts from the left to the right.
◼ “*”, “/” and “mod” have the higher priority than “+” and “-
”.
◼ Brackets can be used to indicate priorities.
◼ “is” is used for binding values.
Arithmetic Calculations
2 Comparing Operators

◼ “>“, “<“, “>=“ and “=<“ are the comparing operators.

◼ “=:=“, “=“ and “==“ are the operators for equal testing.
 “=:=“(arithmetic comparison – the values to be compared
must be numerical. )
 “=“ (general comparison – compares the values on the
left and right sides. If one of them hasn’t been bound,
then the value of the other side will be bound to it )
 “==“ (strict comparison - compares the values on the
left and right sides. The two values must be the same.
No value binding will be conducted.)
Arithmetic Calculations

◼ “=\=“, “\=“, and “\==“ are the operators for not

equal testing.
 “=\=“ (arithmetic)
 “\=“ (general)
 “\==“ (strict)
Arithmetic Calculations
Example

/*maxL2.pl */
/*max(X, Y, Z) finds the larger one of X and Y, and binds it to Z*/
max(X, X, X).
max(X, Y, X) :- X > Y.
max(X, Y, Y) :- Y > X.

This program finds the larger one of the first and second
parameters, and binds the larger value to the third parameter.
Arithmetic Calculations
Queries can be made to the PROLOG executor
?_ max(2, 2, X).
X=2

?- max(4.2, 2.5, X).

X = 4.2

?- max(X, 6, 8).
X=8

?- max(X, 6, 4).
False
Arithmetic Calculations
Example
Define a predicate f(N, F) to calculate the factorial of N,
N! = 1 * 2 * ... * N
and to bind N! to F.

/* factL2.pl */
/* f(N, F) calculates the factorial of N, and binds it to F */
f(0, 1).
f(N, F) :- N > 0, N1 is N - 1, f(N1, Temp), F is N * Temp.
Homework Exercise
Define the predicate sumOddEven(N, S) where N and S are
positive integers. The predicate calculates
1 + 3 + ... + N (if N is odd)
2 + 4 + ... + N (if N is even)
and binds the sum to S.
Homework Exercise (Answer)

/*sumOddEven.pl*/
sumOddEven(1, 1).
sumOddEven(2, 2).
sumOddEven(N, S) :- N > 2, NN is N - 2, sumOddEven(NN, Temp), S
is N + Temp.
Input and Output
1 Input

The built-in predicate read/1 is defined for reading from the

standard input (or a file).

read(X)
reads a term from the standard input or a file, and uses the
input value to instantiate X. The input is terminated by a full
stop.
Input and Output
2 Output

the predicate write/1 is defined for output.

write(X)
outputs the contents of X.

Example

write(X).
write(100).
write(‘Hello’).
Input and Output - Examples
Example

/* readL2.pl */
test1 :- read(X), Y = X, write(Y).
test2 :- read(X), Y == X, write(Y).
test3 :- read(X), read(Y), X == Y.

?- test1.
12.
12
true
(Y was unbound, but now is bound to the value of X)
Input and Output - Examples
?- test1.
/* readL2.pl */
anna.
test1 :- read(X), Y = X, write(Y).
anna test2 :- read(X), Y == X, write(Y).
true test3 :- read(X), read(Y), X == Y.

?- test2.
12.
false
(Y was unbound, and hence Y == X returns false)
Input and Output - Examples
?- test3.
/* readL2.pl */
12. test1 :- read(X), Y = X, write(Y).
12. test2 :- read(X), Y == X, write(Y).
true test3 :- read(X), read(Y), X == Y.

?- test3.
12.
13.
false
Input and Output

The built-in predicate tab/1 outputs tab spaces indicated by

the programmer.

The built-in predicate nl/0 outputs a new line.

Example
/* readL2.pl */
test1 :- read(X), Y = X, tab(12), write(Y).
test2 :- read(X), Y = X, nl, tabl(12), write(Y).
test3 :- read(X), read(Y), X == Y.
Class Exercise

Define the predicate abstract/0. abstract reads a numerical value

(X) from the standard input, and then outputs
X if X >= 0
-X if X < 0
Class Exercise (Answer)

/*abstract.pl*/
abstract :- nl, write('enter X '), read(X), positive(X).
positive(X) :- X < 0, Y is 0 - X, write(Y).
positive(X) :- X >= 0, write(X).
Derivation in PROLOG
Given a logic program (which is a set of facts and rules) and a
goal, the PROLOG executor evaluates the goal by selecting a
fact/rule that matches the goal.
◼ A fact matching the goal means the fact and goal have the

same predicate identifier.

◼ A rule matching the goal means the head of the rule and

the goal have the same predicate identifier

If multiple facts/rules match the goal, then the PROLOG

executor selects the first one from the top of the program.

When evaluating a rule, the PROLOG executor evaluates the

body of the rule from left to right.

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 41

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(X), studying(X).

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 42

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(X), studying(X).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 43

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(X), studying(X).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 44

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(X), studying(X).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 45

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(X), studying(X).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 46

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(X), studying(X).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 47

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(X), studying(X).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 48

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(X), studying(X).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 49

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(X), studying(X).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 50

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(b), studying(b).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 51

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(b), studying(b).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 52

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(b), studying(b).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 53

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(b), studying(b).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 54

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(b), studying(b).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 55

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(b), studying(b).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 56

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(b), studying(b).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 57

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(X), studying(X).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 58

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(c), studying(c).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 59

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(c), studying(c).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 60

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(c), studying(c).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 61

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(c), studying(c).

Answers X=a

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 62

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(c), studying(c).

Answers X=a;
X=c

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 63

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(X), studying(X).

Answers X=a;
X=c

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 64

Derivation in PROLOG
Example

Given the program below and the goal -? student(X).

student(a).
person(b).
person(c).
studying(c).
student(X) :- person(X), studying(X).

Answers X=a;
X=c

CSE5ALR Artificial Intelligence – Logic & Reasoning Lecture 2 PROLOG 65

Recursion
Recursion is an important programming skill. It enable us to
repeatedly break a complicated problem into a smaller version
of the same problem until the solution can be easily reached.
Recursion

In PROLOG, recursion refers to the phenomenon that a clause

contains a call to itself (ie. the same predicate identifier
appears in the head and the body of a rule).

Recursion also refers to the phenomenon that there are a set

of clauses among which one calls another, and hence makes the
reasoning into a circle.

Recursion is frequently used in PROLOG programming.

Recursion
Example
Below are some examples of recursive clauses.

ancestor(X, Y) :- ancestor(X, Z), parent(Z, Y).

connected(X, Y) :- connected(X, Z), connected(Z, Y).

haveChicken (X) :- haveEgg(X).

haveEgg(X) :- haveChicken(X).
Recursion
In PROLOG, the structure of a recursive program contains
◼ A recursive rule or a set of recursive rules

◼ A terminating case to end the recursion

Recursion
Example
In the program below p(X, Y, Z) calculates the Yth power of X,
and binds the value to Z.

/*powerL3.pl*/
p(X, 0, 1).
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.

In this program,
p(X, 0, 1).
defines a terminate case/condition
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.
is the recursive rule.
Recursion - How does it work
p(X, 0, 1).
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.
?-p(5, 2, Z).

5 2
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.
Recursion - How does it work
p(X, 0, 1).
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.
?-p(5, 2, Z).

5 2 2 1 2 5 1
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.
Recursion - How does it work
p(X, 0, 1).
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.
?-p(5, 2, Z).

5 2 2 1 2 5 1
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.

5 1
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.
Recursion - How does it work
p(X, 0, 1).
p(X, Y, Z) :- A > 0, A is Y - 1, p(X, A, B), Z is B * X.
?-p(5, 2, Z).

5 2 2 1 2 5 1
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.

5 1 1 0 1 5 0
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.
Recursion - How does it work
p(X, 0, 1).
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.
?-p(5, 2, Z).

5 2 2 1 2 5 1
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.

5 1 1 0 1 5 0
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.

5 0 1
p(X, Y, Z).
Recursion - How does it work
p(X, 0, 1).
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.
?-p(5, 2, Z).

5 2 2 1 2 5 1
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.

5 1 1 0 1 5 0 1
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.

5 0 1
p(X, Y, Z).
Recursion - How does it work
p(X, 0, 1).
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.
?-p(5, 2, Z).

5 2 2 1 2 5 1
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.

5 1 5 1 0 1 5 0 1 5 1 5
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.

5 0 1
p(X, Y, Z).
Recursion - How does it work
p(X, 0, 1).
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.
?-p(5, 2, Z).

5 2 2 1 2 5 1 5
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.

5 1 5 1 0 1 5 0 1 5 1 5
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.

5 0 1
p(X, Y, Z).
Recursion - How does it work
p(X, 0, 1).
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.
?-p(5, 2, Z).

5 2 25 2 1 2 5 1 5 25 5 5
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.

5 1 5 1 0 1 5 0 1 5 1 5
p(X, Y, Z) :- Y > 0, A is Y - 1, p(X, A, B), Z is B * X.

5 0 1
p(X, Y, Z).
Class Exercise

Write a program to calculate the nth fibonacci number f(n).

fib(1) = 1
fib(2) = 1
fib(n) = fib(n-1) + fib(n-2)
Class Exercise (Answer)
Write a program to calculate the nth fibonacci number.
fib(1) = 1
fib(2) = 1
fib(n) = fib(n-1) + fib(n-2)

/* fibL3.pl */
fib(1, 1).
fib(2, 1).
fib(N, Z) :- N > 2, N1 is N-1, N2 is N-2, fib(N1, Temp1),
fib(N2, Temp2), Z is Temp1+Temp2.
Iteration
Iteration (a loop) can be created by using recursive rules.
Iteration
Example
/* loopL3.pl */
loop(Index, Index) :- body(Index).
loop(Index, End) :- Index < End, body(Index), Index1 is Index + 1,
loop(Index1, End).
body(Index) :- write('In the loop with index = '), write(Index), nl.

The program creates a loop which is equivalent to the following

python code :

while Index <= End:

print(Index++)
Iteration
?- loop(2, 1).
false

?- loop(1, 3).
In the loop with index = 1
In the loop with index = 2
In the loop with index = 3
true
Iteration
?- loop(2, 2).
In the loop with index = 2
true
Iteration
A loop is normally created using two clauses. The two clauses
have the same head. One clause defines the terminating case
while the other executes the body, and then move the loop
into the next iteration.

Defines the terminating condition.

(first parameter = second parameter)
End of the loop

loop(Index, Index) :- body(Index).

loop(Index, End) :- Index < End, body(Index), Index1 is Index + 1,
loop(Index1, End).

Change index
Start a new iteration
Iteration
Example

loop(X) :- X == end.
loop(X) :- X \== end, body(X), write('enter X '), read(Y), loop(Y).
body(X) :- write(' X = '), write(X), nl.

Where is the point that the loop ends?

How does the loop move into the next iteration?
Class Exercise
Write a program to calculate the average weight of a group of
new born babies. The program repeatedly reads the weight of
each new born till 0 is entered. It then calculates the average
weight.

A sample of the program execution can be

3 ?- calculate.
enter a weight or 0 to terminate the program 3.4.
enter a weight or 0 to terminate the program 3.5.
enter a weight or 0 to terminate the program 3.0.
enter a weight or 0 to terminate the program 3.3.
enter a weight or 0 to terminate the program 0.
The average weight is 3.3
true
Class Exercise (Answer)
/* averageWeight.pl */
/* repeatedly reads a weight and calculates the average weight */

calculate :- average(0, 0).

average(S, N) :- input(X), loop(S, N, X).
loop(S, N, X) :- X > 0, S1 is S + X, N1 is N + 1, average(S1, N1).
loop(S, N, X) :- X = 0, write('The average weight is '), A is S/N,
write(A).
input(X) :- write('enter a weight or 0 to terminate the program '),
read(X), nl.
Selection
Selection can be constructed by using the pre-defined
predicate ->/0. The if ... then ... else clause can be defined as
such

if_test(X) :- (condition(X) -> then_comp(X); else_comp(X)).

 Selection
Example
The code below outputs ‘positive’ if X is greater than 0. Otherwise, it
outputs ‘non-positive’

if_test(X) :- (X > 0 -> write('positive'); write('non-positive')), nl.

Class Exercise
Write the program voting.pl that acts as a vote counting
machine. It repeatedly reads people’s vote (1 for “support” and
-1 for “against”). The counting is terminated when 0 is
entered. It, then, displays the numbers of support votes and
against votes.
Class Exercise (Answer)
/* voting.pl */
voting :- select(0, 0).

select(S, A) :- input(X), (X = 0 -> terminate(S, A); continue(S, A, X)).

continue(S, A, X) :- (X > 0 -> S1 is S + 1, select(S1, A) ; A1 is A + 1,
select(S, A1)).

input(X) :- write('type 1 for support or -1 for against or 0 to terminate

the voting program '), read(X), nl.

terminate(S, A) :- write(S), write(' support votes and '), write(A), write('

against votes.'), nl.
Lists
A list is a sequence of elements. Each of the elements can be a
constant, an atom, a list, or a structure. (We will learn
structures in the next lecture.)

The length of a list may vary during the program execution.

This means that elements can be inserted/deleted to/from
the list.

Elements are separated by using a comma ','

A list is included in a pair of square brackets.

Lists
Example

[32, may, [positive(a), positive(b)], [a, b]]

is a list of 4 elements.

[]
is an empty list (ie. a list contains no element).
Lists
The pre-defined predicate nth1/3 can be used to extract an
element of specific position.

Example
?- nth1(2, [1, 2, 3, 4], X).
X=2

A list can be divided into two components: the head and the
tail. The first element of the list is the head; the rest is the
tail of the list. The head is a term, and the tail is a list.

The notation [ | ] is used to separate the head and the tail. If

the list contains only one element, then the element makes the
head, and the tail is an empty list.
Lists
Example
Assume the program below is loaded into the PROLOG executor.
weekdays([monday, tuesday, wednesday, thursday, friday]).
like([pear]).

?-weekdays(X).
X = [monday, tuesday, wednesday, thursday, friday].

?-weekdays([First_day|Rest_of_days]).
First_day = m onday.
Rest_of_days = [tuesday, wednesday, thursday, friday].
Lists
?-weekdays([First_day,Second_day|Rest_of_days]).
First_day = monday.
Second_day = Tuesday.
Rest_of_Days = [wednesday, thursday, friday].

?-like([X|Y]).
X = pear.
Y = [].
Lists
Example
/* memberL.pl */
memberL(X, [X|T]).
memberL(X,[Y|T]) :-memberL(X,T).

What is the purpose of memberL/2 ?

Lists
Example
/* memberL.pl */
memberL(X, [X|T]).
memberL(X,[Y|T]) :- memberL(X,T).

?- memberL( c, [a, b, c, d]).

true

?- memberL(a, [1, 2, 3, 4]).

false
Lists
?- memberL(X, [a, b, c]).
X=a;
X=b;
X=c;
false

?- memberL(a, [X, b, c]).

X=a;
false
List
The pre-built predicate member/2 functions exactly like
memberL/2

Example
?- member(4, [3, 5, 4, 6]).
true

?- member(4, [1, 2, 3]).

false
Lists
Example
week_days( [monday, tuesday, wednesday, thursday, friday]).
writeL([]).
writeL([H|T]) :-write(H), nl, writeL(T).

What is the purpose of writeL/1 ?

Lists
Example
week_days( [monday, tuesday, wednesday, thursday, friday]).
writeL([]).
writeL([H|T]) :-write(H), nl, writeL(T).

?- week_days(X), writeL(X).
monday
tuesday
wednesday
thursday
friday

X = [monday,tuesday,wednesday,thursday,friday] ;
false
Lists
Example
week_days([monday, tuesday, wednesday, thursday, friday]).
lengthL([],0).
lengthL([H|T], N):-lengthL(T, N1), N is N1+1.

What is lengthL/2 for?

Lists
Example
week_days([monday, tuesday, wednesday, thursday, friday]).
lengthL([],0).
lengthL([H|T], N):-lengthL(T, N1), N is N1+1.

?- week_days(X), lengthL(X, Y).

X = [monday, tuesday, wednesday, thursday, friday],
Y = 5;
false

?_lengthL( [[purple, blue], [white, grey]], X).

X = 2;
false
Lists
length/2 is a pre-built predicate for calculating length of a list.
Lists
Example
maxL([X], X) :- !.
maxL([X|T],X):-maxL(T,M), X>M.
maxL([X|T],M):-maxL(T,M), X=<M.

What is the purpose of maxL/2 ?

Lists
Example
maxL([X], X) :- !
maxL([X|T],X):-maxL(T,M), X>M.
maxL([X|T],M):-maxL(T,M), X=<M.

?- maxL([2, 1, 5, 4, 7], X).

X = 7;
false

?- maxL([5, 7, X], 20).

X = 20;
false
Lists
Example
maxL([X], X) :- !
maxL([X|T],X):-maxL(T,M), X>M.
maxL([X|T],M):-maxL(T,M), X=<M.

?- maxL([2, 1, 5, 4, 7], 20).

What can be the output?

Lists
Example
del([], X, []).
del([X|T], X, Rest) :- del(T, X, Rest).
del([Y|T], X, [Y|Rest]):- X \= Y, del(T, X, Rest).

del(T, X, R) deletes the element X from the list T and assigns

the rest of the list to R.

?- del([b, a, c, a], a, R).

R = [b, c];
false

The pre-built predicate delete/3 functions exactly the same.

Lists
Example
week_days([monday, tuesday, wednesday, thursday, friday]).
appendL([], L2, L2).
appendL([H|T], L2, [H|L3]) :- appendL(T, L2, L3).

appendL(List1, List2, NewList) appends List2 to the end of List1

and return the result to NewList.

[a, b, c] [g, h]

[b, c] [a, g, h]

[c] [a, b, g, h]

[] [a, b, c, g, h]
Lists
Example
week_days([monday, tuesday, wednesday, thursday, friday]).
appendL([], L2, L2).
appendL([H|T], L2, [H|L3]) :- appendL(T, L2, L3).

appendL(List1, List2, NewList) appends List2 to the end of List1

and return the result to NewList.

?- week_days(X), appendL(X, [saturday, sunday], Week).

X = [monday, tuesday, wednesday, thursday, friday],
Week = [monday, tuesday, wednesday, thursday, friday,
saturday, sunday] ;
false
Lists
The pre-built predicate forall/2 can be used to traverse a list,
and preform an action.

Example
?- forall(member(X, [purple, blue, green, orange, red]),
(write(X),tab(4))).

purple blue green orange red

true
Class Exercise
Define predicate reverseL/2. In reverseL(X, Y), X is a list and Y
is the reverse of X.
Class Exercise (Answer)
/* reverse.pl */
appendL([], L2, L2).
appendL([H|T], L2, [H|L3]) :- appendL(T, L2, L3).

reverseL([X], [X]) :- !.
reverseL([H|T], R) :- reverseL(T, R1), appendL(R1, [H], R).
Strings
A string is a sequence of symbols enclosed in a pair of single
quotation marks.

A string is stored as a list of ASCII codes in the computer

memory. Consequently, list operations can be applied to a
string.
Strings
Example
‘hello’, ‘there’

In the machine, they are stored as

[104,101,108,108,111]
[116,104,101,114,101]
Strings
A built-in predicate name/2 can be utilized to convert between
a string and a list of ASCII codes.

The first parameter is a string while the second is a list.

Strings
Example
Assume the program below is loaded

st1(‘hello’).
st2(‘there’).

appendL( [], L, L).

appendL( [X|L1], L2, [X|L3]):- appendL(L1, L2, L3).
Strings
?- st1(X), st2(Y), appendL(X, Y, Z), name(W,Z).

X = [104,101,108,108,111]
Y = [116,104,101,114,101]
Z = [104,101,108,108,111,116,104,101,114,101]
W = hellothere.

?- name(apple, X), name(pear, Y), appendL(X, Y, Z), name(W, Z).

X = [97, 112, 112, 108, 101],
Y = [112, 101, 97, 114],
Z = [97, 112, 112, 108, 101, 112, 101, 97, 114],
W = applepear.
Class Exercise
Define the predicate convert/2. convert(X, Y) converts X which
is a string of lower-case chars to Y which is the string of
capitalised chars. (Note that the ASCII codes for ‘A’ is 65;
for ‘a’ is 97)

For example
?- convert(‘abba’, Y).
Y = ABBA;
false
Class Exercise (Answer)
/* convert.pl */
modify([], X, []).
modify([H|T], X, [NH|NT]) :- NH is H - X, modify(T, X, NT).

convert(S, NS) :- name(S, L), modify(L, 32, NL), name(NS, NL).

Structures

PROLOG does not support global variables. The scope of a

variable is within a clause.

Example
postive(X) :- X > 0.
greaterThan(X, Y) :- greaterThan(X, Z), greaterThan(Z, Y).

The X in the first clause and the X in the second clause are
irrelevant.

Data structures can be built with user-defined predicates to

pass value from one clause to the other. A data structure is an
atom or the composition of atoms.
Structures

Example
student(may, smith, 21061985, sbcs, 2021).
book(prolog, ivan, bratko, cs, ai, ai_language).
borrow (21061985, prolog).

student, book and borrow are structures. They are single-layer

data structures (ie. their arguments are terms). If the
structures are loaded in the prolog executor, we can enter
queries as below.

?- student(may, smith, X, Y, Z).

X = 21061985,
Y = sbcs,
Z = 2021;
Structures
?- book(U, V, W, cs, ai, X).
U = prolog,
V = ivan,
W = bratko,
X = ai_language;

?_ borrow(X, prolog), student(Y, Z, X, _, _).

X = 05061985,
Y = may,
Z = smith;
Structures
we can also build multi-layered structures with user-defined
predicates. A multi-layered structure is a structure that
contains other structures (the composition of atoms).
Structures
Example
student(names(may, smith), 21061985, sbcs, 2021).
book(prolog, author(ivan, bratko), category(cs, area(ai,
subject(ai_language)))).

?- studnet(X, Y, Z, 2021).
X = names(may, smith),
Y = 21061985,
Z = sbcs;

?- book(prolog, X, Y).
X = author(ivan, bratko),
Y = category(cs, area(ai, subject(ai_language)));
Structures
functor/3 is a built-in predicate that can be utilized to examine
a structure.

If X is a structure, functor(X, Y, Z) binds the predicate symbol

of X to Y and the number of arguments of X to Z.
Structures
Example
book(prolog, author(ivan, bratko), category(cs, area(ai,
subject(ai_language)))).

?- book(prolog, X, Y), functor(X, NX, NAX), functor(Y, NY, NAY).

X = author(ivan, bratko),
Y = category(cs, area(ai, subject(ai_language))),
NX = author,
NAX = 2,
NY = category,
NAY = 2;
Structures

arg/3 is a built-in predicate which can be used to get an

argument from a structure.

Let Y be the structure, arg(X, Y, Z) takes the Xth argument of

Y and instantiate it to Z.
Structures
Example

?- arg(3, student(may, smith, 21061985, sbcs, 2021), Z).

Z = 21061985;

?- arg(5, student(may, X, 05061985, sbcs, Y), Z).

Y = Z;
Structures
functor/3 and arg/3 can be used together to build structures.

Example

?- functor(X, names, 2), arg(1, X, may), arg(2, X, smith).

X = names(may, smith)

?- functor(X, names, 2), arg(1, X, may), arg(2, X, smith),

functor(Y, student, 2), arg(1, Y, X), arg(2, Y, 20).
X = names(may, smith),
Y = student(names(may, smith), 20)
Class Exercise
Write a program that changes the structure

bookL([prolog, cs, ai, 112.95])

into

book(title(prolog), category(cs, area(ai)), price(112.95))

Class Exercise (Answer)
/* change.pl */

bookL([prolog, cs, ai, 112.95]).

change(B) :- bookL([X1, X2, X3, X4]), functor(A, area, 1), arg(1, A,
X3), functor(T, title, 1), arg(1, T, X1), functor(C, category, 2), arg(1,
C, X2), arg(2, C, A), functor(P, price, 1), arg(1, P, X4), functor(B,
book, 3), arg(1, B, T), arg(2, B, C), arg(3, B, P).
Built-in Predicates
The built-in operator =.. is used to convert between a list and
a structure. The left side of the operator is the structure and
right side is the list.
a(b1, b2, ..., bn) =.. [a, b1, b2, ..., bn]

Example
?- person(names(may, smith), 670903) =.. Y.
Y = [person, names(may, smith), 670903] ;

?- X =.. [names, may, smith].

X = names(may, smith);
Built-in Predicates
The built-in predicate call/1 will invoke a system evaluation.

call(X) will put X as a goal for the system to evaluate.

Built-in Predicates
The built-in predicate clause/2 can be used to search for the
clauses satisfying certain conditions.

clause(X, Y) searches all the user-defined clauses existing in

the PROLOG executor, matches X with the head and Y with
the body. In the case the clause is a fact, it will assign “true”
to Y.
Built-in Predicates
Example
assume the program below is loaded
loop(Index, Index) :- body(Index).
loop(Index, End) :- Index < End, body(Index), Nindex is Index +
1, loop(Nindex, End).
body(Index) :- write('In the loop with index = '), write(Index), nl.

?- clause(loop(X, Y), Z).

X = Y,
Z = body(Y) ;

Z = (X<Y, body(X), _G441 is X+1, loop(_G441, Y));

false
Built-in Predicates
loop(Index, Index) :- body(Index).
loop(Index, End) :- Index < End, body(Index), Nindex is Index +
1, loop(Nindex, End).
body(Index) :- write('In the loop with index = '), write(Index), nl.

?- clause(body(X), Y).

Y = (write('In the loop with index = '), write(X), nl) ;

false
Built-in Predicates
The built-in predicate assert/1 add an atom or a clause into the
database of the PROLOG executor. All data being asserted
will disappear when the PROLOG executor is halt.

Example
1 ?- assert(rain(yesterday)).
true.

2 ?- assert(rain(today)).
true.

3 ?- rain(X).
X = yesterday ;
X = today.
Built-in Predicates
4 ?- assert(rain(X)).
true.

5 ?- rain(anyDay).
true.
Built-in Predicates
The built-in predicate retract/1 functions in the opposite way as
assert/1. retract(X) deletes the occurrence of X in the database
of the PROLOG executor.
Built-in Predicates
Example
1 ?- assert(rain(yesterday)), assert(rain(today)).
true.

2 ?- rain(X).
X = yesterday ;
X = today.

2 ?- retract(rain(X)).
X = yesterday ;
X = today.

3 ?- rain(X).
false.