429,078 Members | 2,164 Online
Need help? Post your question and get tips & solutions from a community of 429,078 IT Pros & Developers. It's quick & easy.

# Lazy evaluation question

 P: n/a Why does C do lazy evaluation for logical boolean operations but not bitwise ones? Ie: the following program prints "1 2" , not "1 1" under gcc main() { int a = 1; int b = 1; 0 && ++a; 0 & ++b; printf("%d %d\n",a,b); } Surely the bitwise boolean ops are just as appropriate for doing lazy evaluation with? B2003 Jan 5 '08 #1
39 Replies

 P: n/a On 5 Jan, 16:26, Boltar

 P: n/a Boltar said: Why does C do lazy evaluation for logical boolean operations but not bitwise ones? Because logical operations are intended to establish the truth or falsity of an expression, so that appropriate action can be taken in either case. For example, if the expression is "if it's raining and I'm going out, I'll need an umbrella", once we've established that it's not raining, we don't need to know whether or not I'm going out - the falsity of the expression is already established, so an umbrella is not required. Another example: "if you're tall enough or can find a stepstool, you can fetch down that saucepan". Once we've established that you're tall enough, we don't need to look for a stepstool. So it makes good sense for C to do lazy evaluation of && and ||. But bitwise operators are not used to establish truth or falsity. They are used to calculate the result of a mathematical operation. Lazy evaluation would be pointless and meaningless. -- Richard Heathfield Email: -http://www. +rjh@ Google users: "Usenet is a strange place" - dmr 29 July 1999 Jan 5 '08 #3

 P: n/a On Jan 5, 6:26 pm, Boltar int main(void) { int i = 0; printf("sizeof(int) = %zu\n", sizeof ++i); printf("i = %d\n", i); /* will print 'i = 0' */ return 0; } -- As you see, sizeof does not evaluate it's operand/expression. (I heard it might evaluate it if you 'pass' a VLA; I am not sure thought, I will leave that to the regulars) Jan 5 '08 #4

 P: n/a On Sat, 05 Jan 2008 08:29:21 -0800, Boltar wrote: On 5 Jan, 16:26, Boltar Surely the bitwise boolean ops are just as appropriate for doing lazyevaluation with? That should have read SOME bitwise ops - ie AND and XOR when the left hand side is zero. Oh? So you're saying the value of (x ^ y), when x == 0, doesn't depend on y? What is that value, then, and why? Jan 5 '08 #5

 P: n/a vi******@gmail.com said: Furthermore, there is no concept of 'lazy evaluation' in C. Perhaps in Haskell or some other programming language but certainly not in C, not only that, but I fail to see what lazy evaluation has to do with this. (a && b) in this expression, b is evaluated ONLY if after 'a' gets evaluated it is not equal to 0 (or NULL) This is generally what people mean by "lazy evaluation". If you only mean that the Standard does not define the term, however, then you are correct. -- Richard Heathfield Email: -http://www. +rjh@ Google users: "Usenet is a strange place" - dmr 29 July 1999 Jan 5 '08 #6

 P: n/a Boltar

 P: n/a Richard wrote: ) vi******@gmail.com said: ) ) ) )Furthermore, there is no concept of 'lazy evaluation' in C. Perhaps in )Haskell or some other programming language but certainly not in C, not )only that, but I fail to see what lazy evaluation has to do with this. )> )(a && b) in this expression, b is evaluated ONLY if after 'a' gets )evaluated it is not equal to 0 (or NULL) ) ) This is generally what people mean by "lazy evaluation". If you only mean ) that the Standard does not define the term, however, then you are correct. This is one of the many forms of lazy evaluation, but it's a much more general term. The term I've heard used for this specific form is 'short-curcuiting'. Now that we're talking about it anyway, here's a gripe I have about the logical operators in C: Why oh why is (a || b) not equivalent to (a ? a : b) [1] The same way (less useful), (a && b) could be equivalent to (a ? b : 0) AIUI, now it's (a || b) is (a ? 1 : b ? 1 : 0) and (a && b) is (a ? b ? 1 : 0 : 0) 1] Of course, a would only be evaluated once, which is the whole point of the usefulness of this operation. SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT Jan 5 '08 #8

 P: n/a On 5 Jan, 16:39, Harald van D©¦k

 P: n/a On 5 Jan, 17:12, Willem

 P: n/a Boltar wrote: ) Yes , my mistake. Should just be AND. Why not OR ? SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT Jan 5 '08 #11

 P: n/a On 5 Jan, 17:21, Willem

 P: n/a On 5 Jan, 16:38, Richard Heathfield

 P: n/a Willem wrote: ) Now that we're talking about it anyway, here's a gripe I have about the ) logical operators in C: ) ) Why oh why is (a || b) not equivalent to (a ? a : b) [1] ) The same way (less useful), (a && b) could be equivalent to (a ? b : 0) Never mind, it hit me a few minutes after I made this post: It would require the types of a and b to be compatible. SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT Jan 5 '08 #14

 P: n/a Boltar wrote: ) On 5 Jan, 17:21, Willem )) Yes , my mistake. Should just be AND. )> )Why not OR ? ) ) Yes , if the LHS value is 0xFFFFFFF or whatever theres no point ) evaluating the RHS of a bitwise OR. The RHS could have side effects. You don't want those side effects to suddenly not happen on the rare occasion that the LHS is all-bits-one or all-bits-zero. SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT Jan 5 '08 #15

 P: n/a Boltar said: On 5 Jan, 16:38, Richard Heathfield But bitwise operators are not used to establish truth or falsity. Theyare used to calculate the result of a mathematical operation. Lazyevaluation would be pointless and meaningless. Why? If theres a zero on the LHS of a bitwise AND you know the result will be zero no matter what is on the RHS so why bother evaluating the RHS? That's the kind of thing a good optimising compiler will already do. -- Richard Heathfield Email: -http://www. +rjh@ Google users: "Usenet is a strange place" - dmr 29 July 1999 Jan 5 '08 #16

 P: n/a Boltar wrote: Why does C do lazy evaluation for logical boolean operations but not bitwise ones? Ie: the following program prints "1 2" , not "1 1" under gcc main() { int a = 1; int b = 1; 0 && ++a; 0 & ++b; printf("%d %d\n",a,b); } Surely the bitwise boolean ops are just as appropriate for doing lazy evaluation with? No, they are not. An important goal of C was to generate efficient code. The operands of the logical operators &&, ||, !, and ? must usually be tested at run time for a true or false value, normally by a conditional branch. There is no extra cost to short circuit evaluation and it is a short-hand convenience to programming. The boolean operators normally map to bit-wise and, or, xor, and complement, which return a result value. In general, zero is not a special case for the operators and no zero test is needed. Performing short circuit evaluation at run time would be added code and execution time with little payoff. It would also lead to less useful results using operators with side effects. Defining a = b .& c++; /* where .& is defined as bitwise and with no evaluation of second operand when first operand is 0 */ is less useful than the current a = b & c++; for me. Compilers can and do take advantage of special values when known at compile time. a += 0; will generate no code on many compilers if a is not volatile. But if you write a += 0 * y++; the compiler must increment y, even though it is not needed for the determination of a. 0 & ++b in your example code falls into the same category. -- Thad Jan 5 '08 #17

 P: n/a In article <5P******************************@bt.com>, Richard Heathfield Furthermore, there is no concept of 'lazy evaluation' in C. Perhaps inHaskell or some other programming language but certainly not in C, notonly that, but I fail to see what lazy evaluation has to do with this.(a && b) in this expression, b is evaluated ONLY if after 'a' getsevaluated it is not equal to 0 (or NULL) >This is generally what people mean by "lazy evaluation". No, that's not what's usually meant by lazy evaluation. Lazy evaluation means delaying evaluation until the result is needed. So if you call f(a+b), a+b might not be evaluated until (and unless) the function needs the value of its argument. It's a very general idea. What's being referred to here is short-circuit evaluation. You could regard it as a very special case of lazy evaluation, in that the right operand is not evaluated until the right operand has been determined to be true. -- Richard -- :wq Jan 5 '08 #18

 P: n/a Richard Tobin said: In article <5P******************************@bt.com>, Richard Heathfield >Furthermore, there is no concept of 'lazy evaluation' in C. Perhaps inHaskell or some other programming language but certainly not in C, notonly that, but I fail to see what lazy evaluation has to do with this.(a && b) in this expression, b is evaluated ONLY if after 'a' getsevaluated it is not equal to 0 (or NULL) >>This is generally what people mean by "lazy evaluation". No, that's not what's usually meant by lazy evaluation. Yes, I accept the correction. I was of course thinking of short-circuiting. My mistake. -- Richard Heathfield Email: -http://www. +rjh@ Google users: "Usenet is a strange place" - dmr 29 July 1999 Jan 5 '08 #19

 P: n/a Boltar Now that we're talking about it anyway, here's a gripe I have about thelogical operators in C:Why oh why is (a || b) not equivalent to (a ? a : b) [1]The same way (less useful), (a && b) could be equivalent to (a ? b : 0) And why isn't there a logical XOR operator? eg: a ^^ b Logical XOR might not be required often but it is required and having to do (a && !b) || (!a && b) is hardly efficient or particularly readable. There are lots of simpler options: !a != !b is one. -- Ben. Jan 5 '08 #20

 P: n/a On Sat, 05 Jan 2008 18:00:38 +0000, Richard Heathfield Boltar said: >On 5 Jan, 16:38, Richard Heathfield >But bitwise operators are not used to establish truth or falsity. Theyare used to calculate the result of a mathematical operation. Lazyevaluation would be pointless and meaningless. Why? If theres a zero on the LHS of a bitwise AND you know the resultwill be zero no matter what is on the RHS so why bother evaluating theRHS? That's the kind of thing a good optimising compiler will already do. Even though the RHS might have side effects? Jan 5 '08 #21

 P: n/a On Sat, 05 Jan 2008 11:04:10 -0700, Thad Smith Boltar wrote: >Why does C do lazy evaluation for logical boolean operations but notbitwise ones?Ie: the following program prints "1 2" , not "1 1" under gccmain(){ int a = 1; int b = 1; 0 && ++a; 0 & ++b; printf("%d %d\n",a,b);}Surely the bitwise boolean ops are just as appropriate for doing lazyevaluation with? No, they are not.An important goal of C was to generate efficient code. The operands of thelogical operators &&, ||, !, and ? must usually be tested at run time for atrue or false value, normally by a conditional branch. There is no extracost to short circuit evaluation and it is a short-hand convenience toprogramming. This isn't really right. The point of short circuit evaluation of && and || is to suppress evaluation of the RHS when the LHS establishes the truth of falsity of the boolean expression. This is a programming convenience in code patterns like if (ptr && foo(ptr)) {...} IF we don't want to call foo when ptr is null. However if we do want to call foo regardless of whether ptr is null, then short circuit evaluation forces us to do something like tmp = foo(ptr); if (ptr && tmp) {...} It turns out that short circuit evaluation is more convenient (IMHO) and that C made the right choice. >The boolean operators normally map to bit-wise and, or, xor, andcomplement, which return a result value. In general, zero is not a specialcase for the operators and no zero test is needed. Performing shortcircuit evaluation at run time would be added code and execution time withlittle payoff.It would also lead to less useful results using operators with sideeffects. Defining a = b .& c++; /* where .& is defined as bitwise and with no evaluation of second operand when first operand is 0 */is less useful than the current a = b & c++;for me.Compilers can and do take advantage of special values when known at compiletime. a += 0; will generate no code on many compilers if a is notvolatile. But if you write a += 0 * y++;the compiler must increment y, even though it is not needed for thedetermination of a. 0 & ++b in your example code falls into the same category.--Thad Jan 5 '08 #22

 P: n/a Richard Heathfield wrote: Boltar said: >On 5 Jan, 16:38, Richard Heathfield >But bitwise operators are not used to establish truth or falsity. Theyare used to calculate the result of a mathematical operation. Lazyevaluation would be pointless and meaningless. Why? If theres a zero on the LHS of a bitwise AND you know the resultwill be zero no matter what is on the RHS so why bother evaluating theRHS? That's the kind of thing a good optimising compiler will already do. Really? Methinks, & operator always evaluate both operands, just like the | operator. -- Tor Jan 5 '08 #23

 P: n/a Boltar schrieb: On 5 Jan, 17:21, Willem Boltar wrote:) Yes , my mistake. Should just be AND.Why not OR ? Yes , if the LHS value is 0xFFFFFFF or whatever theres no point evaluating the RHS of a bitwise OR. Right. But theres no point in checking the LHS side first for a 2 in 2^32 chance of not having to do the operation. In x86 assembly this relates to 2 instructions, a CMP ..,0 + a JE .. or a CMP ..,0xFFFFFFFF + a JE .. just to save an AND or OR? A preprocessor can replace such an instruction in case of a constant, but with vars such a check is complete bullshit. > B2003 Jan 5 '08 #24

 P: n/a Consider the loops for (i = 0; i < n; ++i) *p++ = *q++ & *r++; and for (i = 0; i < n; ++i) *p++ = *r++ & *q++; Would you want both loops to have the same or different behaviour? Jan 5 '08 #25

 P: n/a Boltar wrote: Why does C do lazy evaluation for logical boolean operations but not bitwise ones? Ie: the following program prints "1 2" , not "1 1" under gcc main() { int a = 1; int b = 1; 0 && ++a; 0 & ++b; printf("%d %d\n",a,b); } Surely the bitwise boolean ops are just as appropriate for doing lazy evaluation with? In C, 32 out of 34 binary operators always evaluate both their operands. Many C coding standards prohibits side-effects on the second operand of the && and the || operators, because there are some clueless programmers, not aware of the conditional evaluation of the second operand. -- Tor Jan 5 '08 #26

 P: n/a Richard Harter said: On Sat, 05 Jan 2008 18:00:38 +0000, Richard Heathfield >Boltar said: >>On 5 Jan, 16:38, Richard Heathfield Email: -http://www. +rjh@ Google users: "Usenet is a strange place" - dmr 29 July 1999 Jan 5 '08 #27

 P: n/a Tor Rustad said: Richard Heathfield wrote: >Boltar said: >>On 5 Jan, 16:38, Richard Heathfield Email: -http://www. +rjh@ Google users: "Usenet is a strange place" - dmr 29 July 1999 Jan 5 '08 #28

 P: n/a Richard Heathfield wrote: Tor Rustad said: >Richard Heathfield wrote: >>Boltar said:On 5 Jan, 16:38, Richard Heathfield Jan 6 '08 #29

 P: n/a Tor Rustad said: Richard Heathfield wrote: >Tor Rustad said: >>Methinks, & operator always evaluate both operands, just like the |operator. I was thinking of cases such as 0 & 1, 0 & vanilla_int_object, and soon. The context was: 0 && ++a; 0 & ++b; In that context, of course, RHS evaluation is indeed required. I was guilty of not reading the thread properly. -- Richard Heathfield Email: -http://www. +rjh@ Google users: "Usenet is a strange place" - dmr 29 July 1999 Jan 6 '08 #30

 P: n/a Richard Harter wrote: On Sat, 05 Jan 2008 11:04:10 -0700, Thad Smith Boltar wrote: >>Why does C do lazy evaluation for logical boolean operations but notbitwise ones?Ie: the following program prints "1 2" , not "1 1" under gccmain(){ int a = 1; int b = 1; 0 && ++a; 0 & ++b; printf("%d %d\n",a,b);}Surely the bitwise boolean ops are just as appropriate for doing lazyevaluation with? No, they are not.An important goal of C was to generate efficient code. The operands of thelogical operators &&, ||, !, and ? must usually be tested at run time for atrue or false value, normally by a conditional branch. There is no extracost to short circuit evaluation and it is a short-hand convenience toprogramming. This isn't really right. Which statement do you consider incorrect? The point of short circuit evaluation of && and || is to suppress evaluation of the RHS when the LHS establishes the truth of falsity of the boolean expression. This is a programming convenience in code patterns like if (ptr && foo(ptr)) {...} I mentioned that it is a programming convenience. I was giving a rationale for short circuit evaluation for logical operators and not bitwise operators, saying that the implementation for logical short circuit is both useful and efficient, in contrast to implementing short circuit bitwise operators. -- Thad Jan 6 '08 #31

 P: n/a Boltar wrote: On 5 Jan, 16:38, Richard Heathfield But bitwise operators are not used to establish truth or falsity. They areused to calculate the result of a mathematical operation. Lazy evaluationwould be pointless and meaningless. Why? If theres a zero on the LHS of a bitwise AND you know the result will be zero no matter what is on the RHS so why bother evaluating the RHS? By that reasoning, a * x++ shouldn't increment x when a is 0, either. Or foo < bar() shouldn't call bar if it returns an int and foo is INT_MIN. -- Army1987 (Replace "NOSPAM" with "email") Jan 6 '08 #32

 P: n/a On Sun, 06 Jan 2008 13:30:28 +0000, Army1987 wrote: Boltar wrote: >Why? If theres a zero on the LHS of a bitwise AND you know the resultwill be zero no matter what is on the RHS so why bother evaluating theRHS? By that reasoning, a * x++ shouldn't increment x when a is 0, either. Or foo < bar() shouldn't call bar if it returns an int and foo is INT_MIN. If foo == INT_MIN, the result of foo < bar() depends on whether bar also returns INT_MIN. If foo == INT_MAX, the result doesn't depend on bar. Jan 6 '08 #33

 P: n/a On Jan 6, 3:34 pm, Harald van D©¦k int bar(void) { return 0; } int foo = INT_MAX; int main(void) { printf("%d\n", foo < -bar()); return 0; } -- -bar() might trigger undefined behavior. Jan 6 '08 #34

 P: n/a On Sun, 06 Jan 2008 07:46:21 -0800, vippstar wrote: #include int bar(void) { return 0; } int foo = INT_MAX; int main(void) { printf("%d\n", foo < -bar()); return 0; } -- -bar() might trigger undefined behavior. No, that's not allowed. -0 is always equal to plain old zero. I understand the point you're making, and it is a valid one, but you would've needed to use ~bar() as an example. How about "If the evaluation of x is defined to produce a result, then the value of INT_MAX < x does not depend on the value of x."? It also covers the case where the evaluation of x leads to a call to exit() or abort(). Jan 6 '08 #35

 P: n/a On Jan 6, 6:23 pm, Harald van D©¦k int bar(void) { return 0; } int foo = INT_MAX; int main(void) { printf("%d\n", foo < -bar()); return 0; } -- -bar() might trigger undefined behavior. No, that's not allowed. -0 is always equal to plain old zero. I understand the point you're making, and it is a valid one, but you would've needed to use ~bar() as an example. -0 is valid but i think -- not sure at all -- that -x where x is 0 might be a trap representation.. Maybe someone else knows? How about "If the evaluation of x is defined to produce a result, then the value of INT_MAX < x does not depend on the value of x."? It also covers the case where the evaluation of x leads to a call to exit() or abort(). As long as 'x' is of type int, short or signed char yes, but now I have lost your point.. Jan 6 '08 #36

 P: n/a On Sun, 06 Jan 2008 08:36:43 -0800, vippstar wrote: -0 is valid but i think -- not sure at all -- that -x where x is 0 might be a trap representation.. Maybe someone else knows? -x where x is 0 just means -0. When a is 1, and b is 2, you wouldn't expect a+b to be different from 1+2, would you? >How about "If the evaluation of x is defined to produce a result, thenthe value of INT_MAX < x does not depend on the value of x."? It alsocovers the case where the evaluation of x leads to a call to exit() orabort(). As long as 'x' is of type int, short or signed char yes, but now I have lost your point.. I corrected a message which used INT_MIN instead of INT_MAX. That's all. Jan 6 '08 #37

 P: n/a Ben Bacarisse