Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > logical expressions simplification with short circuit evaluation

Reply
Thread Tools

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.

Thanks in advance.
Vincent
 
Reply With Quote
 
 
 
 
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.
>
> Thanks in advance.
> Vincent


I was wrong. All 1-6 cannot be simplified.
 
Reply With Quote
 
 
 
 
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.
>
> Thanks in advance.
> 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.


 
Reply With Quote
 
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
. @ .
 
Reply With Quote
 
aadilsabri aadilsabri is offline
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
 
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
logic expressions & short circuit evaluation mingze zhang C++ 2 07-15-2010 01:56 PM
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
Evaluation context of C-style Logical And/Or truexueweizhong@hotmail.com Perl Misc 10 01-15-2007 02:13 PM
Short-Circuit Evaluation of Boolean Expressions webposter C Programming 2 09-14-2004 03:43 AM



Advertisments