Velocity Reviews > C++ > logic expressions & short circuit evaluation

# logic expressions & short circuit evaluation

mingze zhang
Guest
Posts: n/a

 07-15-2010
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.

Vincent

mingze zhang
Guest
Posts: n/a

 07-15-2010
On Jul 15, 11:16*am, Sam <(E-Mail Removed)> 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

Thanks.

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

I'll reconsider the whole problem.

James Kanze
Guest
Posts: n/a

 07-15-2010
On Jul 15, 3:20 am, mingze zhang <(E-Mail Removed)> 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