Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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.

Thanks in advance.
Vincent

 
Reply With Quote
 
 
 
 
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
> < 1KViewDownload


Thanks.

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

I'll reconsider the whole problem.
 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
logical expressions simplification with short circuit evaluation mingze zhang C Programming 4 10-22-2011 09:51 AM
short-circuit evaluation and assignment operators Anthony Paul C Programming 5 06-06-2009 06:49 PM
short circuit evaluation Lassie C Programming 29 09-25-2008 08:08 PM
A Sorting Circuit in Digital Logic Design Johnathan Coll VHDL 1 12-28-2006 08:08 PM
Short-Circuit Evaluation of Boolean Expressions webposter C Programming 2 09-14-2004 03:43 AM



Advertisments