On Wed, 2005-02-09 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: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net