c# - Comparing Multivariable Boolean Functions -

c# - Comparing Multivariable Boolean Functions -

an application i'm writing involved parsing plaintext boolean lambda expressions. for purposes of testing, need create sure parsing occurring correctly. so, wrote recursive look tree comparing routine, bool expressioncomparison.equvalentto(this look self, look other). if self , other both logical operators, , share same set of operands, equvalentto should homecoming true.

my current algorithm uses expressionvisitor. pass body of lambda look visitor , replaces operands (expressions aren't logical operators) boolean parameters. phone call on both lambdas, compare operands, reorder binary parameters sec lambda, if necessary, correspond same operands, compile 2 binary functions, , exhaustively compare results.

is there more efficient way compare logical equivalence of 2 boolean functions?

public static class expressioncomparison { public static bool equals(this look left, look right) { homecoming compare(left, right, equals); } public static bool equvalentto(this look self, look other) { if (object.equals(self, other)) homecoming true; if (self == null || other == null) homecoming false; if ((self.nodetype == expressiontype.not || self.nodetype == expressiontype.andalso || self.nodetype == expressiontype.orelse) && (other.nodetype == expressiontype.not || other.nodetype == expressiontype.andalso || other.nodetype == expressiontype.orelse)) homecoming new visitor(self).compare(new visitor(other), equvalentto); else if (self.nodetype != other.nodetype) homecoming false; if (self.nodetype == expressiontype.constant) { var _self = (constantexpression)self; var _other = (constantexpression)other; if (object.referenceequals(_self.value, _other.value)) homecoming true; } if (self.type != other.type) homecoming false; switch (self.nodetype) { case expressiontype.add: case expressiontype.addchecked: case expressiontype.multiply: case expressiontype.multiplychecked: case expressiontype.and: case expressiontype.or: case expressiontype.exclusiveor: var selfsubs = ((binaryexpression)self).linearize().tolist(); var othersubs = ((binaryexpression)other).linearize().tolist(); foreach (var leftsub in selfsubs) { int i; (i = othersubs.count - 1; >= 0; i--) if (equvalentto(leftsub, othersubs[i])) { othersubs.removeat(i); break; } if (i < 0) homecoming false; } homecoming othersubs.count == 0; } homecoming compare(self, other, equvalentto); } private static bool compare(expression self, look other, func<expression, expression, bool> comparer) { if (object.equals(self, other)) homecoming true; if (self == null || other == null) homecoming false; if (self.nodetype != other.nodetype) homecoming false; if (self.type != other.type) homecoming false; if (self binaryexpression) { var _left = (binaryexpression)self; var _right = (binaryexpression)other; homecoming comparer(_left.left, _right.left) && comparer(_left.right, _right.right); } else if (self conditionalexpression) { var _left = (conditionalexpression)self; var _right = (conditionalexpression)other; homecoming comparer(_left.iffalse, _right.iffalse) && comparer(_left.iftrue, _right.iftrue) && comparer(_left.test, _right.test); } else if (self constantexpression) { var _left = (constantexpression)self; var _right = (constantexpression)other; if (!object.equals(_left.value, _right.value)) homecoming false; homecoming true; } else if (self defaultexpression) { homecoming true; } else if (self indexexpression) { var _left = (indexexpression)self; var _right = (indexexpression)other; if (_left.arguments.count != _right.arguments.count) homecoming false; if (!object.equals(_left.object, _right.object)) homecoming false; if (!object.equals(_left.indexer, _right.indexer)) homecoming false; (var = _left.arguments.count - 1; >= 0; i--) if (!comparer(_left.arguments[i], _right.arguments[i])) homecoming false; homecoming true; } else if (self invocationexpression) { var _left = (invocationexpression)self; var _right = (invocationexpression)other; if (_left.arguments.count != _right.arguments.count) homecoming false; if (!comparer(_left.expression, _right.expression)) homecoming false; (var = _left.arguments.count - 1; >= 0; i--) if (!comparer(_left.arguments[i], _right.arguments[i])) homecoming false; homecoming true; } else if (self lambdaexpression) { var _left = (lambdaexpression)self; var _right = (lambdaexpression)other; if (_left.parameters.count != _right.parameters.count) homecoming false; (var = _left.parameters.count - 1; >= 0; i--) if (!comparer(_left.parameters[i], _right.parameters[i])) homecoming false; if (!object.equals(_left.returntype, _right.returntype)) homecoming false; homecoming comparer(_left.body, _right.body); } else if (self listinitexpression) { var _left = (listinitexpression)self; var _right = (listinitexpression)other; if (comparer(_left.newexpression, _right.newexpression)) homecoming false; (var = _left.initializers.count - 1; >= 0; i--) { var leftinit = _left.initializers[i]; var rightinit = _right.initializers[i]; if (object.equals(leftinit, rightinit)) continue; if (!object.equals(leftinit.addmethod, rightinit.addmethod)) homecoming false; if (leftinit.arguments.count != rightinit.arguments.count) homecoming false; (var j = leftinit.arguments.count - 1; j >= 0; j--) if (!leftinit.arguments[i].equvalentto(rightinit.arguments[i])) homecoming false; } homecoming true; } else if (self memberexpression) { var _left = (memberexpression)self; var _right = (memberexpression)other; if (!object.equals(_left.member, _right.member)) homecoming false; homecoming comparer(_left.expression, _right.expression); } else if (self memberinitexpression) { } else if (self methodcallexpression) { var _left = (methodcallexpression)self; var _right = (methodcallexpression)other; if (!object.equals(_left.method, _right.method)) homecoming false; if (!comparer(_left.object, _right.object)) homecoming false; (var = _left.arguments.count - 1; >= 0; i--) if (!comparer(_left.arguments[i], _right.arguments[i])) homecoming false; homecoming true; } else if (self newarrayexpression) { var _left = (newarrayexpression)self; var _right = (newarrayexpression)other; (var = _left.expressions.count - 1; >= 0; i--) if (!comparer(_left.expressions[i], _right.expressions[i])) homecoming false; homecoming true; } else if (self newexpression) { var _left = (newexpression)self; var _right = (newexpression)other; if (!object.equals(_left.constructor, _right.constructor)) homecoming false; (var = _left.members.count - 1; >= 0; i--) if (!object.equals(_left.members[i], _right.members[i])) homecoming false; (var = _left.arguments.count - 1; >= 0; i--) if (!comparer(_left.arguments[i], _right.arguments[i])) homecoming false; homecoming true; } else if (self parameterexpression) { homecoming true; } else if (self typebinaryexpression) { var _left = (typebinaryexpression)self; var _right = (typebinaryexpression)other; if (_left.typeoperand != _right.typeoperand) homecoming false; homecoming comparer(_left.expression, _right.expression); } else if (self unaryexpression) { var _left = (unaryexpression)self; var _right = (unaryexpression)other; if (!object.equals(_left.method, _right.method)) homecoming false; homecoming comparer(_left.operand, _right.operand); } throw new exception("unhandled look type: " + self.gettype()); } private static ienumerable<expression> linearize(this binaryexpression expr) { var type = expr.nodetype; if (expr.left.nodetype == type) foreach (expression subexpr in ((binaryexpression)expr.left).linearize()) yield homecoming subexpr; else yield homecoming expr.left; if (expr.right.nodetype == type) foreach (expression subexpr in ((binaryexpression)expr.right).linearize()) yield homecoming subexpr; else yield homecoming expr.right; } class visitor : expressionvisitor { ilist<expression> _expressions = new list<expression>(); ilist<parameterexpression> _parameters = new list<parameterexpression>(); parameterexpression _next(expression expression) { var parameter = expression.parameter(typeof(boolean)); _expressions.add(expression); _parameters.add(parameter); homecoming parameter; } public override look visit(expression node) { switch (node.nodetype) { case expressiontype.not: case expressiontype.andalso: case expressiontype.orelse: homecoming base.visit(node); default: homecoming _next(node); } } public look visited { get; private set; } public expression[] expressions { get; private set; } public parameterexpression[] parameters { get; private set; } public visitor(expression node) { visited = visit(node); expressions = _expressions.toarray(); parameters = _parameters.toarray(); } private delegate naturalorder() { homecoming expression.lambda(visited, parameters).compile(); } private delegate forcedorder(int[] order) { homecoming expression.lambda(visited, order.select(i => parameters[i])).compile(); } public bool compare(visitor that, func<expression, expression, bool> comparer) { if (this.expressions.length != that.expressions.length) homecoming false; var order = new int[this.expressions.length]; var compareexpr = that.expressions.toarray(); (int = expressions.length - 1, j; >= 0; i--) if (comparer(expressions[i], compareexpr[i])) order[i] = i; else { (j = compareexpr.length - 1; j >= 0; j--) if (i == j) continue; else if (comparer(expressions[i], compareexpr[j])) { order[i] = j; compareexpr[j] = null; break; } if (j < 0) homecoming false; } dynamic thisd = this.naturalorder(); dynamic thatd = that.forcedorder(order); var args = new bool[order.length]; (var = ((ulong)1 << order.length); > 0; i--) { (var j = (byte)order.length - 1; j >= 0; j--) args[j] = ((i - 1) & ((ulong)1 << j)) != 0; if (!funchelper.exec(thisd, thatd, args)) homecoming false; } homecoming true; } } }

asside/update: comparing expression<func<tmodel, bool>>s utilize in clauses linq entities. want know given text string correctly parsing lambda, , so, compare generated lambda against lambda expect. i want know both lambda homecoming same result set. can't test against data, of queries intentionally absurd, end of making sure parser robust. additionally, info changing, query might subtly different query b, moment both homecoming same set, etc. test lambdas equivalence.

i define 2 expressions equivalent if 1 of following:

object.equals(a, b) returns true a , b logically equivalent (only applicable not, andalso, , orelse nodes; defined below) a , b both commutatively equivalent (only applicable add, multiply, (bitwise) and, or, , exclusiveor nodes; defined below) their expressiontypes of a , b equal , of operands, operators, parameters, arguments, etc equivalent (for expressions) or equal (for other objects).

i define 2 expressions logically equivalent if: 'operands' equivalent and, if replace each boolean operand boolean parameter, 2 resulting n-ary boolean functions have same truth tables. process follows:

for each, visit expression, skipping nodes of nodetype not, andalso, or orelse, replacing other nodes new boolean parameter. boolean parameters , expressions replace captured in arrays. check same number of expressions captured. compare captured expressions of b, determining if equivalent sets, , determining relative order (parama.propa == 1 && paramb.propb == 2 considered equivalent paramb.propb == 2 && parama.propa == 1, in more complicated cases, different order of parameters result in different truth table). alter order of boolean parameters of b b.parameters[i] corresponds look b.expressions[j] equivalent a.expressions[i]. compile visited expressions 2 boolean functions , compare truth tables.

i define 2 expressions commutatively equivalent if: expressiontypes of a , b equal , if, , b, walk downwards tree, stopping @ expression not same expressiontype a/b, , set look in list, list a , b contain same set of expressions (determined equivalency).

c# c#-4.0 lambda