Download Definitional Programming in GCLA Techniques, Functions, and

Functional Logic Programming in GCLA
7.1
Why Pattern Matching Causes Problems
Let us try to define the function min returning the smallest value of two natural
numbers. If we only allow canonical objects as arguments the natural definition
is:
min(0,_) <= 0.
min(s(_),0) <= 0.
min(s(X),s(Y)) <= succ(min(X,Y)).
When we wish to allow arbitrary expressions as arguments we need at least one
more clause to evaluate arguments. First we try to define a version that only
evaluates the arguments which are not natural numbers, that is, we evaluate
exactly the needed arguments. The difficulty in doing this is to write evaluation
clauses without introducing overlapping clauses while still covering all possible
cases. One solution is to add four more clauses giving a total of seven clauses:
min(0,_) <= 0.
min(s(_),0) <= 0.
min(s(X),s(Y)) <= succ(min(X,Y)).
min(E,s(X))#{E \= 0, E \= s(_)} <= (E -> V) -> min(V,s(X)).
min(E,0)#{E \= s(_),E \= 0} <= 0.
min(s(X),E)#{E \= 0,E \= s(_)} <= (E -> V) -> min(s(X),V).
min(E1,E2)#{E1 \= 0,E1 \= s(_), E2 \= 0, E2 \= s(_)} <=
(E1 -> V1),(E2 -> V2) -> min(V1,V2).
This is rather terrible and can not be considered as a serious alternative. We can
do slightly better if we evaluate both arguments when none of the original clauses
match, that is we add a fourth clause:
min(E1,E2)# Guard <= (E1 -> V1),(E2 -> V2) -> min(V1,V2).
When E1 or E2 is already a canonical object this clause will perform redundant
computations when one of the arguments is evaluated to itself, but that cost is
negligible compared to the gain in readability. What we need is a guard that
excludes the three first cases but catches all cases where one of the arguments
is something else than 0 or s( ). The guards are built-up of conjunctions of
inequalities. One guard that does not work is the one in the last clause above
since it also excludes all cases where one argument is a canonical object. Instead
we have to write the fourth clause:
min(E1,E2)#{min(E1,E2) \= min(0,_),
min(E1,E2) \= min(s(_),0),
min(E1,E2) \= min(s(_),s(_))} <=
(E1 -> V1),(E2 -> V2) -> min(V1,V2).
51