Reference:  Bratko, I., Programming in Prolog for Artificial Intelligence, 4th Edition, AddisonWesley, 2011, chapters 15 
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: 

Alain Colmerauer 
Robert Kowalski 
mix ingredients;
beat until smooth;
bake for 20 minutes in a moderate oven;
remove tin from oven;
put on bench;
close oven;
turn off oven;
Some applications of Prolog are:
Reference:  Bratko, Chapter 1


Two people are sisters ifthey are both female and
they have the same parents.
A and B are sisters ifA and B are both female and
they have the same father and
they have the same mother and
A is not the same as B
One then uses the system by:
lectures(turing, 9020).
reads(fred, "War and Peace")
).
lectures(turing, 9020).
is also called a predicate
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.
% prolog s facts03 (multiline welcome message) ? lectures(turing, 9020). true. ? <controlD> % 
facts03 loaded into Prolog "?" is Prolog's prompt output from Prolog hold down control & press D to leave Prolog 
green italics
is what the user types.
? lectures(codd, 9020). false.
true.
, the query succeeded
false.
, the query failed. Note: many early
versions of Prolog, including early versions of SWIProlog, say No
instead of false.
See the article on
negation
in the
Prolog dictionary
to find out why No.
is a more accurate description of what is
happening.
codd
is critical.
lectures(fred, 9020).
or lectures(xyzzy, 9020).
fred
is
a student, not a lecturer, and that xyzzy
is neither student
nor lecturer.
Is there a course, X, that Turing teaches?
? lectures(turing, Course).
Course = 9020
←
output from Prolog
? lectures(codd , Course).
← type "
Course = 9311 ;;
" to get next solution
Course = 9314
?
If Prolog can tell that there are no more solutions, it just
gives you the ?
prompt for a new query, as here.
If Prolog can't tell, it will let you
type ;
again, and then if there
is no further solution, report false.
? lectures(turing, Course), studies(fred, Course).
Course
and Fred studies
(the same) Course
".
,
", as and.
There is a way to write or: (";
")
head : body1. head : body2.has the same effect as
head : body1 ; body2.
;
if you can, at least until you
have learned how to manage without it. While some uses of ;
are harmless, others can make your code hard to follow.
;
in the first (Prolog) assignment in COMP9414. This prohibition
means you can't use the … > … ; …
construct either, in the first assignment. The
… > … ; …
construct is not taught
in COMP9414, but in the past, some people have found out about it.
? lectures(codd, Course), studies(Student, Course). Course = 9311 Student = jack ; Course = 9314 Student = jill ; Course = 9314 Student = henry ;
lectures(codd, Course)
lectures
clauses, but only two have
codd
as their first argument.
codd
: lectures(codd, 9311).
Course = 9311
, it tries to
satisfy the next goal, studies(Student, 9311)
.
studies(jack, 9311).
and
hence the first solution: (Course = 9311, Student = jack
)
9311
(but finds none).
Course
to 9314
,
lectures(codd, 9314)
branch
studies(Student, 9314)
,
Course = 9314, Student = jill
)Course = 9314, Student = henry
).
To picture what happens when Prolog tries to find a solution and backtracks, we draw a "proof tree":
One person, Teacher, teaches another person, Student if Teacher lectures in a course, Course and Student studies Course.
teaches(Teacher, Student) : lectures(Teacher, Course), studies(Student, Course). ? teaches(codd, Student).
more_advanced(S1, S2) : year(S1, Year1), year(S2, Year2), Year1 > Year2.
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 
?
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
true
instead of
true.
(i.e. no fullstop after true
).
bad_dog(fido). bad_dog(Dog) : bites(Dog, Person), is_person(Person), is_dog(Dog). bites(fido, postman). is_person(postman). is_dog(fido).There are two ways to prove
bad_dog(fido)
: (a) it's there
as a fact; and (b) it can be proven using the bad_dog
rule:
? bad_dog(fido). true ; true.The missing fullstop prompts us to type
;
if we want to check for another proof. The true.
that follows means that a second proof was found. Alternatively,
we can just press the "return" key if we are not interested in whether
there is another proof.
Reference: 
owns
have arity 2, but the detailed
structure of the arguments changes.
gives(john, book, mary).
is a term with arity 3.
? owns(john, book(Title, author(leguin, GivenName))). Title = 'Tehanu' GivenName = ursula
? owns(john, Book). Book = book('Tehanu', author(leguin, ursula))
? owns(john, book(Title, Author)). Title = 'Tehanu' Author = author(leguin, ursula)
book(CatalogNo, Title, author(Family, Given)). libmember(MemberNo, name(Family, Given), Address). loan(CatalogNo, MemberNo, BorrowDate, DueDate).
date(Year, Month, Day)
date(2012, 6, 16)
represents 16 June 2012.
borrowed(MemFamily, Title, CatalogNo) : libmember(MemberNo, name(MemFamily, _), _), loan(CatalogNo, MemberNo, _, _), book(CatalogNo, Title, _).
_
)
are used because for the purpose of this query we don't care
about the values in some parts of these structures.
%later(Date1, Date2) if Date1 is after Date2: later(date(Y, M, Day1), date(Y, M, Day2)) : Day1 > Day2. later(date(Y, Month1, _), date(Y, Month2, _)) : Month1 > Month2. later(date(Year1, _, _), date(Year2, _, _)) : Year1 > Year2.
Day1 > Day2
and the Y
and M
are the same, or if the Y
is the same and Month1 > Month2
, or if
Year1 > Year2
.
later
, again we are using the
comparison operator ">"
X + Y >= Z * W * 2
.
Operator  Meaning  Syntax 

>  greater than  Expression1 > Expression2 
<  less than  Expression1 < Expression2 
>=  greater than or equal to  Expression1 >= Expression2 
=<  less than or equal to  Expression1 =< Expression2 
=:=  equal to  Expression1 =:= Expression2 
=\=  not equal to  Expression1 =\= Expression2 
Expression1
and Expression2
.
% 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(date(Y, Month1, D), date(Y, Month2, D)) : Month1 < 12, Month2 is Month1 + 1. due_date(date(Year1, 12, D), date(Year2, 1, D)) : Year2 is Year1 + 1.
is
operatoris
must be an
arithmetic expression that
can be evaluated right now (no unbound variables).
is
is not
a Cstyle assignment statement:
X is X + 1
won't work!
is
or any other way
=
does not cause evaluation of
its arguments:
? X = 2, Y = X + 1. X = 2 Y = 2+1 

? X = 2, Y is X + 1. X = 2 Y = 3 
is
if and only if you need to evaluate something:
X is 1  BAD!   nothing to evaluate  
X = 1  GOOD! 
is
, you
will be penalised in the first Prolog assignment if you use it where
it is not needed.
is
is
.
Variables on the RHS of is
must be instantiated at the time the is
goal
is tried by Prolog. This is why the following example fails:
? X is Y + 1, Y = 3. ERROR: is/2: Arguments are not sufficiently instantiatedvs
? Y = 3, X is Y + 1. Y = 3, X = 4.
is
, =
and =:=
? X =:= 3+2.  X is not currently bound, so can't be evaluated.

? X = 3+2.  = doesn't evaluate, so X is bound to 3+2 .

? X is 3+2.  is does evaluate its righthand side.

? 4+1 is 3+2.  3+2 is evaluated to 5 .4+1 is not evaluated. So 4+1 is different from 5 .

? 4+1=3+2.  Neither side is evaluated by = .The two expressions are different. 
? 4+1 =:= 3+2.  Both sides are evaluated by =:=

=
is used for matching, so a more appropriate use would be:? likes(mary, X) = likes(Y, pizza). X = pizza, Y = mary.
Reference: 
book
contained name
.
tree(tree(L1, jack, R1), fred, tree(L2, jill, R2))
tree
) is said to be recursive.
empty
is an arbitrary symbol to represent the empty
tree. In full, the tree above would be:tree(tree(empty, jack, empty), fred, tree(empty, jill, empty))
empty
nodes:tree(tree(empty, 7, empty), '+', tree(tree(empty, 5, empty), '', tree(empty, 3, empty)))
is_tree(empty).  trivial branch 
is_tree(tree(Left, Data, Right)) :  recursive branch 
tree_size(empty, 0). tree_size(tree(L, _, R), Total_Size) : tree_size(L, Left_Size), tree_size(R, Right_Size), Total_Size is Left_Size + Right_Size + 1.
tree_size
contains goals that call for the tree_size
of
smaller trees.
Reference: 
is_list(nil). is_list(list(Head, Tail)) : is_list(Tail).
list(1, list(2, list(3, nil)))
.
instead of
list
and []
instead of nil
.
So Prolog would recognise .(1, .(2, .(3, [])))
as a list
of three numbers. This is briefer but still looks strange, and
is hard to work with.
[1, 2, 3] = .(1, .(2, .(3, []))) ? X = .(1, .(2, .(3, []))). X = [1, 2, 3]

[ ]
, the symbol

acts as an operator to construct a list from
an item and another list.
? X = [1  [2, 3]]. X = [1, 2, 3].
? Head = 1 , Tail = [2, 3], List = [Head  Tail]. List = [1, 2, 3].
? [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 = 1  So [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. 
? [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
.
member(X, [X  _]).
 trivial branch: a rule with a head but no body  
member(X, [_  Y]) :  recursive branch 
The first rule has the same effect as: member(X, [Y_]) : X = Y.
The form member(X, [X_]).
is preferred, as it avoids the extra
calculation.
member
is actually predefined in Prolog. It is a
builtin predicate. There are quite a few builtin
predicates in Prolog. We do not have the time to find out about most of them
in COMP9414. Look at the COMP9814 Prolog Extension
notes if you want to get an idea about some of the builtin predicates.
"Predefined" means that you do not need to put the rules for
member
into your code  Prolog already knows the definition
of member
. Do not redefine predefined predicates.
=
in goalsEarlier, 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.
In the definition of member
, we are already assuming that
we know how to find a member in the tail.
[1, 3]
and [5, 2]
and
concatenate them to make [1, 3, 5, 2]
% concat(List1, List2, Concat_List1_List2) % Concat_List1_List2 is the concatenation of List1 & List2There are two rules:
concat([], List2, List2).
concat([Item  Tail1], List2, [Item  Concat_Tail1_List2]) : concat(Tail1, List2, Concat_Tail1_List2).
? concat([1], [2], [1, 2]).
concat([1  []], [2], [1  [2]]) : concat([], [2], [2]).and
concat([], [2], [2])
holds because of the trivial branch.
% concat(List1, List2, Concat_List1_List2): % Concat_List1_List2 is the concatenation of List1 & List2 concat([], List2, List2). concat([Item  Tail1], List2, [Item  Concat_Tail1_List2]) : concat(Tail1, List2, Concat_Tail1_List2).
cost(cornflakes, 230). cost(cocacola, 210). cost(chocolate, 250). cost(crisps, 190).
total_cost([], 0). % trivial branch total_cost([ItemRest], Cost) : % recursive branch cost(Item, ItemCost), total_cost(Rest, CostOfRest), Cost is ItemCost + CostOfRest.
? total_cost([cornflakes, crisps], X). X = 420
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.
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([ItemRest], 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?
% remove_dups(+List, NewList): % New List isbound to List, but with duplicate items removed. remove_dups([], []). remove_dups([First  Rest], NewRest) : member(First, Rest), remove_dups(Rest, NewRest). remove_dups([First  Rest], [First  NewRest]) : not(member(First, Rest)), remove_dups(Rest, NewRest).
? remove_dups([1,2,3,1,3,4], X). X = [2, 1, 3, 4] ; false.
not
to negate a condition.
An alternative to not
is \+
. See the
article on
negation
in the
Prolog dictionary
to find out why there are two names for not
.
% prolog q s mycode.pl Warning: .../mycode.pl:4: Singleton variables: [Item]The

q means "quiet"  i.e. don't print the SWI Prolog
welcome message. This way, any warnings are easier to notice.
1 % count(Item, List, Count) counts the number of times the 2 % Item occurs in the List, and binds Count to that number. 3 4 count(Item, [], 0). 5 count(Item, [Item  Rest], Count) : 6 count(Item, Rest, RestCount), 7 Count is RestCount + 1. 8 count(Item, [Other  Rest], Count) : 9 not(Item = Other), 10 count(Item, Rest, Count).
_
in front of the
word Item
on line 4 (only). This makes it "don't care"
variable. Check for the possible spelling error, first!
4 count(_Item, [], 0).
See also the entry on singleton variables in the Prolog dictionary.
Reference: 
!
, is a builtin goal that prevents backtracking.
Recall this example:
facts03
database, try
? lectures(codd, X). X = 9311 ; X = 9314. ? lectures(codd, X), ! . X = 9311.
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 multirule 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.
max
, without cut:
% max(A, B, C) binds C to the larger of A and B. max(A, B, A) : A > B. max(A, B, B) : A =< B.
max
, with cut:
max(A, B, A) : A > B, !. max(A, B, B).
=<
vs >
).
The second version substitutes a cut in the first rule for
the negated test.
remove_dups
, without cut:
remove_dups([], []). remove_dups([First  Rest], NewRest) : member(First, Rest), remove_dups(Rest, NewRest). remove_dups([First  Rest], [First  NewRest]) : not(member(First, Rest)), remove_dups(Rest, NewRest).
remove_dups
, with cut:
remove_dups([], []). remove_dups([First  Rest], NewRest) : member(First, Rest), !, remove_dups(Rest, NewRest). remove_dups([First  Rest], [First  NewRest]) : remove_dups(Rest, NewRest).
not(member(First, Rest))
).
The second version substitutes a cut in the second rule for
the negated test in the third rule.
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". 