COMP9414/9814 Artificial Intelligence

INTRODUCTION TO PROLOG PROGRAMMING

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.
Plan:


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 http://www.cse.unsw.edu.au/~billw/cs9414/notes/prolog/Kowalski.pdf). 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

Reference:

Bratko, Chapter 1

Picture of Cover of Bratko's book

Picture of Ivan Bratko

Ivan Bratko

Relations


A little more on being sisters


Programming in Prolog

One then uses the system by:


Facts


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 http://www.cse.unsw.edu.au/~billw/cs9414/notes/prolog/facts03.


Queries


Another example query

?- lectures(codd, 9020).
false.


Variables


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":


Rules


Clause Syntax


Tracing Execution

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

?- trace.
true.
[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) ?
true.
[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
succeeds
succeeds
* 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


Structures

Reference:
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
http://www.cse.unsw.edu.au/~billw/cs9414/code/library.pro

The is operator


Order of goals with is


is, = and =:=


Recursive Programs

Reference:
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


Lists

Reference:
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.

true.
[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

Reference:
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.