Re^2: Why is the execution order of subexpressions undefined? (basics)

Maybe, just maybe, I've hit upon the explanation that will calrify the defined EO thing.

Your assertion is that :

If I write $x = f() + g(); and the order of evaluation is defined, let's say from left to right, then f() must be called before g().

First, let's assume that for reasons of generalisation, that the order defined is right to left. That's okay in your example because addition is communicative, so your expression will still do the right thing.

But, now let's switch to a non communicative operator: $x = f() - g();. What happens?

Nothing. Because the defined EO only pertains to the order in which the functions are called, not to the order in which the results they produce are used. The defined EO doesn't force the results to be used in reverse.

Now come back to your assertion that defined EO means that f() and g() cannot be parallelised because f() must be called before g().

Why?

Once f() and g() have returned their values, you have a simple expression: $rv1 + $rv2; and there is nothing about defined EO that prevents that from being completed.

And prior to that, f() and g() can be called in parallel, because I'm explicitly stating that with defined EO, parallelisable operations either side of a non-serialising operator can be called in parallel.

That is, I'm not just saying I think they can, I'm saying that defined EO can be defined such that it is so.

Where the defined EO comes into play is when you have a compound expression. This is, as you picked up on when you said:

Now, BrowserUk had an example closer to $x = f($i) + g(++$i); and so perhaps BrowserUk is thinking that a defined EO is important to allow the compiler to add parallelization because otherwise writing this expression is basically an error -- because what gets passed to f() and/or g() depends on the implementation. If so, then he has a point there.

the purpose of the parameters I showed in my examples. They are the simplest sub-expressions that have a side effect, which is their entire purpose for being there.

It is at the level of the compound expression, where the defined EO becomes important.

I'm going to contrive an example for the purposes of discussion. It will probably be a weak and somewhat non-sensical in it's contrivance, but I'm admitting that up front to avoid the ensuing argument about it. I'm contriving the circumstance using the simplest expressions possible to demonstrate the point, but the expressions and logic behind them act as placeholders for any similar set of circumstances that could exist.

Here I want the first value returned by $o->next given to f() and the second to g():

$x = f( $o->next ) + g( $o->next );
$y = f( $o->next ) - g( $o->next );
[download]

Here, I want the reverse:

$x =  g( $o->next ) + f( $o->next );
$y = -g( $o->next ) + f( $o->next );
[download]

Yes, I can achieve the same thing in the presence of undefined EO by doing:

my $temp1 = $o->next;
my $temp2 = $o->next;
$x = f( $temp1 ) + g( $temp2 );

$temp1 = $o->next;
$temp2 = $o->next;
$y = g( $temp1 ) - f( $temp2 );
[download]

and reversed

my $temp1 = $o->next;
my $temp2 = $o->next;
$x = f( $temp2 ) + g( $temp1 );

$temp1 = $o->next;
$temp2 = $o->next;
$y = f( $temp1 ) - g( $temp2 );
[download]

but why should I have to? Did you see how much clearer the first pair are than the second?

And did you notice that the second pair contain an error? An error that would have stood out like a sore thumb in the first pair, but that gets lost in the noise of the second.

Of course, nothing is forcing anyone to use the first form if EO is defined, it just enables it for those that wish to. There is no shotgun either way with defined EO, but without it one option is excluded--not very Perlish.

And yes, in the presence of defined EO, f() and g() can be executed in parallel--if we chose to allow that. No compiler analysis is required, the programmer is explicitly condoning it.

If that does not convince you that defined EO is a gain-something, lose-nothing proposal, then probably nothing will, but your being unconvinced will not change that it is so.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

Lingua non convalesco, consenesco et abolesco.

Rule 1 has a caveat! -- Who broke the cabal?

Comment on Re^2: Why is the execution order of subexpressions undefined? (basics) Select or Download Code

Replies are listed 'Best First'.
Re^3: Why is the execution order of subexpressions undefined? (basics) by Tanktalus (Canon) on Apr 17, 2005 at 06:23 UTC
Your definition of EO is significantly different from what I think everyone else assumed it could mean. And, I would like to make the observation that your definition of EO is counter-intuitive - at least to the majority of those who have participated in this thread. For all intents and purposes, your defined EO is pretty much undefined. Which gets called first - f or g? You're saying that you're not defining this. This is a seriously underdefined execution order, because only bits and pieces (and a very difficult bit and piece to define, as is evidenced by this thread) are defined, but not the entire expression. It's an interesting definition. I don't think there is much of a gain if only because you've left it pretty much completely undefined. (What if f or g affect $o? What order then?) We've gained so little, and so counter-intuitively, that I'm not sure it's significant enough to put forth code to implement it. Parallelism is not something we've gained - it's something we still lose. Any definition of execution order is, well, by definition, a definition of serialisation. For example, no matter what, the addition of the two values must happen prior to the assignment to the LHS. We can't add and assign in parallel. Similarly, if we must evaluate all the arguments to functions prior to calling any of them, then we are introducing a sequence point (which is quite invisible, which is why it's counter-intuitive) where we must synchronise everything before paralellising anything. Further, I'm not sure why you're only defining this for arguments to functions. Why not full subexpressions? That is, defining whether the LHS of a binary operator is evaluated before or after the RHS. Why the arbitrariness of the definition? It would be more intuitive if the whole expression was defined. It's confusing to only go half way, and to stop at some arbitrary point which doesn't seem to have any purpose to it. You may think I'm opposing you for the sake of opposing. And I'm definitely not as tactful as TimToady. But, at the very least, I hope that I'm helping to refine your idea, or at least the presentation of it. At this moment, however, I do remain unconvinced that there is an idea here that would make life better, so, at the most, I'm hoping that I convince you to see the light. ;-)	[reply]
Re^4: Why is the execution order of subexpressions undefined? (basics) by BrowserUk (Patriarch) on Apr 17, 2005 at 07:13 UTC
What if f or g affect $o? What order then? Then, as TimToady put it: you are implicitly promising that the parallel branches either A) don't have side effects, or that if they do, B) you don't think the side effects will interact, or C) the side effects are idempotent so it doesn't matter in which order they happen, or D) you just don't give a rip Or as I put it: the programmer has explicitly indicated that there are no interdependancies between func1() and func2(), or if there are any interdependancies, he knows that they will "do the right thing". If there are interdependancies between f() and g(), for example, they modify $o in some way that precludes their being parallelised, then then programmer must not put them in the same statement. `my $rv1 = f( $o->next ); my $rv2 = g( $o->next ); my $x = $rv1 + $rv2;` [download] No paralleisation is possible because they are no longer in the same expression. Further, I'm not sure why you're only defining this for arguments to functions. As stated, I have been restricting myself to the simplest possible case that demonstrates the possibility of parallelism, and the need for defined EO. The mechanism does, by implication, extend to all sub expressions within expressions. `my $x = $i + ++$i;` [download] Because `++$i` involves a unary operator, it is a subexpression. With undefined EO, the programmer cannot know what this will produce, with defined EO he can. I'm not for one moment suggesting that it is a good thing to do in practice, but it demonstrates the point. But it is not a good example for the wider discussion because there is not scope for parallelism. And in this: `$x = f( g() + h() ) * p( q() - r() );` [download] has 3 points of possible paralellism. Each of g() & h(), q() & r() and f() & p(). And with defined EO, if h() has a dependancy on r(), and must be executed first, then I can write that as: `$x = p( q() - r() ) * f( g() + h() );` [download] and know it will do the right thing. Without it, I have to write: `my $temp1 = p( q() - r() ); my $temp2 = f( g() + h() ); $x = $temp1 * $temp2;` [download] and lose the oportunity for one level of parallelism. Or as: `$temp1 = q() - r(); $temp2 = g() + h(); $x = f( $temp2 ) * p( $temp1 );` [download] Which anyway you cut it is less clear and more open to maintainance errors than the first one above. I do not consider my definition of EO incomplete--for one thing, I haven't outlined what my definition would be--but the point remains that it can be whatever is required to achieve the desired effect. The point is that subexpression must be evaluated before the expression they are a part of. Once the complex expression is reduce to a simple expression, the rules can change, if that is what is required to achieve the result. You say it is unintuative--which I take to mean that you cannot think of any other reason to oppose it--but you do not find the current Perl 5 "the compiler might do it this way or it might do it that way" intuative? And I'm definitely not as tactful as TimToady Strange, but I saw many confirmations of my position, though I agree not complete agreement, in his posts. Maybe I misread him, but much of the little he said echoed things I have been saying in this thread. For now, I admit defeat--I am not going to change your mind and nothing I have seen here has changed mine. So, I'll stop right here. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. Lingua non convalesco, consenesco et abolesco. Rule 1 has a caveat! -- Who broke the cabal?	[reply] [d/l] [select]


P is for Practical
	PerlMonks