From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id WAA01491; Fri, 2 Jan 2004 22:48:07 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f 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 WAA01850 for ; Fri, 2 Jan 2004 22:48:06 +0100 (MET) Received: from mwinf0601.wanadoo.fr (smtp6.wanadoo.fr [193.252.22.25]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id i02Lghv07677 for ; Fri, 2 Jan 2004 22:42:47 +0100 (MET) Received: from zyfo (Mix-Grenoble-105-1-226.w193-249.abo.wanadoo.fr [193.249.40.226]) by mwinf0601.wanadoo.fr (SMTP Server) with SMTP id C1737340012F; Fri, 2 Jan 2004 22:42:30 +0100 (CET) Message-ID: <002b01c3d179$520149d0$e228f9c1@zyfo> From: "Jean-Baptiste Rouquier" To: , "caml-list" References: <1072936720.4626.18.camel@pelican> Subject: Re: [Caml-list] flow optimisation q Date: Fri, 2 Jan 2004 22:42:26 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2800.1106 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1106 X-Loop: caml-list@inria.fr X-Spam: no; 0.00; ens-lyon:01 caml-list:01 recursion:01 procs:01 recursively:01 vertices:01 vertices:01 procs:01 elided:01 primitives:01 primitives:01 exists:01 algorithm:03 algorithm:03 constructor:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > Suppose there is a set of > primitive procedures pr1 pr2 and a procedure constructor: > > proc = proc list > > which defines a new procedure to be a list of calls > to other procedures, with mutual recursion allowed. > > A special procedure is the empty > procedure whose call list is empty. > > Problem: remove all empty procedures > (and of course calls to them). This is a graph problem : draw a vertice for each proc and a vertice from a to b when b calls a (so a -> b mean "a is called by b"). First suppose that there are no cycle. You just have to start from primitive procs, mark recursively all their callers, and delete all non marked vertices. O(n). If there are cycle and if you want to keep a structure like a calls b b calls a where neither a nor b is a primitive proc, you can calculate strongly connected components of your graph. Then draw the graph of this strongly connected components (vertices are the strongly connected components, and there is an edge A -> B iff there exists a in A and b in B such that there is an edge a -> b in the first graph). Finnally apply the first algorithm using components with two or more procs as primitives procs, plus the initial primitives procs. > My current algorithm is functional: > make a new set of procedures which > (a) excludes empty procedures > (b) has calls to empty procedures elided > > To make this solve the problem requires > repeated application until there are no > empty procedures left. Seems O(n^2). Jean-Baptiste Rouquier. ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners