Next: Solutions and Comments Chapter 11 Up: Solutions and Comments Chapter 9 Previous: Solutions and Comments Chapter 9

Exercise Chapter 9.1

First, we examine the execution of the query female_author. We take the first clause for female_author/0 and solve for author(X). We use the first clause of author/1 and solve the resulting subgoal, name(X), using the first clause of name/1 to get X=sartre. The subgoals write(X), write(' is an author') and nl succeed with the side-effect of writing:
```
 
sartre is an author
```
on the screen. Then we solve the subgoal female(X) with X still bound to sartre. Neither of the heads of the clauses for female/1 match the goal female(sartre) so Prolog fails and backtracks. We keep backtracking until we get to redo the subgoal author(X). This means that we now try to redo name(X) and we satisfy this with X=calvino. Again, we generate the side-effect on the screen of
```
 
calvino is an author
```
and try to satisfy female(X) with X bound to calvino. Again, this fails and we backtrack. Again, the subgoal name(X) can be satisfied ---this time, for the last time, with X=joyce. On the screen we get
```
 
joyce is an author
```
and another attempt to prove that female(X) with X=joyce (which fails). This time, on backtracking, there are no more solutions for name(X). We now move on to resatisfy author(X) by using its second clause. This generates, on the screen,
```
 
no more found!
```
then fails. We now backtrack and, since there are no more ways of satisfying author(X), we are through with the first clause of female_author/0. The second succeeds by writing
```
 
no luck!
```
and succeeds.
We now explain how to place the cuts to get the desired outputs.
1. The first solution requires the use of one cut to produce the side-effect:
```
 
sartre is an author

no more found!

no luck!
```
  Note that, compared with before, we have much the same but we infer that there is only one solution for name(X). This suggests that we place the cut so that name(X) succeeds once only. This can be done by rewriting the first clause of name/1 as
```
 
name(sartre):-!.
```
2. The next solution requires the use of one cut to produce the side-effect:
```
 
sartre is an author

calvino is an author

joyce is an author

no more found!
```
  Compared with the original output, we observe that the phrase `no luck!' is not generated. This suggests that we want to commit ourselves to the first clause of female_author and not use the second at all. Hence we have the solution:
```
 
female_author:- !,author(X),write(X),and so on
```
  but note that now the original query fails after producing the desired side-effect.
  Also note that we have to put the cut before the call to author/1 ---otherwise we would only generate one of the names rather than all three.
3. The next solution requires the use of one cut to produce the side-effect:
```
 
sartre is an author

no luck!
```
  This time we observe that we only get one name and we don't generate the phrase `no more found!'. This suggest that we want author(X) to succeed once and once only ---and go on to use the second clause of female_author (this suggests that the cut cannot be one of the subgoals in the first clause of female_author). We don't want to generate the phrase `no more found' ---so this suggests that we commit to the first clause of author/1. We will put a cut in the body of this clause ---but where? If we put it thus:
```
 
author(X):- !,name(X).
```
  then we would generate all three names by backtracking. Hence the desired solution is:
```
 
author(X):- name(X),!.
```
  We can read this as being committed to the first, and only the first, solution for name(X).
4. The next solution requires the use of one cut to produce the side-effect:
```
 
sartre is an author
```
  Now we don't want to generate either `no more found!' or `no luck!' ---and we only want one of the names generated.
  So we definitely want to be committed to the first clause of female_author/0. This suggests putting the cut in the body of the first clause of this predicate ---but where? If we put it after the subgoal female(X) then we would get all three solutions to name(X) and their associated side-effects. If we put it before author(X) we also get roughly the same. Therefore we want something like:
```
 
female_author:- author(X),!,write(X),and so on
```
5. The next solution requires the use of one cut to produce the side-effect:
```
 
sartre is an author

calvino is an author

joyce is an author

no luck!
```
  Now we don't get the message `no more found!'. This suggests that we want to commit to the first clause of author/1. If we put the cut after the subgoal name(X) then we will commit to the first solution and not be able to generate the other two. Hence we must put the cut before as in:
```
 
author(X):- !,name(X).
```
We will assume a mode of mode delete(+,+,?). i.e. the first two arguments are always completely instantiated and the third argument can be either instantiated or a variable.
```
 
delete([], _, []).

delete([KillTail], Kill, Rest) :-

		        delete(Tail, Kill, Rest),!.

delete([HeadTail], Kill, [HeadRest]):-

		       delete(Tail, Kill, Rest).
```
The cut is placed in the body of the second clause. This is needed because, in the code given in the probem, any usage of the second clause to delete an element allows the query to be resatisfied on redoing. This is caused by the fact that any query matching the head of the second clause will also match the head of the third clause.
To define disjoint/2, here is the solution found in the standard DEC-10 library.
```
 
%   		disjoint(+Set1, +Set2)

%   		is true when the two given sets have no elements in common.

%   		It is the opposite of intersect/2.

disjoint(Set1, Set2) :-

		        member(Element, Set1),

		        memberchk(Element, Set2),

		        !, fail.

disjoint(_, _).

member(X,[XRest]).

member(X,[YRest]):-

			member(X,Rest).

memberchk(X,[XRest]):- !.

memberchk(X,[YRest]):-

			memberchk(X,Rest).
```
Note the definition is quite interesting: First, note that we make use of the generate---test schema: the first clause of disjoint/2 uses member/2 as a (finite) generator to generate each of the elements in the first list one by one. Next, the solution is tested using memberchk/2 for the second set. Second, if the element is in both sets then we meet the cut---fail schema. This means the call to disjoint/2 fails. If the generated element never passes the test, then the attempt tosatisfy the call to disjoint/2 using the first clause fails and we use the second clause which makes use of a catch-all condition.
Other solutions are possible:
```
 
disjoint(Set1, Set2) :-

		        \+(member(Element, Set1), member(Element, Set2)).
```
Here, disjoint succeeds whenever it is impossible to find a common element for both lists. If such an element exists then it fails.

To define plus/3:

 
plus(A, B, S) :-

		      integer(A),

			integer(B),

		        !,

		        S is A+B.

plus(A, B, S) :-

			integer(A),

			integer(S),

		        !,

		        B is S-A.

plus(A, B, S) :-

		      integer(B),

			integer(S),

		        !,

		        A is S-B.
plus(A, B, S) :-

			plus_error_message(A, B, C).

The first three clauses cope with the cases where two or more of the arguments to plus/3 are instantiated to integers.

We need the cut to implement a commit schema as we don't have disjoint cases.

The last clause is intended to point out to the programmer that an instantiation fault has occurred. The exact form of the message is up to you.

Next: Solutions and Comments Chapter 11 Up: Solutions and Comments Chapter 9 Previous: Solutions and Comments Chapter 9

Paul Brna
Mon May 24 20:14:48 BST 1999