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 p92BpBkr017417 for ; Sun, 2 Oct 2011 13:51:14 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AoUBAJRPiE5KfVI0kGdsb2JhbABBp0RhCCIBAQEBCQkNBxQEIYFsAhMZARseAxIQXQERAQUBIhsaoFmCWQqLTYJcg1Y9iG4CBAaHGwSTYI0UPYNv X-IronPort-AV: E=Sophos;i="4.68,476,1312149600"; d="scan'208";a="122461184" Received: from mail-ww0-f52.google.com ([74.125.82.52]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Oct 2011 13:51:14 +0200 Received: by wwj40 with SMTP id 40so5192633wwj.9 for ; Sun, 02 Oct 2011 04:51:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:date:message-id:subject:from:to:content-type; bh=iRwhNjjmo41TBkMzHB65JD7yRMnWKVKTP9RdsSeKgxs=; b=WRGXcC40DWNzErgUA9nHwHiFcYXuu5lJVQvjWTseM5KLdgTzqUhfh0eRqM6U3vqJdw PdZQq+eppvJKcWIVAMnTXOFOZzMUo0l3/X62jDNIwvulOv68g1EATnCBwhJI3VOIkKlB hDRDvnScS5d+dvAEz89McZK8+eu2GUYCFbLNk= MIME-Version: 1.0 Received: by 10.216.4.168 with SMTP id 40mr5732540wej.9.1317556273703; Sun, 02 Oct 2011 04:51:13 -0700 (PDT) Received: by 10.216.13.67 with HTTP; Sun, 2 Oct 2011 04:51:13 -0700 (PDT) Date: Sun, 2 Oct 2011 13:51:13 +0200 Message-ID: From: Diego Olivier Fernandez Pons To: caml-list Content-Type: multipart/alternative; boundary=0016364d30d5aa6b1104ae4f7904 Subject: [Caml-list] How to simplify an arithmetic expression ? --0016364d30d5aa6b1104ae4f7904 Content-Type: text/plain; charset=ISO-8859-1 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 2. My set of simplifications is optimal in the sense it doesn't traverse subtrees without need 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 type expr = | Constant of float | Plus of expr * expr | Minus of expr * expr | Times of expr * expr | Variable of string let rec normalForm = function | Minus (e1, e2) -> normalForm (Plus (normalForm e1, Times (Constant (-1.0), normalForm e2))) | Plus (e1, e2) -> begin match (normalForm e1, normalForm e2) with | (Constant a, Constant b) -> Constant (a +. b) | (Constant 0.0, e) -> normalForm e | (e, Constant b) -> normalForm (Plus (Constant b, normalForm e)) | (Constant a, Plus (Constant b, e)) -> Plus (Constant (a +. b), normalForm e) | (Plus (Constant a, e1), Plus (Constant b, e2)) -> Plus (Constant (a +. b), normalForm (Plus (normalForm e1, normalForm e2))) | (Variable a, Variable b) when a = b -> Times (Constant 2.0, Variable a) | (Times (Constant n, Variable b), Variable a) when a = b -> Times (Constant (n +. 1.0), Variable a) | (Variable a, Times (Constant n, Variable b)) when a = b -> Times (Constant (n +. 1.0), Variable a) | (Times (Constant n, Variable a), Times (Constant m, Variable b)) when a = b -> Times (Constant (n +. m), Variable a) | other -> Plus (e1, e2) end | Times (e1, e2) -> begin match (normalForm e1, normalForm e2) with | (Constant a, Constant b) -> Constant (a *. b) | (Constant 0.0, e) -> Constant 0.0 | (Constant 1.0, e) -> e | (e, Constant b) -> normalForm (Times (Constant b, normalForm e)) | (Constant a, Times (Constant b, e)) -> Times (Constant (a *. b), e) | other -> Times (e1, e2) end | x -> x let (++) = fun x y -> Plus (x, y) let ( ** ) = fun x y -> Times (x, y) let ( --) = fun x y -> Minus (x, y) let f = function fl -> Constant fl let x = Variable "x" let h = fun i -> f i ** x -- f i ** f i ** x ++ (f 3.0 ++ f i) let e = List.fold_left (fun t i -> Plus (t, h i)) (f 0.0) [1.0; 2.0; 3.0; 4.0; 5.0] normalForm e Diego Olivier --0016364d30d5aa6b1104ae4f7904 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable =A0 =A0 OCaml list,

It's easy to encapsulate a coupl= e of arithmetic simplifications into a function that applies them bottom up= to an expression represented as a tree

let rec si= mplify =3D function
=A0 =A0 | Plus (e1, e2) ->
=A0 =A0 =A0 =A0 match (simplif= y e1, simplify e2) with
=A0 =A0 =A0 =A0 =A0 =A0 =A0| (Constant 0,= _) -> e2=A0

With a couple well known tricks li= ke pushing constants to the left side and so on...

How can I however guarantee that
=A0 =A0 1. M= y final expression reaches a kind of minimal normal form
=A0 =A0 = 2. My set of simplifications is optimal in the sense it doesn't travers= e subtrees without need

Here is my current simplifier and I have no way of tell= ing if it really simplifies the expressions as much as possible and if it d= oes useless passes or not

type expr =3D
=A0 =A0 | Constant of float
=A0 =A0 | Plus of expr * expr
=A0 =A0 | Minus of expr * expr
=A0 =A0 | Times of expr * = expr
=A0 =A0 | Variable of string

=
let rec normalForm =3D function
=A0 =A0 | Minus (e1, e2) -> normalForm (Plus (normalForm e1, Times = (Constant (-1.0), normalForm e2)))
=A0 =A0 | Plus (e1, e2) -><= /div>
=A0 =A0 =A0 =A0 begin
=A0 =A0 =A0 =A0 match (normalForm= e1, normalForm e2) with
=A0 =A0 =A0 =A0 =A0 =A0 | (Constant a, Constant b) -> Constant (a += . b)
=A0 =A0 =A0 =A0 =A0 =A0 | (Constant 0.0, e) -> normalForm= e
=A0 =A0 =A0 =A0 =A0 =A0 | (e, Constant b) -> normalForm (Pl= us (Constant b, normalForm e))
=A0 =A0 =A0 =A0 =A0 =A0 | (Constant a, Plus (Constant b, e)) -> Plu= s (Constant (a +. b), normalForm e)
=A0 =A0 =A0 =A0 =A0 =A0 | (Pl= us (Constant a, e1), Plus (Constant b, e2)) -> Plus (Constant (a +. b), = normalForm (Plus (normalForm e1, normalForm e2)))
=A0 =A0 =A0 =A0 =A0 =A0 | (Variable a, Variable b) when a =3D b -> = Times (Constant 2.0, Variable a)
=A0 =A0 =A0 =A0 =A0 =A0 | (Times= (Constant n, Variable b), Variable a) when a =3D b -> Times (Constant (= n +. 1.0), Variable a)
=A0 =A0 =A0 =A0 =A0 =A0 | (Variable a, Times (Constant n, Variable b))= when a =3D b -> Times (Constant (n +. 1.0), Variable a)
=A0 = =A0 =A0 =A0 =A0 =A0 | (Times (Constant n, Variable a), Times (Constant m, V= ariable b)) when a =3D b -> Times (Constant (n +. m), Variable a)
=A0 =A0 =A0 =A0 =A0 =A0 | other -> Plus (e1, e2)
=A0 =A0 = =A0 =A0 end
=A0 =A0 | Times (e1, e2) ->
=A0 =A0 =A0 = =A0 begin
=A0 =A0 =A0 =A0 match (normalForm e1, normalForm e2) wi= th
=A0 =A0 =A0 =A0 =A0 =A0 | (Constant a, Constant b) -> Const= ant (a *. b)
=A0 =A0 =A0 =A0 =A0 =A0 | (Constant 0.0, e) -> Constant 0.0
=A0 =A0 =A0 =A0 =A0 =A0 | (Constant 1.0, e) -> e
=A0 =A0 = =A0 =A0 =A0 =A0 | (e, Constant b) -> normalForm (Times (Constant b, norm= alForm e))
=A0 =A0 =A0 =A0 =A0 =A0 | (Constant a, Times (Constant= b, e)) -> Times (Constant (a *. b), e)
=A0 =A0 =A0 =A0 =A0 =A0 | other -> Times (e1, e2)
=A0 =A0= =A0 =A0 =A0end
=A0 =A0 | x -> x

let (++) =3D fun x y -> Plus (x, y)
let ( ** ) =3D fun = x y -> Times (x, y)
let ( --) =3D fun x y -> Minus (x, y)
let f =3D function = fl -> Constant fl

let x =3D Variable "x&qu= ot;
let h =3D fun i -> f i ** x -- f i ** f i ** x ++ (f 3.0 += + f i)
let e =3D List.fold_left (fun t i -> Plus (t, h i)) (f 0.0) [1.0; 2= .0; 3.0; 4.0; 5.0]

normalForm e

=A0 =A0 =A0 =A0 Diego Olivier

--0016364d30d5aa6b1104ae4f7904--