PROLOG Summary Volume 2
PROLOG Summary Volume 2
(Volume one obtainable by
clicking at the link at the end)
Lists
Firstly, what is a list? Simply, it’s a sequence (i.e. order is important) of single elements that may (and mostly do in practical programming) bear some relation to each other. e.g.
(i) a, b, c, d, e
(ii) lion, tiger, puma, lynx
(iii) f, r, 3, X, y
As you can see, (i) and (ii) are lists that contain members of a particular category - letters of the alphabet and big cats respectively. The third example is a collection of constants, integers and variables.
The point here is that any syntactically correct Prolog element (constant, variable or structure) may appear in a Prolog list. This includes the case where one list is part of another.
The structure of lists
In order to make lists useful, we need to be able to access each individual element of the list. To do this we use the concept of splitting the list into two parts, the head and the tail, for example for the list
lion, tiger, puma, lynx
The head is: lion (the element)
The tail is: tiger, puma, lynx (the list)
So the head of the list is the first element of the list. The tail of the list is that list made up of the remainder of the list, whatever that may contain, with the order maintained
Note again that the head is an element and the tail is a list.
e.g. the list Joe, Bloggs
head = Joe
tail = Bloggs
tail is still a list (just containing one element)
Also we could have a list containing one element
Joe
head = Joe
tail = the empty list
The concept of an empty list is very important (and is analogous to the null set in set notation). Because of this concept there are no logical problems with respect to empty lists and this leads to consistency.
So how do we write lists in Prolog?
In order to make use of the ability to split lists into head and tail, Prolog provides a special notation with which to define lists in programs There are two special symbols used:
(i) The square open/close brackets
These are used to denote the beginning and end of a list respectively, e.g.
[a, b, c, d]
[lion, tiger, puma, lynx]
[f, r, 3, X, y]
(ii) The separator symbol
This is written as | and is used to allow a list to be represented as a head and a tail. The element to the left of the separator is taken to be the head of the list and that to the right as the tail of the list. Thus to represent a list broken up in this way, we write
[H|T]
Example session
If we have a list that we wish to call letters, we have the predicate letters with a single argument, namely the list [a, b, c, d]. This fact would be represented as follows:
letters( [a, b, c, d]).
That's the program. Now, as users using the program and its knowledge, we will perform some operations on the list:
(Remember system's communication in red; human user's communication in blue.)
?- letters(X).
X = [a, b, c, d]
?- letters([H|T]).
H = a
T = [b, c, d]
?- letters([X,
Y|T]).
X = a
Y = b
T = [c, d]
?- letters([H|_]).
H = a
?- session ends
Exercise
A knowledge base contains the following facts/clauses
fish([shark, pike, salmon, cod]).
birds([hawk, dove, sparrow, canary]).
The following questions were asked by the user, after the Prolog system was asked to consult the file containing the information in brown:
(i) fish([H|T]).
(ii) birds([_|T]).
(iii) birds(Birds).
(iv) fish([shark, X, salmon, Y]).
(v) birds(X, Y, Z).
What would the system return?
Answers:
(i) H=shark
(ii)T=[dove,sparrow,canary]
(iii)Birds=[hawk,dove,sparrow,canary]
(iv)X=pike,Y=cod
Manipulating the contents of lists
The basis for success with the manipulation is an understanding of the structure of lists (i.e. the head - tail concept) and the application of recursion.
The first predicate we will look at is the member predicate i.e. is E an element of the list L, or member(E, L).
To begin with, we know that an element which represents the head of a list must be an entry in that list and we can use that property to write a boundary condition, as in
member(E, L) :- L = [E|_].
this states that "E is a member of the list L if L is made up of a head E and any tail (hence the blank variable). A more elegant way of writing this is
member(E, [E|_]).
We can simply say that E is a member of any list of which it's
the head - obviously! Just as any person is in a bus queue if
he's at the head of the queue. There may be other ways in which
he can be in the queue other than being at its head, but if he's
the first person, then he's definitely in the queue. (he could be
she of course)
Next, we need a second (recursive) clause which will allow all other entries to be identified. To construct the rule, we use the property that any member in the tail of the list must also be a member of the list itself.
member(E, [_|T]) :- member(E, T).
/*E is a member of a list if the list
comprises any head and a tail T, which contains E.*/
This leads us to the full rule :
member(E, [E|_]). /*Rule 1 */
E is a member of any list of which it's the head.
member(E, [_|T]) :- member(E, T). /*Rule
2 */ but if it's not the head, then it's a member of
the list if it's in the tail.
Let us examine the way in which the member predicate operates with the use of an example. Consider the following query:
?-member(c, [a,b,c,d]).
Enter knowledge base - try Rule 1 - this will fail because c is not the same as a (the head of the list).
Proceed to Rule 2 - the query will match with the head of the rule and E will be instantiated to c and T to [b,c,d]. The problem is thus reduced to satisfying the subgoal:
member (c, [b,c,d]).
Re-enter knowledge base-try Rule 1 - this will fail because c is not the same as b (the head of the list)
Proceed to Rule 2 - the subgoal will match with the head if the rule and E will be instantiated to c and T to [c,d]. The problem is thus reduced to satisfying the subgoal:
member(c, [c,d]).
Re-enter knowledge base - try Rule 1 - this will succeed because c is the same as c (the head of the list).
Prolog will thus record a success and respond yes.
But what if an object is not a member of the list? Where is the stopping condition to halt the procedure?
If the element being searched for is not a member of the list, the problem will eventually reduce to that of attempting to satisfy the subgoal: member(object, []). Prolog will re-enter the knowledge base to try and prove or disprove this. It will first meet Rule 1 which will fail because it is impossible to reduce the empty list to a head and a tail. Rule 2 will also fail for the same reason. Prolog will find no other rules which could be used to match and therefore possibly satisfy the subgoal. It will therefore respond no.
In summary, the member predicate works in the following manner:
Prolog will continually remove elements from the head of the list until either
or
The member predicate is very important and is used as a building block for many other list manipulation predicates.
In general, a list is a recursive structure, consisting of a head and a tail. The tail is, in turn, a list.
It follows that any rule to perform operations on a list is likely to be itself recursive. This is, in fact the case. Such a rule usually operates by performing the necessary manipulations on the head of the list and then using itself recursively to manipulate the tail of the list. Thus, such rules are often of the format:
manipulate(list with head H and tail T) :-
perform manipulation on head H, recursively manipulate tail T.
To put it in more Prolog-like language :
manipulate([H|T]) :- process(H), manipulate(T).
The above form will apply in many (but unfortunately, not all) situations.
Appending two lists
It is often necessary to append two lists. We need to define a predicate
append(X, Y, Z)
which succeeds if Z is the list formed by appending the list Y to the end of the list X. e.g.
?- append( [a,b,c] , [d,e,f], L).
will return
L = [a,b,c,d,e,f] since we're asking what list L is formed from joining [d,e,f] on to [a,b,c]
The recursive predicate is written as
append( [], L, L).
append([H|T], M, [H|S]) :- append(T, M,
S).
Using append
Clever use of the append predicate can lead to other useful list-processing functions:
Decompose a list:
?- append(A,
B, [a,b,c]). /* what two lists when concatenated will form
the list [a,b,c] */
A = []
B = [a,b,c] ?r
A = [a]
B = [b,c] ?r
A = [a,b]
B = [c] ?r
A = [a,b,c]
B = [] ?r
no
Note that there was no one answer to that question; all the above lists B joined to their A lists give [a,b,c]. It's really just that simple!
Find a pattern in a list: (just a reminder here that words beginning with upper case letters are variables; the others are constants)
?- append(Before,
[may|After], [jan, feb, mar, apr, may, june, july, aug, sep, oct,
nov, dec]).
Before = [jan, feb, mar, apr]
After = [june, july, aug, sep, oct, nov,
dec]
We could write a predicate to delete a pattern P, and all that follows, from list L:
del_pattern_to_end(P, L, R) :-
append(R, P, B), append(B, A, L).
/* delete the pattern P and all the
follows from L and put result in R */
Remember that here as always :- means if and , means AND. Remember to recite to yourself the predicate in English when you're revising.
Justification:
Suppose L = APB (1)
Then (obviously) R = A (2)
since we're supposed to remove P and all that follows!!
Now, inserting (2) into (1) gives L =
RPB (3)
Rename B as A
so L = RPA (3)
Let B = RP (4) *
Inserting (4) into (3) gives L = BA (5)
*
Writing (4) and (5) in terms of append
gives the answer. [Note that the object is to get equations with
one variable on the left and two on the right so as to be able to
use append. Note too that (3) becomes discardable since all that
is expressed in it is now contained in (4) and (5). In other
words (4) and (5) replace (3)]
We could write a predicate to delete a pattern P (and nothing more) from a list L:
del_pattern_only(P, L, R) :-append(A,
B, R), append(P, B, C), append(A,C,L).
/* delete the pattern P (only!) from L
and put result in R */
Justification:
Suppose L = APB (1)
Then (obviously) R = AB (2)
since we're supposed to remove P alone!! (compare with the
situation above)
Let C = PB (3)
Inserting (3) into (1) gives L = AC (4)
Writing (2), (3) and (4) in terms of
append gives the answer.
User Examples
?-del_pattern_to_end([c,d],[a,b,c,d],Answer)
Answer=[a]
?-del_pattern_only([c,d],[a,b,c,d],Answer)
Answer=[a,d]
More list processing predicates
Calculate the length of a list.
The length of the list L, whose composition is [H|T] is, to
state the blindingly obvious, 1 plus the length of the list T.
The length of the empty list is zero.
Alternatively: The length of any list is one more than
the length of that list with its head removed. The length
of the empty list is zero.
length([], 0). /*Boundary
condition rule */
length([_|T], N) :- length(T, M), N is
M+1. /* R2 */
(Note: Once T is stripped down to an empty list, the first rule provides a match, thus terminating the recursive calling process. )
examples:
?-length([a,b,c,d,e,f,g],7)./*is
7 the length of the list a,b,c,d,e,f,g */
yes /*yes it
is*/
?-length([a,b,c,d,e,f,g],6).
no
?-length([a,b,c,d,e,f,g],N)./*what's
the length of the list a,b,c,d,e,f,g */
N=7 /* it's 7
of course*/
Determining the nth term of a list:
We do this by recursively removing N elements of a list. The variable R keeps track of how many elements have been removed. When R = 1, then X is assigned to Nth element.
nth(X,1,[X|_]).
nth(X,N,[_|T]):-nth(X,M,T),N is M + 1.
examples:
?-nth(c,3,[a,b,c,d,e,f,g])./*is
c the third entry in the list a,b,c,d,e,f,g */
yes /*yes it
is*/
?-nth(c,4,[a,b,c,d,e,f,g])./*is
c the fourth entry in the list a,b,c,d,e,f,g */
yes /*no it
isn't*/
?-nth(d,Dog,[a,b,c,d,e,f,g])./*where
does d occur in the list a,b,c,d,e,f,g? */
Dog=4 /*it
occurs in the 4th position*/
Asserting, retracting clauses,
Getting Prolog to learn
If we want to look at interactive programming in Prolog, we need the system to remember what has been said to it. Also we need to be able to get the system to selectively forget what it has been told. We will examine the predicates:
The assert predicate
This predicate takes one argument which must be instantiated to a clause. The effect of assert(X) is to place the clause instantiated to X in the knowledge base.
This predicate allow us to add to the knowledge base, in other words, to remember additional information. Once an assert goal has been satisfied, the clause remains in the knowledge base until it is removed.
Example terminal session:
Prolog User
?- assert(man(john)).
yes ?- man(X).
X = john
... session ends
The retract predicate
The retract predicate also takes one predicate, again instantiated to a clausal form, but its effect is to remove clauses from the knowledge base. Once a retract goal has succeeded, the clause referred to is lost from the knowledge base. Example terminal session:
Prolog User
?- assert(man(john)).
yes
?- man(X).
X = john ? y
yes
?- retract(man(john)).
yes
?- man(X).
no
session ends ...
It is possible to retract knowledge referenced in a file consulted by the Prolog system, but the file itself doesn't change, and on each order to consult that file, the knowledge retracted will be automatically restored to the current knowledge base.
For instance we could start with asking the Prolog system to consult a text file with two facts A and B. If we assert another, namely C, during a user session, then it now knows three facts during that session. If we retract fact B, it now knows only facts A and C during that session. Of course the original text file doesn't change since only use of a text editor can do that.
Thus what a Prolog system knows at any time is based (i) on what files it has been told to consult during a user session (ii) plus what's been asserted (iii) minus what's been retracted.
e.g.
peoplefact.pl has
man(john).
man(paul).
User session on VAX (computer talking in red, user in blue):
$setup pop
$prolog
?-consult('peoplefact.pl').
yes
?-male(X). //
English translation list all people who are male.
X=john.y
X=paul.y
no
?-assert(male(frank)).
?-male(X).
X=john.y
X=paul.y
X=frank.y
no
etc