Assocative predicates
Peter David ROSS
petdr at cs.mu.OZ.AU
Thu Apr 16 17:10:50 AEST 1998
Hi,
Having implemented a portion of accumulator introduction (it works
for list__length), the solution needs to be made more general. For
that to happen we need to know for some predicates called by a
predicate if that predicate is associative (ie (A+B)+C = A+(B+C))
My preferred solution is that the user annotates the predicates the
user knows to be associative by some method. With the onus on the
user to ensure that the predicate is actually assocative (unless anyone
knows who to prove this in general).
The issues that arise are that
- these annotations need to be accessible by modules which import the
predicate.
- the assocativity of a predicate depends on the mode of the
predicate.
:- func int * int = int.
:- mode in * in = out. ( is assocative )
:- mode out * in = in. ( is not assocative since effectively division
and division not assocative )
Suggestions on the syntax for this?
Pete.
PS.
The predicate below can be transformed to use accumulator recursion
l__multiply([], 1).
l__multiply([H|T], R) :-
l__multiply(T, R0),
R = R0 * H.
If however R = R0 * H becomes R0 = R * H this is equivalent to
R = H / R0
which cannot use accumulator recursion since (A/B)/C != A/(B/C)
More information about the developers
mailing list