Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   logical expressions simplification with short circuit evaluation (http://www.velocityreviews.com/forums/t728282-logical-expressions-simplification-with-short-circuit-evaluation.html)

 mingze zhang 07-15-2010 02:40 AM

logical expressions simplification with short circuit evaluation

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 07-15-2010 04:28 AM

Re: logical expressions simplification with short circuit evaluation

On Jul 15, 10:40*am, mingze zhang <zhangmin...@gmail.com> 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.

 Gene 07-15-2010 04:13 PM

Re: logical expressions simplification with short circuit evaluation

On Jul 14, 10:40*pm, mingze zhang <zhangmin...@gmail.com> 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.

 Niklas Holsti 07-15-2010 06:24 PM

Re: logical expressions simplification with short circuit evaluation

christian.bau wrote:
> On Jul 15, 3:40 am, mingze zhang <zhangmin...@gmail.com> 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
. @ .