We're going in circles here. You keep claiming that a compiler can parallelise an expresssion if EO is defined. Which is backwards to everyone else. You're going to need to go into more details in your explanation for anyone to buy in.

Using the func1/func2 example above, we define an order: left-to-right makes as much sense as anything else. This means that func1 is evaluated, then func2 is evaluated. That's a defined execution order. There may be others, but ltr and rtl are the only ways I can think of defining these things.

And this makes defined execution order serial.

[W]ith defined execution order, the compiler is not free to "do this is any order"

Is this an admission (finally) that defined EO prevents parallelism, and any optimisation that the compiler could elicit from such parallel computation? That is all I've been saying: defined EO == serial; undefined EO permits parallel. I think you've been grossly misinterpreting everything in this thread if you think anyone has been saying anything other than this, except you.

Why do I claim that the following statement is parallelisable (if EO is defined)?

    my $result = func1( $a ) + func2( $a++ );
[download]

The simple answer is "Because there is nothing to prevent it!".

In the absence of defined EO, the compiler is theoretically free to process that line as follows:

1. Increment $a
2. Stack an alias to $a.
3. Call func2().
4. Returning from func2() leaves it's result on the stack.
5. Stack an alias to $a.
6. Call func1().
7. Returning from func1() leaves it's result on the stack.
8. Call add().
9. The result of Add() is left on the stack.
10. Add a variable $result to the pad and initialise it with the value popped from the stack.

Or, it could do that

1. Stack an alias to $a.
2. Call func1().
3. Returning from func1() leaves it's result on the stack.
4. Increment $a
5. Stack an alias to $a.
6. Call func2
7. Returning from func2() leaves it's result on the stack.
8. Call add().
9. The result of Add() is left on the stack.
10. Add a variable $result to the pad and initialise it with the value popped from the stack.

The results will be different, even without the possibility of either function modifying their parameter.

The value of $a will be different, dependant upon the unknowable order in which the compiler executes the code.

With EO undefined, the programmer cannot indicate the required order, and so must place the calls to func1() and func2() in separate statements, and that explicitly prevents the two functions being called in parallel.

---

With defined EO, there is only one possible sequence:

1. Place an alias to $a somewhere (for func1()).
2. Increment $a.
3. Place an alias to $a somewhere (for func2()).
4. * see below.
5. Invoke an asyncronous call to func1() also passing a semaphore.
6. Invoke an asyncronous call to func2() also passing a semaphore.
7. Wait until both semaphores clear.
8. Retrieve the results from func1() and stack.
9. Retrieve the results from func2() and stack.
10. Call Add().
11. The result of Add() is left on the stack.
12. Add a variable $result to the pad and initialise it with the value popped from the stack.

*Because there are no other dependancies or ambiguities, the compiler can know that (if they are parallelisable), it only needs the results from func1() and func2() in order to call Add(), so it is free to parallelise func1() and func2().

Because of defined EO, 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".

The onus is on the programmer, and is completely within his control, and the compiler does not need to make that determination.

That is the salient point.

Without defined EO, the only control the programmer has over the order of execution is to use separate statements, but separate statements automatically precludes transparent parallelism.

With defined EO, the programmer is explicitly indicating that any two functions (methods) that are marked as being parallelisable, that appear in the same statement, as co-operands to a non-serialising operation, can be parallelised.

He is telling the compiler this by that placement. The compiler cannot make this determination without huge amounts of complex analysis, but the programmer can make that determination--IF EO is defined.

Without EO, it requires complicated extra syntax, which entirely negates the concept of transparent parallelisation.

---

You may argue that the concept of transparent parallelisation isn't usful--I'd say you where wrong, but that's a philosophical argument.

You may argue that extra syntax is the way to go--again, I will argue with you about that.

But if the concept is useful, and I strongly believe it is, then having a defined EO is an unarguable necessity.

I also happen to think that it will be seen to be a requirement for other parts of the Perl 6 syntax to work also, but that's still not completely clear.

I also think that as the supposed benefit of potentially improved efficency, through statement reordering, has never, and can never be realised, the only reason for not defining EO is a myth.

That leaves us with gaining a benefit from defining it and loosing nothing, or not defining it and not gaining something.

I do not see why people are arguing for retaining ambiguity for no gain.

---

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?

With your explanation, I finally got that by "with defined EO, that func1() and func2() can be parallelised.", you actually mean "In some cases, it's possible to parallelize even with a defined EO, and give the user a well-defined result". In no way does an undefined EO prevent parallelization, as I've shown in another node. It merely frees the compiler/interpreter/CPU from the requirement to produce reproducible results if the subexpressions contain side effects.

Your "defined execution/evaluation order" cannot protect against side effects, even if you place semaphores everywhere, because IO or other deep/unprotected sideeffects will get in the way, unless you factually reduce the whole expression evaluation to a single thread. "defined execution/evaluation order" is the promise to the user that, no matter what, subexpression A will always be evaluated before subexpression B. Which obviously prevents parallelization.

Let's assume a simple order of execution of left-to-right. Your expression evaluation then obviously needs to perform all of func1, before it ever is allowed to enter func2, because it doesn't know what side effects func1 and func2 will share (assuming that a list of the side effects of both, func1 and func2 is not available before the two are called).

Your idea that "With defined EO, the programmer is explicitly indicating that any two functions (methods) that are marked as being parallelisable, that appear in the same statement, as co-operands to a non-serialising operation, can be parallelised." does in no part rely on the defined EO. If two pieces of code are marked as being parallelisable, then the only time you will notice the difference in the result is, if they are not actually parallelisable, because then the side-effects in the undefined EO can produce differing results in two executions of the program. With a defined EO, there can never be two differing results, because the program can effectively only be executed in a single path of execution.

• Invoke an asyncronous call to func1() also passing a semaphore.
• Invoke an asyncronous call to func2() also passing a semaphore.
• Wait until both semaphores clear.

Either both functions get the same semaphore, and in effect, they run in serial. Or they don't, and the semaphore is in principle bogus. And there's no order of execution here, since you don't know in which order the functions are going to be performed.

But we've said this dozens of times already.

I am not sure why you think that a defined execution order helps, and I think the following gedankenexperiment could help you understand my point of view:

The lockstep game.

Let's play a game:

We have six houses and a set of bus lines that we can take between the houses. Our goal is to visit all houses, but we can only take the bus lines to go from one house to the next, and the bus only travels in one direction. We have an unlimited number of clones of ourselves. It is obvious that our clones must start in all houses that have no incoming bus, because otherwise they could never reach that house again by bus.

The only extra rule is, that we are not allowed to visit a house Y if there is at least one house X with a bus connection going from X to Y, and we have not yet visited X.

Now, let's consider the following two towns:

   lower town        upper town

    a -> b            A -> B
    b -> c            B -> C
    c -> d      
    d -> e              D -> E
    e -> f            E -> F
[download]

1. If we only have one clone at our disposal, how long will it take us to visit all 6 houses in lower town?
2. How long will it take us in upper town?
3. How does the number change if we have two clones at our disposal? Why?
4. Does an increased number of clones help us? Why?

Please take a minute or two to answer the above questions before continuing.

Now, let's transfer this into Execution Order:

The execution order for the expression a,b,c,d,e,f is well defined and ordered, because for any two elements of the expression, it is exactly clear which one has to happen first. For example, c has to be computed before any of d,e,f can be computed.

The execution order for the expression A,B,C,D,E,F is only partially ordered, and it's not even a half-order. There are two ordered subsets however, and for every subexpression in the sets, we can exactly tell which subexpression has to be evaluated first.

So, we can split up the uppercase expression A,B,C,D,E,F into two unrelated subexpressions A,B,C and D,E,F, and each of the two expressions is unrelated to the other and the two calculation sequences can be executed at the computers leisure. The following execution orders could be valid:

A,D,B,C,E,F
D,E,F,A,B,C

(AD),(BE),(CF) # with a parallel machine
[download]

Note that you don't even need a parallel machine - if one of the expressions is, for example, sleep 1, the other expression can still be evaluated while the first expression is sleeping, without needing a real second CPU.

The trouble with your lockstep game is that each step is dependant upon a single previous step--but most operations in computing have two operands.

With your chain of events (a->b->c->d->e->f), there is no opportunity for parallelisation, but with every two operand operation, there is such an opportunity.

The thing to remember is that we are talking about Perl 6 and Parrot. At the Parrot level, every Perl level operation becomes a method call. That means that for every non-simple expression (ie. any expression that involves anything other than directly referencable simple scalar operands), there is the opportunity to overlap the execution of the derivation of those operands.

I'll try to clarify that. In these expressions:

my $scalar = $untied_var1 <op> $untied_var2;
my $scalar = func1() <op> $untied_var;
my $scalar = $untied_var <op> func1();
[download]

There is no opportunity for parallelisation, because there is nothing to overlap.

However, in these expressions:

my $scalar = func1() <op> func2();
my $scalar = $tied_var1 <op> $tied_var2;
my $scalar = $tied_var <op> func1();
my $scalar = func1() <op> $tied_var;
my $scalar = $obj1->method() <op> $obj2->method();
# and all the other combinations
[download]

There is an opportunity for parallelisation.

The processing involved in calculating the operands to <op> could involve a db access, or network IO or File IO or just a long mathematical calculation that would benefit from using a second cpu, or a floating point calculation that could be executing within the FPU whilst the main CPU does something else.

Some of this type of paralellism is already performed by the pipelining and hyperthreading architectures, but it is very limited--by locality--to sequential steps within a given routine.

In order to extend the acceptance of the opportunites, it traditionally requires the programmer to manually perform the steps required to asynchronously invoke the overlappable routines and then perform the resyncing required to pull the results back together. This is tedious and error prone. If these steps can be automated, then the potential of the soon-to-be-ubiquitous availablity of multi-cored, multi-processing arcutectures can be more easily and reliably utilised.

Now imagine that there was some mechanism for indicating that a subroutine or method may take some time to calculate or obtain, and could benefit from being overlapped. Ignore what that mechanism would be, or under what circumstances it could be used for now.

The compiler now knows that when it encounters two such subroutines or methods as the source of operands to a single, non-serialising operation, it can make those calls asyncronously and await their completion before using the results the produce as arguments to the operation in question. The compiler writers can get the mechanism right and it will be used whenever and whereever the opportunity arises. That is transparency.

But the compiler can only do this, if the programmer can clearly indicate that there are no dependancies--and that requires that EO be defined.

---

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?

First of all, you did silently ignore my second, upper town example. I don't know why, as it fits very well with your idea of "two operands" yet does not require order of execution/evaluation to be totally defined.

But the compiler can only do this, if the programmer can clearly indicate that there are no dependancies--and that requires that EO be defined.

Bogus. If the execution order is left undefined, the programmer can still clearly indicate the order by moving out the expressions into different statements. So this is no requirement for parallelization. In fact, it actually prevents parallelization, because the compiler/interpreter/CPU (generally) cannot determine if a function call will have side effects and thus must delay all further execution until the one function call has finished and produced the result.