[m-dev.] Assocative predicates

[Peter David ROSS]

Fergus Henderson, you wrote:
> 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...
> 

I like the syntax as well and it also has the added benefit that it can
show how to transform a call from being right assocative to left
assocative or vice versa.

ie
:- pragma assert(all [A,B,C,R,T] (
    append(A, B, T), append(T, C, R) <=>
    append(B, C, T), append(A, T, R))).

Knowing this information is useful for transforming reverse to use
accumulator recursion.

Pete.