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,
> 
> Most ML compilers do this sort of thing to break big blocks of mutually
> recursive functions into smaller such blocks.  The algorithm used is
> generally to extract the "strongly connected components" of the graph.
> Google for it and you'll surely find an algorithm.

I'm not sure the problem is quite the same though.
Call graphs are transitive: if A calls B, and B calls C,
then A calls C.

However, 'depends on' is not transitive. Here

 x,y = y,x

x and y are mutually dependent, but in the solution:

  t = x; x = y; y = t

t depends on x, x depends on y, and y depends on t.
If the dependency were transitive, y would then 
depend on x, but it doesn't.

That is: the graph of the solution seems strongly connected:

  T -> X -> Y --+
  ^             |
  +-------------+

however, these are *sequential* and not parallel assignments.

A solution using digraph decomposition may well be the 
right answer, perhaps changing the relation to
'depends on the old value of'. This would break
the cycle above (since t has no old value, y now
doesn't depend on anything).

See another post for an algorithm..


-- 
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