Partager via

Simplifying boolean expressions

  • Article

i was doing a little fun C# coding on the side and i was running into one of those cases where i had a conditional expression to write and i couldn't figure out the best way to write it.  it was basically something like:

void Foo(a, b) {
if (!((a && !b) || (!a && b))) {
//do stuff
}
}

i was sitting there playing with this expression until i realized that it could be reduced to just "if (a == b)".  After that i was thinking "it would be nice if this could just be taken care of for you".  Similarly we could transform expressions like:

if (a > b || a == b) { //...

into

if (a >= b) { //...

Or could we...

interestingly enough we might not actually be allowed to do that.  Why?  Well lets say the user had written their type with the following members:

bool operator >(T t1, T t2) { return true; }
bool operator ==(T t1, T t2) { return true; }
bool operator >=(T t1, T t2) { return false; }

(egads!  Legal, although discouraged).

Now we've gone ahead and changed the legal meaning of your code. 

Here's another example:  Say we tried to transform the following expression:

if (a > 0 || a > 0) { //...

into

if (a > 0) { //...

Seems fine, but actually it might not be.  Here's how:

int _a;
int a { get { return _a++; } }

So, in order to get something like this right it seems like we'd have to go deeper than just looking at the parse structure of the code, and we'd have to go deeper to examine the semantics behind it.  in the first case we can't assume that overloaded operators have the same combinatoric semantics that we're used to with most of the builtin types, and in the second the expression has side affects, so reducing it will not preserve those changes.  Luckily the compiler can at least tell us if an expression leads to executable code, and in that case we can just assume the expression is unsafe to manipulate. 

Of course, it's quite possible that one might want to still go through with the transformation because they know that it's safe for their domain.  For example, this would allow them to simplify:

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

into

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

This would be OK as long as the user was confident that the semantics of those operators expressions are the same as if they were just dealing with simple boolean expressions.

So i figured i'd provide two expression manipulation tools.  One to just simplify the expression "safely" and one to simplify it "aggressively" as per the caveats i listed above. 

i'd also want to be able to handle code of the form:

if (a) {
if (b) {
c;
} else {
d;

   }
} else {
d;
}

and transform it into:

if (a && b) {
c;
} else {
d;
}

So now, how do i go about doing this?  Well, the next post will go into the prototype i wrote to get it done.

 If you'd like something like this in the IDE, let me know!

 

 

Edit: Note that this is not about showing you optimizations that can be done with your code.  This is about allowing you to take an overly complex and confusing bit of code and being able to rewrite it into a form that's much more clear and maintainable.  In the first example i had rather than having to put down some complicated implication rules i was just able to use a simple equivalence which not only was incredibly easy to read but it also helped me understand better what the code meant that i was writing at that point.

Comments

  • Anonymous
    January 23, 2005
    The comment has been removed
  • Anonymous
    January 23, 2005
    Sounds nice, but it does only work with booleans in certain cases. Your first example won't work if a and b are ints.

    Won't the (a>0||a>0) with side effects in operator> cause undefined behaviour, according to the standard, with two post-increments in what is basically the same expression?
  • Anonymous
    January 23, 2005
    The comment has been removed
  • Anonymous
    January 23, 2005
    Arrrgghhh!

    operator> with side effects?
    It doesn't work if a and b are ints?
    bool operator ==(T t1, T t2) { return true; } ?

    Why did I even bother to study computer science for four years?

    Assuming this is c# why not invent a keyword similar to unsafe called unsound. And only allow these kind of montrosities inside that construct. Like this.

    unsound
    {
    // Inside this block the laws of logic and mathematics no longer apply and you are free to use any kind of side effects and redefinitions you like.

    }
  • Anonymous
    January 23, 2005
    Steven: "Sounds nice, but it does only work with booleans in certain cases. Your first example won't work if a and b are ints. "

    That code won't compile if "a" and "b" are ints, so i'm not sure what the problem is there :)

    "Won't the (a>0||a>0) with side effects in operator> cause undefined behaviour, according to the standard, with two post-increments in what is basically the same expression? "

    I don't believe the behavior is undefined as C# specifies an exact left to right evaluation of expressions.
  • Anonymous
    January 23, 2005
    Lars:"Arrrgghhh!

    operator> with side effects?
    It doesn't work if a and b are ints?
    bool operator ==(T t1, T t2) { return true; } ?

    Why did I even bother to study computer science for four years?

    Assuming this is c# why not invent a keyword similar to unsafe called unsound. And only allow these kind of montrosities inside that construct. Like this.

    unsound
    {
    // Inside this block the laws of logic and mathematics no longer apply and you are free to use any kind of side effects and redefinitions you like.

    } "

    I agree. But it's still allowed by the language. (i actually don't know any language that disallows it).

    Do you have a suggestion on how you would enforce sanity in a language?

    Also... i'm not sure where people are getting the idea that this wouldn't work with ints...
  • Anonymous
    January 23, 2005
    The comment has been removed
  • Anonymous
    January 23, 2005
    It's called Boolean Algebra and the new C++/CLI compiler supports these optimizations with managed and unmanaged code. The version7 C++ compiler supports this with unmanaged code.
  • Anonymous
    January 23, 2005
    CN: That code won't compile if "a" and "b" are ints, so i'm not sure what the problem is there :)

    CN: I don't believe the behavior is undefined as C# specifies an exact left to right evaluation of expressions.

    Ah, it's C#. You didn't mention that anywhere and I assumed C/C++ (where my remarks do apply).
  • Anonymous
    January 23, 2005
    You might want the option of having a truth table pop up, which you can fill-in, and then have a generated (and optimized) if/then expression created for you.
  • Anonymous
    January 24, 2005
    The comment has been removed
  • Anonymous
    January 24, 2005
    The comment has been removed
  • Anonymous
    January 24, 2005
    What youre describing is very similar to karnaugh maps, or at least, a multivalued variant thereof.

    For complex boolean expressions, I often find myself writing out truth tables and working from there.

    Maybe its just my EE background.
  • Anonymous
    January 24, 2005
    One great big advantage of something like this would be easy inversion of complex expressions.

    Suppose you have something like
    if (a && (!b || c > 15) || c == 3)
    and want to invert it, you can, of course, just turn that into
    if (!(a && (!b || c > 15) || c == 3))
    but that makes it even more confusing. Let the proposed functionality clean that up.
    Beats figuring it out manually:
    if (!a || (b && c <= 15) && c != 3)

    Then again, others may want the reverse. They might prefer to have the original expression converted into:
    if (c == 3)
    {
    //True
    } else {
    if (a)
    {
    if (!b || c > 15)
    {
    //True
    } else {
    //False
    }
    } else {
    //False
    }
    }
    which makes the flow much easier to follow (to me, at least).
  • Anonymous
    January 24, 2005
    Well... my code above would be easier to follow if the indenting had been preserved.
  • Anonymous
    January 24, 2005
    Steven: your code would look like:

    if (c == 3) {
    ....//True
    } else {
    ....if (a) {
    ........if (!b || c > 15) {
    ............//True
    ........} else {
    ............//False
    ........}
    ....} else {
    ........//False
    ....}
    }

    And yes, easy collapsing/expansion of if/elses into boolean expressions would be nice as well and i'll try to get that.
  • Anonymous
    January 24, 2005
    The comment has been removed
  • Anonymous
    June 15, 2009
    PingBack from http://mydebtconsolidator.info/story.php?id=18378