Path: utzoo!attcan!uunet!husc6!bloom-beacon!tut.cis.ohio-state.edu!mailrus!ames!ncar!noao!arizona!debray
From: debray@arizona.edu (Saumya Debray)
Newsgroups: comp.lang.prolog
Subject: Re: Clause fusion
Summary: optimization not all that obvious, in general
Message-ID: <5501@megaron.arizona.edu>
Date: 16 May 88 19:23:05 GMT
References: <983@cresswell.quintus.UUCP>
Organization: U of Arizona CS Dept, Tucson
Lines: 165

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

> The original code was
> 
> 	association(Stack, Key, Val, absent) :-
> 		is_empty(Stack),
> 		!.
> 	association(Stack, Key, Val, Result) :-
> 		pop_stack(Key1, Val1, Stack, Stack1),
> 		Key1 \== Key,
> 		!,
> 		association(Stack1, Key, Val, Result).
> 	association(Stack, Key, Val, present) :-
> 		pop_stack(Key1, Val1, Stack, Stack1),
> 		Key1 == Key,
> 		Val1 = Val,
> 		!.
> 	association(Stack, Key, Val, conflict).

Richard points out several problems with a proposed solution.  It
turns out, however, that the problems are not with Clause Fusion itself,
but rather with some subsequent transformations involving moving cuts
around a clause.  It shouldn't be surprising that this is not an easy
thing to do in general.

It's interesting to transform this code a little at a time, to
see what assumptions are necessary at each step in order to preserve
equivalence.  To reduce clutter as far as possible in what follows,
I'll consider only the clauses that Richard fused, and ignore the first
clause in this definition.
--------------------
STEP 1: No assumptions: all we can do is move some arguments
from the head to just beyond the neck of the clause, to get:

 	association(Stack, Key, Val, Result) :-
 		(pop_stack(Key1, Val1, Stack, Stack1),
 		 Key1 \== Key,
 		 !,
 		 association(Stack1, Key, Val, Result)
		) ;
	     (Result = present,	  		     
 		 pop_stack(Key1, Val1, Stack, Stack1),
 		 Key1 == Key,
 		 Val1 = Val,
 		 !
		) ;
		Result = conflict.
--------------------
STEP 2: Assume that association/4 is always called with its
last argument free.  This allows us to delay the unification
"Result = present" in the second disjunct, to get the disjuncts:

   (pop_stack( ... ), Key1 \== Key, ... ) ;
   (pop_stack( ... ), Key1 == Key, Val1 = Val, !, Result = present) ;
   Result = conflict.
--------------------
STEP 3: Assume pop_stack/4 is free of side effects.  This allows us to
factor the literal for pop_stack/4 in the disjunct, producing

 	association(Stack, Key, Val, Result) :-
          (pop_stack(Key1, Val1, Stack, Stack1),
 		 (Key1 \== Key,
 		  !,
 		  association(Stack1, Key, Val, Result)
		 ) ;
	      ( /* Key1 == Key, */
 		  Val1 = Val,
 		  !
            Result = present
		 )			
          ) ;
          Result = conflict.

We can't do much more at this point.  Note that the inner disjunction
can't really be converted to an if-then-else, because the cut is necessary
to cut away the alternative "Result = conflict" in the outer disjunct.
Notice also that even if pop_stack/4 is known to be deterministic, we can't
transform this to

	   pop_stack( ... ) ->
	        ( ... ) ;
		   Result = conflict.

(Consider the case where pop_stack/4 succeeds, "Key1 \== Key" fails, and
 "Val1 = Val" fails.)
--------------------
STEP 4: Richard assumed, in addition, that association/4 is always called
with its first three arguments ground terms.  Looking at the code, it seems
to me that the predicate is intended to search a (given) stack for a value
associated with a (given) key, so I think it's more reasonable to assume
that the third argument to association/4 is also free in each call to it.
If we make this assumption, then the unification "Val1 = Val" (after
"Key1 == Key") can also be delayed until after the cut.  This transforms
the inner disjunct to

	   	  (Key1 \== Key, !, association( ... ) ) ;
	   	  (!, Val1 = Val, Result = present)

This, with some easy massaging, yields

 	association(Stack, Key, Val, Result) :-
          (pop_stack(Key1, Val1, Stack, Stack1),
 		 (Key1 \== Key ->
 		     association(Stack1, Key, Val, Result) ;
			(Val1 = Val,
                Result = present
			)
		 ),
		 !
          ) ;
          Result = conflict.
--------------------
STEP 5: Assume that association/4 is deterministic.  This allows us to
bubble the cut backwards, eventually yielding

 	association(Stack, Key, Val, Result) :-
          (pop_stack(Key1, Val1, Stack, Stack1),
		 !,
 		 (Key1 \== Key ->
 		     association(Stack1, Key, Val, Result) ;
			(Val1 = Val,
                Result = present
			)
		 )
          ) ;
          Result = conflict.

It's now a simple matter to reformat this to

 	association(Stack, Key, Val, Result) :-
        pop_stack(Key1, Val1, Stack, Stack1) ->
		 (Key1 \== Key ->
 		     association(Stack1, Key, Val, Result) ;
			(Val1 = Val,
                Result = present
			)
		 ) ;
           Result = conflict.
--------------------
[ If we don't want to assume that association/4 is always called with
  its third argument uninstantiated, then different (and, in my opinion,
  less reasonable) assumptions are necessary to take the transformation
  beyond step 3 above.  This article's getting too long for that. ]

The resulting code is seen to be quite different from the proposed

> 	association(Stack, Key, Val, Result) :-
> 		pop_stack(Key1, Val1, Stack, Stack1),
> 		(   Key1 \== Key ->
> 		    association(Stack1, Key, Val, Result)
> 		;   Val1 = Val ->
> 		    Result = present
> 		;   Result = conflict
> 		).

To sum up: the problems mentioned by Richard are not with clause fusion
per se, but rather with some subsequent transformations involving 
moving cuts around a clause.  Not surprisingly, this is nontrivial
in general.
-- 
Saumya Debray		CS Department, University of Arizona, Tucson

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