```Programming Languages for
Intelligent Systems (CM2008)
Lecture on Prolog #3
Recursion & List
http://www.comp.rgu.ac.uk/staff/khui/teaching/cm2008
Content





A quick reminder
Arithmetic Operations
Some Built-in Predicates
Recursion
List
Previously...

Unification


Resolution



making 2 terms identical by substituting variables
resolving a goal into subgoals
depth-first search
Backtracking

at an OR node, if a branch fails, automatically try
another branch
Arithmetic Operations

Prolog has some built-in arithmetic operators:


+ - * / mod
to "get" a value from an expression into a
variable

"=" only tests for unification



it does not evaluates the expression
only works when the expression is already evaluated
examples:
?- X=1+2.
X=1+2
Yes
a term structure,
NOT evaluated
The is/2 Predicate

use is/2 to assign value to a variable


variable must be uninstantiated
examples:
?- is(X,1+2).
X=3
Yes
?- X is 1+2.
X=3
Yes
evaluates
1+2
is/2 used as
an infix
operator
Assignment or Not?




is/2 is NOT an assignment
it is evaluation + unification
there is NO destructive assignment
in Prolog
you unify variables with values/terms
created from other terms
The ==/2 Predicate


test for equality of 2 terms
examples:
?- ==(X,X).
X=_G123
Yes
?- X==Y.
No
?- X=Y.
X=_G456
Y=_G456
Yes
X identical to the
variable X
X and Y are 2
different variables,
even though they
can be unified
X and Y can
be unified
The =:=/2 Predicate


evaluate expressions before comparing
terms can be
examples:
unified
?- 1+2=1+2.
Yes
?- 1+2=2+1.
No
?- 1+2=:=2+1.
Yes
terms
CANNOT be
unified
values are
equal
Recursion

“something” defined on itself


i.e. coming back
the concept applies to predicates/
functions (e.g. in LISP)
Recursive Function Example

the factorial function
N! = 1 × 2 × … × N

e.g.


OR recursively defined as



3!=1 ×2 ×3 =6
if N=0 then N!=1
if N>0 then N!=N ×(N-1)!
e.g.


3!=3 ×2!=3 ×(2 × 1!)=3 ×(2 ×(1 ×0!))
=3 ×(2 ×(1 ×1))=6
The fact/2 Predicate


define the factorial function as a
predicate fact/2:
fact(N,X)
relates N with N! (i.e. X)
Implementation of fact/2
fact(0,1).
fact(N,Ans) :N>0,
integer(N),
M is N-1,
fact(M,Temp),
Ans is Temp*N.
%0!=1
%N>0
%integer
%M is N-1
%get Y=M!
%N!=N*(N-1)!
A Trace of fact/2
fact(3,X)?
fact(2,X2)?
X3=1
fact(1,X3)?
X4=1
fact(0,X4)?
X4=1
θ={X4=1}
X2=2
X=6
The ancestor/2 Predicate

logical meaning:



case 1: X is the ancestor of Y if X is a parent of Y
case 2: X is the ancestor of Y if X is the parent of
Someone, and Someone is the ancestor of Y
implementation:
ancestor(X,Y) :parent(X,Y).
ancestor(X,Y) :parent(X,Z),
ancestor(Z,Y).
The Classic Tower of Hanoi
Problem



1 disc at a time
no big disc above small disc
must move top disc
The Tower of Hanoi Problem
Predicate

define a predicate:
hanoi(N,Start,End,Aux)





a tower of N disc
start from Start pole
end in End pole
auxiliary pole Aux
gives instructions of moving a tower of
N disc from Start to End with auxiliary
pole Aux
Implementation of hanoi/4
hanoi(1,Start,End,_) :write('move disc from '),
write(Start),
write(' to '),
write(End),
nl.
 logical meaning:

if there is only 1 level, move disc from pole
Start to End
Implementation of hanoi/4
(cont’d)
hanoi(N,Start,End,Aux) :N>0,
M is N-1,
hanoi(M,Start,Aux,End),
write('move disc from '),
write(Start),
write(' to '),
write(End),nl,
hanoi(M,Aux,End,Start).
 logical meaning:

if there are N levels & N>0, then:



move N-1 levels from Start to Aux
move disc from Start to End
move N-1 levels back from Aux to End
A Trace of hanoi/4
hanoi(3,a,b,aux)
hanoi(2,a,aux,b)
hanoi(1,a,b,aux)
move disc
from a to b
hanoi(2,aux,b,a)
hanoi(1,aux,a,b)
move disc
from a to aux
hanoi(1,b,aux,a)
move disc
from aux to b
hanoi(1,a,b,aux)
General Guideline for Writing
Recursive Predicates

there must be at least:



a special/base case: end of recursion
a general case: reduce/decompose a general
case into smaller cases (special case)
there must be some change in arguments
(values) when you make a recursive call



decompose problem in each recursive call
get closer to special/base case
otherwise the problem (goal) is not reduced
General Guidelines for Writing
Recursive Predicates (cont'd)


the predicate relates the arguments
it works as a black-box

assume that the predicate is implemented
correctly



if you provide these arguments, here is the
effect
although you haven't completed it yet
state how the general case is related to
simpler cases (closer to special/base
case)
List


a linearly ordered collection of items
syntactically:






surrounded by square brackets
list elements separated by commas
e.g. [john,mary,sue,tom]
e.g. [a,b,c,d]
may contain any number of elements or
no element
[] is the empty list
List (cont’d)

the empty list [] has no head/tail
?- []=[_|_].
No

a singleton list has only 1 element
its tail is an empty list
?- [a]=[X|Y].
X=a
Y=[]
Yes

Lists vs Arrays


no fixed size
each item can be of different types,
even nested term structures/list



e.g. [john,mary,20.0,
date(10,may,2004)]
e.g. [a,[1,2,3],b,[c,d]]
you may not directly access an element
by its index

you can use unification, however
Head & Tail of a List


a list is a structured data
each list has a:




head: 1st element of the list
tail: rest of the list
a list can be expressed as
Note:


Head is an element
Tail is a list
List (cont’d)



is a term
has the functor “.”
2 arguments


the head & the tail
a list with >1 element can be written as
a nested term
List Examples
?- [a,b,c]=[X,Y,Z].
X=a
Y=b
Z=c
Yes
?- [a,b,c]=[_,_,X].
X=c
Yes
?- [a,b,c] = [X|Y].
X=a
Y=[b,c]
Yes
?[a,b,c]=[_|[X|Y]]
.
X=b
Y=[c]
Yes
?- [a,b,c]=[_,_|X].
X=[c]
Yes
A List as a Nested Term





[1,2,3,4]
=[1|[2,3,4]]
=[1|[2|[3,4]]]
=[1|[2|[3|[4]]]]
=[1|[2|[3|[4|[]]]]]
.
1
.
.
2
3
.
4
[]
List Examples (cont’d)





[a,b,c,x(y,z)]
=[a|[b,c,x(y,z)]]
=[a|[b|[c,x(y,z)]]]
=[a|[b|[c|[x(y,z)]]]]
=[a|[b|[c|[x(y,z)]]]]
.
a
.
.
b
c
.
x
y
[]
z
List Examples (cont’d)



[date(2,april,2004),time(9,20,32)]
=[date(2,april,2004)|[time(9,20,32)]]
=[date(2,april,2004)|[time(9,20,32)|[]]]
.
date
2 april 2004
.
time
9 20 32
[]
The member/2 Predicate

member(X,L)

is true if X is an element of list L
examples:
?- member(a,[a,b,c]).
Yes
?- member(c,[a,b,c]).
Yes

Other Ways of using
member/2
?- member(X,[a,b,c]).
X=a;
X=b;
X=c;
no
?- member(a,List).
List=[a|_123];
List=[_456,a|_789];
…
tell me who is
an element of
the list [a,b,c]
tell me the
list which
has 'a' as an
element
Implementation of member/2
member(X,[X|_]).
member(X,[_|Tail]) :member(X,Tail).

logical meaning:


X is a member of a list if it is the head.
OR X is a member of a list if it is a member
of the tail.
A Trace of member/2
try R1
member(c,[a,b,c])?
member(c,[a,b,c])=member(c,[c|_])?
FAIL!
try R2
member(c,[a,b,c])=member(X,[_|Tail])?
Ө={X=c,_=a,Tail=[b,c]}
member(c,[b,c])?
try R1
member(c,[b,c])=member(c,[c|_])?
FAIL!
try R2
member(c,[b,c])=member(X2,[_|Tail2])?
Ө={X2=c,Tail2=[c]}
try R1
member(c,[c])=member(X3,[X3|_])
Ө={X3=c,_=[]}
member(c,[c])?
append/3
appends 2 lists together (gives a 3rd list)
 examples:
?- append([a,b],[x,y],Result).
Result=[a,b,x,y]
Yes
?- append([a,b,c],[],Result).
Result=[a,b,c]
Yes

Implementation of append/3
append([],L,L).
append([H|T],L2,[H|Rest]) :append(T,L2,Rest).
 logical meaning:


appending an empty list to a list L gives L
appending a list L1 to L2 gives a list whose
head is the head of L1 and the tail is the
resulting of append the tail of L1 to L2
String in Prolog

double quoted



single quoted is an atom
a String is a list of integers (ASCII code)
example:
?- S="hello".
S=[104,101,108,108,111]
Yes
Converting between String &
Atom

use name/2

example:
?- S="hello",name(X,S).
S=[104,101,108,108,111]
X=hello
Yes
Summary

a recursive predicate




defines on itself
always has a special (base) case & a
general case
breaks down/decomposes a problem
(goal) in each recursive call
a list


is a structure
consists of a head & a tail

Bratko, chapter 3
```