Re: [Caml-list] How to simplify an arithmetic expression ?

[Goswin von Brederlow <goswin-v-b@web.de>]

Diego Olivier Fernandez Pons <dofp.ocaml@gmail.com> 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