logical expressions simplification with short circuit evaluation

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

  1. mingze zhang

    mingze zhang Guest

    Hi all,

    We all know that logical 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 logical expression (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, 10:40 am, mingze zhang <> wrote:
    > Hi all,
    >
    > We all know that logical 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 logical expression (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


    I was wrong. All 1-6 cannot be simplified.
    mingze zhang, Jul 15, 2010
    #2
    1. Advertising

  3. mingze zhang

    Gene Guest

    On Jul 14, 10:40 pm, mingze zhang <> wrote:
    > Hi all,
    >
    > We all know that logical 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 logical expression (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


    By "not valid" I assume you mean that the transformed expressions may
    evaluate predicates a different number of times, allowing side effects
    of functions embedded in the predicates to differ. This is true.

    To avoid it, you can translate short circuit expressions as
    conditionals:

    x || y becomes x != 0 ? 1 : y != 0 ? 1 : 0
    x && y becomes x != 0 ? y != 0 ? 1 : 0 : 0

    and then reason about these to get new identities for simplification.
    Gene, Jul 15, 2010
    #3
  4. christian.bau wrote:
    > On Jul 15, 3:40 am, mingze zhang <> wrote:


    [snip]

    > For example the expression (x = 1) has a side effect, but evaluating
    > it twice makes no difference.


    .... unless x is volatile.

    --
    Niklas Holsti
    Tidorum Ltd
    niklas holsti tidorum fi
    . @ .
    Niklas Holsti, Jul 15, 2010
    #4
  5. mingze zhang

    aadilsabri

    Joined:
    Oct 22, 2011
    Messages:
    1
    The simplify expression they logically manipulative and simplified with logical compair with other component which gives exact value in coordination in //X is equal or not that's find by multiplication of X and Y that's coordinate value compair with given term in question in this method x&&y=x&&z which are logically devloped
    aadilsabri, Oct 22, 2011
    #5
    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. Phil...
    Replies:
    10
    Views:
    728
    Joona I Palaste
    Oct 23, 2003
  2. webposter
    Replies:
    2
    Views:
    650
    Peter Shaggy Haywood
    Sep 14, 2004
  3. Lassie

    short circuit evaluation

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

    short-circuit evaluation and assignment operators

    Anthony Paul, Jun 6, 2009, in forum: C Programming
    Replies:
    5
    Views:
    1,284
  5. mingze zhang
    Replies:
    2
    Views:
    466
    James Kanze
    Jul 15, 2010
Loading...

Share This Page