Path: utzoo!attcan!uunet!husc6!uwvax!oddjob!ncar!noao!arizona!debray
From: debray@arizona.edu (Saumya Debray)
Newsgroups: comp.lang.prolog
Subject: Re: Clause fusion
Summary: applicability
Message-ID: <5502@megaron.arizona.edu>
Date: 16 May 88 20:04:24 GMT
References: <983@cresswell.quintus.UUCP>
Organization: U of Arizona CS Dept, Tucson
Lines: 57

In article <983@cresswell.quintus.UUCP>, Richard A. O'Keefe writes,
regarding the obvious optimization of "clause fusion":

> In general ... the main predicate may still have the same solutions
> after this optimisation, but they may not be found in the same order.

I'm not sure I see that.  Clause fusion is simply the transformation of
a pair of clauses of the form

	   p( Args ) :- Body1.
	   p( Args ) :- Body2.

where both clauses have the identical argument tuple in the head, to

	   p( Args ) :- Body1 ; Body2.

Note: it's enough to have the argument tuples in the head subsume
each other, i.e. be alphabetic variants, but then renaming may be
necessary before the fusion step.

Now assuming that the search strategy remains the same, the only way to
change the order of solutions found is to change the shape of the (ordered)
SLD-tree.  As far as I can see, there are only two ways of doing this:
either change the order of clauses for some predicate, or change the
order of literals in some clause.  Comments:

(1) Clause fusion has nothing to say about reordering clauses or literals:
    you can fuse clauses without doing any reordering; and you can reorder
    without doing any fusing.  The two transformations are orthogonal in
    general.

(2) Reordering clauses and literals is MESSY!  In the general case, you
    have to worry about termination issues -- probably not the sort
    of thing a compiler would like to get involved with.  Notice that
    even if we're given two literals
    
	       	   		 p(X), q(Y)

    that are guaranteed to be independent, we can't reorder them in
    general (consider the case where p fails and q loops).  Even if
    termination is guaranteed, you have to worry about side effects and
    metalanguage features like var/1, nonvar/1, ==/2, etc.  Finally,
    as Richard pointed out, there's the problem of order of solutions.
    There are, of course, special cases that one can try to identify,
    such as deterministic predicates that are guaranteed to terminate.
    E.g., suppose p/1 is a deterministic predicate, then
    
    	   Lits1, p(Arg), !, Lits2

    is equivalent to

    	   Lits1, !, p(Arg), Lits2.
-- 
Saumya Debray		CS Department, University of Arizona, Tucson

     internet:   debray@arizona.edu
     uucp:       {allegra, cmcl2, ihnp4} !arizona!debray