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

Is that because you know they'll disagree with you? Or because you've now seen the light?
  • Comment on Re^47: Why is EO undefined? (More details!)

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

    Because, if you bother to read the language definition, you'll see that everything in the language is well-defined.

    Another opportunity for the "I don't understand this so I'm going to downvote it" crowd. Another quote:

    In XXX, synchronization is done on data and typically takes the form of waiting for a variable to become instantiated. Furthermore, this happens automatically: every operation that requires determined data will suspend until this data becomes determined.

    XXX seems to be a very well thought out system, but it isn't Perl.

    I like Perl. I like most of what I see in Perl 6. I want to be able to use threads in Perl 6. Not for the sake of using threads, but because I think that any 21st centuary language will need to be able to use threads if it is to make good use of hyperthreaded and multi-core processors and distributed processing.

    But if using threads in perl is going to require messing around with horribly complex and tedious low-level syynchronisation constructs--mutexes, semaphores, etc.--then that isn't going to live up to Perl historical knack of making difficult things easy. I think I see how to make threading easy, almost transparent, within Perl.

    No, I cannot guarentee it will work, but I'm doing my best to follow the idea up as best I can.

    The concept is dataflow threading. Simply stated, that means that when a (shared) value is required, the requiring thread block until the providing threads provides it. But if the providing thread always blocks waiting for just one value, that is the same as a synchronous call--with the addition of a context switch. To make use of it, the requiring thread has to wait on two (or more) dataflows. That allows two thing to process, one of which will itself be in a wait state awaiting IO completion, whilst the other is calculating locally.

    So the basic idea, as applied to Perl, is that whenever two, non trivial values are required at a non-serialising point in the program, parallelisation can occur. Cheaply, automatically and transparently.

    Non-triviality means derived from a function or method (which could be hidden behind a tied FETCH). Non-serialising mean that both (or more) values must be required at the same point in the code. Ie, the same expression.

    But, if the two values who's derivations are being parallellised are (by definition), being derived from functions (methods, tied FETCHes), then those functions will themselves often take parameters. As is, there can be no guarentee that those parameters will be evaluated in the order the programmer specifies--because EO is undefined in many cases. That puts the programmer in the position of having to serialise the derivation of those parameters. And that defeats the possibility of parallelising the functions to which those parameters will be passed, or requires elaborate additional code.

    This is the point I arrived at when I asked the question in the OP. Why is EO undefined, the answer is "No good reason"-and the rest is history.


    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?
      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.

        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?