# logical expressions simplification with short circuit evaluation

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

1. ### mingze zhangGuest

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.

Vincent

mingze zhang, Jul 15, 2010

2. ### mingze zhangGuest

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.
>
> Vincent

I was wrong. All 1-6 cannot be simplified.

mingze zhang, Jul 15, 2010

3. ### GeneGuest

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.
>
> 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
4. ### Niklas HolstiGuest

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

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