next up previous contents
Next: Failure-Driven Loop Up: Some General Program Previous: Finite and Infinite

Test --- Process

Now we look at another fundamental schema. The idea with test --- process is to guarantee that some inputs will only be `processed' if the input passes a test.

 
 test_process( Info,X,Y):-

test( Info,X),

process( Info,X,Y).

where we assume that the Info is 0 or more arguments which are all input arguments, the last but one argument is an input argument and the last argument is a output argument. Although this gives a very procedural view it is often possible to give a declarative reading.
We usually want to make sure that
  1. test does not have alternative ways of confirming that the generated element is ok
  2. process does not have alternative ways of `processing' the input
In short, we often want only one way of finding an output.

We have already met a program that satisfies this schema ---one for parity/2 (which is slightly rewritten here).

 
parity(X,Y):-

odd(X),

Y=odd.

parity(X,Y).

\+(odd(X)),

Y=even.

plus set of facts defining odd/1

This example illustrates that if the input argument is an integer then we see two cases: either the integer is even or it is odd. There is no third case. Nor can any integer be both even and odd.

As in the above example, the usage of test --- process is closely coupled with the idea of writing all the clauses for a predicate in this form ---each clause is designed to handle one `class' of input. The whole scheme falls down if we do not design the `classes' of input to be disjoint -- i.e. no input falls into more than one category. We also require that each input falls in at least one category ---to summarise, each input falls in one and only one class.

We can show a previous example which does not properly use the test --- process schema (for good reasons). Modifying the code using this schema results in a different and useful program.

 
member(Element,[ElementTail]).

member(Element,[HeadTail]):-

member(Element,Tail).

Now member/2 can be used as a generator if the first argument is a variable and its second argument is a list ---as in the goal member(X,[a,b,c,d,e,f]. The first solution for X is the first element of the list [a,b,c,d,e,f]. On redoing, we get, in succession, X bound to the different elements in the list.

We now rewrite using the test --- process schema. We also rename the predicate to the standard name of memberchk/2 (this is its usual name in libraries of Prolog code).

 
memberchk(Element,[HeadTail]):-

Element = Head.

memberchk(Element,[HeadTail]):-

\+(Element = Head),

memberchk(Element,Tail).

This will no longer generate alternative solutions on backtracking for the goal memberchk(X,[a,b,c,d,e,f]) (because there are no alternative ways of resatisfying it). If the mode of use is mode memberchk(+,+) then the meaning is that we check that the first argument is an element of the list (which is the second argument).



next up previous contents
Next: Failure-Driven Loop Up: Some General Program Previous: Finite and Infinite



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