From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p95LVlFt028931
	for <caml-list@sympa-roc.inria.fr>; Wed, 5 Oct 2011 23:31:47 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AjYBAGvLjE5KfVK2kGdsb2JhbABCqBIIIgEBAQEJCQ0HFAQhgVMBAQEBAxICLAEbHQEDDAYFCw0uIQEBEQEFARwGEyKhZwqLS4JchH09iG4CBAaHIwSTbYoggnk9g3A
X-IronPort-AV: E=Sophos;i="4.68,493,1312149600"; 
   d="scan'208";a="111871524"
Received: from mail-wy0-f182.google.com ([74.125.82.182])
  by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 05 Oct 2011 23:31:42 +0200
Received: by wyj26 with SMTP id 26so3868959wyj.27
        for <caml-list@inria.fr>; Wed, 05 Oct 2011 14:31:42 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=mime-version:in-reply-to:references:from:date:message-id:subject:to
         :cc:content-type:content-transfer-encoding;
        bh=gAsIMTqC9nPpfGve89OnNoqAQKAAhGz/2ys9y6za7mg=;
        b=PbikhkO2BhoKpWIQQ2jWSkHdPC/aiLhXf29+Ad/s86Dt3AhS11t4GvRhBZYoE0cpPA
         v9xtTJY2PeP7tE9DGYBTQvI0xfcjQRQoVWWKtHW0HEEv24luGOgSBTNuHHxgjv+/hvmU
         nNVaVS5SnvHH5R5wPzF9+LUU1xsBPn4lvV9xs=
Received: by 10.227.167.1 with SMTP id o1mr3664162wby.6.1317850301940; Wed, 05
 Oct 2011 14:31:41 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.227.155.67 with HTTP; Wed, 5 Oct 2011 14:31:20 -0700 (PDT)
In-Reply-To: <87zkhfpogp.fsf@frosties.localnet>
References: <CAHqiZ-K9dVQL2QNuQEXHedqZgeWgPRTmt4XKmCUJW7eUtgpy1A@mail.gmail.com>
 <CAPFanBE6RX4y_VQuaTJx40DJ=TFY9y_4PeLkfJ3d4Py=+X9Ckw@mail.gmail.com>
 <CABY2naxBqwtD2NVzz+kUVOix-FJ44-uYkjX9+hph4D3yJBUAuQ@mail.gmail.com>
 <4E88922C.6080303@inria.fr> <CAPFanBHKXaLcAwa5rRDcrwd33xXkHy3WY3cLODBhe_uATCatQA@mail.gmail.com>
 <CAPFanBFQpsmv=U+=4u0d0x8TH3MD4HktL9ptt5qq0vjtupuY9Q@mail.gmail.com> <87zkhfpogp.fsf@frosties.localnet>
From: Gabriel Scherer <gabriel.scherer@gmail.com>
Date: Wed, 5 Oct 2011 23:31:20 +0200
Message-ID: <CAPFanBG+FQGauE8ydJWgEnk=kHsv31LAuVDHDcRb50SjFeP-Ew@mail.gmail.com>
To: Goswin von Brederlow <goswin-v-b@web.de>
Cc: caml-list@inria.fr
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p95LVlFt028931
Subject: Re: [Caml-list] How to simplify an arithmetic expression ?

On Wed, Oct 5, 2011 at 3:17 PM, Goswin von Brederlow <goswin-v-b@web.de> wrote:
> (1*Y)? That certainly isn't optimal.

The inefficiency is in the code translating the semantic value back
into the expression type, not in the evaluation code.
Feel free to add the few lines needed to spot that corner case and
behave accordingly, as I did for the initialization of the sum (to
avoid "+ 0" everywhere).
Note that this doesn't stop the simplification to be involutive, so
still a valid simplification/normalization; whether the normal form
actually respects our sense of "optimality" is a different question.

On Wed, Oct 5, 2011 at 3:17 PM, Goswin von Brederlow <goswin-v-b@web.de> wrote:
> Gabriel Scherer <gabriel.scherer@gmail.com> writes:
>
>>> Below is a quick tentative implementation of NbE, on a slightly
>>> restricted expression type (I removed the not-so-interesting Minus
>>> nodes).
>>
>> Sorry, I forgot to give a small example of what the implementation
>> does. Really the obvious thing, but it may not be so obvious just
>> looking at the code.
>> Here is an example of (X*2+Y)*(3+(Y*2+Z)) being 'rewritten' to
>> (1*Y)*Z+((2*Y)*Y+(3*Y+((2*X)*Z+((4*X)*Y+6*X)))).
>
> (1*Y)? That certainly isn't optimal.
>
> MfG
>        Goswin
>