Next: Solutions and Comments Chapter 8 Up: Solutions and Comments Chapter 6 Previous: Solutions and CommentsChapter 6

Exercise Chapter 6 on Techniques

All the programs in these examples can be done by selecting the right schema and then instantiating it correctly.

We now produce solutions making use of the schema Test For Existence.
```
 
 list_existence_test( Info,[HeadTail]):-

		        element_has_property( Info,Head).

 list_existence_test( Info,[HeadTail]):-

		        list_existence_test( Info,Tail).
```
1. We discard all the parameters from the schema ( Info). We rename list_existence_test to an_integer and element_has_property to integer. We will not show how the others programs are written using the schema.
```
 
an_integer([HT]):-

			integer(H).

an_integer([HT]):-

			an_integer(T).
```
  If the head of the list is an integer then the list contains an integer (this describes the first clause) ---otherwise we require that the tail of the list has an integer somewhere (the second clause).
  Note that the second clause does not strictly have to be second. The two clauses could be the other way round.
```
 
an_integer([HT]):-

			an_integer(T).

an_integer([HT]):-

			integer(H).
```
  If this were so, however, the program would execute much less efficiently. You could try defining the program both ways round and look at what happens using the trace command. What is going on? Either way round, we have the same declarative reading but the procedural reading is not so straight forward.
  For the first way, it goes roughly like this: examine the head of the list and stop with success if this is an integer ---otherwise discard the head of the list and examine the remainder for whether it contains an integer. For the second way: throw away the head of the list and examine the remainder to see whether it has an integer in it ---otherwise look at the head of the list to see whether it is an integer. This sounds very peculiar but it works. What happens is that Prolog throws away all the elements, gets to the empty list and then fails. Backtracking now leads it to try showing that the list consisting of the last element in the original list is an integer: if this is not so then further backtracking will lead Prolog to try the list consisting of the last two elements of the original list has an integer at the front of the list. This keeps on until either an integer is found (working back through the list) or there is no way to backtrack.
2. ```
 
has_embedded_lists([HT]):-

			H=[Embeddedhead_Tail].

has_embedded_lists([HT]):-

			has_embedded_lists(T).
```
  A list has an element which is itself a (non-empty) list if the head of the list is a non-empty list (the first clause) or else the list's tail has an element in it that is a (non-empty) list (the second clause).
  We can also rewrite this to perform implicit unification rather than the explicit unification H=[Embeddedhead_Tail]:
```
 
has_embedded_lists([[Embeddedhead_Tail]T]).

has_embedded_lists([HT]):-

			has_embedded_lists(T).
```
  Does the order of these clauses matter? The same issues apply as with the previous example.
  Note that if we want to fix the problem of extending the code to handle the empty list as well we need:
```
 
has_embedded_lists([HT]):-

			H=[].

has_embedded_lists([HT]):-

			H=[Embeddedhead_Tail].

has_embedded_lists([HT]):-

			has_embedded_lists(T).
```
  That is, another clause to handle the case where the head of the list is an empty list.
  By the way, this can be rewritten as:
```
 
has_embedded_lists([[]T]).

has_embedded_lists([[Embeddedhead_Tail]T]).

has_embedded_lists([HT]):-

			has_embedded_lists(T).
```
  That is, we can rewrite the explicit unification ( H=[Embeddedhead_Tail] as an implicit unification.
  Why does this solution become dubious for e.g. the query ?- has_embedded_lists([a,X,b])? The check that the head element is a list will eventually encounter the equivalent of X=[Embeddedhead_Tail] (or X=[]) ---which will succeed! Is this what is wanted? For then, a list containing a variable will always have an embedded list in it. This may be OK but we would want to know a little more before making a decision.
We now produce solutions for the schema Test All Elements.
```
 
 test_all_have_property( Info,[]).

 test_all_have_property( Info,[HeadTail]):-

			  element_has_property( Info,Head),

		        test_all_have_property( Info,Tail).
```
1. We discard all the parameters from the schema ( Info). We rename test_all_have_property to all_integers and element_has_property to integer. We will not show how the others programs are written using this schema.
```
 
all_integers([]).

all_integers([HT]):-

			integer(H),

			all_integers(T).
```
  We now require that every member of the input list has a common property --- viz that of being an integer.
  We note that the reading of the first clause is that every element of the empty list is an integer. The second clause states that for every list, every element is an integer if the head of the list is an integer and every element of the remaining list is an integer.
2. ```
 
no_consonants([]).

no_consonants([HT]):-

			vowel(H),

			no_consonants(T).

vowel(a).

vowel(e).

vowel(i).

vowel(o).

vowel(u).
```
  Again, the empty list is such that every element in it is not a consonant. And, again, a list has no consonants if the head of the list (first element) is not a consonant and the remainder (tail) of the list has no consonants in it.
  We could have done this a little differently with the help of the predicate \+/1.
```
 
no_consonants([]).

no_consonants([HT]):-

			\+ consonant(H),

			no_consonants(T).

consonant(b).

consonant(c).

(etc.)
```
  The need to specify 26 consonants is a little tedious but acceptable.
We now produce the solutions that make use of the schema Return a Result ---Having Processed One Element.
We use this schema:
```
 
 return_after_event( Info,[HT],Result):-

			  property( Info,H),

			  result( Info,H,T,Result).

 return_after_event( Info,[HeadTail],Ans):-

		        return_after_event( Info,Tail,Ans).
```
1. This one can be shown to be an example of the schema but the `obvious' solution doen't fit exactly.
```
 
nth(1,[HT],H).

nth(N,[HT],Ans):-

			NewN is N-1,

			nth(NewN,T,Ans).
```
  The first clause has the declarative reading that the first element of the list is its head. The second clause has the declarative reading that the nth element of the list is the n-1th element of the list's tail.
  It can be difficult to appreciate how this works. So the procedural reading for the second clause can be taken as: to find the nth element of the list, lop off the first element (the head) and then look for the n-1th element in the remainder of the list (the tail).
  Note that the order of the subgoals is important here. If an attempt is made to write this as:
```
 
nth(1,[HT],H).

nth(N,[HT],Ans):-

			nth(NewN,T,Ans),

			NewN is N-1.
```
  then we get into trouble: when the first subgoal (assuming the first argument is an integer greater than 1) is executed then the variable NewN will not be bound to an integer. This will mean that once we have recursed down the list until the first clause succeeds then we will have a number of subgoals awaiting execution ---the first of which will be 1 is Variable -1. This fails with an error message as the is/2 predicate requires that the right hand side (second argument) be an arithmetical expression and it is not.
  We can generate another solution with a little bit of trickery.
```
 
nth2(N,[HT],H):-

			1 is N.

nth2(N,[HT],Ans):-

			nth2(N-1,T,Ans).
```
  This, if you trace the execution, generates a series of subgoals of the form nth2(somenumber-1-1-1-1-1...,list,variable. The first clause succeeds when the first argument evaluates to 1. Note that the second clause is much neater as a consequence.
  The observant will notice that these various versions of nth/3 do not fit the schema that well. This is partly because the recursion variable is the first argument and is on the natural numbers rather than lists.
2. ```
 
next(PossibleElement,[PossibleElement,NextElementT],NextElement).

next(PossibleElement,[HT],Ans):-

			next(PossibleElement,T,Ans).
```
  This program has a straightforward (declarative) reading: the first clause states that the next element (third argument) after the named one (first argument) is when the list (second argument) begins with the named element and followed by the desired next element. Note the flexible use of the list notation which allows the user to specify a fixed number of elements at the front of a list (here, two).
3. This solution fits the desired schema exactly (and also makes use of the schema Building Structure in the Clause Head).
  We use one parameter from the schema ( Info). We rename return_after_event to del_1st1, property to =, result to =. This results in:
```
 
del_1st1(ToGo,[HT],Ans):-
			H=ToGo,

			Ans=T.

del_1st1(ToGo,[HT],[HNewT]):-

			del_1st1(ToGo,T,NewT).
```
  which can be rewritten to
```
 
del_1st1(ToGo,[ToGoT],T).

del_1st1(ToGo,[HT],[HNewT]):-

			del_1st1(ToGo,T,NewT).
```
  The declarative reading is that when the first argument is the head of the list (which is the second argument) then the third argument is the tail (remainder) of the list ---otherwise, the third argument is a list with the first element the same as that of the second argument and the tail is the list with the desired element deleted.
  We can also describe this procedurally, but we will assume that it is intended that the third argument is output and the other two are inputs.
  When we find the desired element at the head of the input list (the second argument) then we return the tail of that list. When we do not find this, we copy over the head into the output list and go looking for the result of deleting the desired element from the remainder (tail) of the input list.
  Now here is a `solution' using the schema Building Structure in the Clause Body.
```
 
del_1st2(ToGo,L,Ans):-

			del_1st2(ToGo,L,[],Ans).

del_1st2(ToGo,[ToGoT],Acc,Ans):-

			append(Acc,T,Ans).

del_1st2(ToGo,[HT],Acc,Ans):-

			del_1st2(ToGo,T,[HAcc],Ans).

append([],L,L).

append([HL1],L2,[HL3]):-

			append(L1,L2,L3).
```
  Note that we have defined a predicate del_1st2/3 which interfaces to del_1st2/4 and initialises the accumulator (third argument) to the empty list.
  The two clauses have a procedural reading: when we find the desired element then we glue the accumulator onto the front of the remainder (tail) of the list found in the second argument using append/3 ---otherwise, we copy the head of the list to the head of the accumulator and then try to delete the desired element from the tail of the list using the new accumulator.
For each of these examples, we use the schema Return a Result ---Having Processed All Elements. We have, however, two ways of writing each with each way corresponding to a different (list processing) schema. These are, namely, Building Structure in the Clause Head and Building Structure in the Clause Body.
Here is the schema making use of the Building Structure in the Clause Head:
```
 
 process_all( Info,[],[]).

 process_all( Info,[H1T1],[H2T2]):-

		        process_one( Info,H1,H2),

		        process_all( Info,T1,T2).

where  process_one/1 takes  Info and  H1 as input and outputs  H2
```
1. We keep one parameter from the schema ( Info). We rename process_all to nple1 and process_one to is. We will not show how the others programs are written using the schema.
```
 
nple1(N,[],[]).

nple1(N,[HT],[NewHNewT]):-

			NewH is N*H,

			nple1(N,T,NewT).
```
  The declarative reading: every element in the empty list (third argument) is the given multiple (first argument) of the corresponding element in the empty list (second argument) ---otherwise, the list found in the third argument position is in the desired relation to the list found in the second argument position if the head of one list is the desired multiple of the head of the other list and the desired relation holds between the tails of these two lists.
```
 
nple2(N,L,Ans):-

			nple2(N,L,[],Ans).

nple2(N,[],Ans,Ans).

nple2(N,[HT],Acc,Ans):-

			NewN is N*H,

			nple2(N,T,[NewNAcc],Ans).
```
  Again, when using the schema Building Structure in the Clause Body together with an accumulator, we define a predicate nple2/3 which initialises the accumulator for nple2/4.
  Now we have the procedural reading for nple2/4 assuming that the output list is the fourth argument, and the other argument positions are inputs.
  We return the result found in the accumulator once the input list is empty ---otherwise we remove the head from the input list, multiply it by the desired amount, place the result in the accumulator and repeat the process for the tail of the input list and the new accumulator.
2. For this predicate, we need three cases to handle: the empty list, when the head of the list matches the element to be deleted and the case where these two elements do not match.
  The first clause results from the observation that the empty list with all the occurrences of the named element removed is the empty list.
```
 
del_all1(ToGo,[],[]).

del_all1(ToGo,[ToGoT],Ans):-

			del_all1(ToGo,T,Ans).

del_all1(ToGo,[HT],[HAns]):-

			del_all1(ToGo,T,Ans).
```
  The second clause is read declaratively as being true when the element to be deleted unifies with the head of the list (second argument) then the result of deleting all occurrences will be the same as deleting all occurrences from the tail of that list.
  The third clause is the ``otherwise'' case: the result of deleting all occurrences from the list will is the head of the list together with the result of deleting all undesired occurrences from the tail of that list.
  There is a serious problem here. If a program which makes use of del_all1/3 backtracks to redo the call to del_all1/3 then we will get some undesirable behaviour as this definition will generate false solutions (we assume here that we always call del_all1/3 with the second argument a list, the first argument some ground term ( i.e. a term containing no variable) and the third argument a variable).
  Consider the query del_all1(a,[b,a,n,a,n,a],X). The first solution will result in X=[b,n,n]. Fine. But the last `a' was removed through a use of the second clause ---the subgoal would be del_all1(a,[a],X) and originally produced X=[]. Now, on redoing, we try to satisfy the goal with the third clause. The query del_all1(a,[a],X) matches with the head of the clause --- del_all1(ToGo,[HT],[HAns])--- resulting in ToGo=a, H=a, T=[] and X=[HAns] with a subgoal of del_all1(a,[],Ans).. This gets satisfied with Ans=[] and therefore we have another solution for the query del_all1(a,[a],X) --- viz X=[a] and this is wrong.
  The problem arises because any query for which the second argument is a non-empty list such that its head is the element-to-be-deleted will also be guaranteed to match the head of the third clause. This means that there are ways of resatisfying the query which result in undesired (and wrong) solutions.
  How do we solve this? There are two basic ways ---one of which is fairly easy to read and the other relies on the use of the `cut'.
  1. add an extra test condition to the third clause to ensure that attempts to backtrack will fail. We make it impossible for a goal to simultaneously match against the same goal.
```
 
del_all1(ToGo,[],[]).

del_all1(ToGo,[ToGoT],Ans):-

			del_all1(ToGo,T,Ans).

del_all1(ToGo,[HT],[HAns]):-

			\+(H=ToGo),

			del_all1(ToGo,T,Ans).
```
    This is straightforward but does effectively require that unification between the element-to-be-deleted and the head of the list is done twice. Fine for simple checks but this rapidly gets more expensive in more complex situations. Now for the cut.
  2. a cut ( !/0) can be placed to say that once clause 2 has been used then never look for another match...this means:
```
 
del_all1(ToGo,[],[]).

del_all1(ToGo,[ToGoT],Ans):-

			del_all1(ToGo,T,Ans),!.

del_all1(ToGo,[HT],[HAns]):-

			del_all1(ToGo,T,Ans).
```
    This is much less easy to read but is generally more efficient. Beginners, however, tend to spray cuts around producing code like this:
```
 
del_all1(ToGo,[],[]):-!.

del_all1(ToGo,[ToGoT],Ans):-

			del_all1(ToGo,T,Ans),!.

del_all1(ToGo,[HT],[HAns]):-

			del_all1(ToGo,T,Ans),!.
```
    They do this because they do not understand the way the cut works. Because of this, the code written has effects they can't predict or understand. Extra, useless cuts also means a loss of efficiency. Therefore, we strongly recommend the first version.
  Every program you write that is intended to succeed once and once only should be checked to make sure that this will happen at the time you write the predicate.
  The second version making use of the schema Building Structure in the Clause Body:
```
 
del_all2(ToGo,L,Ans):-

			del_all2(ToGo,L,[],Ans).

del_all2(ToGo,[],Ans,Ans).

del_all2(ToGo,[ToGoT],Acc,Ans):-

			del_all2(ToGo,T,Acc,Ans).

del_all2(ToGo,[HT],Acc,Ans):-

			del_all2(ToGo,T,[HAcc],Ans).
```
  Again, we use del_all2/3 to initialise the accumulator for del_all2/4.
  
  Again, note that we would need protection against unexpected backtracking if this program is to be used in another program. Again, we would want a cut in the second clause of del_all2/4.
3. Here we have the version making use of the schema Building Structure in the Clause Head:
```
 
sum1([X],X).

sum1([HT],Ans):-

			sum1(T,RestAns),

			Ans is RestAns+H.
```
  In this first version, we have a straightforward declarative reading. The first clause reads that the sum of integers in a list with a single (assumed) integer is that single integer. The second clause states that the sum of integers in a list is found by summing the integers in the tail of the list and then adding the head of the list to the result.
  Now for the version making use of an accumulator.
```
 
sum2(X,Y):-

			sum2(X,0,Y).

sum2([],Ans,Ans).

sum2([HT],Acc,Ans):-

			NewAcc is Acc+H,

			sum2(T,NewAcc,Ans).
```
  The second version uses an accumulator. Here, we make use of sum2/2 to call sum3 with the accumulator initialised to 0. In this case, the first clause can br read procedurally as saying that once we have an empty list then the answer desired (third argument) is the accumulated total (second argument). The second clause states that we find the answer (third argument) by adding the head of the list (first argument) to the accumulator (second argument) and then repeating the process on the remainder of the list (with the accumulator set appropriately).

Next: Solutions and Comments Chapter 8 Up: Solutions and Comments Chapter 6 Previous: Solutions and CommentsChapter 6

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