in reply to Re^24: Why is the execution order of subexpressions undefined?
in thread Why is the execution order of subexpressions undefined?

BrowserUk, you're confusing most of us, I think. Defined EO implies serialisation, undefined EO implies parallelisable, and you keep stating it backwards.

Yes, separate statements means serialise. The semicolon is a "sequence" point (as per the ANSI C definition) which means that all effects and side effects must be resolved from the expression previous to the sequence point before beginning resolution of the expression following that sequence point. There are other sequence points other than the semicolon (&&, ||, ?:, and maybe even ()). But the bottom line is that anything happening between sequence points is undefined, but from one sequence point to the next is always in code order.

It's the very fact that having the EO left as undefined that the compiler says, "I trust the developer that there are no interdependancies, because I haven't told the developer how I'm going to resolve them." If you don't know that func1 is called before, after, or at the same time as func2, then you shouldn't be putting them in the same expression (between sequence points) if they have interdependancies.

However, if you know that func1 is called prior to func2, then you also know that func2 is about to be called with a value of $var that is 1 more than func1 was called with, and you may depend on this. If you depend on this behaviour, the compiler cannot parallelise func1 and func2 because you expect the op to be a sequence point where all side effects of func1 are resolved prior to func2 being called.

You just simply have the effects of defined EO backwards.

  $a = 1;
  $x = $a++ + ++$a;

[download]

Let's say we did define EO as left-to-right. That means that $a++ would evaluate prior to ++$a. Thus, the compiler must finish evaluating (and storing) $a++ completely prior to beginning evaluation of ++$a. That means that the compiler must take $a (1), put it in the register, and increment the remote memory, then take $a again (now 2), increment it (now 3) and put it back into remote memory, and add the current value to the former value, and get $x = 4, $a = 3. That is the definition of serial processing.

If, however, we leave the EO undefined, the compiler could start evaluating $a++ (e.g., load the number 1 into a register), then start evaluating ++$a (e.g., load the number 1 again into another register), continue evaluating ++$a (add one in the register, now 2), go back to evaluating $a++ (increment the value in RAM, not the register, to 2), go back to evaluating ++$a (store the new value 2 in RAM), and then finally add the two (registers) together. This would leave $a = 2, and $x = 3. Note how the compiler did evaluate this in parallel. The programmer said that there were no interdependancies, but was incorrect in that statement, and the undefined nature of the outcome is based solely on this ability of the compiler to parallelise the activity.

Replies are listed 'Best First'.
Re^26: Why is the execution order of subexpressions undefined?
by BrowserUk (Patriarch) on Apr 15, 2005 at 14:38 UTC

    In this 

    $x = $a++ + ++$a;

    [download]

    you have SUBEXPRESSION OP SUBEXPRESSION

    Whereas in this 

    $x = $a + $a;

    [download]

    You have TERM op TERM.

    With 

    $x = $a++ + ++$a;

    [download]

    The subexpressions must be resolved to terms, before the expression containing op can be evaluated.

    With EO defined, there is no abiguity about what order those sub expression must be resolved. There is no opportunity here for parallelization when resolving the subexpressions because there is no shared OP involved. Ie. Each subexpression hash it's own op (pre and post increment).

    Once both subexpressions have been resolved the parameters to + become available, the are just unnamed, intermediate, numeric values. Again, no parallelisation is possible (because you already have the operands to '+').

    Your mistake is that you are not seeing the subexpressions that defined EO would force to be resolved first and in a defined sequence.

    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]

      Ah, I think I've finally got a glimse of what BrowserUk is smoking.

      He appears to think that he can have subexpressions run in parallel by having the compiler know what the evaluation order is defined to be, and then instead of running the regular code in parallel (which can't guarantee evaluation order, obviously -- at least it is obvious to everyone but BrowserUk) but instead the compiler will analyse the code and run different code that will produce the same results as if the code were run in the defined order. (And he said it is impossible for a Perl optimizer to do some quite simple things, so I'm impressed that he thinks a Perl compiler can perform this astounding magic.)

      Or, more likely, he is just stuck in a rut about how he is thinking about this and can't see that a few of his ideas just don't make any sense.

      BrowserUk, you've dug into this argument too far. You aren't making sense and you should really take a break and come back to this with a less-tunneled view so you can hear several things that people have posted repeatedly (and either learn from them or respond to them in a way that addresses what was said -- and the latter would radically transform the field of computing, so good luck).

      - tye        

[reply]

        Thanks tye. You have seen a glimpse of where I'm heading--with caveats which I will get back to.

        The problem with this discussion is that noone (except me) seems to recall how it started. I asked the question, why is the execution order of Perl (5) undefined. And the answer is: "There is no good reason!".

        So then we move on to my suggesting why defining it-- for Perl 6. I'm not advocating any change to Perl 5--would be a good idea.

        90% of the counter arguments conflate the two things.

        We have people saying it doesn't need to be defined, because it is easy to avoid the problems that is undefinedness creates--but they completely ignore the fact that there is no good reason for it's undefinedness, so rather than needing to avoid the problems it creates (no matter how easy that is), we could define EO and those problems simply do not exist.

        Then we have people making statements about what "programmers" collectively assume about defined EO--which is really what one (or two) programmers think having thought about it for 5 minutes.

        What I am trying to suggest is radically different. I am saying that once you realise that undefined EO doesn't benefit Perl, that you can use that knowledge to think differently about what defined EO means.

        I have been thinking, and coding, and researching this for a loong time, and the muddled, assumptive counter-arguments in this thread have served (me), by confirming my position--not weakening it. That I cannot seem to pursuade people to separate the "what is", from the "what could be" and apply logic rather than rhetoric, doesn't change my position.

        I keep thinking that one person has made the transition in thinking--anonymonk2 almost got there--but then another person jumps in and re-covers old ground with the old arguments and their own set of assumptions and misunderstandings. This is not unusual when radical ideas are first proposed. Many a radical thinker has had to suffer the slings and arrows of entrenched dogma.

        Now, getting back that glimpse you had.

        the compiler will analyse the code and run different code that will produce the same results as if the code were run in the defined order

        That's where you came up short. The whole point of requiring defined EO, is that it precludes the compiler from having to perform the analysis, because it allows the programmer to completely indicate what is and is not possible--using very clean syntax I might add, so I will.

        ... so I'm impressed that he thinks a Perl compiler can perform this astounding magic.

        I do not understand that sentence. It implies that the Perl compiler (Perl 6 remember) has some limitations that "other compilers" do not have.

        The Perl 6 compiler is going to have to exhibit a great deal of intelligence in order to deal with those things that are already accepted into the language. What happens when a junction is made shared and utilised on multiple threads? What happens when a shared junction is used as a formal parameter to a multi-method subroutine? Etc. etc. There are many areas of Perl 6 syntax that will make having an undefined EO require the programmer to explicitly serialise subexpressions in order to ensure that what he requires to happen, happens.

        Defining the EO removes a burden of intelligence from the compiler, by placing the requirement upon the programmer.

        Finally, if I could pursuade anyone to accept that last premise, then once the programmer has the tool of a defined EO in his possession, he can use that tool to convey extra information to the compiler that he cannot convey without it.

        Your point appears to be that you believe that this thread has now gone on too long, so in deference, this will be my last post, but do not mistake my future silence for an acceptance that the ideas I've been trying to explain are defunct, they are not. They simply need a more receptive, less dogma entrenched forum for their exploration.

        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]
          A reply falls below the community's threshold of quality. You may see it by logging in.
      The subexpressions must be resolved to terms, before the expression containing op can be evaluated.
      Excuse me? What has parsing the construct to do with evaluating them? Do you want to suggest that in order to know in which order an expression is evaluated, people have to grok the grammar used to parse Perl?
[reply]

      You're not making any sense. Forget about TERMs - they are irrelevant. Why does it matter whether we load $a from memory before $b in $a * $b? It can't. It can only matter when we're dealing with EXPRessions (or subexpressions or subsubexpressions - these are all still expressions), including, but not limited to, function or method calls.

      In every case where defining EO will mean something to the developer, it means "serialisation" to the compiler. It's just that simple.

      Defining EO restricts the perl VM to serial behaviour, leaving it undefined allows the VM the flexibility to parallelise some expressions. That is the answer to the original question. You have almost admitted it, although you probably don't see how you did. "With EO defined, there is no abiguity about what order those sub expression must be resolved." Exactly correct. Violent agreement. With EO defined, serialisation is a requirement. The logical negation of this is not that without defined EO, serialisation is not allowed, but that without defined EO, parallelism is permitted.

      And there are a number of us who are looking forward to automatic parallelisation that is just simply possible with undefined EO, and is simply impossible with defined EO.

[reply]

In Section Seekers of Perl Wisdom