[m-dev.] Assocative predicates
Peter David ROSS
petdr at cs.mu.OZ.AU
Fri Apr 17 16:58:25 AEST 1998
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.
:- 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
More information about the developers