Order of evaluation of expressions

[Anno Siegel]

Anno Siegel ([email protected]) wrote on MMMDCLVI
September MCMXCIII in <URL:!! > In article <[email protected]>,
!! > >Where is its order of evaluation documented? Where in the documentation
!! > >does it say that:
!! >
!! > Yes, that's what I would like to know.
!! > Or, if it doesn't say that, I would like to know that it doesn't.
!! >
!! > Does anyone have any actual facts?
!! >
!! > I wasn't able to find anything about it in the manuals, but the
!! > manuals are pretty badly organized on basic matters like this, so I'm
!! > not sure I was looking in the right places.
!!
!! Like you, I was never able to find a general commitment in the docs.
!! While Perl documentation is huge, and a moving target, I think it's
!! safe to say that it is silent about the point. I mean, *someone*
!! would have found it by now
!!
!! Only some (few) operators are described individually as having left-right
!! evaluation order. Some that come to mind are the short-circuiting boolean
!! operators, the list- and comma operators (both ","), and (I think)
!! assignment ("="), though I'm not entirely sure of the latter.

Where in the documentation do you read that about comma in list context?
Perlop says:

Comma Operator

Binary "," is the comma operator. In scalar context it
evaluates its left argument, throws that value away, then
evaluates its right argument and returns that value. This
is just like C's comma operator.

In list context, it's just the list argument separator,
and inserts both its arguments into the list.

which is explicite for the scalar case, but doesn't say anything about
evaluation order in list context.

Hmm... Your quote above is what I had in mind, but it doesn't say what
I thought it says about the comma as list separator.

Looking for other evidence, I found (in the Camel, p. 109)

Once a list operator starts chewing up comma-separated arguments,
the only things that will stop it are tokens...

which seems to imply a left-to-right progress, but that's about parsing,
not evaluation order. Also, the part has been reworded in the current
perldoc to avoid exactly the left-to-right suggestion. It now talks of
"all comma-separated expressions found there (the right side of a list
operator)".

Elsewhere in the same manual page,
it is written:

In the absence of parentheses, the precedence of list
operators such as "print", "sort", or "chmod" is either
very high or very low depending on whether you are looking
at the left side or the right side of the operator. For
example, in

@ary = (1, 3, sort 4, 2);
print @ary; # prints 1324

the commas on the right of the sort are evaluated before
the sort, but the commas on the left are evaluated after.

which suggest that if there's an evaluation order, it's from right
to left!

I don't understand the argument in this bit of documentation. It would
print "1234", no matter in which order the three list elements are evaluated.

But I can't be bothered now. I must mourn for my lost belief in left-to-
right evaluation of (argument-)lists.

Anno

 

[Bob Walton]

Like you, I was never able to find a general commitment in the docs.
While Perl documentation is huge, and a moving target, I think it's
safe to say that it is silent about the point. I mean, *someone*
would have found it by now

Hmmmmm...doesn't the "synopsis" table at the beginning of perlop define
operator precedence and evaluation order rather nicely and completely?
It appears to describe the observed behaviors of the operators, and
doesn't seem to contain any errors or omissions. That is what I refer
to when I have precedence or evaluation order issues.


....

 

[Sam Holden]

Hmmmmm...doesn't the "synopsis" table at the beginning of perlop define
operator precedence and evaluation order rather nicely and completely?
It appears to describe the observed behaviors of the operators, and
doesn't seem to contain any errors or omissions. That is what I refer
to when I have precedence or evaluation order issues.

No. It defines associativity and precendence. It does not mention
order of evaluation.

 

[David Combs]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
SNIP

- From Harbison & Steele, 4ed, p 227:

<blockquote>
To control the order of evaluation, the programmer can
use assignments to temporary variables. However, a good
optimizing compiler might even rearrange computations
such as this:

int temp1, temp2;
...
/* Compute q=(a+b)+(c+d), exactly that way. */
temp1 = a+b;
temp2 = c+d;
q = temp1 + temp2;


Once again, in a language such as C in which order of evaluation is not
defined, parentheses do *not* affect order of evaluation! They affect
precedence only.

From the zero-indentation of those last three lines,
I assume that it's *you* that's saying it, not Steele (or Harbison).

Your statement, that in C the parens do not force the
order of calculation to follow the paren's order and nesting,
that's so contrary to everything I've ever read about C
or any other language -- that I'm asking you (or someone)
to please say a bit more about it.

I mean, is that claim in the language-definition?

Or just in some (weird) compiler, but not in (many) others?

Or might it be an option *to* some compiler?

Or have I just been reading incorrectly, for years,
every ref I've seen to C (and other languages too, perhaps)?

*Very* puzzled (that I'm the first to follow-up on this post).

THANKS!

(and if I'm wrong, please accept, in advance, my apologies.)

David

 

[David Combs]

Earlier, I replied to an article in this thread
that I believed said that even with parentheses,
in C the compiler could legally rearrange even
that -- implied with that is that of course
the *algebraic* result came out the same.

(I sure hope it included the word "parentheses",
because that's what I based my unbelieving reply on.)

Anyway, woe to the fledgling numerical analyst
who codes:

z = a + b + c + d + e + f

, where, in alphebetical order (a-f) the
values are:

..00000000333

(same for b, c, d, and e)

3.0000000000

, where the size of the mantissa in the floating-point
word makes a difference, ie compared with it
being *calculated* in *this* order:

z = a + b + f + c + d + e

Worrying ahead of time about optimizers changing
the order on you, you'd have to write it, maybe,
like this:

z = (a + (b + (c + (d + (e + (f))))))

, at least in the case where, suppose, a is smallest (eg .00000001),
b is next smallest (eg .0000006), and so on.

If the compiler could freely screw *this* around, even
with the parens -- horrors.


(Now I'm hoping that I did misread that post!)

David

 

[David Combs]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Parentheses don't control order of evaluation. Associativity is more
related to precedence than to order of evaluation.

THERE IT IS AGAIN, THAT STATEMENT! (this time not referring to C, though)

If true, I guess that in perl you cannot add up wildly-differently-sized
reals (er, numbers) (where you know which are big and which are small).

What, have to write separate assignment statements, each one
growing by the next one of a, b, c, d, etc, being thus forced
to recode the only *intuitively* numerical-analysisly-correct:

z = (a + (b + (c + (d + (e + (f))))))


David

 

[Sam Holden]

[snip order or evaluation and precendence being different]

THERE IT IS AGAIN, THAT STATEMENT! (this time not referring to C, though)

If true, I guess that in perl you cannot add up wildly-differently-sized
reals (er, numbers) (where you know which are big and which are small).

What, have to write separate assignment statements, each one
growing by the next one of a, b, c, d, etc, being thus forced
to recode the only *intuitively* numerical-analysisly-correct:

z = (a + (b + (c + (d + (e + (f))))))

Associativity and prededence have almost *nothing* to do with order of
evaluation. The order of evaluation in that example is irrelevant (assuming
those letters represent single numeric values.

Order of evaluation comes in, when you do something like:

z = (a() + ((b() + (c() + (d() + (e() + (f())))))))

The result will be as expected, in that e() + f() will be calculated, and then
d() + <prior result> and so on and so on.

Order of evaluation defined the order in which the functions a(), b(), .. f()
will be called.

They could be called as they are needed, in which case e() and f() will be
called first, then d(), then c(), then b(), then a(). Or they all be called
before the calculation begins arbitrary order. Or some micture of the two.

Order of evaluation only matters when those function have side effect, or
when when things like a++ are used, which also have side effects.

So in the perl example from above with some modification to make the
side effects of the shift function matter:

*a = *b = *c = *c; #make the side effects matter...
@a = qw/a b c d/;
$first = (shift(@a) . (shift(@b) . (shift(@c) . shift(@d))));

@a = qw/a b c d/;
$second = shift(@c) . shift(@d);
$second = shift(@b) . $second;
$second = shift(@a) . $second;
print "first: $first; second: $second\n";

Both $first and $second use the same associativity and precedence. However,
they have different order of evaluations.

From the output I get perl is evaluating the shift()s from left to right,
even though the parenthesis mean it is calculating the result from right
to left.

The calculation will be done in the order indicated by the precendence
and parenthesis. However, the evaluation of the individual terms is done
in a different (possibly arbitrary or random) order. The evaluation of
individual terms can *not* affect the result, unless there are
*side effects*.

 

[Sam Holden]

So in the perl example from above with some modification to make the

^^^^^^^^^^^^^^^^^^^^^^^

Which I trimmed and hence isn't there...

*a = *b = *c = *c; #make the side effects matter...

^^
Should be *d :
*a = *b = *c = *d;

Which I did when I tested the code, but failed to copy the modified code
back to my posting.

 

[Eric J. Roode]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

(e-mail address removed) (David Combs) wrote in @reader2.panix.com:

From the zero-indentation of those last three lines,
I assume that it's *you* that's saying it, not Steele (or Harbison).

Yes, that was me.

Your statement, that in C the parens do not force the
order of calculation to follow the paren's order and nesting,
that's so contrary to everything I've ever read about C
or any other language -- that I'm asking you (or someone)
to please say a bit more about it.

Sure.

I think the confusion here is that many people are using the fact that
parentheses *group* expressions to mean that the expressions must be
evaluated in some particular order.

Let's take a simple example, again in C:

a = b + c * d;

Let's further suppose that before this statement, a is 1, b is 2, c is 3,
and d is 4.

Someone who didn't know about precedence might think that the result
would be an assignment of 20 to a (b + c is 2 + 3 which is 5, multiplied
by 4 is 20). But of course multiplication has a higher precedence, so
the actual result is an assignment of 14 to a (c * d is 3 * 4 which is
12, added to 2 is 14).

Now it is clear that the multiplication must happen first, before the
addition. This is because of precedence (and associativity, although
that does not enter into this particular example). Right. Also, if you
use parentheses to regroup the expression:

a = (b + c) * d;

then it is now clear that the addition must happen first, before the
addition.

This is the source of the confusion, and why you think that parentheses
control order of evaluation. They do not. They override (or refine,
depending on how you want to look at it) the precedence of operations,
which does have some effect on the order in which the operators are
evaluated.

However: what is explicitly NOT guaranteed is the order of evaluation of
the expressions a, b, c, d. In the above examples they are simple
variables. Nothing about the C standard, nor 30 years of C's existence,
dictates anything about the order in which those variables are fetched
from memory.

So what?

Well, perhaps those variables are declared volatile, and map to I/O
devices. Which value gets fetched first could have a drastic effect on
the result of the expression. (Think of tied variables in Perl). Or to
take a more common example, let's change the expression slightly to:

a = b() + c() * d();

Now, as we have seen before, the result of the function call c() is first
multiplied by the result of the function call d(), and that product is
then added to the result of the function call b(). BUT: There is no --
absolutely NO -- guarantee or standard or rule as to which function gets
called first, second, or third. Perhaps the compiler looks at the
expression and sees that three calls are needed, and invokes b(), then
c(), then d(), then multiplies the (stored) results of c() and d(), then
adds the (stored) result of b(). Perhaps it invokes the functions in a
different order.

If the functions have side effects, and especially if they have side
effects that affect each other (note grammatically correct usage of
"affect" and "effect"!), then the results are, as explicitly stated by
the ANSI and ISO C standards, *undefined*.

Much has been made of this in the C newsgroups; see the comp.lang.c FAQ
entry about the expression "i = i++".

Now, how does this relate to Perl?

I had been under the impression that Perl's order of evaluation was well-
defined, but that impression seems to have been incorrect. As far as I
can tell, there is no defined O of E in Perl, so the same caveats above
seem to apply to the Perl language.

But I'm not sure.

- --
Eric
$_ = reverse sort $ /. r , qw p ekca lre uJ reh
ts p , map $ _. $ " , qw e p h tona e and print

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>

iQA/AwUBP1qiUmPeouIeTNHoEQJy/ACgqu3wokJBFG1DXONvu+VToAavHaoAnA1q
nxf14p5AFoT9Sob4UciQyN06
=1I6d
-----END PGP SIGNATURE-----

 

[Ilya Zakharevich]

[A complimentary Cc of this posting was sent to
Eric J. Roode

Parentheses don't control order of evaluation. Associativity is more
related to precedence than to order of evaluation.

IIRC, C compiler would not rearrage floating point expressions using
associativity/distributivity. However, it may rearrange integer
expressions (since for integer types the associativity/distributivity
hold); or rearrange things due to commutativity.

Perl lacking any optimization lieves it out of question completely...

Hope this helps,
Ilya

 

[David Combs]

What I believe to be true is that when dealing
with *reals*, addition doesn't necessarily
commute, ie a + b doesn't necessairly equal b + a,
because of the limited precision of reals.

So, suppose you want to sum a bunch of reals, maybe 10% of them
"big", and 90% tiny, such that if you add a big and a tiny,
the tiny add-on never shows up, because it "falls off the end"
of the number of bits allocated for the characteristic and
mantessa (these terms might be incorrect, but I simply
mean the two numerical parts a real is represented by in
the computer (hardware) you are using).

So it's like you never added-on the tiny number, as far
as the result you get.

However, suppose you had *lots* of those tiny numbers,
and the result of adding *those* up gives you a result
several orders of magnitude larger than the typical
single tiny one.

Now, the calculation order makes all the difference!

If you add up the big numbers before you start adding on to
the thus-far sum the the tiny ones, no matter how many
gillions of them you add in (one by one), the sum never
changes, not even by one bit.

However, if you add them up smallest first, then
the tiny ones *do* get counted -- well, their *sum*
does, assuming that that sum has gotten to be large enough
as to not be shoved off the end by the following large
numbers.



Does what I'm trying to say come across at all?


Thanks,

David

 

[Eric J. Roode]

(e-mail address removed) (David Combs) wrote in @reader2.panix.com:

What I believe to be true is that when dealing
with *reals*, addition doesn't necessarily
commute, ie a + b doesn't necessairly equal b + a,
because of the limited precision of reals.

Offhand, I can't think of an example where this would be true. Can you
give an example?

 

[David Combs]

(e-mail address removed) (David Combs) wrote in @reader2.panix.com:


Offhand, I can't think of an example where this would be true. Can you
give an example?

Nope -- Ilya corrected "commute" to "associate".

d.

 

[David Combs]

[snip order or evaluation and precendence being different]

THERE IT IS AGAIN, THAT STATEMENT! (this time not referring to C, though)

If true, I guess that in perl you cannot add up wildly-differently-sized
reals (er, numbers) (where you know which are big and which are small).

What, have to write separate assignment statements, each one
growing by the next one of a, b, c, d, etc, being thus forced
to recode the only *intuitively* numerical-analysisly-correct:

z = (a + (b + (c + (d + (e + (f))))))

Associativity and prededence have almost *nothing* to do with order of
evaluation. The order of evaluation in that example is irrelevant (assuming
those letters represent single numeric values.

Order of evaluation comes in, when you do something like:

z = (a() + ((b() + (c() + (d() + (e() + (f())))))))

The result will be as expected, in that e() + f() will be calculated, and then
d() + <prior result> and so on and so on.

Order of evaluation defined the order in which the functions a(), b(), .. f()
will be called.

They could be called as they are needed, in which case e() and f() will be
called first, then d(), then c(), then b(), then a(). Or they all be called
before the calculation begins arbitrary order. Or some micture of the two.

Order of evaluation only matters when those function have side effect, or
when when things like a++ are used, which also have side effects.

So in the perl example from above with some modification to make the
side effects of the shift function matter:

*a = *b = *c = *c; #make the side effects matter...
@a = qw/a b c d/;
$first = (shift(@a) . (shift(@b) . (shift(@c) . shift(@d))));

@a = qw/a b c d/;
$second = shift(@c) . shift(@d);
$second = shift(@b) . $second;
$second = shift(@a) . $second;
print "first: $first; second: $second\n";

Both $first and $second use the same associativity and precedence. However,
they have different order of evaluations.

From the output I get perl is evaluating the shift()s from left to right,
even though the parenthesis mean it is calculating the result from right
to left.

The calculation will be done in the order indicated by the precendence
and parenthesis. However, the evaluation of the individual terms is done
in a different (possibly arbitrary or random) order. The evaluation of
individual terms can *not* affect the result, unless there are
*side effects*.

So few understand what I (probably badly) said, although
Ilya did. It's to do with the limited precision of
reals, on computers.

Perhaps Ilya's post makes everything clear.

David

 

[Ilya Zakharevich]

[A complimentary Cc of this posting was sent to
David Combs

So few understand what I (probably badly) said,

The famous example is calculate sum of 1/n in opposite orders, once
from large values to small ones, the second time from small values to
large ones:

perl -wle "$s=0; $s += 1/$_ for 1..1e7; print $s"
16.6953113658567
perl -wle "$s=0; $s += 1/(10000001 - $_) for 1..1e7; print $s"
16.6953113658599

Doing calculations with precision of 77 digits (with gp):

? \p75
realprecision = 77 significant digits (75 digits displayed)
? sum(X=1,10000000,1./X)
%2 = 16.6953113658598518153991189395404518842498697523730804627851359543562876569

As you can see, the second way gives a practically precise value
(doing printf '%.20f' gives 16.69531136585989017360, so the result is
100x times more precise).

The idea is that when you add a small number to a large one, very few
digits of the small number matter (you can think that the small number
is first "denormalized" to the magnitude of the large one, with binary
digits "out of range" thrown away); this does not matter if you do
this addition once, but if you increment by a small number millions of
times, these rounding errors accumulate.

In the second way of addition when you calculate $s += $a with a small
$a (i.e., a large 10000001 - $_), $s is much smaller than in the first
way (check it with a pencil and a piece of paper for the first several
terms). In consequence, the errors due to rounding $a when
denormalizing to the size of $s are much smaller.

Hope this helps,
Ilya