Assocative predicates

Peter David ROSS petdr at
Thu Apr 16 17:10:50 AEST 1998


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 
- the assocativity of a predicate depends on the mode of the

:- 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?



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