When boolean logic breaks down


In a previous post i mentioned a little bit of work i was doing to create a little feature would Simplify Boolean Expressions.  To refresh your memory it would allow you to transform:


   if ((!((Foo() && !Bar()) || (!Foo() && Bar()))) { //…


into


   if (Foo() == Bar()) { //…


Of course, this isn’t valid in the case where Foo and Bar have side-effects, however, if you know that they don’t then it should be a completely safe change to make.  The intent of this was to help you safely transform expressions that were gettign out of control into simpler and easier understand snippets.  Often when you do this (applying all sorts of combining and mutating boolean laws) it’s quite simple to make a mistake, so having an automated tool would be very handy.


Now, it recently came to my attention that even with side effect free expressions this stuff could break down.  Say you’d written the following:


   if (bb || !bb) { //bb has no side-effects…


Then it should be safe to just transform that into:


   if (true) { //…


But it actually turns out that that’s not necessarily the case.  There are two reasons i’ve found that that assumption might not hold.  Any ideas about what those might be?  Once i see the right responses i’ll put them up here!


Comments (24)

  1. Depending on the language, null/undefined/NaN can cause problems because they put you in the realm of ternary logic instead of expected binary logic.

  2. Dan t says:

    If multithreaded, the value could change mid if statement.

  3. Robert Kozak says:

    Cyrus,

    Comments : I don’t see comments unless I post one first. Can you look into this cause I can’t i9magine you like it this way. Maybe you do. I dunno. 🙂

  4. Garry Trinder says:

    Compiler code flow analysis is different:

    Example 1:

    if (true) {

    } else {

    Console.WriteLine(); // Unreachable code

    }

    Example 2:

    Definite assignment rules:

    bool b = true;

    object x;

    if (true)

    {

    x = null;

    }

    if (x == null) { }

    No error in case of if (true) versus "Error use of unassigned local variable ‘x’ " in case of if (b ||! b)

  5. CyrusN says:

    Awesome responses.

    "Operator overloading?"

    Yup! Overload "operator true", "operator !" or "operator ||" and you can get this behavior.

    "Depending on the language, null/undefined/NaN can cause problems because they put you in the realm of ternary logic instead of expected binary logic."

    Yup. Until now C# didn’t have ternary logic. But the additional of the Nullable type has now introduced it.

    "If multithreaded, the value could change mid if statement."

    Yup. I wasn’t really counting this when i wrote the post because i was intending that "bb has no side effects" meant that "bb" would evaluate to the same thing. I wasn’t clear about that, so your case definitely applies.

  6. CyrusN says:

    Robert: I wasn’t aware of that. I’ll send that info to the people who run the blog.

    Sorry about this!

  7. I’m not sure if this falls into the ‘side effects’ category, but operator overloading could cause the above case to not be if(true)

  8. Haacked says:

    I just ran into this recently. If you compare two sql types (for example two SqlInt values), you’ll get a SqlBoolean instead of a bool.

  9. Even before nullable-types, NaN could throw a big kink in logic simplification. Still, these special rules could be taken into account, as they are not unpredictable.

    The rules still require the operators to be deterministic and have no side-effects.

    Perhaps it’d be nice if to mark a method/function/property with a [Deterministic] attribute. Then code tools could determine if removing extra calls with the same arguments will not result in a change of behavior.

    This would allow (in theory) the compiler/JIT to optimize away redundant calls, so if(Foo(x) == 3 || Foo(x) == 4) would result in only one call to Foo. Of course, apply this attribute to a non-deterministic function and beware the very unpredictable results, but it’d be nice for methods such as Math.Sin() or TimeSpan.FromDays() to be marked deterministic.

    I believe that T-SQL has such a mechinism, which allows it to optimize away function calls in a loop (this is where it really pays off, although this optimization can be done manually).

  10. Larry Smith says:

    Two that come to mind are nullable types, and classes that overload ! to mean something other than simple boolean inversion.

    BTW, yes I did get the Shakespearean reference. Cute!

  11. damien morton says:

    I like the idea of a [Deterministic] attribute.

    It would also allow the compiler to optimize code like this:

    for (int i = 0; i < Math.Sin(x); i++)

    foo(i);

    By lifing the Math.Sin(x) evaluation out of the loop.

  12. The ! operator could be overridden.

    The ‘true’ operator could also be overridden.

  13. Ha. This new comment posting system is throwing me off. Since I didn’t see the previous comments, I assumed nobody had answered yet. Sorry for being redundant.

    However, note that you cannot overload operator || in C#.

  14. Darren Oakey says:

    There’s a weirder one as well – suppose class y has an implicit operator converting it to bool.

    Then if bb is an instance of y

    if (bb || !bb) is a valid expression – but if bb happens to be a null, this could actually throw an exception (dependiing on what is done in the implicit operator)

    However if (true) can never throw an exception

  15. MrMills says:

    Yes, in certain very odd edge cases this won’t help. But that doesn’t mean you still shouldn’t do it. I mean, sure, disclaimer it up, but in the hands of the professional programmer who knows enough to avoid the pitfalls, it would be very helpful.

  16. Mark Mullin says:

    This could fail for any cases where the terms are not constant, i.e. they are the product of function evaluation – and yes, side effects are not an issue.

    For example, if there was a function DatabaseAvailable(), the logic could evaluate the first term and fail (not available) and then evaluate the second term (now available) and fail again. Likewise, if you have a time function IsMidnight(), it’s pretty evident how this could fail.

    If the values are static terminals, i.e. boolean constants from the pov of the evaluator, then it should be reduceable

  17. Well, I’ll take a wild stab at it:

    1. If bb were a nullable type, this isn’t a safe replacement.

    2. If operator! is overridden, this isn’t safe. (Frankly, I’m not sure offhand if this is even possible in C#…I’m a C++ guy :P.)

  18. James Antill says:

    To refresh your memory it would allow you to transform:

    if ((!((Foo() && !Bar()) || (!Foo() && Bar()))) { //…

    into

    if (Foo() == Bar()) { //…

    …remind me again, why can’t you do the obvious…

    if (!Foo() == !Bar())

  19. poofias says:

    The logic reductions you’ve presented are extremely basic. Taking a look at the example you’ve provided:

    !((Foo && !Bar) || (!Foo && Bar))

    ![(F’*B) + (F’*B’)]

    (F’+B)*(F+B’)

    F’F + F’B’ + FB + BB’

    F’B’ + FB

    F XNOR B

    An intro on boolean or symbolic logic would be the order of the day here:

    http://www-inst.eecs.berkeley.edu/~cs150/fa04/Lecture/lec05.ppt

    In regards to "side-effects," the basic idea is that you’re to evaluate functions which alter program state before performing logical reductions. This is a well-understood concept in compiler theory or relational algebra/calculus.

    As well, from your January post:

    "it would be nice if this could just be taken care of for you"

    It [b]is[/b] taken care of for you by any useful compiler.

  20. poofias says:

    >…remind me again, why can’t you do the

    >obvious…

    >

    >if (!Foo() == !Bar())

    If "foo" and "bar" were only boolean values, then what you’ve written is exactly the same as ‘Foo() == Bar().’ Write out the truth table and prove it to yourself.

  21. CyrusN says:

    James: You could. Did i imply otherwise? if so, i apologize.

  22. CyrusN says:

    Poofias: "It [b]is[/b] taken care of for you by any useful compiler."

    As i mentioned in my post on boolean simplification, this is absolutely *not* about optimization. This is about clarity and maintainability. Complex expressions can be difficult to grok and there is value in simplification as it can mroe accurately get your intent across. Simplification can also help because you might not even realize yoruself that what you are saying is far simpler than you realized.

    In my original case (in the first boolean simplification blog post), i mentioned a simplification that went from something extremely complex and difficult (for me) to reason about, into a simple:

    if (a == b)

    which made things so much nicer.

    That is the purpose of this refactoring.

  23. poofias says:

    >In my original case (in the first boolean

    >simplification blog post), i mentioned a

    >simplification that went from something

    >extremely complex and difficult (for me) to

    >reason about, into a simple:

    >

    >if (a == b)

    >

    >which made things so much nicer.

    Before I come up with a retort which may not be well-taken, might I ask how you came up with the original if() statement in the first place? I ask this because, sometimes, it’s more difficult to understand a logical reduction than it is to understand the starting equation.

    I can even give you an example (which may seem a little contrived, but is extremely valid in the world of integrated circuits): say you wanted to implement an OR operation across 256 variables. Assume that you only have access to NOR, NAND, and INV instructions.

    The naive way to implement the operation is to perform NOR on two inputs, then complement the output with an INV. This is very simple and straightforward for anyone to understand.

    The logically-reduced method would be to cascade NOR and NAND instructions. The reason for this is the following:

    A NOR B = (A+B)’ = X

    C NOR D = (C+D)’ = Y

    X NAND Y = (XY)’ = [(A+B)'(C+D)’]’ = (A+B)+(C+D)

    Hence, while we’ve come up with something which is tighter and more efficient, it’s not as clear as the original expression since the reader may be unfamiliar with de Morgan’s law.

    Sometimes, "nicer" doesn’t always mean "clearer" 🙂

Skip to main content