From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 62B8CBC88 for ; Wed, 9 Feb 2005 11:11:43 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j19ABgRq003864 for ; Wed, 9 Feb 2005 11:11:42 +0100 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id LAA28022 for ; Wed, 9 Feb 2005 11:11:42 +0100 (MET) Received: from smtp1.adl2.internode.on.net (smtp1.adl2.internode.on.net [203.16.214.181]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j19ABeOL003849 for ; Wed, 9 Feb 2005 11:11:41 +0100 Received: from [192.168.1.200] (ppp212-197.lns2.syd3.internode.on.net [203.122.212.197]) by smtp1.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id j19ABMjQ018345; Wed, 9 Feb 2005 20:41:33 +1030 (CST) Subject: Re: [Caml-list] Re: paralell assignment problem From: skaller Reply-To: skaller@users.sourceforge.net To: Radu Grigore Cc: Stefan Monnier , caml-list In-Reply-To: <7f8e92aa05020823485b62fcde@mail.gmail.com> References: <1107832025.13571.260.camel@pelican.wigram> <87y8dzi0ns.fsf-monnier+gmane.comp.lang.caml.inria@gnu.org> <1107882489.5022.175.camel@pelican.wigram> <7f8e92aa05020810335ab052e0@mail.gmail.com> <7f8e92aa05020823485b62fcde@mail.gmail.com> Content-Type: text/plain Message-Id: <1107943881.5022.508.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 09 Feb 2005 21:11:22 +1100 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 4209E1DE.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 4209E1DC.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 sourceforge:01 wrote:01 wrote:01 sourceforge:01 rhs:01 rhs:01 buffering:01 glebe:01 48,:98 1765:98 061:98 arbitrary:01 nsw:01 algorithm:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: On Wed, 2005-02-09 at 18:48, Radu Grigore wrote: > On Tue, 8 Feb 2005 20:33:52 +0200, Radu Grigore wrote: > > On Tue, 08 Feb 2005 09:12:32 -0800 (PST), skaller > > 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