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
- Suppose we want to take two lists, like
[1, 3] and [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 & List2
There 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], [1, 2]).
By the recursive branch:
concat([1 | []], [2], [1 | [2]]) :-
concat([], [2], [2]).
and concat([], [2], [2]) 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
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
- The next procedure removes duplicates from a list.
- It has three rules. This is an example of a common
list-processing template.
- Algorithm:
- 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
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.
Singleton Variables
- 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 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.
Controlling Execution
| 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
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
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
(
=< vs >).
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.
|
