[Swift-devel] Problem with iterate

[Mihael Hategan]

On Thu, 2010-02-18 at 17:08 +0000, Ben Clifford wrote: 
> > I'm unsure. I have a feeling that static dealdock detection is
> > undecidable in swift. I need to think some more about that.
> 
> I think doing it statically (i.e. at compile time) is equivalent to 
> executing the code (including external apps) - I think there's probably a 
> straightforward example where something depends on an integer read from an 
> externally executed app which then influences an if statement that decides 
> which of two different arrays is being written to; or something like that.

Right. So termination is undecidable by virtue of it being a turing
complete language. What I'm unsure is whether deadlocks follow as a
consequence of that. They are a different beast.

We can probably start with simpler things. The following deadlocks with
the current swift:
a = cat(b);
b = cat(a);

So it seems that loops in the graph will create a deadlock and detecting
loops requires knowing the graph. We can probably detect the static
parts and we may be able to handle alternatives by issuing warnings of
the "branch 1 in that 'if' combined with branch 2 in that other 'if'
leads to a deadlock" sort.

Arrays may be a bit tougher.