Module 5
Multiple uses of procedures

 

 
Back | Top of this Module | Next
The three patterns of list processing have been presented. Now we will look again at some of the selected examples.
app/3 revisited

The definition of app/3 was: 
     % 1 terminating condition
     app([], List, List).
     % 2 recursive
     app([Hd|Tl1], List2, [Hd|Tl3]) :-
          app(Tl1, List2, Tl3).
We could use this to find: 
     | ?- app([a,b,c], [1,2,3], List).

     List=[a,b,c,1,2,3] ? ;

     no
This is the use we would expect of such a procedure: we're asking "what does [a,b,c] and [1,2,3] make when appended?". We can ask an alternative question: what pairs of lists, when appended, make [a,b,c,1,2,3]. 
     | ?- app(List1, List2, [a,b,c,1,2,3]).

     List1 = [] 
     List2 = [a,b,c,1,2,3] ? ;

     List1 = [a] 
     List2 = [b,c,1,2,3] ? ;

     List1 = [a,b] 
     List2 = [c,1,2,3] ? ;

     List1 = [a,b,c] 
     List2 = [1,2,3] ? ;

     List1 = [a,b,c,1] 
     List2 = [2,3] ? ;

     List1 = [a,b,c,1,2] 
     List2 = [3] ? ;

     List1 = [a,b,c,1,2,3] 
     List2 = [] ? ;

     no
We can see that there are seven possible pairs that make up the original list.

One way of looking at what we have done is that we have used this procedure normally (ie we have found what the appending of two lists will give), and "back-to-front" (ie by finding the question for which know the answer). This way of using procedures in more than one way is one of logic programming's strengths. Given enough imagination the part of the programmer, it is possible to create some very elegant and simple solutions to problems. However, as will be seen later in the course, it is quite easy to get caught out by inadvertently finding infinite branches in the search tree: ie situations where Prolog will recurse forever without finding a solution.  
 

 
delete_element/3

The definition of delete_element/3 was given as: 
     % 1 terminating condition
     delete_element(Elem, [Elem|Tail], Tail).
     % 2 recursive
     delete_element(Elem, [Head|Tail1], [Head|Tail2]) :-
          delete_element(Elem, Tail1, Tail2).
We have seen that we can use this to find what a list is with a particular item deleted: 
     | ?- delete_element(b, [a,b,c], [a,c]).

     yes
     | ?- delete_element(c, [a,b,c], List).

     List = [a,b] ? ;

     no
We can also use this procedure to find what lists can be created by adding a single element to it: 
     | ?- delete_element(b, List, [a,c]).

     List = [b,a,c] ? ;

     List = [a,b,c] ? ;

     List = [a,c,b] ? ;

     no
We can also use it to find what pairs of an element and a list can be made from another list: 
     | ?- delete_element(Elem, [a,b,c], List).

     Elem = a 
     List = [b,c] ? ;

     Elem = b 
     List = [a,c] ? ;

     Elem = c 
     List = [a,b] ? ;

     no

 
 
Examples that use Prolog arithmetic
 

We have seen two examples of the multiple uses of procedures, but it would be wrong to think that all Prolog procedures can be used in more than one way. Apart from procedures with only one argument and examples which disappear into infinite recursion, another important group of procedures are those that include arithmetic. In Prolog, arithmetic is implemented as an extra-logical extension and is not bi-directional. Simply put, Prolog is happy with an uninstantiated variable on the left-hand side of is/2, but will halt with an instantiation error is there is an uninstantiated variable on the right-hand side.

In a previous section, we defined memb/3 as: 

     % 1 terminating condition
     memb(Elem, [Elem|_], Cnt) :-
          write(Cnt),
          nl.
     % 2 recursive
     memb(Elem, [_|Tail], Cnt) :-
          Cnt1 is Cnt + 1,
          memb(Elem, Tail, Cnt1).
and described its use to find the position at which a given element occurred. It seems very similar to position/3, which we defined as: 
     % 1 terminating condition
     position(1, Elem, [Elem|_]).
     % 2 recursive
     position(Cnt, Elem, [_|Tail]) :-
          Cnt1 is Cnt - 1,
          position(Cnt1, Elem, Tail).
However, if we use position/3 to perform the functionality of memb/3, or vice versa, we will soon have instantiation errors because the variable Cnt will be uninstantiated.

The patterns of list processing given so far don't provide a way around this problem. However, there is another pattern of list processing that side-steps the problem and also offers more opportunity to write more efficient recursive programs. Procedures in this pattern are generally called accumulators.
 

 
 
Back | Top of this Module | Next