Further discussions

in
Prolog programming
 What's inside?
• Prolog input/output
• Lists
• Arithmetic
• Backtracking
• CUT
• Negation
• Translation of Prolog Clauses into Formulas

Prolog Notes 2
 Input/output in Prolog
• Uses write(term) and read(term)
• Predicate write(term) causes a term to be written
to the current output stream (the monitor screen
by default)
• If term is uninstantiated, an underscore followed
by a number unique to the variable will be
output, eg, _64
• Predicate read(term) is used to read a term from
thecurrent input stream (the keyboard by default)
Prolog Notes 3
 Arithmetic in Prolog
• Predefined basic arithmetic operators:
+ addition
- subtraction
* multiplication
/ division
** power
// integer division
mod modulo, the remainder of integer division

| ?- X = 1+2.
Operator ‘is’ is a built-in
X = 1+2
procedure.
yes
| ?- X is 1+2.
X=3
yes
4
 Arithmetic in Prolog
 Another example:
| ?- X is 5/2,
Y is 5//2,
Z is 5 mod 2.
X = 2.5
Y=2
Z=1
 Since X is 5-2-1 X is (5-2)-1, parentheses can be used to indicate
different associations. For example, X is 5-(2-1).
 Prolog implementations usually also provide standard functions such as
sin(X), cos(X), atan(X), log(X), exp(X), etc.
| ?- X is sin(3).
X = 0.14112000805986721
 Example:
| ?- 277*37 > 10000.
yes

5
 Arithmetic Relations
• Are predefined comparison operators:
X>Y X is greater than Y
X<Y X is less than Y
X >= Y X is greater than or equal to Y
X =< Y X is less than or equal to Y
X =:= Y the values of X and Y are equal
X =\= Y the values of X and Y are not equal

| ?- 1+2 =:= 2+1.

yes
| ?- 1+2 = 2+1.
no
| ?- 1+A = B+2.
A=2
B=1
yes 6
 Arithmetic Functions
• Addition or multiplication are examples for arithmetic functions.
– examples: 2 + (-3.2 * X - max(17, X)) / 2 ** 5
• The max/2-expression evaluates to the largest of its two arguments
• 2 ** 5 stands for \2 to the 5th power" (25).
• Other functions available include:
– min/2 (minimum), abs/1 (absolute value), sqrt/1 (square root), and
sin/1 (sinus).1 The operator // is used for integer division. To obtain
the remainder of an integer division (modulo) use the mod-operator.
• Precedence of operators is the same as it is in mathematics,
– i.e., 2 * 3 + 4 is equivalent to (2 * 3) + 4
• You can use round/1 to round a float number to the next integer
and float/1 to convert integers to floats.
• All these functions can be used on the right hand side of the is-
operator.

Prolog Notes 7
 Arithmetic GCD Problem
• GCD (greatest common divisor) problem:
– Given two positive integers, X and Y, their greatest common divisor, D,
can be found according to three cases:
(1) If X and Y are equal then D is equal to X.
(2) If X < Y then D is equal to the greatest common divisor of X and the
difference Y-X.
(3) If Y < X then do the same as in case (2) with X and Y interchanged.
– The three rules are then expressed as three clauses:
gcd( X, X, X).
gcd( X, Y, D) :- X<Y, Y1 is Y-X, gcd( X, Y1, D).
gcd( X, Y, D) :- Y<X, gcd( Y, X, D).
?- gcd( 20, 25, D).
D=5

8
 GCD
(1) gcd( X, X, X).
(2) gcd( X, Y, D) :- X<Y, Y1 is Y-X, gcd( X, Y1, D).
(3) gcd( X, Y, D) :- Y<X, gcd( Y, X, D).
| ?- gcd( 10, 25, D).
1 1 Call: gcd(10,25,_23) ?
2 2 Call: 10<25 ? 9 4 Call: gcd(5,10,_23) ?
2 2 Exit: 10<25 ? 10 5 Call: 5<10 ?
3 2 Call: _121 is 25-10 ? 10 5 Exit: 5<10 ?
3 2 Exit: 15 is 25-10 ? 11 5 Call: _327 is 10-5 ?
4 2 Call: gcd(10,15,_23) ? 11 5 Exit: 5 is 10-5 ?
12 5 Call: gcd(5,5,_23) ?
5 3 Call: 10<15 ?
12 5 Exit: gcd(5,5,5) ?
5 3 Exit: 10<15 ?
9 4 Exit: gcd(5,10,5) ?
6 3 Call: _199 is 15-10 ? 7 3 Exit: gcd(10,5,5) ?
6 3 Exit: 5 is 15-10 ? 4 2 Exit: gcd(10,15,5) ?
7 3 Call: gcd(10,5,_23) ? 1 1 Exit: gcd(10,25,5) ?
8 4 Call: 10<5 ?
8 4 Fail: 10<5 ? D=5?
8 4 Call: 5<10 ?
8 4 Exit: 5<10 ? (15 ms) yes

9
 Lists
• Lists are contained in square brackets with the
elements being separated by commas.
• E.g. [elephant, horse, donkey, dog]
• Elements of lists could be any valid Prolog terms,
– i.e., atoms, numbers, variables, or compound terms.
– This includes other lists.
– [elephant, [], X, parent(X, tom), [a, b, c], f(22)]
– Note the empty list []
– Read more on lists:
https://www.doc.gold.ac.uk/~mas02gw/prolog_tutori
al/prologpages/lists.html

Prolog Notes 10
 Lists head and tail
• The 1st element of a list is called its head and
the remaining list is called the tail.
– An empty list doesn't have a head.
– A list just containing a single element has a head
(namely that particular single element) and its tail
is the empty list.

Prolog Notes 11
 List Operator [H |T]
• [a,b,c] is a list in Prolog.
• [H|T] = [a,b,c] results in
– H = a i.e. the head of list
– T = [b,c] i.e. the tail of the list.
 Lists “Chemsha Bongo”
• Answer Yes or No if list unifies or not
– [a,d,z,c] and [H|T]
– [apple,pear,grape] and [A,pear|Rest]
– [a|Rest] and [a,b,c]
– [a,[]] and [A,B|Rest]
– [One] and [two|[]]
– [one] and [Two]
– [a,b,X] and [a,b,c,d]

Prolog Notes 13
 Some Built-in predicates for lists
• length/2: 1st argument is the list, 2nd
argument is the Length; e.g.
length([5,6,8,2,90], Length)
• member/2: checks if an element is in the list
• append/3: Concatenate two lists.
• last/2: checks if last element matches 2nd
argument.
• reverse/2: This predicate can be used to
reverse the order of elements in a list.
Prolog Notes 14
 Backtracking and Nondeterminism

member(X, [X|_]). % _ is an anonymous variable

member(X, [_|T]) :- member(X, T).

?- member(fred, [john, fred, paul, fred]).

yes Deterministic query

?- member(X, [john, fred, paul, fred]).

X = john;
X = fred; Nondeterministic query
X = paul;
X = fred;
no
 The Problem of Controlling Backtracking

?- color(banana, X).
color(cherry, red).
X = yellow
color(banana, yellow).
color(apple, red). ?- color(physalis, X).
X = unknown
color(apple, green).
color(orange, orange). ?- color(cherry, X).
X = red;
color(X, unknown). X = unknown;
no
 The CUT

• The cut is a built-in predicate written as !

• The cut always succeeds
• When backtracking over a cut, the goal that caused the
current procedure to be used fails
• Not used for its logical properties, but to control
backtracking.
• The cut, in Prolog, is a goal, written as !, which always
succeeds, but cannot be backtracked past. It is used to
prevent unwanted backtracking, for example, to prevent
extra solutions being found by Prolog.
 How CUT works

• Suppose goal H is called, and has two clauses:

H1 :- B1,… Bi, !, Bk,… Bm.
H2 :- Bn,… Bp.

• If H1 matches goals B1...Bi are attempted and may

backtrack among themselves

• If B1 fails, H2 will be attempted

• But as soon as ! is crossed, Prolog commits to the

current choice.
All other choices are discarded.
 Commitment to the Clause

H1 :- B1,… Bi, !, Bk,… Bm.

H2 :- Bn,… Bp.

• Goals Bk...Bm may backtrack amongst themselves,

but

• If goal Bk fails, then the predicate fails and the

subsequent clauses are not matched
 How to Remember Cut

• Think of the ‘cut’ as a ‘fence’

– When crossed it always succeeds,
– And asserts a commitment to the current solution.

• When a failure tries to cross the fence, the entire goal is

failed.
commit

H1 :- B1, B2, ..., Bi, !, Bk, ..., Bm.

fail calling goal

 Uses of Cut: Deterministic Predicates

To define a deterministic (functional) predicate. Example: a

deterministic version of member, which is more efficient for
doing ‘member checking’ because it doesn't need to give
multiple solutions:

membercheck(X, [X|_]) :- !.
membercheck(X, [_|L]) :- membercheck(X, L).

?- membercheck(fred, [joe, john, fred, paul]).

yes.
?- membercheck(X, [a, b, c]).
X = a;
no.
 Uses of Cut: Specify Exclusion Cases

2. To specify exclusion of cases by ‘committing’ to the current

choice.

Example: max(X, Y, Z) makes Z maximum of X and Y

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.
Note: Both clauses are logically correct statement

Using cut can get rid of the second test:

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).
 Max with Cut

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).

If max is called with X ≥ Y, the 1st clause succeeds, and because

of ! the 2nd clause isn't called
• The advantage
– The test isn't made twice if X<Y
• The disadvantage
– Each rule isn't a logically correct statement about the predicate.
– To see why this is a problem, try
?- max(10, 0, 0).
 Max with Cut

• It is better to use ! and both tests:

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y) :- X < Y.
• This backtracks correctly and avoids unnecessary tests

• Or, if order of clause may change:

max(X, Y, X) :- X >= Y, !
max(X, Y, Y) :- X < Y, !.
 Negation-as-Failure

• Using cut together with the built-in predicate fail defines

a kind of negation.

• Examples:
• Mary likes any animals except reptiles:
likes(mary,X) :- reptile(X), !, fail.
likes(mary,X) :- animal(X).

• A utility predicate meaning something like “not equals”:

different(X, X) :- !, fail.
different(_, _).
 Negation-as-Failure: not

• We can use the idea of “cut fail” to define the predicate not,
which takes a term as an argument
• not “calls” the term, evaluating as if it was a goal:
– not(G) fails if G succeeds
– not(G) succeeds if G does not succeed.

• In Prolog,
not(G) :- call(G), !, fail.
not(_).
• call is a built-in predicate.
 Negation-as-Failure: not (cont.)

• Most Prolog systems have a built-in predicate not.

• not does not correspond to logical negation, because it is

based on the success/failure of goals.

• It can, however, be useful

likes(mary, X) :- not(reptile(X)).
different(X, Y) :- not(X = Y).
Translation of Prolog Clauses into
Formulas

Prolog Notes 28
 Translation of Prolog Clauses into
Formulas
• Every Prolog predicate is mapped to an atomic 1st-order logic
formula.
• Commas separating subgoals correspond to conjunctions in logic
– i.e., replace every comma between two predicates by a ^ in the
formula
• Prolog rules are mapped to implications, where the rule body is the
antecedent and the rule head the consequent
– i.e., rewrite :- as → and change the order of head and body
• Queries are mapped to implications, where the body of the query is
the antecedent and the consequent is falsum ( )
– i.e., rewrite :- or ?- as →, which is put after the translation of the body
and followed by
• Each variable occurring in a clause has to be universally quantied in
the formula
– i.e., write x in front of the whole formula for each variable X.

Prolog Notes 29
 END
• CAT Task 2
– 50 marks;
– To be submitted in the lms
– Date and Time we shall agree, but shall be 3 days
work. Proposed: Saturday, Sunday, and Monday
– Accesible from tomorrow

Prolog Notes 30