COMP4418: Knowledge Representation and Reasoning
Introduction to Prolog II
Maurice Pagnucco
School of Computer Science and Engineering University of New South Wales
NSW 2052, AUSTRALIA morri@cse.unsw.edu.au
Reference: Ivan Bratko, Prolog Programming for Artificial Intelligence, Addison- Wesley, 2001. Chapter 3.
COMP4418 ⃝c UNSW, 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog II 1
Prolog
Compound terms can contain other compound terms
A compound term can contain the same kind of term, i.e., it can be
recursive:
tree(tree(empty, jack, empty), fred, tree(empty, jill, empty))
“empty” is an arbitrary symbol use to represent the empty tree
Astructurelikethiscouldbeusedtorepresentabinarytreethatlooks like:
COMP4418
⃝c UNSW, 2019
Generated: 15 September 2019
empty
empty
empty
empty
jack
jill
fred
COMP4418, Monday 30 September, 2019 Introduction to Prolog II 2
Binary Trees
A binary tree is either empty or it is a structure that contains data and left and right subtrees which are also binary trees
To test if some datum is in the tree:
COMP4418
⃝c UNSW, 2019
Generated: 15 September 2019
in_tree(X, tree(_, X, _)). in_tree(X, tree(Left, Y, _) :-
X \= Y,
in_tree(X, Left). in_tree(X, tree(_, Y, Right) :-
X \= Y,
in_tree(X, Right).
COMP4418, Monday 30 September, 2019 Introduction to Prolog II 3
The Size of a Tree
tree_size(empty, 0). tree_size(tree(Left, _, Right), N) :-
tree_size(Left, LeftSize), tree_size(Right, RightSize), N is LeftSize + RightSize + 1.
The size of the empty tree is 0
The size of a non-empty tree is the size of the left subtree plus the
size of the right subtree plus one for the current node
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog II 4
Lists
Alistmaybeniloritmaybeatermthathasaheadandatail. The tail is another list.
Alistofnumbers,[1,2,3]canberepresentedas: list(1, list(2, list(3, nil)))
123
Since lists are used so often, Prolog has a special notation: [1, 2, 3] = list(1, list(2, list(3, nil)))
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019
Introduction to Prolog II 5
Examples of Lists
[X, Y, Z] = [1, 2, 3]?
Unify the two terms on either side of the equals sign
X=1 Y=2
Variables match terms in corresponding positions
Z=3
[X|Y] = [1, 2, 3]?
The head and tail of a list are separated by using ‘|’ to indicate that the term following the bar should unify with the tail of the list
X=1
Y = [2, 3]
[X|Y] = [1]?
The empty list is written as ‘[]’ The end of a list is usually []’
X=1
Y = []
COMP4418
⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019
Introduction to Prolog II 6
More list examples
[X, Y|Z] = [fred, jim, jill, mary]?
There must be at least two elements in the list on the right
X = fred
Y = jim
Z = [jill, mary]
[X|Y] = [[a, f(e)], [n, b, [2]]]?
The right hand list has two elements:
X = [a, f(e)]
Y = [[n, b, [2]]]
[a, f(e)] [n, b, [2]]
Y is the tail of the list,
[n, b, [2]] is just one element
COMP4418
⃝c UNSW, 2019
Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog II 7
List Membership
member(X, [X|_]). member(X, [_|Y]) :-
member(X, Y).
Rules about writing recursive programs:
◮ Only deal with one element at a time
◮ Believe that the recursive program you are writing has already been written and works
◮ Write definitions, not programs
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog II 8
Appending Lists
A commonly performed operation on lists is to append one list to the end of another (or, concatenate two lists), e.g.,
append([1, 2, 3], [4, 5], [1, 2, 3, 4, 5]).
Start planning by considering the simplest case: append([], [1, 2, 3], [1, 2, 3]).
Clause for this case: append([], L, L).
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog II 9
Appending Lists
Next case:
append([1], [2], [1, 2]).
Sinceappend([],[2],[2]):
append([H|T1], L, [H|T2]) :- append(T1, L, T2).
Entire program is:
append([], L, L). append([H|T1], L, [H|T2]) :-
append(T1, L, T2).
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019 Introduction to Prolog II 10
Reversing Lists
rev([1, 2, 3], [3, 2, 1]).
Start planning by considering the simplest case:
rev([], []).
Note:
rev([2, 3], [3, 2]).
and
append([3, 2], [1], [3, 2, 1]).
COMP4418 ⃝c UNSW, 2019 Generated: 15 September 2019
COMP4418, Monday 30 September, 2019
Introduction to Prolog II 11
Reversing Lists
Entire program is:
rev([], []).
rev([A|B], C) :-
rev(B, D),
append(D, [A], C).
COMP4418 ⃝c UNSW, 2019
Generated: 15 September 2019
COMP4418, Monday 30 September, 2019
Introduction to Prolog II 12
An Application of Lists
Find the total cost of a list of items:
cost(flange, 3).
cost(nut, 1).
cost(widget, 2).
cost(splice, 2).
We want to know the total cost of [flange, nut, widget, splice]
COMP4418
⃝c UNSW, 2019
Generated: 15 September 2019
total_cost([], 0). total_cost([A|B], C) :-
total_cost(B, B_cost),
cost(A, A_cost),
C is A_cost + B_cost.