Velocity Reviews > logical expressions simplification with short circuit evaluation

# logical expressions simplification with short circuit evaluation

mingze zhang
Guest
Posts: n/a

 07-15-2010
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
Guest
Posts: n/a

 07-15-2010
On Jul 15, 10:40*am, mingze zhang <(E-Mail Removed)> 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
Guest
Posts: n/a

 07-15-2010
On Jul 14, 10:40*pm, mingze zhang <(E-Mail Removed)> 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
Guest
Posts: n/a

 07-15-2010
christian.bau wrote:
> On Jul 15, 3:40 am, mingze zhang <(E-Mail Removed)> 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
. @ .

Junior Member
Join Date: Oct 2011
Posts: 1

 10-22-2011
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