Diego Olivier Fernandez Pons <dofp.oc...@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 -- 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