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
- Anonymous
April 15, 2005
Operator overloading? - Anonymous
April 15, 2005
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. - Anonymous
April 15, 2005
If multithreaded, the value could change mid if statement. - Anonymous
April 15, 2005
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. :-) - Anonymous
April 15, 2005
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) - Anonymous
April 15, 2005
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. - Anonymous
April 15, 2005
Robert: I wasn't aware of that. I'll send that info to the people who run the blog.
Sorry about this! - Anonymous
April 15, 2005
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) - Anonymous
April 15, 2005
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. - Anonymous
April 15, 2005
The comment has been removed - Anonymous
April 15, 2005
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! - Anonymous
April 15, 2005
The comment has been removed - Anonymous
April 16, 2005
The ! operator could be overridden.
The 'true' operator could also be overridden. - Anonymous
April 16, 2005
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#. - Anonymous
April 16, 2005
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 - Anonymous
April 17, 2005
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. - Anonymous
April 19, 2005
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 - Anonymous
April 20, 2005
The comment has been removed - Anonymous
April 22, 2005
The comment has been removed - Anonymous
April 22, 2005
The comment has been removed - Anonymous
April 22, 2005
The comment has been removed - Anonymous
April 23, 2005
James: You could. Did i imply otherwise? if so, i apologize. - Anonymous
April 23, 2005
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. - Anonymous
April 23, 2005
>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" :)