[Swift-devel] Problem with iterate

[Ioan Raicu]

But doesn't the single assignment criteria prevent loops from happening 
in the dependency graph?

Mihael Hategan wrote:
> On Fri, 2010-02-19 at 11:13 +0000, Ben Clifford wrote:
>   
>>> 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.
>>>       
>> Turing complete languages don't deadlock in general.
>>
>> (yes, concurrent programs do, but regard swift as a serial programming 
>> language, not as a concurrent one; and regard concurrent execution as 
>> 'merely' an execution optimisation)
>>     
>
> Swift semantics can be executed by a single thread without the
> involvement of any concurrency as you point out. It would still lead to
> non-termination due to loops in the dependency graph.
>
>   
>> So I don't think deadlocks are a consequence of that.
>>
>>     
>
> I wasn't asking whether deadlocks are a strict consequence of it being
> turing complete. We can clearly have deadlocks with much simpler classes
> of programs (a = f(b), b = f(a)).
>
> What I was wondering is whether turing completeness implies
> undecidability for deadlocks in the swift semantics.
>
>   
>> But I do think that probably finding deadlocks given the language features 
>> of SwiftScript is undecideable (not as a consequence of turing 
>> completeness, but because of our choice of language features); and on a 
>> more practical note, requires knowledge of the output of app blocks.
>>
>>     
>
> Swift is turing complete, so any algorithm that can be written in java
> can be written in swift.
>
> Say the deadlock finding function is D(program) returning true if
> program deadlocks, false otherwise.
>
> P(program) {
>   if (D(program)) {
>     return;
>   }
>   else {
>     a = b + 1;
>     b = a + 1;
>   }
> }
>
> P(P):
> D(P) = false -> P deadlocks
> D(P) = true -> P returns
>
> It's the textbook proof and does not involve apps or arrays.
>
> _______________________________________________
> Swift-devel mailing list
> Swift-devel at ci.uchicago.edu
> http://mail.ci.uchicago.edu/mailman/listinfo/swift-devel
>
>   

-- 
=================================================================
Ioan Raicu, Ph.D.
NSF/CRA Computing Innovation Fellow
=================================================================
Center for Ultra-scale Computing and Information Security (CUCIS)
Department of Electrical Engineering and Computer Science
Northwestern University
2145 Sheridan Rd, Tech M384 
Evanston, IL 60208-3118
=================================================================
Cel:   1-847-722-0876
Tel:   1-847-491-8163
Email: iraicu at eecs.northwestern.edu
Web:   http://www.eecs.northwestern.edu/~iraicu/
       https://wiki.cucis.eecs.northwestern.edu/
=================================================================
=================================================================


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/swift-devel/attachments/20100219/b71b798e/attachment.html>