logic expressions & short circuit evaluation

[mingze zhang]

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.

Thanks in advance.
Vincent

 

[mingze zhang]

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.


The general guideline is that simplification is "possible" only when there
are no side effects.


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
< 1KViewDownload

Thanks.

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

I'll reconsider the whole problem.

 

[James Kanze]

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.