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 71F04BC88 for ; Tue, 8 Feb 2005 15:54:34 +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 j18EsXxn028043 for ; Tue, 8 Feb 2005 15:54:33 +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 PAA25255 for ; Tue, 8 Feb 2005 15:54:33 +0100 (MET) Received: from ciao.gmane.org (main.gmane.org [80.91.229.2]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j18EsWR2028035 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO) for ; Tue, 8 Feb 2005 15:54:33 +0100 Received: from root by ciao.gmane.org with local (Exim 4.43) id 1CyWhQ-0006Nm-Ex for caml-list@inria.fr; Tue, 08 Feb 2005 15:50:45 +0100 Received: from 65.92.240.235 ([65.92.240.235]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Tue, 08 Feb 2005 15:50:44 +0100 Received: from monnier by 65.92.240.235 with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Tue, 08 Feb 2005 15:50:44 +0100 X-Injected-Via-Gmane: http://gmane.org/ To: caml-list@inria.fr From: Stefan Monnier Subject: Re: paralell assignment problem Date: Tue, 08 Feb 2005 09:34:42 -0500 Message-ID: <87y8dzi0ns.fsf-monnier+gmane.comp.lang.caml.inria@gnu.org> References: <1107832025.13571.260.camel@pelican.wigram> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Complaints-To: usenet@sea.gmane.org X-Gmane-NNTP-Posting-Host: 65.92.240.235 User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/21.3.50 (gnu/linux) Cancel-Lock: sha1:7QGdCefYtc4vF/iUjDfrnRtVYdg= Sender: news X-Gmane-MailScanner: Found to be clean X-Gmane-MailScanner: Found to be clean X-MailScanner-From: gclci-caml-list@m.gmane.org X-MailScanner-To: caml-list@inria.fr X-Miltered: at concorde with ID 4208D2A9.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 4208D2A8.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; umontreal:01 compilers:01 recursive:01 graph:01 functions:01 algorithm:01 algorithm:01 variables:02 expressions:03 generally:03 parallel:04 problem:05 problem:05 describe:06 components:06 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=1.6 required=5.0 tests=RCVD_BY_IP,RCVD_NUMERIC_HELO autolearn=disabled version=3.0.2 X-Spam-Level: * > 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. Stefan