Precedence Misunderstanding

[Charles Richmond]

Consider the following program:

#include <stdio.h>
#include <stdlib.h>

int main()
{
int i = 4, j = 12, k = 41;

printf("expression is %d + %d * %d\n",k,j,i);
printf("--> value is %d\n",k + j * i);
}

When compiled and run, the output was:

expression is 41 + 12 * 4
--> value is 89

Because the multiply operator has a *higher* precedence than the
addition operator... the multiply is done first. So the result is
89, and *not* 212.


Now take the following program:

#include <stdio.h>
#include <stdlib.h>

int callthis();

int main()
{
int i = 1, j = 1, k = 0;

printf("expression is %s\n","i || j && k");
printf("--> value is %d\n",i || j && k);

printf("expression is %s\n","i || j && callthis()");
printf("--> vnext is %d\n",i || j && callthis());
}

int callthis()
{
printf("--> The function is called.\n");

return 1;
}

When compiled and run, the output was:

expression is i || j && k
--> value is 1
expression is i || j && callthis()
--> vnext is 1


The point I'm making is: The Good Book (K&R II) says that
"logical and" (&&) has a *higher* precedence that "logical or"
(||). And that same Good Book says that a series of "logical and"
and "logical or" operations will occur left to right.

And so it is... left to right evaluation. But *how* then does the
"logical and" have a *higher* precedence than "logical or"... when
this is ignored in the series of AND's and OR's???

(Yes, yes... I know about "short circuit" operators. But I
thought this was operator by operator. In other words, if in the
"i || j && callthis()", *if* the AND were done first [it's
*not*]... and if "j" were FALSE, callthis() would *not* be done.

The actual evaluation is "i || j" done first... if "i" is TRUE,
the the *entire* rest of the expression is short circuited.

Can someone explain how "&&" can have a *higher* precedence than
"||"... when the series of AND's and OR's are just going to be
done left to right???

I *thought* I understood C pretty well... guess not.

 

[Stefan Ram]

The point I'm making is: The Good Book (K&R II) says that
"logical and" (&&) has a *higher* precedence that "logical or"
(||). And that same Good Book says that a series of "logical and"
and "logical or" operations will occur left to right.

This quoted paragraph alone might have been sufficient to
make your point. I guess, the above quote means:

- a series of "logical and" operations will occur left
to right.

- a series of "logical or" operations will occur left to
right.

(I'd write »logical-and operation« and »be evaluated« instead
of »occur«.)

 

[Ben Pfaff]

Can someone explain how "&&" can have a *higher* precedence than
"||"... when the series of AND's and OR's are just going to be done
left to right???

I think there's a lot of confusion on this point because we
aren't taught about this in our math classes. That's because
side effects don't exist in math, so order of evaluation doesn't
matter. Precedence does, but that's a different issue.

Consider 2 * 3 + 4 * 5. Precedence says that this must be
treated the same as (2 * 3) + (4 * 5). But once you figure that
out, you have a choice: you can evaluate 2 * 3 first or you can
evaluate 4 * 5 first, because the order doesn't matter. No one
bothers to say that you have to evaluate left-to-right or even
that you have to evaluate right-to-left, because that would not
change the eventual result in any way.

When side effects come in, the situation changes. a() + b()
might do something completely different depending on which of a()
or b() you call first. Extending it to a() + b() * c(), then
precedence comes in. C doesn't say in what order a(), b(), and
c() are evaluated, but it does say that once they are evaluated,
you have to multiply b() by c(), not by a().

I hope that helps.

 

[Stefan Ram]

I think there's a lot of confusion on this point because we
aren't taught about this in our math classes. That's because
side effects don't exist in math, so order of evaluation doesn't
matter. Precedence does, but that's a different issue.

I was taught about associativity already in elementary school IIRC.
After all, you need to know whether 2-3-4 is (2-3)-4 or 2-(3-4).

Effects add the additional twist that, even though one knows that
»f() + g() + h()« means ( f() + g () )+ h(), that does /not/ imply
that »h()« is evaluated last in time.

 

[Ben Pfaff]

I was taught about associativity already in elementary school IIRC.
After all, you need to know whether 2-3-4 is (2-3)-4 or 2-(3-4).

That's just another aspect of precedence. The evaluation of each
function call in a()-b()-c() isn't any more strictly ordered than
a()+b()*c().

 

[Stefan Ram]

That's just another aspect of precedence.

Associativity is not an »aspect of precedence«. Precedence
and associativity are treated as two separate concerns.

»In programming languages and mathematical notation, the
associativity (or fixity) of an operator is a property
that determines how operators of the same precedence are
grouped in the absence of parentheses.«

http://en.wikipedia.org/wiki/Operator_associativity

Of course, the terms are usually not used in N1570,
because there it is all encoded in the grammar.

(Sequencing is yet another story that you should keep
separate from identifying subexpressions of an expression.)

 

[Ben Pfaff]

Associativity is not an »aspect of precedence«. Precedence
and associativity are treated as two separate concerns.

I may be misusing the term--your evidence seems good to me--but
the point that I was making remains: whether 2-3-4 is (2-3)-4 or
2-(3-4) is a separate issue from the order in which each operand
is evaluated.

 

[Ike Naar]

#include <stdio.h>
#include <stdlib.h>

int callthis();

int main()
{
int i = 1, j = 1, k = 0;

printf("expression is %s\n","i || j && k");
printf("--> value is %d\n",i || j && k);

printf("expression is %s\n","i || j && callthis()");
printf("--> vnext is %d\n",i || j && callthis());
}

int callthis()
{
printf("--> The function is called.\n");

return 1;
}

When compiled and run, the output was:

expression is i || j && k
--> value is 1
expression is i || j && callthis()
--> vnext is 1


The point I'm making is: The Good Book (K&R II) says that
"logical and" (&&) has a *higher* precedence that "logical or"
(||). And that same Good Book says that a series of "logical and"
and "logical or" operations will occur left to right.

And so it is... left to right evaluation. But *how* then does the
"logical and" have a *higher* precedence than "logical or"... when
this is ignored in the series of AND's and OR's???

(Yes, yes... I know about "short circuit" operators. But I
thought this was operator by operator. In other words, if in the
"i || j && callthis()", *if* the AND were done first [it's
*not*]... and if "j" were FALSE, callthis() would *not* be done.

The actual evaluation is "i || j" done first... if "i" is TRUE,
the the *entire* rest of the expression is short circuited.

Can someone explain how "&&" can have a *higher* precedence than
"||"... when the series of AND's and OR's are just going to be
done left to right???

I *thought* I understood C pretty well... guess not.

Operator precedence is more about defining which operands
are associated with each operator, than it is about defining
order of evaluation.
And, not only operators are evaluated, but so are operands.

In the case of, say "a() + b() * c()", operator precedence
implies that the expression is parsed as

+
a() *
b() c()

that is, the toplevel operation is "+", with operands "a()"
and the sub-expression "b() * c()".
Now, before the "+" operator can be applied, first its operands
"a()" and "b() * c()" must be evaluated. The order in which "a()" and
"b() * c()" are evaluated is unspecified, so "a()" may be evaluated
first, or "b() + c()" may be.

The evaluation of "b() * c()" consists of evaluating "b()" and
"c()", in either order, and then applying the "*" operator to the
results of evaluating "b()" and "c()".

So, in the end, many orders of evaluation are possible, e.g.

a(), b(), c(), *, +
a(), c(), b(), *, +
b(), c(), *, a(), +
c(), b(), *, a(), +

In "i || j && callthis()", operator precedence implies
that the expression is parsed as

||
i &&
j callthis()

that is, the top-level operation is "||" and its operands
are "i" and "j && callthis()".
Now the short-circuit rule for "||" says that its left operand "i"
is evaluated first, and, since the result is nonzero, the outcome
of the "||" operation is known to be 1, and the right operand
"j && callthis()" is never evaluated.

If i would have been zero, then the subexpression "j && callthis()"
would have to be evaluated before applying "||" to the result of "i"
and "j && callthis()".

And the evaluation of "j && callthis()" would consist of
evaluation of "j" first (because of the short-circuit rule
for "&&"). If "j" would be zero, the outcome of the "&&" would
be 0 and and right hand side "callthis()" would never be evaluated.
Only if "j" would be nonzero, "callthis()" would be evaluated.

 

[Ben Bacarisse]

I may be misusing the term--your evidence seems good to me--but
the point that I was making remains: whether 2-3-4 is (2-3)-4 or
2-(3-4) is a separate issue from the order in which each operand
is evaluated.

In some ways I don't think you are misusing the term, although common
usage has certainly decided that separating precedence and associativity
makes life simpler for most programming languages. Some parser
generators dispense with this distinction by allow an operator to have
two precedences -- a left precedence and a right precedence. This
allows associativity to be folded into the concept of precedence. There
are also languages where you need this concept to understand how to
parse its expressions. Perl's list operators, for example, have highly
asymmetric left and right precedence so they can't be described using
the common notions of precedence and associativity.

 

[Charles Richmond]

I think there's a lot of confusion on this point because we
aren't taught about this in our math classes. That's because
side effects don't exist in math, so order of evaluation doesn't
matter. Precedence does, but that's a different issue.

Consider 2 * 3 + 4 * 5. Precedence says that this must be
treated the same as (2 * 3) + (4 * 5). But once you figure that
out, you have a choice: you can evaluate 2 * 3 first or you can
evaluate 4 * 5 first, because the order doesn't matter. No one
bothers to say that you have to evaluate left-to-right or even
that you have to evaluate right-to-left, because that would not
change the eventual result in any way.

When side effects come in, the situation changes. a() + b()
might do something completely different depending on which of a()
or b() you call first. Extending it to a() + b() * c(), then
precedence comes in. C doesn't say in what order a(), b(), and
c() are evaluated, but it does say that once they are evaluated,
you have to multiply b() by c(), not by a().

Mr. Pfaff, I *do* understand about "side effects" with expression evaluation
in programming languages. I understand *why* short circuiting and
guaranteeing the order of execution... *can* be helpful at times.

The crux of what I do *not* understand is this:

Can someone explain how "&&" can have a *higher* precedence than
"||"... when any series of AND's and OR's are just going to be
done left to right???

For example, if you have a long series of logical AND's and OR's like this:

a && b || c || d && x && y || z

How will "&&" having a higher precedence than "||" effect this at all???
ISTM that evaluation would be the *same* if "&&" and "||" were of equal
precedence.

Create any series of AND's and OR's you want, and please show me how the
precedence of "&&'" and "||" will make any difference under the current C
standard.

Also ISTM that in the above expression, it will *not* matter if one adds
parentheses around any operator/operand pair or grouping. The result seems
to be the same. Please show me where I'm wrong.

I can *not* understand how "&&" can have a higher precedence than "||"...
when it seems to make *no* difference in *any* expression I've seen.

 

[Stefan Ram]

For example, if you have a long series of logical AND's and OR's like this:
a && b || c || d && x && y || z

I answered immediately and precisely to this point
in my first contribution to this thread

<[email protected]>

, but my answer is just being ignored.

(The OP thinks that in this case the standard prescribed

(((((( a && b )|| c )|| d )&& x )&& y )|| z )

, when it says that »that a series of "logical and"
and "logical or" operations will occur left to right«.
I immediately understood this and answered it with the
first reply at all in this thread.)

 

[Ben Pfaff]

For example, if you have a long series of logical AND's and OR's like this:

a && b || c || d && x && y || z

How will "&&" having a higher precedence than "||" effect this at
all??? ISTM that evaluation would be the *same* if "&&" and "||" were
of equal precedence.

Precedence doesn't affect the order of evaluation of the
terminals in this case but it affects the result. Your
expression is equivalent to:
(a && b) || c || (d && x && y) || z
which could have a different value from:
a && (b || c || d) && x && (y || z)
even though in each case the terminals are always evaluated
left-to-right (a fact that I hadn't noticed before) if they are
evaluated at all.

 

[Ben Bacarisse]

Can someone explain how "&&" can have a *higher* precedence than
"||"... when any series of AND's and OR's are just going to be
done left to right???

No, because it's not true. A sequence of &&s is done left to right, and
a sequence of ||s is done left to right, but when &&s and ||s are mixed
the precedence matters.

For example, if you have a long series of logical AND's and OR's like this:

a && b || c || d && x && y || z

How will "&&" having a higher precedence than "||" effect this at
all??? ISTM that evaluation would be the *same* if "&&" and "||" were
of equal precedence.
Create any series of AND's and OR's you want, and please show me how
the precedence of "&&'" and "||" will make any difference under the
current C standard.

Lets take a simple example

a || b && c

means

a || (b && c)

but if && and || had equal precedence it would mean

(a || b) && c

These two expressions are not the same -- the precedence makes a
difference.

Also ISTM that in the above expression, it will *not* matter if one
adds parentheses around any operator/operand pair or grouping. The
result seems to be the same. Please show me where I'm wrong.

It's a messy example but

a && b || c || d && x && y || z

means

((((a && b) || c) || ((d && x) && y))) || z

so it is true if z is non-zero regardless of the values of the other
variables. Add parentheses like this:

a && (b || c || d) && x && (y || z)

and your get quite another expression. For example, a, x and one of b,
c or d must also be non-zero for it to be true.

<snip>

 

[Ben Pfaff]

Can someone explain how "&&" can have a *higher* precedence than
"||"... when any series of AND's and OR's are just going to be
done left to right???

No, because it's not true. A sequence of &&s is done left to right, and
a sequence of ||s is done left to right, but when &&s and ||s are mixed
the precedence matters.
[...]

Lets take a simple example

a || b && c

means

a || (b && c)

but if && and || had equal precedence it would mean

(a || b) && c

These two expressions are not the same -- the precedence makes a
difference.

I think Charles is saying that, regardless of precedence, a is
evaluated before b and b is evaluated before c. That's correct,
I think.

 

[BartC]

The crux of what I do *not* understand is this:

Can someone explain how "&&" can have a *higher* precedence than
"||"... when any series of AND's and OR's are just going to be
done left to right???

For example, if you have a long series of logical AND's and OR's like
this:

a && b || c || d && x && y || z

How will "&&" having a higher precedence than "||" effect this at all???
ISTM that evaluation would be the *same* if "&&" and "||" were of equal
precedence.

Create any series of AND's and OR's you want, and please show me how the
precedence of "&&'" and "||" will make any difference under the current C
standard.

Your example:

( a && b || c || d && x && y || z)

might be written as follows, with parentheses added to show default
structure**. The indices I've added are arbitrary:

((a and1 b) or2 c or3 ((d and4 x) and5 y) or6 z)

Or it can be written lisp-style like this:

(or6 (or3 (or2 (and1 a b) c) (and5 (and4 d x) y)) z)

You can see that evaluation would need to be 'bottom-up', rather than
left-to-right, although they might sometimes correspond.

Also ISTM that in the above expression, it will *not* matter if one adds
parentheses around any operator/operand pair or grouping. The result
seems to be the same. Please show me where I'm wrong.

Because of short-circuit evaluation, and because the result of such an
expression is only ever going to be 0 or 1, it can be difficult to
appreciate differences between one such logical expression and another.

(** I won't use the terms evaluation order, precedence, or associativity
which are full of pit-falls.)

 

[Ben Bacarisse]

No, because it's not true. A sequence of &&s is done left to right, and
a sequence of ||s is done left to right, but when &&s and ||s are mixed
the precedence matters.

....but this could be expressed more clearly: the precedence matters, but
an operand that is further to the right is never evaluated before one to
its left.

This, by the way, is specific to the short-circuit nature of && and ||,
and of the fact that the left-hand operand is always evaluated first.
The right-hand operand may not be evaluated at all, so the notion of a
strict left-to-right evaluation is not exactly true -- the evaluation
can skip one or more operands.

<snip>

 

[Ben Bacarisse]

Can someone explain how "&&" can have a *higher* precedence than
"||"... when any series of AND's and OR's are just going to be
done left to right???

No, because it's not true. A sequence of &&s is done left to right, and
a sequence of ||s is done left to right, but when &&s and ||s are mixed
the precedence matters.
[...]

Lets take a simple example

a || b && c

means

a || (b && c)

but if && and || had equal precedence it would mean

(a || b) && c

These two expressions are not the same -- the precedence makes a
difference.

I think Charles is saying that, regardless of precedence, a is
evaluated before b and b is evaluated before c. That's correct,
I think.

Yes, it is, but he seems to think that that means either that precedence
has no effect, or that && and || must have the same precedence.

My answer should really have unpicked these three things: yes you get
left-to-right evaluation (though it can stop short, of course); yes &&
does have higher precedence than || (simply by definition of the
language); and yes the precedence makes a difference to the expression.

 

[Willem]

Ben Pfaff wrote:
)
)> For example, if you have a long series of logical AND's and OR's like this:
)>
)> a && b || c || d && x && y || z
)>
)> How will "&&" having a higher precedence than "||" effect this at
)> all??? ISTM that evaluation would be the *same* if "&&" and "||" were
)> of equal precedence.
)
) Precedence doesn't affect the order of evaluation of the
) terminals in this case but it affects the result. Your
) expression is equivalent to:
) (a && b) || c || (d && x && y) || z
) which could have a different value from:
) a && (b || c || d) && x && (y || z)
) even though in each case the terminals are always evaluated
) left-to-right (a fact that I hadn't noticed before) if they are
) evaluated at all.

Yes. But some terminals could be skipped because of short-circuiting.
And different ones could be skipped if the parentheses were different.


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

 

[Willem]

Charles Richmond wrote:
) The crux of what I do *not* understand is this:
)
) Can someone explain how "&&" can have a *higher* precedence than
) "||"... when any series of AND's and OR's are just going to be
) done left to right???

The precedence determines how the results *will be used*.
It does not determine the order in which they are evaluated.

) For example, if you have a long series of logical AND's and OR's like this:
)
) a && b || c || d && x && y || z
)
) How will "&&" having a higher precedence than "||" effect this at all???

This is, step by step, what the program will do:

/* Construct for the expression a && b || c || d && x && y || z */
int abcdxyz(int a, int b, int c, int d, int x, int y, int z)
{
if (a) {
if (b) {
return 1;
}
}
if (c) {
return 1;
}
if (d) {
if (x) {
if (y) {
return 1;
}
}
}
if (z) {
return 1;
}
return 0;
}

Now, as you can see: a, b, c, d, x, y, z are evaluated in that order.

Suppose that '&&' had higher precedence, it would become the following:

/* Construct for the expression a && b || c || d && x && y || z
* with precedences reversed */
int abcdxyz(int a, int b, int c, int d, int x, int y, int z)
{
if (!a) {
return 0;
}
if (!b) {
if (!c) {
if (!d) {
return 0;
}
}
}
if (!x) {
return 0;
}
if (!y) {
if (!z) {
return 0;
}
}
return 1;
}

As you can see, they are still evaluated in the same order, yet still they
are grouped differently.

) Create any series of AND's and OR's you want, and please show me how the
) precedence of "&&'" and "||" will make any difference under the current C
) standard.

See above.

) I can *not* understand how "&&" can have a higher precedence than "||"...
) when it seems to make *no* difference in *any* expression I've seen.

int a() { printf("a=0\n"); return 0; }
int b() { printf("b=1\n"); return 1; }
int c() { printf("c=1\n"); return 1; }
int main() {
printf("First\n");
printf("Result: %d\n", (a() && b()) || c());
printf("Second\n");
printf("Result: %d\n", a() && (b() || c()));
return 0;
}

There you go.


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

 

[Rui Maciel]

I think there's a lot of confusion on this point because we
aren't taught about this in our math classes. That's because
side effects don't exist in math, so order of evaluation doesn't
matter. Precedence does, but that's a different issue.

<snip/>

This is nonsense. What you refer as being "side effects" is nothing more
than the result of ignoring an entire subspace of an operator's domain, and
how the components of the subspace you chose to ignore can also influence
how the remaining components are mapped.


Rui Maciel