[Swift-devel] Problem with iterate

[Mihael Hategan]

On Fri, 2010-02-19 at 15:37 -0600, Ioan Raicu wrote:
> 
> 
> Mihael Hategan wrote: 
> > On Fri, 2010-02-19 at 14:08 -0600, Ioan Raicu wrote:
> >   
> > > Yes, I think my confusion is coming from the fact that the order of
> > > statement in the source code is not preserved in the execution order
> > > (assuming there are dependencies). You are saying that the order in
> > > the source code doesn't matter in Swift. Perhaps this is what is
> > > making the analysis harder, to detect these deadlocks?
> > >     
> > 
> > Yes it does. It's also necessary because it's what achieves
> > parallelization.
> >   
> Thinking about this problem briefly, I don't think its *necessary* for
> the parallelization.

Think a bit harder.

>  I can certainly think of how to execute a DAG in parallel (as long as
> there are no dependencies), and where-ever dependencies exist, things
> are done in the right order to maintain the dependencies. I believe
> this is what gets done in Swift right now. The difference is perhaps
> how you build the DAG. If you keep the order of statements from the
> source code, you just have to make sure that order is maintained when
> adding nodes (and edges) to the DAG. 
> 
> For example:
> b = f(a)
> a = f(b)
> 
> You add the first node f_1 to the DAG, with a as input edge, and b as
> output edge. Then you process the second statement, adding another
> node f_2, adding an edge between f_1 and f_2 with dependency b, and
> create an output edge from f_2 with an edge a. The trick is to detect
> that edge a already existed, as an input to node f_1, which would
> cause a loop, which in turn should not be allowed (per the definition
> of a DAG), and an error should be raised. 

Right. Except edges in dags are traditionally the dependencies. So if
you replace "edge" with "node" and the other way around in your above
statement, we may be closer to the generally accepted terminology. And
yes, this is precisely how swift works.

And yes, the trick is to detect loops in the dag. You can do it by
actually constructing a dag or using the nice method hinted about by Ben
(i.e. seeing this as a system of inequations):
b > a
a > b
(you can see ">" as "edge from left to right" if you want).

Now you realize I hope that you've evaluated nor b nor a when you
constructed the dag. Which is where you confusion seemed to be. And if
you re-order the two statements, you get the same dag. And I hope you
also realize that the order in which things are executed in the dag has
little to do with the order in which the edge and node declarations
appear.

> 
> I don't understand why you say its necessary to achieve
> parallelization. I am sure this discussion would be much simpler in
> person in front of whiteboard, or perhaps even in a skype call. Should
> we try that?

I've already spent too much time on this. Sorry.

But I think you are on the right track towards understanding how this
works. I think you should actually try to implement a simple system
(doesn't have to have the full swift semantics) based on what you said
above and see what problems you run into.

So far from the discussion it looks like you pretty much took the same
steps that we did when we first wrote swift, so I suspect that if you
try it out yourself you will learn better why things are the way they
are.