Diego Olivier Fernandez Pons <[email protected]> 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
--
Caml-list mailing list. Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
