COMP9414/9814 Artificial Intelligence


Reference: Bratko, I., Programming in Prolog for Artificial Intelligence, 4th Edition, Addison-Wesley, 2011, chapters 1-5
Aim: To introduce enough of Prolog to allow students to do the assignment work in this course, thereby gaining some experience of AI programming.

What is Prolog?

  • invented early seventies by Alain Colmerauer in France and Robert Kowalski in Britain. (There is a recent 2-page article by Kowalski at Note that historical information in these lectures is not examinable.
  • Prolog = Programmation en Logique (Programming in Logic).
  • Prolog is a declarative programming language
    unlike most common programming languages.
  • In a declarative language
    • the programmer specifies a goal to be achieved
    • the Prolog system works out how to achieve it
  • relational databases owe something to Prolog

Alain Colmerauer

Robert Kowalski

What is Prolog? (continued)

Applications of Prolog

Some applications of Prolog are:

The Prolog Language


Bratko, Chapter 1

Picture of Cover of Bratko's book

Picture of Ivan Bratko

Ivan Bratko


A little more on being sisters

Programming in Prolog

One then uses the system by:


Facts about a hypothetical computer science department:

        % lectures(X, Y): person X lectures in course Y
	lectures(turing, 9020).
	lectures(codd, 9311).
	lectures(backus, 9021).
	lectures(ritchie, 9201).
	lectures(minsky, 9414).
	lectures(codd, 9314).

        % studies(X, Y): person X studies in course Y
	studies(fred, 9020).
	studies(jack, 9311).
	studies(jill, 9314).
	studies(jill, 9414).
	studies(henry, 9414).
	studies(henry, 9314).

        %year(X, Y): person X is in year Y
	year(fred, 1).
	year(jack, 2).
	year(jill, 2).
	year(henry, 4).

Together, these facts form Prolog's database. Should you wish to experiment with them using Prolog, they are available at


Another example query

?- lectures(codd, 9020).


Variables 2

Conjunctions of Goals in Queries

Disjunctions of Goals in Queries

There is a way to write or: (";") danger danger


Backtracking in Prolog

Backtracking in Prolog 2

Backtracking in Prolog 3

To picture what happens when Prolog tries to find a solution and backtracks, we draw a "proof tree":


Clause Syntax

Tracing Execution

	more_advanced(S1, S2) :-
		year(S1, Year1),
		year(S2, Year2),
		Year1 > Year2.

?- trace.
[trace] ?- more_advanced(henry, fred).
  Call: more_advanced(henry, fred) ? *
  Call: year(henry, _L205) ?
  Exit: year(henry, 4) ?
  Call: year(fred, _L206) ?
  Exit: year(fred, 1) ?
^ Call: 4>1 ?
^ Exit: 4>1 ?
  Exit: more_advanced(henry, fred) ?
[debug]  ?- notrace.

bind S1 to henry, S2 to fred
test 1st goal in body of rule
succeeds, binds Year1 to 4
test 2nd goal in body of rule
succeeds, binds Year2 to 1
test 3rd goal: Year1 > Year2
* The ? is a prompt. Press the return key at end of each line of tracing. Prolog will echo the <return> as creep, and then print the next line of tracing. The "creep"s have been removed in the table above, to reduce clutter.

true., false., or true


Bratko chapter 2

Asking Questions with Structures

Library Database Example

Library Database Example 2

Comparing Two Terms

More on Comparisons

Overdue Books

% overdue(Today, Title, CatalogNo, MemFamily):
%   given the date Today, produces the Title, CatalogNo,
%   and MemFamily of all overdue books.

overdue(Today, Title, CatalogNo, MemFamily) :-
  loan(CatalogNo, MemberNo, _, DueDate),
  later(Today, DueDate),
  book(CatalogNo, Title, _),
  libmember(MemberNo, name(MemFamily, _), _).

Due Date

You can find a copy of the code for all the library stuff, and a sample (toy) library database, at

The is operator

Order of goals with is

is, = and =:=

Recursive Programs

Bratko section 1.3 (doesn't cover trees, though)

Binary Trees

Recursive Structures

Another Tree Example

Recursive Programs for Recursive Structures

Recursive Programs for Recursive Structures 2


Bratko chapter 3

List Constructor |

Examples of Lists and Pattern Matching

?- [X, Y, Z] = [1, 2, 3]. Match the terms on either side of =
X = 1
Y = 2
Z = 3
?- [X | Y] = [1, 2, 3]. | separates head from tail of list.
X = 1So [First | Rest] is the usual way
Y = [2, 3]of writing .(First, Rest) in Prolog
?- [X | Y] = [1].
X = 1
Y = []
The empty list is written as []
Lists "end" in an empty list!
Note that [1] is a list with one element.

The first several elements of the list can be selected before matching the tail:

?- [X, Y | Z] = [fred, jim, jill, mary].
X = fred
Y = jim
Z = [jill, mary]
Must be at least two elements
in the list on the right.

More Complex List Matching

?- [X | Y] = [[a, f(e)], [n, m, [2]]].

X = [a, f(e)]
Y = [[n, m, [2]]]

Notice that Y is shown with an extra pair of brackets: Y is the tail of the entire list: [n, m, [2]] is the sole element of Y.

List Membership

= in goals

Earlier, we said:

X = 1     GOOD!
Actually, goals with = in them are mostly avoidable and should be avoided. Beginnner Prolog programmers are tempted to use = frequently, to tie together variables that they now realise should be the same:
% length(List, LengthOfList)
% binds LengthOfList to the number of elements in List.
length([OnlyMember], Length) :-
	Length = 1.
length([First | Rest], Length) :-
	length(Rest, LengthOfRest),
	Length is LengthOfRest + 1.
This works, but involves an unnecessary unification. It is better for the base case to be
length([OnlyMember], 1).
In effect, we take the original version of the base case, and replace Length, in the head of the rule, with the thing that Length is = to. Programmers who fail to do this are usually still thinking procedurally.

Programming Principles for Recursive Structures

Concatenating Two Lists

An Application of Lists

Tracing total_cost

?- trace.

[trace]  ?- total_cost([cornflakes, crisps], X).
   Call: (7) total_cost([cornflakes, crisps], _G290) ? creep
   Call: (8) cost(cornflakes, _L207) ? creep
   Exit: (8) cost(cornflakes, 230) ? creep
   Call: (8) total_cost([crisps], _L208) ? creep
   Call: (9) cost(crisps, _L228) ? creep
   Exit: (9) cost(crisps, 190) ? creep
   Call: (9) total_cost([], _L229) ? creep
   Exit: (9) total_cost([], 0) ? creep
^  Call: (9) _L208 is 190+0 ? creep
^  Exit: (9) 190 is 190+0 ? creep
   Exit: (8) total_cost([crisps], 190) ? creep
^  Call: (8) _G290 is 230+190 ? creep
^  Exit: (8) 420 is 230+190 ? creep
   Exit: (7) total_cost([cornflakes, crisps], 420) ? creep

X = 420 

[debug]  ?- notrace.

Modifying total_cost

This is an optional homework exercise.
What happens if we change the recursive branch rule for total_cost as shown below?

total_cost([Item|Rest], Cost) :-
    total_cost(Rest, CostOfRest),
    cost(Item, ItemCost),
    Cost is ItemCost + CostOfRest.

The second and third lines have been swapped around.
You'll find that the rule still works. Try tracing the new version of this rule, work out what happens differently.
Which version do you find easier to understand? Why do think this is the case?

Another list-processing procedure

Singleton Variables

Controlling Execution

Bratko chapter 5

The Cut Operator (!)

Cut Operator 2

Recall this example:

Cut Prunes the Search Tree

Cut Prunes the Search Tree 2

Using cuts in later to improve efficiency

Recall the code for later:

later(date(Y, M, D1), date(Y, M, D2)) :- D1 > D2.
later(date(Y, M1, _), date(Y, M2, _)) :- M1 > M2.
later(date(Y1, _, _), date(Y2, _, _)) :- Y1 > Y2.
We note that if year and month are the same, all three rules are tried while backtracking. This could be prevented by adding cuts:
later(date(Y, M, D1), date(Y, M, D2)) :- D1 > D2, !.
later(date(Y, M1, _), date(Y, M2, _)) :- M1 > M2, !.
later(date(Y1, _, _), date(Y2, _, _)) :- Y1 > Y2.
This would increase efficiency by eliminating unnecessary backtracking, though it is doubtful if it would be worth bothering about, unless you actually have code that is running too slowly. In that case you should first do an analysis of where the time is being spent, before putting in cuts everywhere!

In other cases, adding cuts of this sort to multi-rule procedures might be a useful (if lazy) way of ensuring that only one rule is used in a particular case. Unless it makes the code very clumsy, it is better to use and rely on "condition" goals in each rule (like M1 > M2 in the second rule for later) to specify the case in which it is appropriate. More examples of this are below.

Another cut example

Another cut example 2

Summary: Introduction to Prolog
We have introduced facts, queries, variables, conjunctions of goals, rules, structures, recursion, trees and lists, and controlling execution by means of the "cut".

CRICOS Provider Code No. 00098G

Copyright © Bill Wilson, 1996-2012, except where another source is acknowledged: much of the material in these notes is based on an earlier edition by Claude Sammut. Certain improvements are due to Maurice Pagnucco. Images of Bratko, Kowalski, and Colmerauer were obtained from Google Images.