|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.|
beat until smooth;
bake for 20 minutes in a moderate oven;
remove tin from oven;
put on bench;
turn off oven;
Some applications of Prolog are:
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:
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
% prolog -s facts03 (multi-line welcome message) ?- lectures(turing, 9020). true. ?- <control-D> %
facts03 loaded into Prolog "?-" is Prolog's prompt output from Prolog hold down control & press D to leave Prolog
green italicsis 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 SWI-Prolog, say
false.See the article on negation in the Prolog dictionary to find out why
No.is a more accurate description of what is happening.
fredis a student, not a lecturer, and that
xyzzyis neither student nor lecturer.
Is there a course, X, that Turing teaches?
?- lectures(turing, Course).← output from Prolog
Course = 9020
?- 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
; again, and then if there
is no further solution, report
?- lectures(turing, Course), studies(fred, Course).
Courseand Fred studies (the same)
,", 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 ;
lecturesclauses, but only two have
coddas their first argument.
Course = 9311, it tries to satisfy the next goal,
studies(jack, 9311).and hence the first solution: (
Course = 9311, Student = jack)
9311(but finds none).
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.(i.e. no full-stop after
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(fido). true ; true.The missing full-stop 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.
ownshave 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 > Day2and the
Mare the same, or if the
Yis the same and
Month1 > Month2, or if
Year1 > Year2.
later, again we are using the comparison operator ">"
X + Y >= Z * W * 2.
% 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.
ismust be an arithmetic expression that can be evaluated right now (no unbound variables).
isis not a C-style assignment statement:
X is X + 1won't work!
isor 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
isif and only if you need to evaluate something:
|BAD!||- nothing to evaluate|
is, you will be penalised in the first Prolog assignment if you use it where it is not needed.
Variables on the RHS of
must be instantiated at the time the
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 used for matching, so a more appropriate use would be:
?- likes(mary, X) = likes(Y, pizza). X = pizza, Y = mary.
tree(tree(L1, jack, R1), fred, tree(L2, jill, R2))
tree) is said to be recursive.
emptyis 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))
tree(tree(empty, 7, empty), '+', tree(tree(empty, 5, empty), '-', tree(empty, 3, empty)))
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_sizecontains goals that call for the
tree_sizeof smaller trees.
is_list(nil). is_list(list(Head, Tail)) :- is_list(Tail).
list(1, list(2, list(3, nil)))
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].
|Match the terms on either side of
|So [First | Rest] is the usual way|
|of writing .(First, Rest) in Prolog|
?- [X | Y] = . X = 1 Y = 
|The empty list is written as |
Lists "end" in an empty list!
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]
?- [X | Y] = [[a, f(e)], [n, m, ]]. X = [a, f(e)] Y = [[n, m, ]]
Y is shown with an extra pair of brackets:
Y is the tail of the entire list:
[n, m, ] is the sole element of
The first rule has the same effect as:
member(X, [Y|_]) :- X = Y.
member(X, [X|_]). is preferred, as it avoids the extra
memberis actually predefined in Prolog. It is a built-in predicate. There are quite a few built-in 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 built-in predicates. "Pre-defined" means that you do not need to put the rules for
memberinto your code - Prolog already knows the definition of
member. Do not re-define predefined predicates.
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 belength([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
=to. Programmers who fail to do this are usually still thinking procedurally.
Programming Principles for Recursive Structures
- Only deal with one element at a time.
- Believe that the recursive program you are writing has already been written.
In the definition of
member, we are already assuming that we know how to find a member in the tail.
- Write definitions, not programs!
- If you are used to writing programs for conventional languages, then you are used to giving instructions on how to perform certain operations.
- In Prolog, you define relationships between objects and let the system do its best to construct objects that satisfy the given relationship.
Concatenating Two Lists
- Suppose we want to take two lists, like
[5, 2]and concatenate them to make
[1, 3, 5, 2]
- The header comment is:% concat(List1, List2, Concat_List1_List2) % Concat_List1_List2 is the concatenation of List1 & List2There are two rules:
- First, the trivial branch:concat(, List2, List2).
- Next, the recursive branch:concat([Item | Tail1], List2, [Item | Concat_Tail1_List2]) :- concat(Tail1, List2, Concat_Tail1_List2).
- For example, consider
?- concat(, , [1, 2]).
By the recursive branch:concat([1 | ], , [1 | ]) :- concat(, , ).and
concat(, , )holds because of the trivial branch.
- The entire program is:% 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).
An Application of Lists
- Find the total cost of a list of items: Cost data:cost(cornflakes, 230). cost(cocacola, 210). cost(chocolate, 250). cost(crisps, 190).
- Rules:total_cost(, 0). % trivial branch total_cost([Item|Rest], Cost) :- % recursive branch cost(Item, ItemCost), total_cost(Rest, CostOfRest), Cost is ItemCost + CostOfRest.
- Sample query:?- 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.
This is an optional homework exercise.
What happens if we change the recursive branch rule for
total_costas 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
- The next procedure removes duplicates from a list.
- It has three rules. This is an example of a common list-processing template.
- If the list is empty, there's nothing to do.
- If the first item of the list is a member of the rest of the list, then discard it, and remove duplicates from the rest of the list.
- Otherwise, keep the first item, and again, remove any duplicates from the rest of the list.
- % 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.
- Note the use of
notto negate a condition. An alternative to
\+. See the article on negation in the Prolog dictionary to find out why there are two names for
- If Prolog finds a variable name that you only use once in a rule, it assumes that it may be a spelling mistake, and issues a Warning about a "singleton variable" when you load the code:% 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.
- Here is the code that produced this (with line numbers added):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).
- To suppress the warning, put an
_in front of the word
Itemon line 4 (only). This makes it "don't care" variable. Check for the possible spelling error, first!4 count(_Item, , 0).
Reference: Bratko chapter 5
The Cut Operator (!)
- Sometimes we need a way to prevent Prolog finding all solutions, i.e. a way to stop backtracking.
- The cut operator, written
!, is a built-in goal that prevents backtracking.
- It turns Prolog from a nice declarative language into a hybrid monster.
- Use cuts sparingly and with a sense of having sinned.
Cut Operator 2
Recall this example:
Cut Prunes the Search Tree
- If the goal(s) to the right of the cut fail then the entire clause fails and the the goal that caused this clause to be invoked fails.
- In particular, alternatives for Course are not explored.
Cut Prunes the Search Tree 2
- Another example: using the
facts03database, try?- lectures(codd, X). X = 9311 ; X = 9314. ?- lectures(codd, X), ! . X = 9311.
- The cut in the second version of the query prevents Prolog from backtracking to find the second solution.
Using cuts in
laterto 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 > M2in the second rule for
later) to specify the case in which it is appropriate. More examples of this are below.
Another cut example
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).
- The first version has a negated test in the second rule (
>). The second version substitutes a cut in the first rule for the negated test.
- Remember, no cuts in the first assignment unless they are essential! Hint: the first assignment can be done without cuts.
Another cut example 2
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).
- The first version has a negated test in the third rule (
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".
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.