List of Exercises
Programming languages can be classified in a variety of ways. One major division is between procedural languages and declarative languages. Procedural languages require the programmer to specify in some detail the steps the program must execute in order to accomplish its intended task. In declarative languages, on the other hand, the programmer provides in the program a definition of the task to be accomplished, but is not concerned with the details of how the computer will use the definition.
Most conventional programming languages (Basic, C, Fortran, Pascal etc.) are procedural. Prolog belongs to the class of declarative programming languages. It gets its name (PROgramming in LOGic) because it is modelled on first order logic and (in principle) requires the programmer to give a logical model of the task to be undertaken. This makes programming in Prolog a rather different experience to programming in a procedural language.
In introducing Prolog, I have followed Pereira and Shieber (1987) in breaking it down into three stages. The first, Database Prolog, is a restricted subset which allows us to exemplify some of the basic ideas. The second, Pure Prolog, is an extension of the first which maintains a purely logical semantics but introduces arithmetic, recursion and lists. The final extension, to Full Prolog, takes us into the range of extra-logical constructs, such as input and output, negation and flow of control.
A Prolog program consists of a file containing a set of facts and (optionally) a set of rules.
Semantically the facts constitute a declaration of a true state of affairs. As far as Prolog is concerned, any fact in its database is treated as true.
If a file containing the fact
male(phil).
is consulted, the goal
|?-male(phil)
elicits the Prolog response
yes
This is Prolog reporting that the expression evaluates as true with respect to its database.
With respect to the same database, the goals
|?-female(phil). |?-male(chas).
will produce the responses:
|?-female(phil). no |?-male(chas). no
That is, with respect to this database, these facts are not known to be true.
A database consisting only of facts is not very interesting. The action picks up when rules are added.
Logic contains rules of inference. A very basic one is the one
known as Modus Ponens. This takes the following form
| p É q | from the formula `p implies q' |
| p | if proposition `p' is true |
| \therefore q | conclude that `q' is true |
For example:
| If John is drunk, then John is happy |
| John is drunk |
| \therefore John is happy |
Prolog includes conditional formulae (like p É q, but with some syntactic reorganisation), and an algorithm for computing inferences using Modus Ponens, but before we look at how rules are represented in Prolog, we need to look in more detail at the relationship between standard logic and Prolog.
The kind of logic used by Prolog is a subset of First Order Logic called quantifier-free Horn Clause Logic. As the name suggests, there are no existential or universal quantifiers. Instead, any variable is implicitly assumed to be universally quantified. The statement
male(X).is therefore to be taken as "x.male(x), or 'Everything is male'.
Note that any expression which begins with a capital letter or with the underscore character is a variable in Prolog.
The implication sign ® or É is represented in Prolog as :-, and the order of antecedent and consequent is reversed, so p É q in Prolog will become q :- p.
Horn Clause logic is characterised by the fact that it allows only one term1 in the consequent of a conditional (i.e. before the :-). What follows the conditional must be a term (possibly complex and consisting itself of subterms including conjunctions and disjunctions).
Conjunctions, i.e. expressions which take the logical form p Ù q are realised in Prolog as p , q, with a comma replacing the standard conjunction sign. So, a term p , q is true iff both p and q are true.
Disjunctions, i.e. expressions which take the logical form p Ú q are realised in Prolog as p ; q, with a semicolon replacing the standard disjunction sign. So, a term p ; q is true if p is true or q is true (or both are).
The formula "x. "y. female(x) Ùparent(x, y) É mother(x, y) (`If x is female and y's parent, then x is y's mother'.) translates into Prolog as
mother(X, Y):-
female(X), parent(X, Y).
The part of the rule preceding the implication sign (i.e. mother(X,
Y)) is termed the head of the rule and the part to the right of the
implication sign is termed the body of the rule.
David Warren, writing in The Art of Prolog (xi) writes,
The main idea was that deduction could be viewed as a form of computation, and that a declarative statement of the form:This is what Prolog does.
Q ÙR ÙS É P
could also be interpreted procedurally, as:
``To solve P, solve Q and R and S."
Given a rule such as the following:
mother(M, C):- female(M), parent(M, C).it attempts to prove a goal such as:
|?-mother(liz, chas).by first proving female(liz) and then (if this is successful) by proving parent(liz, chas). If this process fails at any point, Prolog will report its failure with no.
Note that the deduction algorithm proceeds in a left-to-right, depth-first order.
A set of facts and rules constitutes a (logic) program.
A query is a means of extracting information from a logic program and consists of attempting to prove that the query is a logical consequence of the program. We will say more about how Prolog does this in section 1.4. When we pose a query to Prolog, we are setting up a goal for Prolog to try to satisfy. If Prolog is able to find facts and rules that allow it to conclude that the goal is true, we say that the goal is `satisfied', or `succeeds'; if a goal cannot be satisfied, we say it `fails'.
There is a major difference between the interpretations assigned to variables in facts and queries. In facts, variables are taken as being universally quantified; in queries, they are treated as being existentially quantified.
As a fact in file, human(X) is equivalent to "x. human(x) - `everything is human'.
As a query,
|? human(X).corresponds to evaluating $x. human(x) - `is there at least one thing that is human?'.
The deduction process involves matching terms in the goal against terms in head of the rule, and terms in the body of the rule against other terms, either in the head of other rules or against facts. The matching process used is termed unification.
Briefly, it works as follows:
male(phil). female(liz). parent(phil, chas). parent(liz, chas). mother(M,C):- female(M), parent(M,C).
The goal:
|?-mother(liz,chas).is evaluated like this:
|?- mother(liz,chas). 1 1 Call: mother(liz,chas) ? 2 2 Call: female(liz) ? 2 2 Exit: female(liz) ? 3 2 Call: parent(liz,chas) ? 3 2 Exit: parent(liz,chas) ? 1 1 Exit: mother(liz,chas) ? yes
In this case the terms in the consequent of the rule matched immediately against facts in the database. Let's add the following fact and rules to those given above
male(harry). parent(chas,harry). grandmother(GM, C):- mother(GM, P), parent(P, C).The goal grandmother(liz,harry) evaluates as follows:
|?- grandmother(liz,harry). 1 1 Call: grandmother(liz,harry) ? 2 2 Call: mother(liz,_732) ? 3 3 Call: female(liz) ? 3 3 Exit: female(liz) ? 4 3 Call: parent(liz,_732) ? 4 3 Exit: parent(liz,chas) ? 2 2 Exit: mother(liz,chas) ? 5 2 Call: parent(chas,harry) ? 5 2 Exit: parent(chas,harry) ? 1 1 Exit: grandmother(liz,harry) ? yes
As before, Prolog first tries to prove the leftmost term in the antecedent, but this requires that it search further, since mother(liz,_732) is not a fact. Only when it has successfully concluded this subproof (via female/1 and parent/2) does it continue to attempt the second clause in the definition of grandmother/2.2
Note that this version of Prolog (like most), renames the variables you supply it with. In this case C has become _732. This is to avoid accidental clashes of variable-names. Note also that when GM unifies with the constant liz, Prolog only uses the constant in its subsequent search.
Exercise 1
Extend the program by adding rules for the following family
relationships (add more people if necessary, so that you can
check your results):
What problems do you encounter? What is the nature of the problems?
What solutions (if any) can you suggest. (Reading the literature
on Prolog will help.)
First attempt:
"x. "y married(x, y) É married(y, x)
'married' is a symmetrical predicate.
In theory, this translates straightforwardly into Prolog:
The starting point is to observe that all parents are ancestors of
their children:
This definition brings up a very important point: the definition of
ancestor refers to itself. It is a recursive definition.
brother(X, Y) where X is Y's brother
sister(X, Y) where X is Y's sister
son(X, Y) where X is Y's son
daughter(X, Y) where X is Y's daughter
married(X, Y) where X is married to Y
ancestor(X, Y) where X is Y's ancestor
brother(X, Y):-
male(X),
male(Y),
parent(P, X),
parent(P, Y).
|?- brother(X,Y).
X = harry
Y = harry ;
X = harry
Y = harry ;
X = harry
Y = wills ;
X = harry
Y = wills ;
X = wills
Y = harry ;
X = wills
Y = harry ;
X = wills
Y = wills ;
X = wills
Y = wills ;
no
One problem here is that among the results returned are:
X = harry
Y = harry ;
X = wills
Y = wills ;
The first definition of brother/2 is incorrect. It requires an
additional condition to the effect that the two individuals must be
different:
brother(X, Y):-
male(X),
male(Y),
parent(P, X),
parent(P, Y),
different(X, Y).
You are not in a position to implement different/2 as yet, because it
exceeds the scope of database Prolog. We will return to this at a
later date. However, even if this additional condition is included,
the results may not be what you expect:
|?-brother(X,Y).
X = harry
Y = wills ;
X = harry
Y = wills ;
X = wills
Y = harry ;
X = wills
Y = harry ;
no
The goal returns two sets of identical responses. Why?
son/2
son(X, Y):-
male(X),
parent(Y, X).
daughter/2
daughter(X, Y):-
female(X),
parent(Y, X).
married/2
This needs to be entered as a set of facts. It is not possible to
deduce a marriage relationship from any of the other facts in the
database.
married(liz, phil).
married(di, chas).
These facts will provide correct answers to goals matching the facts,
but will not produce positive answers to goals such as:
married(phil, liz).
One solution to this would be to add this as a new fact. The
disadvantage of this strategy is that, for every marriage
relationship, we would have to enter two new facts into the database,
when there is a generalisation available:
married(X, Y):-
married(Y, X).
Here is the response, given the following facts and rule
married(X, Y):-
married(Y, X).
married(liz, phil).
married(di, chas).
\begin{verbatim}
to the goal
\begin{verbatim}
|?-married(X, Y).
{ERROR: Out of address space}
{Execution aborted}
The problem is that the rule calls itself repeatedly, without ever
coming up with a solution. Even if the order of facts and goals in
the program is reversed, ensuring that at least two solutions are
found,
married(liz, phil).
married(di, chas).
married(X, Y):-
married(Y, X).
the program will still produced an infinite set of solutions, of which
the following are a small subset:
X = liz
Y = phil ;
X = di
Y = chas ;
X = phil
Y = liz ;
X = chas
Y = di ;
X = liz
Y = phil ;
X = di
Y = chas ;
X = phil
Y = liz ;
X = chas
Y = di ;
X = liz
Y = phil
[terminated by user]
The moral is that, with respect to symmetrical predicates, logic and
Prolog are not equivalent. Prolog is not complete (i.e. it won't
necessarily find all solutions). There is, however, a trick for
avoiding this behaviour: to ensure that the rule and the facts do not
use the same predicate name:
married_to(liz, phil).
married_to(liz, phil).
married(X, Y):-
married_to(X,Y).
married(X, Y):-
married_to(Y,X).
ancestor/2
For this we need some parent/2 facts:
parent(george_v, george_v1).
parent(george_v1, liz).
parent(phil, chas).
parent(liz, chas).
parent(chas,harry).
parent(chas,wills).
parent(di,harry).
parent(di,wills).
ancestor(P, C) :-
parent(P, C).
We could use this as a model for including the ancestor relationship
which exists between grandparents and grandchildren, by including a
double call to parent in the body of a second clause for ancestor/2,
but this would not be a good move, because there is no limit on the
number of generations that can be involved in the ancestor
relationship. Instead, the second clause in the definition of the
rule should be like this:
ancestor(A, D):-
parent(A, C),
ancestor(C, D).
So, A is D's ancestor A has a child who is
D's ancestor.
Recursion is an extremely powerful tool and one which is widely used in Prolog programming.3
Although recursion can be used over many different data structures, one of the most frequently encountered in NLP environments is the list. So it is to this that we turn our attention first.
Lists in Prolog are themselves terms, and consist of a sequence of terms separated from one-another by commas and enclosed at each end by matching square brackets:
[a] [a,b] [a,b,c]Note that, as you might expect, [ ] represents the empty list.
Internally to Prolog, lists are represented as right-branching trees. So the structure of [a, b, c] would be
] ] ]
The first element of a list is called the head of the list, and the remainder is called the tail of the list. Note that (perhaps counterintuitively) the last element of every non-empty list is the empty list; although the normal Prolog notation suppresses this fact. So a is the head of all the above lists; [ ] is the tail of the first example, [b] is the tail of the second example, and [b, c] is the tail of the third example.
Because of the importance of the distinction between the head and tail of a list, Prolog provides a convenient notation that can be used to match against the head and tail of any list.
[X | Y]Where X will match against the head, and Y against the tail. (Of course, any variable names may be used, not just X and Y.)
To illustrate these concepts, we will also introduce an operator which can be used to evaluate unification (discussed in section 1.4) directly. This operator is the equals sign =/2. The expression A = B is true in Prolog, if A is a term, and B is term, and A and B unify. The following can be typed in and evaluated:
Two constants:
|?- a = a. yes |?- a = b. noA constant and a variable:
|?- a = X. X = a ? yesTwo variables:
|?- X = Y. Y = X ? yesUsing this operator, we can illustrate how variables unify with lists:
Lists and variables are both terms:
|?- [ ] = X. X = [ ] ?Single-element lists unify (because they have the same `arity'):
|?- [a] = [X]. X = a ? yesThe following fails, because the two lists have different numbers of elements:
|?- [a, b] = [X]. noThe following unify because both lists are of length 2:
|?- [a, b] = [X, Y]. X = a, Y = b ? yesNote carefully the difference between the above and the following using HeadTail notation.
X matches the first element of the list [a], which is the constant a, and Y matches the tail, which is the empty list:
|?- [a] = [X | Y]. X = a, Y = [ ] ? yesHere again, X matches with a, and Y matches with the tail of the list [a, b], which is itself the list [b]:
|?- [a, b] = [X | Y]. X = a, Y = [b] ? yesFinally, a three element list:
|?- [a, b, c] = [X | Y]. X = a, Y = [b, c] ? yesA couple of trivial examples of predicates using lists are the following:
A predicate, which when supplied with a list a first argument, returns the first element of the list as its second argument:4
first([First|Rest], First).
second([First, Second|Rest], Second).
tail([First|Tail], Tail).
Naming variables The only syntactic requirement that Prolog places on variables is that they start either with an upper case letter, or with an underscore. This means that you could restrict yourself to writing X, Y or Z when you want a variable. For example, the program first/2 in footnote 4 might look like this:
first(X, Y):-
X = [Z|W],
Y = Z.
This will do exactly the same job as the original definition, but it
is not a good idea Ð- as programs become more complex, they become very
difficult to understand if you use such simple names for variables.
Even this simple example illustrates how opaque such definitions can
be come.
By giving your variables mnemonic names, you help to document the function of your programs and to explain to a reader (including yourself) what information the variables are intended to convey.
The anonymous variable If you have tried putting any of the above examples into a file which you then consult into SICStus Prolog, you will have discovered that it complains. For example, loading the rule for second/2 produces the following:
{Warning: [First,Rest] - singleton variables in second/2 in lines 1-1}
This is because each of the variables First and Rest
occurs only once in the definition. Because the most common use of
variables in Prolog is to convey information from one part of a
program to another, the occurrence of any singleton variable triggers
a warning, to alert the programmer to the possibility of an error.
What to do?
second([_, Second|_], Second).
Although we have two occurrences of the underscore in this definition, Prolog treats them as unrelated (and identical in interpretation to the original definition), as `anonymous'.
Exercise 2 Rewrite the definitions of second/2 and tail/2
above to include explicit calls to the unification operator =/2.
Two clauses:
A version with explicit unification:
A slightly shorter, but equivalent, version is to 'unfold' the goal
Result = [First|List] and put the relevant unification into the head
of the rule, as follows:
second(_, [_, Second|_], Result):-
Result = Second.
|?- fifth([1,2,3,4,5,6,7], X).
X = 5
yes
fifth([_, _, _, _, Five|_], Five).
The subtle part is to make provision for the
list to be of any arbitrary length greater than 5, by using the Head|Tail
notation.
is_list([ ]).
is_list([_|_]).
cons(First, List, Result):-
is_list(List),
Result = [First|List].
cons(First, List, [First|List]):-
is_list(List).
The ancestor/2 problem of exercise 1 discussed above provides a classical example of recursion. Such recursive rules always have two components,
ancestor(P, C) :- parent(P, C).and
ancestor(A, D):- parent(A, C), ancestor(C, D).
The base of the recursion is a non-recursive clause, which, in a computational context, tells the computation when to stop. Here the minimal definition of ancestor is a parent. The recursion crucially involves the predicate calling itself.
A classical example of recursion in list-processing is identifying whether some item is an element of a list. This predicate is commonly called member/2. It is true if the item is on the list, and false otherwise. The base is that situation where we can be sure that we have found the item in question on the list. The limiting case here would be if the item sought is the first one on the list. We can generalise from this to the following clause:
member(Item, List):- List = [Item|Rest].This is OK if the item sought is indeed the first item, but what if it isn't? In that case, we need to ignore the first item and proceed to check the remainder (i.e. the tail) of the list (note the use of the anonymous variable for the item we aren't interested in):
member(Item, [_|Tail]):- member(Item, Tail).If the item sought is on the list, this procedure will find it, and Prolog will respond with 'yes'; if not, it will fail, and Prolog will respond with 'no'.5 Note that, as usual with many Prolog predicates, member/2 can be used to generate solutions; if the second argument is instantiated to a list and the first is a variable, the predicate can to used to select items off the list:
|?- member(X, [a, b, c]). X = a ? ; X = b ? ; X = c ? ; no
Another classical example of recursion is the predicate append/3. This predicate's three arguments are all lists. append(X, Y, Z) is true if the Z is a list that is the result of sticking the list Y onto the end of the list X. For example, append([a,b], [c,d], [a,b,c,d]) is true.
The definition of append/3 is similar to that of member/2 in that both involve working down a list item by item. In the case of append/3, however, no test is being carried out, and eventually the end of one of the lists will be reached, leaving the empty list. This gives the base: what is the result of appending an empty list to a list L? Clearly just L. In Prolog:
append([ ], List, List).What if the first list isn't empty? We need to take its head, save it, and stick it onto the front of the result. The result itself comes about as the consequence of carrying out the same procedures on the tail of the list. This is the recursive clause:
append([Head|Tail], List, [Head|Result]):-
append(Tail, List, Result).
append/3 can also be used to generate solutions. Here are
some examples:
|?- append([a,b], [c,d], X). X = [a,b,c,d] ? yes
|?- append(X, [c,d], [a,b,c,d]). X = [a,b] ? yes
|?- append([a,b], X, [a,b,c,d]). X = [c,d] ? yes
|?- append(X, Y, [a,b,c,d]). X = [ ], Y = [a,b,c,d] ? ; X = [a], Y = [b,c,d] ? ; X = [a,b], Y = [c,d] ? ; X = [a,b,c], Y = [d] ? ; X = [a,b,c,d], Y = [ ] ? ;
Hint: in all of the following, the base involves the case where the first list argument is the empty list.
Exercise 6 Define a predicate delete/3 whose arguments are 1) a
term, 2) a list and 3) another list consisting of the second argument
minus the first occurrence of the term, if it occurs. For example,
delete(b, [a,b,c,a,b], X) should give X = [a,c,a,b].
Note also that delete/3 should not fail; if the item to be
deleted is not on the list, the original list should be returned as
the value of the third argument. E.g. delete(a, [b,c,d], X)
should give X = [b,c,d]
This, like member/2, can be reduced to the case where the item to be
deleted is the head of the list, in which case the third argument
simply becomes whatever is left on the list (i.e. its tail):
delete(Item, [Item|Rest], Rest).
The recursion deals with those cases where the head of the list is not
the item sought. In that case, we disregard it and continue searching
the tail of the list. We also need to ensure that the disregarded
item is returned as part of the result:
delete(Item, [Head|Tail], Result):-
delete(Item, Tail, InterimResult),
Result = [Head|InterimResult].
(Again, this can be shortened by unfolding the explicit call to =/2,
as follows:
delete(Item, [Head|Tail], [Head|InterimResult]):-
delete(Item, Tail, InterimResult).
Finally, we need a clause to cover cases where the item sought is not
on the list. In that case, the problem reduces to the case where we
have reached the end of the list:
delete(Item, [], [ ]).
The complete definition is the following three clauses:
delete(Item, [Item|Rest], Rest).
delete(Item, [], [ ]).
delete(Item, [Head|Tail], [Head|InterimResult]):-
delete(Item, Tail, InterimResult).
Exercise 8 Define a predicate reverse/2 whose arguments are both lists, the second being the mirror image of the first. E.g. reverse([a,b,c], X) should give X=[c,b,a]. Hint: you will find it useful to use append/3 in the recursive clause of reverse/2.
Exercise 9
Write a recursive definition that will translate a string of
English words into their French (or German or Swedish or ¼
counterparts). You will need a set of 2-place facts giving the
English and French counterparts, and a two-place recursive rule
that works its way down a list, looking up the word-translations
item by item, and putting the resulting translation into the
second argument. The predicate should produce the following kind
of result:
|?- translate(['John', is, an, idiot], French).
French = [Jean,est,un,imbecile] }
yes
Before looking at other examples of recursion, it will be helpful to look at operators, because these are used in Prolog arithmetic. The basic arithmetic operations of addition, subtraction, multiplication etc., could be treated as predicates within the kind of Prolog style you have encountered so far. Addition, for example, might look like this:
+(X, Y, Z)where X and Y are the arguments to be added, and Z is the result of the addition. Indeed, some Prologs allow you to do addition like this. Many more Prologs, however, define arithmetical operations in a way which is much more like the standard conventions, and write the above equation as
Z is X + YThis is a novel format, because it writes the predicate symbols is and + between their arguments, without brackets. This is because these two symbols have been defined within Prolog as infix operators.
In working with operators, we need to pay attention to two factors: precedence and associativity.
In an expression with more than one operator, we need to know which operator to evaluate first. For example, the arithmetical expression 1 + 2 * 3 is potentially ambiguous. It could be (1 + 2) * 3 (i.e. 9), or 1 + (2 * 3) (i.e. 7). In fact, the convention in mathematics is to the latter: multiplication has precedence over addition. The * operator in Prolog is defined so that it too has precedence over the + operator.
Precedence involves the case where there are different operators in a single expression. Associativity involves multiple occurrences of the same operator. For example, 3 - 2 -1 gives different results depending on whether it is treated as (3 - 2) - 1 (i.e. 0), or 3 - (2 -1) (i.e. 2). In arithmetic it is the first order which is conventional: the left-most pair of numbers is evaluated first, then the next left-most, and so on. The subtraction operator is said to be left-associative.
Precedence and associativity are defined in Prolog with the built-in predicate op/3. The first argument determines precedence, the second associativity and the third defines the operator symbol. i.e.
op(Precedence,Associativity,Operator)
The associativity argument is also used to declare whether the operator is an infix operator (like the arithmetical ones), a prefix operator or a postfix operator.
The precedence argument is an integer. The principle is: the
lower the number, the higher the precedence. In Sicstus Prolog,
the arithmetical operators have the following precedence values:
| Operator | Precedence Value |
| + | 500 |
| - | 500 |
| * | 400 |
| / | 400 |
The conventions for defining the order (prefix, infix and postfix)
and associativity (left, right, none) of operators are as follows,
where f stands for the position of the operator and x
and y for its arguments:
| Prefix | Postfix | Infix | Associativity |
| fx | xf | xfx | none |
| yf | yfx | left | |
| fy | xfy | right |
The occurrence of the argument symbol y indicates that an expression may contain multiple occurrences of the operator in question, and its position (left or right of f) indicates whether it is left or right associative.
The set of built-in operators and their properties can be explored by use of the built-in predicate current_op/3:
|?- current_op(Precedence,Associativity,Operator). Operator = sequential, Precedence = 1150, Associativity = fx ? yesForcing Prolog to backtrack, producing further responses, by using semi-colon <return> will produce a complete listing of all the operators know to the system at the time the goal is posed.
Prolog is not the programming language of choice for carrying
out heavy-duty mathematics. It does, however, provide arithmetical
capabilities. The pattern for evaluating arithmetic expressions
is (where Expression is some arithmetical expression)
X is Expression6
The variable X will be instantiated to the value of Expression. For example,
|?- X is 10 + 5. X = 15 ? yes ?- X is 10 - 5. X = 5 yes ?- X is 10 * 5. X = 50 yes ?- X is 10 / 5. X = 2 yes ?- X is 10 + 5 * 6 / 3. X = 20 yesIt is important to note that Expression is not evaluated by itself. You have to supply a variable (followed by the infix operator is/2) to collect a result.
Other pre-defined Prolog arithmetic infix operators are
| > | greater than |
| < | less than |
| >= | greater than or equal to |
| =< | less than or equal to |
Later in the course we will use op/3 to define operators of our own, to make programs easier to read. Here we will return to the topic of defining recursive rules, with the addition of arithmetic.
It is often useful to be able to calculate (or check) the length of a list. With arithmetic operators this is something that we can now do. The base is the empty list, which is obviously of length 0. This give us the Prolog clause:
length([ ], 0).The recursion simply requires that we add 1 for each item on the list:7
length([H|T], N):- length(T, N1), N is N1 + 1.
Exercise 10 Define predicate square/2 that takes a number as its first argument and returns the square of that number as its second argument. (No recursion in this one.)
Exercise 11
Define a predicate power/3 that takes numbers as its first
two arguments P and N and returns as the value of its third
argument a number which is N to the power of P. E.g.
Note that this requires a recursive rule and the use of arithmetic.
|?- power(3,2,P).
P = 8
yes
Earlier, I partitioned Prolog into 3 subsets:
Database Prolog was what we started with; Pure Prolog introduced lists, maths and operators
Full Prolog goes beyond purely logical constructs and introduces various non-logical predicates for handling such operations as input and output, and controlling the execution of programs.
The most useful input output predicates are write/1, read/1 and nl/0.
write(term) is true if term is a Prolog term. As a side-effect, it causes term to appear on the current output device (e.g. your screen in the Winterm window).
nl is always true, and as a side-effect, sends a newline instruction to the current output device. So the conjunction of a write/1 instruction and a nl/0 instruction will result in a term being displayed on the screen, followed by a carriage return.
read(X) is true if the user types a term followed by a full-stop. X becomes instantiated to the term. E.g.
| ?- read(X). |: this. X = this ? yes | ?-read/1 can be used to input a list of words (because a list is a term), but the list has to be typed complete with brackets and commas:
|?-read(X). [this,is,a,list]. X = [this,is,a,list] yes
Getting Prolog to accept a string of atoms and convert them into a list is quite heavy-duty Prolog programming and involves the use of get/1 and get/0, which accept single characters (in ASCII numerical format); the building of a list of such numbers; their conversion from a list of numbers into a Prolog atom, using the predicate name/2 and, finally the construction of a list of such atoms.
Other predicates in full Prolog allow you to test for the type of an expression:
var(X) is true if X is a variable when var/1 is called.
atom(X) is true if X is an atom
etc. Any Prolog textbook will have a section discussing such predicates.
One very important, and very tricky, predicate is the 'cut', written as the exclamation mark !. This is quite dangerous in inexperienced hands (such as yours!). It is an instruction to Prolog not to back-track looking for other solutions. Here is are some examples:
Negation as failure
In dealing with data-base Prolog, we discovered that the correct definition of brother/2 and sister/2 require a test for inequality:
sister(X,Y):- female(X), parent(P, X), parent(P, Y), different(X,Y).We know how to check that two terms are the same (by unification, using =/2), but how do we check that they are different? In principle by checking that they do NOT unify. In fact, Prolog has a built-in predicate +/1 which allows this to be done:8
|?- \+ a=b. yesSo different/2 could be programmed as:
different(X, Y):-
\+ X=Y.
The interesting thing from the present perspective is how
+/1 itself is programmed. The standard
definition is the following two clauses:
\+ X :- X, !, fail. \+ X.These clauses MUST occur in this order, if the definition is to work. When + term is called, X is instantiated to term, and the first call in the body of the first clause of +/1 tests to see if term is true. If it is known to the Prolog data-base, this call will succeed and control will pass to !/0 ('cut'). Cut always succeeds, so control passes to the built-in predicate fail/0. fail/0 always fails. (Surprise, surprise.)
Normally, when a goal fails, Prolog backtracks to see if there are any alternative solutions. Here, to see if term has any more solutions. It will then repeat the procedure until all the possibilities have been exhausted, at which point control would pass to the second clause of +/1, which (since it has no conditions) would succeed.
However, the presence of the cut in the first clause prevents this behaviour. Instead, when the call to cut has succeeded, Prolog `cuts away' all the information about alternative choices before the cut. Therefore, when fail/0 is encountered, there is nowhere else to go and the call + term fails straightaway.
The only situation in which the second clause will be reached is if term itself fails. This will be the case if term can't be found in the Prolog database, or proved indirectly.
So, + a=b will fail if a=b; and will succeed if a=b fails.
Read carefully a Prolog textbook before using the cut yourself. (Using +/1 is OK, provided you realise that when it fails its 'meaning' is 'Prolog was unable to find a solution'. I.e. 'don't know', rather than false. This definition of negation is called 'negation by failure'.
delete_all/3
You may have noticed that the predicate delete_all/3 (which you defined in response to an exercise) does not work as anticipated if you force Prolog to give you more than one solution. Here is what happens:
|?- delete_all(a, [a,b,a], X). X = [b] ? ; X = [b,a] ? ; X = [a,b] ? ; X = [a,b,a] ? ; no
Recall the definition of delete_all/3:
1. delete_all(_, [ ], [ ]).
2. delete_all(Item, [Item|Tail] , Result):-
delete_all(Item, Tail, Result).
3. delete_all(Item, [Head|Tail] , [Head|Result]):-
delete_all(Item, Tail, Result).
What happens is that, when the user requests a second solution,
Prolog first of all goes back to the last procedure call made
in providing the first solution (this was the second line of
clause 2 of the definition, which succeeded by using clause 1
of the definition), and tries to see if there is an alternative
way of satisfying the goal
delete_all(a,[ ],_595)There isn't, so Prolog backtracks; having tried clause 2 unsuccessfully, it now tries clause 3. Clause 3 succeeds with Item = a and Head = a, as can be seen in the trace:
|?- delete_all(a, [a,b,a], X). 1 1 Call: delete_all(a,[a,b,a],_93) ? 2 2 Call: delete_all(a,[b,a],_93) ? 3 3 Call: delete_all(a,[a],_595) ? 4 4 Call: delete_all(a,[],_595) ? 4 4 Exit: delete_all(a,[],[]) ? 3 3 Exit: delete_all(a,[a],[]) ? 2 2 Exit: delete_all(a,[b,a],[b]) ? 1 1 Exit: delete_all(a,[a,b,a],[b]) ? X = [b] ? ; 1 1 Redo: delete_all(a,[a,b,a],[b]) ? 2 2 Redo: delete_all(a,[b,a],[b]) ? 3 3 Redo: delete_all(a,[a],[]) ? 4 4 Redo: delete_all(a,[],[]) ? 4 4 Fail: delete_all(a,[],_595) ? (in clause 2) 4 4 Call: delete_all(a,[],_813) ? (in clause 3) 4 4 Exit: delete_all(a,[],[]) ? 3 3 Exit: delete_all(a,[a],[a]) ? 2 2 Exit: delete_all(a,[b,a],[b,a]) ? 1 1 Exit: delete_all(a,[a,b,a],[b,a]) ?
The problem arises because we have assumed that the second clause excludes the third - but it doesn't. Now that we have access to the cut, we can impose this assumption on the program.
There are (at least) two ways to do this:
3. delete_all(Item, [HeadTail] , [Head|Result]):-
\+ Item = Head,
delete_all(Item, Tail, Result).
|?- delete_all(a, [a,b,a], X).
1 1 Call: delete_all(a,[a,b,a],_93) ?
2 2 Call: delete_all(a,[b,a],_93) ?
3 3 Call: a=b ?
3 3 Fail: a=b ?
3 3 Call: delete_all(a,[a],_603) ?
4 4 Call: delete_all(a,[],_603) ?
4 4 Exit: delete_all(a,[],[]) ?
3 3 Exit: delete_all(a,[a],[]) ?
2 2 Exit: delete_all(a,[b,a],[b]) ?
1 1 Exit: delete_all(a,[a,b,a],[b]) ?
X = [b] ? ;
1 1 Redo: delete_all(a,[a,b,a],[b]) ?
2 2 Redo: delete_all(a,[b,a],[b]) ?
3 3 Redo: delete_all(a,[a],[]) ?
4 4 Redo: delete_all(a,[],[]) ?
4 4 Fail: delete_all(a,[],_603) ?
4 4 Call: a=a ?
4 4 Exit: a=a ?
3 3 Fail: delete_all(a,[a],_603) ?
2 2 Fail: delete_all(a,[b,a],_93) ?
2 2 Call: a=a ?
2 2 Exit: a=a ?
1 1 Fail: delete_all(a,[a,b,a],_93) ?
no
delete_all(_, [], []).
delete_all(Item, [Item|Tail] , Result):-
!,
delete_all(Item, Tail, Result).
delete_all(Item, [Head|Tail] , [Head|Result]):-
delete_all(Item, Tail, Result).
Once execution of the program has passed the point at which the
cut occurs, it cannot subsequently backtrack beyond this point.
This means that once the head of clause 2 has unified with a
goal, there is no longer any possibility of resorting to clause
3, as the following trace shows.
|?- delete_all(a, [a,b,a], X). 1 1 Call: delete_all(a,[a,b,a],_93) ? 2 2 Call: delete_all(a,[b,a],_93) ? 3 3 Call: delete_all(a,[a],_598) ? 4 4 Call: delete_all(a,[],_598) ? 4 4 Exit: delete_all(a,[],[]) ? 3 3 Exit: delete_all(a,[a],[]) ? 2 2 Exit: delete_all(a,[b,a],[b]) ? 1 1 Exit: delete_all(a,[a,b,a],[b]) ? X = [b] ? ; 1 1 Redo: delete_all(a,[a,b,a],[b]) ? 2 2 Redo: delete_all(a,[b,a],[b]) ? 3 3 Redo: delete_all(a,[a],[]) ? 4 4 Redo: delete_all(a,[],[]) ? 4 4 Fail: delete_all(a,[],_598) ? 3 3 Fail: delete_all(a,[a],_598) ? 2 2 Fail: delete_all(a,[b,a],_93) ? 1 1 Fail: delete_all(a,[a,b,a],_93) ? no
Exercise 12
Another example. Recall the definition of member/2:
As the following trace shows, each time a goal succeeds, it is
by choosing the first clause of member/2. Whenever an additional
solution is requested, Prolog backtracks from the first clause
of the definition and tries the second clause instead, until
all possibilities have been exhausted.
Here is a modified version of the standard definition of member/2;
one with a cut in the first clause. How does its behaviour differ
from the standard member/2, and why?
What is the function of the following program?
member(Item, [Item|_]).
member(Item, [_|Tail]):-
member(Item, Tail).
We previously used member/2 to discover whether the first
argument was an element of the second argument, but, if the first
argument is a variable, it can also be used to generate a set
of answers:
|?- member(X, [a,b,c]).
X = a ? ;
X = b ? ;
X = c ? ;
no
|?- member(X, [a,b,c]).
1 | 1 call member(_1630,[a,b,c])
1 | 1 exit member(a,[a,b,c])
X = a ;
1 | 1 redo member(a,[a,b,c])
2 | 2 call member(_1630,[b,c])
2 | 2 exit member(b,[b,c])
1 | 1 exit member(b,[a,b,c])
X = b ;
1 | 1 redo member(b,[a,b,c])
2 | 2 redo member(b,[b,c])
3 | 3 call member(_1630,[c])
3 | 3 exit member(c,[c])
2 | 2 exit member(c,[b,c])
1 | 1 exit member(c,[a,b,c])
X = c ;
1 | 1 redo member(c,[a,b,c])
2 | 2 redo member(c,[b,c])
3 | 3 redo member(c,[c])
4 | 4 call member(_1630,[])
4 | 4 fail member(_1630,[])
3 | 3 fail member(_1630,[c])
2 | 2 fail member(_1630,[b,c])
1 | 1 fail member(_1630,[a,b,c])
memberchk(Item, [Item|_]):- !.
memberchk(Item, [_|Tail]):-
memberchk(Item, Tail).
pred(X, [X]).
pred(X, [_|Y]):-
pred(X, Y).
Provide a trace of the program executing the following call and state
what the value of X will be when the call terminates.
|?- pred(X, [the,talk,of,the,town]).
What would be the result of forcing the program to backtrack?
Exercise 14
Write a Prolog program in which you type in an English sentence
and Prolog replies with another sentence that is an altered version
of the one you have typed in. For example, the program might
produce an interaction like the following:
It is easy to write a program to do this by simply following
these steps:
You should take the input to be a list; so that the interaction
goes:
This program is just a variant of the one we constructed in class
to translate English into French, so you can model this program
on that one.
A difference between this program and the French translator, however,
is that here 'reply' is a zero-place predicate; to accept
input from the user, it must contain a call to read/1 as part
of its definition. Similarly, Prolog's answer has to be produced
using the write/1 predicate. Note that the Prolog response
does not contain any brackets or commas; you therefore will need to
write a (recursive) predicate which will 'write' the items on a list
one by one, with a space between each one, until it reaches the end of
this list and stops - and integrate it into your program.
Write your program so it will run indefinitely, until the interaction
is terminated by the user.
You: you are a computer
Computer: i am not a computer
You: do you speak french
Computer: no, i speak german
|?- reply.
|:[do, you, know,french].
no, i know german
yes
Most computer programs which handle natural language input contain a component known as a parser. This is a program which assigns a linguistic analysis to the input (a parse).
Parsing is a big topic, which L433 Introduction to Computational Linguistics covers in some depth, but we will present an example here.
We need to supply the program with information about the grammar and lexicon of the language it will be dealing with.
So, first we need to decide on a representation for these. We will keep things very simple and try to stay close to what elementary linguistics texts provide.
Linguists are in the habit of writing rules such as
S Þ NP VP
V Þ likes
We can keep quite close to this kind of respresentation in Prolog by defining Þ as an infix operator:
:- op(500, xfx, `==>').
We can now specify a grammar as follows, keeping to the Prolog conventions of using lower case letters for constants, commas to conjoin items and full-stop to terminate a statement.
s ==> np, vp. np ==> det, n. vp ==> v, np. det ==> the. n ==> dog. n ==> cat. v ==> chased.
parse/3 will return `yes' if the string can be analysed as an instance of the syntactic category. So we will get interactions like the following:
| ?- parse(s, [the,dog,chased,the,cat], []). yes | ?- parse(np, [the,dog,chased,the,cat], []). no | ?- parse(vp, [chased,the,cat], []). yes | ?- parse(np, [the,cat], []). yesThe parser that we will describe here operates (like Prolog) in a left-to-right, top-down, depth-first fashion.
We start by seeing how the syntactic category we are seeking (Cat) is defined by the grammar. There are two possibilities
In the first case, we compare that first item in the string of words with the right hand side of a rule which has Cat as its left-hand side. If they match, we have parsed the first word, with the rest of the string left over (i.e. the third argument):
parse(Cat, [Firstword|Restwords], Restwords):-
Cat ==> Firstword.
In the second case, we need to look up a rule which has Cat
as its left-hand side, find out what its daughters are and parse
them. Because parse/3 is expecting only a single category as
its first argument, and there may be more than one daughter in a rule,
we need to define a new predicate to handle the parsing of the
daughters of a rule: parsedaughters/3:
parse(Cat, String, Rest ):- (Cat ==> Daughters), parsedaughters(Daughters, String, Rest).That is parse/3 dealt with. We now have to define parsedaughters/3. Again, there a two cases to consider:
If there is more than one, we pass the first and the string to be parsed to parse/3 to deal with, and then pass the remaining daughters and what is left of the string to parsedaughters/3 to work on further:9
parsedaughters((Cat, Cats), String, Rest):-
parse(Cat, String, Next), parsedaughters(Cats, Next, Rest).
If there is exactly one, we just pass it and the string to be parsed
to parse/3:
parsedaughters(Cat, String, Rest):- parse(Cat, String, Rest).That's it.
The complete code is:
parse(Cat, [Firstword|Restwords], Restwords):-
(Cat ==> Firstword).
parse(Cat, String, Rest ):-
(Cat ==> Daughters),
parsedaughters(Daughters, String, Rest).
parsedaughters((Cat, Cats), String, Rest):-
parse(Cat, String, Next),
parsedaughters(Cats, Next, Rest).
parsedaughters(Cat, String, Rest):-
parse(Cat, String, Rest).
Finally, here is a variant, parse/4, whose extra (second) argument builds a tree of the parse - represented like a bracketed string.
parse(Cat, [Cat,Firstword], [Firstword|Restwords], Restwords):-
Cat ==> Firstword.
parse(Cat, [Cat|Tree], String, Rest ):-
(Cat ==> Daughters),
parserest(Daughters, Tree, String, Rest).
parserest((Cat, Cats), [Tree, Resttree], String, Rest):-
parse(Cat, Tree, String, Next),
parserest(Cats, Resttree, Next, Rest).
parserest(Cat, Tree, String, Rest):-
parse(Cat, Tree, String, Rest).
Here is an example:
| ?- parse(s, T, [the,dog,chased,the,cat], []). T = [s,[np,[det,the],[n,dog]],[vp,[v,chased],[np,[det,the],[n,cat]]]] ? yes