[m-dev.] Assocative predicates

[Fergus Henderson]

On 16-Apr-1998, Peter Schachte <pets at cs.mu.OZ.AU> wrote:
> On 16-Apr-98, Peter David ROSS wrote:
> 
> >My preferred solution is that the user annotates the predicates the
> >user knows to be associative by some method.  The issues that arise are that 
> >
> >- these annotations need to be accessible by modules which import the 
> >  predicate.
> 
> I'll let the people who understand transopt files address this...

This should not be a difficulty -- we already do this sort of thing
for termination analysis.  Just make it a new pragma, and add a clause

	pragma_allowed_in_interface(..., yes).

to modules.m.

> >- the assocativity of a predicate depends on the mode of the
> >  predicate.
> 
> I think it's clearer to say that associativity is directional.  Given a
> predicate, say foo/5, you'd like to be able to say, for example, that
> 
>    foo(A, B, C, D, E), foo(D, E, F, G, H)
> 
> is always equivalent to
> 
>    foo(A, B, F, D, E), foo(D, E, C, G, H)
> 
> The statement is basically independent of the modes.

Yes.  Statements about associativity should not depend on the modes.

> To say this, you have to say which arguments are "associated" with which
> (that's a *really* bad choice of word there).  In this example, the first and
> fourth are  associated, and so are the second and fifth.  So maybe some syntax
> like:
> 
>    :- pragma associative(foo(A, B, _, A, B)).
> 
> would give you what you need.  For +, you might write
> 
>    :- pragma associative(A+_ = A).
>    :- pragma associative(_+A = A).
> 
> Also keep in mind that in the future we may wish to allow declarations of
> other interesting algebraic properties which the compiler might be able to
> capitalize on.  Commutativity is probably not too interesting, but
> distributativity is.  Having identities could be useful, maybe knowing if
> there is a zero might be helpful.

How about just `pragma assert(Goal)'?

	:- pragma assert(all [A,B,C] (A+B)+C=A+(B+C)).

	:- pragma assert(all [A,B,C,D,E,F,G,H] (
		foo(A, B, C, D, E), foo(D, E, F, G, H) <=> 
		foo(A, B, F, D, E), foo(D, E, C, G, H))).

This syntax seems to be nice, at least from the user's perspective.
It may require more effort for the compiler to figure out which
assertions specify associativity...

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.