logic expressions & short circuit evaluation

Discussion in 'C++' started by mingze zhang, Jul 15, 2010.

  1. mingze zhang

    mingze zhang Guest

    Hi all,

    Sorry that this post may not be a correct place for C++ forum. I hope
    someone can give me some idea on this.

    We all know that logic expressions can be manipulated or simplified,
    for example,
    1. (x && y) || (x && z) is equivalent to x && (y || z)
    2. x && (x || y) is equivalent to x
    3. (x || y) && (x || z) is equivalent to x || (y && z)

    4. (y && x) || (z && x) is equivalent to (y || z) && x
    5. (x || y) && x is equivalent to x
    6. (y || x) && (z || x) is equivalent to (y && z) || x

    But this simplification is apparently not all valid if short-circuit
    evaluation is considered. In the above examples, Cases 1-3 are valid,
    but 4-6 are not (assume x, y, z may have side effects).

    So here comes my question, is there a general guideline to simplify a
    very complicated logic expressions (under short-circuit equivalence)
    when some of the logic expressions have side effect and some do not.

    I know some compilers may do this kind of simplification. I just want
    to know whether there are some tutorial or general procedures so that
    I can quickly catch up. I tried to search on Google but with no good
    luck.

    Thanks in advance.
    Vincent
     
    mingze zhang, Jul 15, 2010
    #1
    1. Advertising

  2. mingze zhang

    mingze zhang Guest

    On Jul 15, 11:16 am, Sam <> wrote:
    > mingze zhang writes:
    > > Hi all,

    >
    > > Sorry that this post may not be a correct place for C++ forum. I hope
    > > someone can give me some idea on this.

    >
    > > We all know that logic expressions can be manipulated or simplified,
    > > for example,
    > >  1. (x && y) || (x && z) is equivalent to x && (y || z)
    > >  2. x && (x || y) is equivalent to x
    > >  3. (x || y) && (x || z) is equivalent to x || (y && z)

    >
    > >  4. (y && x) || (z && x) is equivalent to (y || z) && x
    > >  5. (x || y) && x is equivalent to x
    > >  6. (y || x) && (z || x) is equivalent to (y && z) || x

    >
    > > But this simplification is apparently not all valid if short-circuit
    > > evaluation is considered. In the above examples, Cases 1-3 are valid,
    > > but 4-6 are not (assume x, y, z may have side effects).

    >
    > No. None of them are valid. Given that each expression may have a side
    > effect, short-circuit evaluation order matters:
    >
    > (func1() && func2()) || (func1() && func3())
    >
    > If the first call to func1() returns 0, func1() gets called against a second
    > time.
    >
    > func1() && (func2() || func3())
    >
    > If the first call to func1() returns 0, func1() does not get called a second
    > time.
    >
    > We are not talking about a pure formula, but logic. A subtle difference.
    >
    > > So here comes my question, is there a general guideline to simplify a
    > > very complicated logic expressions (under short-circuit equivalence)
    > > when some of the logic expressions have side effect and some do not.

    >
    > The general guideline is that simplification is "possible" only when there
    > are no side effects.
    >
    > > I know some compilers may do this kind of simplification. I just want

    >
    > Compilers will optimize short-circuit evaluations only if parts of it
    > evaluate to a constant, in which case the compiler will unfold the short
    > circuit to whatever degree is possible.
    >
    >  application_pgp-signature_part
    > < 1KViewDownload


    Thanks.

    I am wrong and I ignored the fact that a statement can be evaluated
    twice.

    I'll reconsider the whole problem.
     
    mingze zhang, Jul 15, 2010
    #2
    1. Advertising

  3. mingze zhang

    James Kanze Guest

    On Jul 15, 3:20 am, mingze zhang <> wrote:

    > Sorry that this post may not be a correct place for C++ forum. I hope
    > someone can give me some idea on this.


    > We all know that logic expressions can be manipulated or simplified,
    > for example,
    > 1. (x && y) || (x && z) is equivalent to x && (y || z)
    > 2. x && (x || y) is equivalent to x
    > 3. (x || y) && (x || z) is equivalent to x || (y && z)


    > 4. (y && x) || (z && x) is equivalent to (y || z) && x
    > 5. (x || y) && x is equivalent to x
    > 6. (y || x) && (z || x) is equivalent to (y && z) || x


    If this is C++: the && and || are not (Boolean) logic operators,
    but something very computer specific, which does NOT obey the
    rules of Boolean algebra. Your "equivalent" aren't, at least
    not in general.

    > But this simplification is apparently not all valid if short-circuit
    > evaluation is considered. In the above examples, Cases 1-3 are valid,
    > but 4-6 are not (assume x, y, z may have side effects).


    None are valid, unless the compiler can prove that they make no
    difference in the observable behavior. (If, for example, x,
    y and z are expressions without any function calls, using only
    doubles and ints, the compiler can use any of the equivalences
    above. If x, y and z contain a function call which outputs to
    cout, none of the above rewrites can be done. Note too that
    because && and || introduce sequence points, they determine the
    order the side effects become visible.)

    > So here comes my question, is there a general guideline to
    > simplify a very complicated logic expressions (under
    > short-circuit equivalence) when some of the logic expressions
    > have side effect and some do not.


    General guidelines, I don't know. In general, I suspect that
    compilers avoid any reordering when there is any possibility of
    side effects.

    > I know some compilers may do this kind of simplification. I just want
    > to know whether there are some tutorial or general procedures so that
    > I can quickly catch up. I tried to search on Google but with no good
    > luck.


    One of the major objections to short-circuiting is that it
    inhibits optimization. The practical benefits for the
    programmer are such, however, that most modern languages support
    it.

    --
    James Kanze
     
    James Kanze, Jul 15, 2010
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. webposter
    Replies:
    2
    Views:
    680
    Peter Shaggy Haywood
    Sep 14, 2004
  2. Lassie

    short circuit evaluation

    Lassie, Sep 16, 2008, in forum: C Programming
    Replies:
    29
    Views:
    855
  3. Anthony Paul

    short-circuit evaluation and assignment operators

    Anthony Paul, Jun 6, 2009, in forum: C Programming
    Replies:
    5
    Views:
    1,312
  4. mingze zhang
    Replies:
    4
    Views:
    1,147
    aadilsabri
    Oct 22, 2011
  5. Ahmed Abdulshafy

    Short-circuit Logic

    Ahmed Abdulshafy, May 26, 2013, in forum: Python
    Replies:
    65
    Views:
    375
    Stefan Drees
    May 31, 2013
Loading...

Share This Page