From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 627E7BC88 for ; Tue, 8 Feb 2005 19:33:54 +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 j18IXrnc026692 for ; Tue, 8 Feb 2005 19:33:53 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA00493 for ; Tue, 8 Feb 2005 19:33:53 +0100 (MET) Received: from rproxy.gmail.com (rproxy.gmail.com [64.233.170.199]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j18IXqda023861 for ; Tue, 8 Feb 2005 19:33:53 +0100 Received: by rproxy.gmail.com with SMTP id i8so1004271rne for ; Tue, 08 Feb 2005 10:33:52 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:references; b=cttEbiVOFIqDWexiwOcvZGoyEWJH47u0xGBNPPsH0PCeoed4jg0uaTNHYbFmWd/IpEy7ji0ttMGnM3m5pJdjdzrHktNnMAx1gx+lqSHvIEoWUFB84YRPey80ReZx8QaBJaQui62ONigx1awQddOjUW6I5jjmG8CyDqgzBxzz8Nk= Received: by 10.38.82.61 with SMTP id f61mr285741rnb; Tue, 08 Feb 2005 10:33:52 -0800 (PST) Received: by 10.38.65.58 with HTTP; Tue, 8 Feb 2005 10:33:52 -0800 (PST) Message-ID: <7f8e92aa05020810335ab052e0@mail.gmail.com> Date: Tue, 8 Feb 2005 20:33:52 +0200 From: Radu Grigore Reply-To: Radu Grigore To: skaller@users.sourceforge.net Subject: Re: [Caml-list] Re: paralell assignment problem Cc: Stefan Monnier , caml-list In-Reply-To: <1107882489.5022.175.camel@pelican.wigram> Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit References: <1107832025.13571.260.camel@pelican.wigram> <87y8dzi0ns.fsf-monnier+gmane.comp.lang.caml.inria@gnu.org> <1107882489.5022.175.camel@pelican.wigram> X-Miltered: at concorde with ID 42090611.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 42090610.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 sourceforge:01 wrote:01 node:01 arbitrary:01 expression:01 graph:01 graph:01 edges:01 algorithm:01 breaks:02 identifier:04 cycles:04 problem:05 radu:05 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=RCVD_BY_IP autolearn=disabled version=3.0.2 X-Spam-Level: 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. Imagine a graph where an arrow is drawn from A to B only if A appears in the expression to be assigned to B. You can imagine the process of introducing temporaries as marking a few edges in this graph so that you break all cycles. One marked edge = one temporary. But since no identifier appears more than once on the left side, in this graph the in-degree is at most 1 and each node is part of at most one cycle. >>From this it follows that each marked edge breaks at most one cycle. Since all your temporaries break at least one cycle the algorithm should work. -- regards, radu http://rgrig.idilis.ro/