paralell assignment problem
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  skaller <skaller@u...> 
Subject:  Re: [Camllist] Re: paralell assignment problem 
On Wed, 20050209 at 18:48, Radu Grigore wrote: > On Tue, 8 Feb 2005 20:33:52 +0200, Radu Grigore <radugrigore@gmail.com> wrote: > > On Tue, 08 Feb 2005 09:12:32 0800 (PST), skaller > > <skaller@users.sourceforge.net> wrote: > > > > > 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. > > > > I'm mildly convinced that it works. > > I was obviously too tired yesterday: there are lots of mistakes in my argument. > > Actually here is an example on which your algorithm uses more > assignments than necessary: > > a = b+c > b = c > c = a+b > > The solution is > t = c > c = a+b > a = b+t > b = t That's confirmed, my algorithm produces this: ASG _tmp_a<2009> = (Int::add (f::b, f::c)) ASG _tmp_c<2010> = (Int::add (f::a, f::b)) ASG b<1764> = f::c ASG c<1765> = index_2010 ASG a<1763> = index_2009 However, your solution, whilst correct, breaks one of the rules: one of the RHS is refering to the old value of 'c' using the name 't'. The original rules required only assignments using the original LHS variables, the original RHS expressions, and the temporaries, that is, only permitted buffering the RHS expressions, not old values of variables. Allowing *both* RHS expressions (new values of variables) and LHS variables (old values of variables) makes sense, however, as your example demonstrates. And also seems to make solving the problem harder :)  John Skaller, mailto:skaller@users.sf.net voice: 061296600850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net