Computing Fibonacci Numbers
fib(n) =
0,
if n = 0
1,
if n = 1
fib(n-2) + fib(n-1),
if n > 1
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 1
Recursive Fibonacci Program
fib(0, 0).
fib(1, 1).
fib(X, Y) :X > 1,
X2 is X 2, fib(X2, Y2),
X1 is X 1, fib(X1, Y1),
Y is Y1 + Y2.
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 2
Running the Fibonacci Program
fib(5)
fib(3)
fib(4)
1 + fib(2)
0 +1
fib(2)
0 +1
+ fib(3)
1 + fib(2)
0 + 1
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 3
Efficient Fibonacci Program
fib(0, 0).
fib(X, Y) :- X > 0, fib(X, Y, _).
fib(1, 1, 0).
fib(X, Y1, Y2) :
COMP 222
X > 1,
X1 is X - 1,
fib(X1, Y2, Y3),
Y1 is Y2 + Y3.
Logic and Programming
Module B Prolog
Chapter 7, Slide 4
Collecting all Solutions
Getting all answers to a question
Through backtracking we can get all answers to
a question one by one.
Using setof we can collect all answers to a question
in a list.
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 5
Collecting all Solutions
age(peter, 7).
age(ann, 5).
age(pat, 8).
age(tom, 5).
?- setof(Child, age(Child, 5), List).
List = [ann, tom]
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 6
Collecting all Solutions
?- setof(Child, age(Child, Age), List).
Age = 7
List = [peter] ;
Age = 5
List = [ann, tom] ;
Age = 8
List = [pat] ;
No
?- setof(Child, Age ^ age(Child, Age), List).
List = [ann, pat, peter, tom]
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 7
Collecting all Solutions
age(peter, 7).
age(ann, 5).
age(pat, 8).
age(tom, 5).
?- setof(Child, age(Child, 3), List).
No
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 8
Testing Prolog Code
Easy because all state accessible in
parameters
Need to check both number and values of
all answers to calls (failure is same as no
answers)
We will ignore the order of the answers
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 9
Test Example - fibonacci
test(fib(0,
test(fib(1,
test(fib(2,
test(fib(3,
test(fib(4,
test(fib(5,
test(fib(6,
test(fib(7,
0)).
1)).
1)).
2)).
3)).
5)).
8)).
13)).
testFail(fib(-1,_)).
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 10
Test Example - fibonacci
?- [fib,fibTest,test].
Yes
?- testRun.
starting testing
++++++++end of testing
Yes
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 11
Quick Sorting
quicksort([], []).
quicksort([X | Tail], Sorted) :split(X, Tail, Small, Big),
quicksort(Small, SSmall),
quicksort(Big, SBig),
append(SSmall, [X | SBig], Sorted).
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 12
Quick Sorting
split(_X, [], [], []).
split(X, [Y|Tail], [Y|Small], Big) :X >= Y, split(X, Tail, Small, Big).
split(X, [Y|Tail], Small, [Y|Big]) :X < Y, split(X, Tail, Small, Big).
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 13
Testing sort
Different ways of saying the same thing:
test(quicksort([3,1,2], [1,2,3])).
test(quicksort([3,1,2], S), [quicksort([3,1,2], [1,2,3])]).
test(quicksort([3,1,2], S), S, [[1,2,3]]).
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 14
Testing sort
A handy way that shows you can write testing rules.
test(quicksort(L,X), X, [S]) :- test_sort(L, S).
test_sort([], []).
test_sort([1], [1]).
test_sort([2,1], [1,2]).
test_sort([1,2], [1,2]).
test_sort([3,1,2], [1,2,3]).
test_sort([5,6,1,3,4,7,2],
[1,2,3,4,5,6,7]).
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 15
Testing split
test(split(X,L,Sn,Bn), [Sn,Bn], [[S,B]]) :test_split(X,L,S,B).
test_split(3, [3,2,1,4,5,1,7],
[3,2,1,1], [4,5,7]).
test_split(0, [3,2,1,4,5,1,7],
[], [3,2,1,4,5,1,7]).
test_split(1, [], [], []).
test_split(1, [1], [1], []).
test_split(0, [1], [], [1]).
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 16
Implementing Test
check(G, Re, Ex) :setof(Re, G, Res)
-> soln(G, Ex, Res)
; failed(G, Ex).
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 17
Implementing Test
soln(G, Ex, Res) :- sort(Ex, Exs),
(Res = Exs
-> (Ex = [] -> print('-') ; print('+'))
; error(G, Exs, Res))
).
failed(G, Ex) :(Ex = []
-> print('-')
; error(G, Ex, []))
).
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 18
Implementing Test
testRun :- nl, print('starting testing'), nl, fail.
testRun :- test, fail.
testRun :- nl, print('end of testing'), nl.
test :- test(G, Re, Ex), check(G, Re, Ex).
test :- test(G, Ex), check(G, G, Ex).
test :- test(G), check(G, G, [G]).
test :- testFail(G), check(G, G, []).
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 19
Testing sort
test :- test_sort(L, S),
check(quicksort(L,X), [S], X).
test_sort([], []).
test_sort([1], [1]).
test_sort([2,1], [1,2]).
test_sort([1,2], [1,2]).
test_sort([3,1,2], [1,2,3]).
test_sort([5,6,1,3,4,7,2],
[1,2,3,4,5,6,7]).
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 20
Merge Sort
merge_pass([], []).
merge_pass([L], [L]).
merge_pass([L1, L2 | L], [M | Ln]) :- merge(L1, L2, M),
merge_pass(L, Ln).
COMP 222
Logic and Programming
Module B Prolog
Chapter 7, Slide 21
