<div dir="ltr"><div><div><div>I'm aware K supports execution loops out of order - I think the out of order execution is the "right" behavior. But it doesn't coexist with versioned variables nicely. In your example the dataflow matches the serial control flow dependencies, so there's no direct ordering conflict, and anyway, there are no versioned variables to cause problems. <br><br> If you reverse it though, then the data flow and implied serial control flow don't match. This code should work according to my understanding of Swift's current
semantics, but the implementation would have to infer that
executing the iteration for v=1000 first didn't violate any dependencies arising from sequential control flow:<br><br>
float a[];<br>
a[1000] = 10;<br>
<br>
foreach v, k in a {<br>
if (a[k] > 0.01) {<br>
a[k - 1] = f(a[k]);<br>
}<br>
}<br></div><br></div><div>If you add in a versioned variable, then the code is definitely going to deadlock because the data dependencies and control dependencies go in opposite directions:<br><br>
float a[];<br>
a[1000] = 10;<br></div><div>versioned float x = 1;<br></div><div>
<br>
foreach v, k in a {<br>
if (a[k] > x) {<br>
a[k - 1] = f(a[k]);<br></div><div> x += a[k];<br></div><div>
}<br>
}<br></div><div><br></div>There's also another problem even with ascending indices if you add in a versioned variable. In order for the k = 1 iteration to execute and the program to make
progress, it has to infer that there is no iteration for k < 1 that
would have a version of x that precedes the version of x for the k = 1
iteration. In this example it's possible to prove by induction, but in
general it's equivalent to solving the halting problem:<br><br>
float a[];<br>versioned float x = 1<br>
a[1] = 10;<br>
<br>
foreach v, k in a {<br>
if (a[k] > x) {<br>
a[k + 1] = f(a[k]);<br></div> x = x + a[k]<br><div>
}<br>
}<br><br></div><div>So to do some kind of variable versioning you need a sequential foreach loop that has semantics that are not entirely compatible with Swift's existing foreach loop. The only way I can see to make this compatible with existing Swift semantics is to automatically switch between the two foreach loops depending on whether a versioned variable is being modified in the loop. I.e. if you use a versioned variable, you asked for a sequential foreach loop and your code might deadlock.<br><br></div><div>I think having two versions of the foreach loop that are explicitly different may be a good idea with use cases, but it's not a good idea to have them be syntactically identical and switch between incompatible behaviors based on the presence or absence of a variable of a particular type. <br><br></div><div>- Tim<br></div><div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jan 22, 2015 at 1:12 AM, Mihael Hategan <span dir="ltr"><<a href="mailto:hategan@mcs.anl.gov" target="_blank">hategan@mcs.anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="">On Thu, 2015-01-22 at 00:26 -0600, Tim Armstrong wrote:<br>
> I agree that the language can pick whatever schedule with whatever degree<br>
> of parallelism as long as it satisfies the partial order defined by data<br>
> flow and there are no false control dependencies inserted that will prevent<br>
> progress.<br>
<br>
</span>Right. There would be no false dependencies. But if the user has a data<br>
dependency<br>
<br>
a[i + 1] = f(a[i])<br>
<br>
then we can't say that they shouldn't. So the issue is not what<br>
dependencies are there but whether we would allow that statement to be<br>
written as "a = f(a)". This would allow nothing that isn't already<br>
allowed.<br>
<br>
We should probably drop this though. I think we went past usefulness and<br>
I do think that a functional approach is more clear and easy to<br>
implement, it has no blanks to fill in, and is almost certainly less<br>
contentious.<br>
<br>
[...]<br>
<span class="">> in the loop body to prevent them from doing so, since otherwise the program<br>
> might fail to make progress when it should, or even deadlock if there is<br>
> some sort of recursive dependency where the array being iterated over<br>
> depends directly or indirectly on the computation in the loop body.<br>
<br>
</span>Hmm. Maybe I shouldn't point out that K allows this already and perhaps<br>
this is the missing piece in the conversation. You can write the<br>
following code:<br>
<br>
float a[];<br>
a[0] = 10;<br>
<br>
foreach v, k in a {<br>
if (a[k] > 0.01) {<br>
a[k + 1] = f(a[k]);<br>
}<br>
}<br>
<br>
It's meant as a pure dataflow replacement for iterate{}.<br>
<span class=""><font color="#888888"><br>
Mihael<br>
<br>
</font></span></blockquote></div><br></div></div></div>