Building Structure in the Clause Body

Next: Proof Trees Up: Reconstructing Lists Previous: Building Structure in

Building Structure in the Clause Body

Now we produce a variant which achieves a similar (but not identical) effect. We introduce a new kind of variable: the accumulator. Consider the example:

 
triple([],Y,Y).

triple([H1T1],X,Y):-

			 H2 is 3*H1,

		       triple(T1,[H2X],Y).

We still have the first argument as the recursion argument but now the third argument is the result argument and the second argument is the accumulator. Now, we can see that the recursive call triple(T1,[H2X],Y) is simpler in the first argument than the head triple([H1T1],X,Y) and more complex in the second argument (the accumulator).

Note that the third argument is unchanged. If this is so, how can it take a value at all? Well, the recursion stops once we reach a call with its first argument as the empty list. This means that we will need to unify the goal with the head of the first clause. This will result in the second argument (the accumulator) being unified with the third argument (the result) which, at this point, is an unbound variable. We establish that this up-to-now unchanged variable is bound to the term in the accumulator. Following back along the path of recursive calls, we see that (more or less) the result we want is returned.

The goal triple([1,2,3],[],X) will result in X=[9,6,3]. Note two things: the expected order is reversed and that the accumulator has to be initialised in the original call. Sometimes, however, the order is not too important.

Here is the schema:

 
 process_all( Info,[],Acc,Acc).

 process_all( Info,[H1T1],Acc,Ans):-

		        process_one( Info,H1,H2),

		        process_all( Info,T1,[H2Acc],Ans).

where  process_one/1 takes  Info and  H1 as input and outputs  H2

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