From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p95D9Tsm013572 for ; Wed, 5 Oct 2011 15:09:29 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Aj8CAKtVjE7ZSMDjfWdsb2JhbABCqBEiAQELCwkHFAUigVMBAQQBJwsBRgULAQMHISUPAQQNGyETh30CtneHKQSZFIR5hyY X-IronPort-AV: E=Sophos;i="4.68,491,1312149600"; d="scan'208";a="122908521" Received: from fmmailgate02.web.de ([217.72.192.227]) by mail1-smtp-roc.national.inria.fr with ESMTP; 05 Oct 2011 15:09:24 +0200 Received: from smtp05.web.de ( [172.20.4.166]) by fmmailgate02.web.de (Postfix) with ESMTP id 2EC641AF46579; Wed, 5 Oct 2011 15:09:24 +0200 (CEST) Received: from [78.43.204.177] (helo=frosties.localnet) by smtp05.web.de with asmtp (TLSv1:AES256-SHA:256) (WEB.DE 4.110 #2) id 1RBRDv-0008ER-00; Wed, 05 Oct 2011 15:09:24 +0200 Received: from mrvn by frosties.localnet with local (Exim 4.76) (envelope-from ) id 1RBRDv-0002iq-6N; Wed, 05 Oct 2011 15:09:23 +0200 From: Goswin von Brederlow To: Diego Olivier Fernandez Pons Cc: caml-list References: Date: Wed, 05 Oct 2011 15:09:23 +0200 In-Reply-To: (Diego Olivier Fernandez Pons's message of "Sun, 2 Oct 2011 13:51:13 +0200") Message-ID: <874nznr3ek.fsf@frosties.localnet> User-Agent: Gnus/5.110009 (No Gnus v0.9) XEmacs/21.4.22 (linux, no MULE) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Sender: goswin-v-b@web.de X-Sender: goswin-v-b@web.de X-Provags-ID: V01U2FsdGVkX1+sdKX4c9cPiV5YFu+G6JRgDxn2uEqY9OwtQcTC yqauRywoxd7oIJQ8310A4yEqhqmn+VWJCopIYllDDsSLRyBIqM fjW2uBZCc= Subject: Re: [Caml-list] How to simplify an arithmetic expression ? Diego Olivier Fernandez Pons writes: >     OCaml list, > > It's easy to encapsulate a couple of arithmetic simplifications into a function > that applies them bottom up to an expression represented as a tree > > let rec simplify = function >     | Plus (e1, e2) -> >         match (simplify e1, simplify e2) with >              | (Constant 0, _) -> e2  > > With a couple well known tricks like pushing constants to the left side and so > on... > > How can I however guarantee that >     1. My final expression reaches a kind of minimal normal form First you have to define what you mean by that. For a (good) compiler a minimal normal form would be one that uses the least number of instructions (optimize size) or least number of cpu cycles (optimize speed) to execute. And that is quite a complex problem. One simplification that will probably destroy any idea of a simple minimal normal form is probably eliminating common subexpressions. Some optimizations will require complex heuristics or much larger patterns. >     2. My set of simplifications is optimal in the sense it doesn't traverse > subtrees without need That you have to think through. I don't think you can get the compiler to tell you when a traversal isn't needed. You could annotate your syntax tree with traversal counts and check if the count goes up too much somewhere. If you do extra unneeded traversals then I expect them to become exponential quite quickly so it should be easy to spot by running a bunch of expressions through your code. > > Here is my current simplifier and I have no way of telling if it really > simplifies the expressions as much as possible and if it does useless passes or > not It doesn't. 1 - 1 -> 0 a + b + 2 * (a + b) -> 3 * a + 3 * b or 3 * (a + b)? (a + 1) * (a - 1) -> a * a - 1 9 * a -> 8 * a + a? The last would be something a compiler does to optimize speed since a muliplication by a power of 2 is a shift and shift + add is faster than multiplication. MfG Goswin