Re: [Caml-list] Re: paralell assignment problem

[skaller <skaller@users.sourceforge.net>]

On Wed, 2005-02-09 at 01:34, Stefan Monnier wrote:
> > Does anyone know how to solve the parallel assignment problem?
> > Name invented by me to describe this problem:
> 
> > x1,x2,x3..xn = e1,e2,e3 .. en
> 
> > where ei might contain the variables xj. (Note = here is assignment).
> 
> > The solution is a sequence of assignments involving
> > only xi, ei, and ti, where ti are temporaries introduced
> > to save the values of the expressions. For example,

Here's the algorithm I have implemented, I believe it works,
but I'm not sure it finds the minimal solution. The main
difficulty is in step 5.

1. Strip out equations of the form xi = xi since
   they don't do anything.

2. Create 3 lists: head, middle, and tail.

3. For each assignment in the working set:

  if the RHS does not depend on a variable in the working set, 
    prepend it to the tail
  else if no RHS in the working set depends on the LHS
    variable, prepend it to the head
  else add it to the middle

4. If we moved any assignment to the head or tail list,
   set the working set to the middle, and go back to step 3

5. The middle now has the property that for any assignment,
   there is at least one other assignent such that the RHS
   of one whch depends on the LHS variable of the other.

   So pick one assignment x = e out of the middle, 
   create a temporary variable t, prepend t = e
   to the head list and x = t to the tail list,
   set the working set to the remaining assignments
   of the middle. 

   If the working set is empty, the result is the reversed
   head list concatenated with the tail, otherwise
   go back to step 3


This algorithm (a) finds an equivalent set of serial assignments,
and (b) it is clearly locally minimal in the sense that
whenever it introduces a temporary in step 5,
there was no alternative but to do so.

However it isn't clear (to me) that just picking an arbitrary
assignment to split into two using a temporary
actually minimises the number of temporaries.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net