in reply to Re^48: Why is EO undefined? (More details!)
in thread Why is the execution order of subexpressions undefined?

Here's a little snippet from the Sather FAQ. I don't know if you'll like it, because it talks about why they eliminated undefined order of evaluation, or if you'll hate it, because they say that doing so eliminates implicit parallelization possibilities because of the presense of side-effects.
In many languages, such as C, the order of evaluation of routine arguments is undefined. In Sather, however, arguments are always evaluated left to right. This brings greater determinism across platforms to Sather code; unlike C, there is no place in the Sather specification where we resort to declaring the results of an operation to be undefined.

A frequently cited reason for not specifying an order of evaluation is to allow the compiler to choose an order of evaluation which leads to the most efficient code; for example, simple arguments can be evaluated after complicated ones to relieve register pressure. This can also be done for ordered Sather arguments in the absence of side effects.

While the order is unspecified in C, the evaluations of arguments must appear to occur in _some_ order, not interleaved in execution. (In the extreme this would allow C compilers to fork threads when evaluating arguments, a practice which would break most existing code.) Since a compiler capable of taking advantage of the parallelism made available by unordered arguments must do dependency analysis to make sure the generated instructions appear to evaluate the arguments in some order, such a compiler would of course be able to do the same dependency analysis and instruction reordering on arguments required to be observed evaluating left to right. The generated code would only be different if there were side effects in an argument evaluation which would make the order of evaluation important; and such code would clearly be in error if the argument order was unspecified.

It's really a question about what the language does with erroneous code that depends on the order of evaluation. It would be nice to detect such situations, but this is very hard. By leaving the order unspecified one allows bugs (which usually appear only when changing compilers). Sather chooses to just eliminate the possibility.

  • Comment on Re^49: Why is EO undefined? (More details!)

Replies are listed 'Best First'.
Re^50: Why is EO undefined? (More details!)
by BrowserUk (Patriarch) on Apr 18, 2005 at 21:57 UTC

    I like.

    It says everything I have been saying about the determinism of defined EO, the insecurity of undefined EO, and requirement for complicated compilers if they are to detect conflicting side-effects.

    Now, rewrite the rules of what "defined EO" means.

    Follow the traditional definition right up to the point where you end up with func1() op func2(). Traditionally with defined EO, func1() must be evaluated before func2(), but change that final step and say, because we got this far with defined EO, we are sure that everything we did to this point was done as the programmers wished it.

    So, because the programmer got exactly what he asked for to this point, and func1() and func2() are both marked as being parallelisable, we trust his judgement and we'll go ahead and run func1() and func2() in parallel. No analysis...just do it because the programmer, knowing these modified rules, gave us carte blanche to do so.

    If he didn't want that to happen, he would not have placed them either side of a non-serialising operator.


    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?
      Now I think we might be getting somewhere (well, I think. I haven't been following all the threads here. We must be rapidy approching 200+). I know I've been confused, because sometimes you talk about implicit concurrency. But your statement "If he didn't want that to happen, he would not have placed them either side of a non-serialising operator" implies we are talking about explicit concurrency.

      And that makes most of the discussion we've been having moot. (I'm sure you'll disagree, but an explicit concurrency operator is really an "undefine the evaluation order" operator for these expressions)

        but an explicit concurrency operator is really an "undefine the evaluation order" operator for these expressions

        You're right, I do disagree :)

        The token 'op' was a placeholder for any non-serialising operation That is, not and, or, &&, ||, ',' or any operator where the existing semantics would force an evaluation order.

        Therefore, it could include +, -, *, /, **, ^, &, | etc. etc. Basically, any binary operator that doesn't impose an evaluation order of it's own.

        And I can only go back to my earlier examples. In

        func1( <expression(s) rendering the argument list1> ) + func2( <expression(s) rendering the argument list2> )

        the programmer needs to know what order the arguments will be evaluated in. He needs that so that he can put his hand on his heart and swear "I know about any and all side-effects that may occur as a result of deriving those argument lists, and I am happy that, done in the order I have specified, they will do the right thing".

        At that point, if func1() and func2() have any potential for parallelism, and have been marked as such by their authors, the compiler is free to invoke them in parallel, implicitly. Ie. without any further explicit authorisation through additional syntax.

        But without the knowledge of what order those argument lists will be evaluated, it isn't possible for the programmer to put his hand on his heart and so swear.


        By the by, I would also like a non-serialising comma-equivalent operator. One that says, the expressions either side of this operator are unrelated, but can be run in parallel. This would enable:

        my( $x, $y ) = ( $db->getData() >>,<< $lwp->getdata() );

        I don't expect that syntax to be acceptable to anyone, it's just the nearest thing to anything existing I could think of off the top of my head (although it does have some merit :)

        Or maybe that would be:

        while( my $x = $db->getData() >>and<< my $y = $lwp->getData() ) { ## Use $x and $y }

        But maybe that is already covered by junctions:

        while( all( my $x = $db->getData() & my $y = $lwp->getData() ) ) { ## use $x and $y }

        Be kind of neat if the problem of processing data from multiple files or multiple sockets could be reduced to

        while( my $messageObj = read( any( @sockets ) ) ) { ## reply send $msgObj->socket, "Thanks for your message '$msgObj->text', we'll get back to yo +u." }

        Kind of remeniscent of the 4-args select loop, but without the need for bit-twiddling.


        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?
        And FWIW BrowserUk, that last post put me back in the camp of thinking you're not on crack. (But I still think you're mildly confused with some terminology, but a little more familiarity with concurrent languages will get up up to speed in no time)