Linq.Expression.Optimizer
Linq.Expression.Optimizer copied to clipboard
Boolean expression reduction (help wanted)
Hi, I am trying to simplify boolean expressions, that I think it might be achieved with the "binary tree balancing" feature but I am not able to do it based in your examples...
I am looking for something like:
Original: X = AB + A!C
Reduction X = A*(B + !C)
Can you tell me if it is possible and how to do it?
Thanks Renato Martins
Binary-tree-balancing is for optimizing mainly 2 types of clauses:
(a and b and c and d and ...)
and (a or b or c or d or ...)
to not cause stack-overflows, which happens easily with normal LINQ because of the way LINQ evaluates things.
Your example is near the boolean algebra gather-rule.
What are the types of your A and B and C?
This project is initially for boolean algebra because database queries are often related to and
and or
-logics (in e.g. where-clauses) where as you would probably want more kind of maths algebra term rewriting like this?
Which would be totally doable here, I just have not needed it. :-) Would you like to describe more the use-case or benefits why this would be needed?
One problem is also that we don't always know the best optimization for the target system, e.g. your original and reduction examples are totally two-way, so by constructing this kind of term-rewriting, the system has to be careful not to start to oscillate back and forth between these two states forever.
A B and C are booleans, where the "*" is an "and" , "+" an "or" and the "!" a "not"
The expression would be like: X = A and B or A and notC
My main goal is to compare 2 boolean expressions and verify if they contain the same logic, to know if both are true given the same inputs, and I would like to apply a reduction first for that. And to know if by applying the reduce feature to similar expression I would get always the same output...
I guess this might be outside your goal.
But thanks anyway :)
This is doable by this library already. ExpressionOptimizer.reductionMethods is a static list of which optimizations you want to use. So set there first a list what methods you want to use, and then use like normal.
This system optimizes LINQ Expressions for the abstract syntax trees. Which are good if you do C# Expression trees and want to actually execute the logic. But if you just want to play with boolean algebra, I'd recommend github.com/mavnn/Algebra.Boolean which has the same optimizations in boolean algebra as this library (because I converted those to C#-LINQ-Expressions). @mavnn has done some presentations about that also.
Thanks for your help!
I will try it.