<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">No<div><br><div><div>On Feb 19, 2010, at 11:36 AM, Ioan Raicu wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">
<div bgcolor="#ffffff" text="#000000">
But doesn't the single assignment criteria prevent loops from happening
in the dependency graph?<br>
<br>
Mihael Hategan wrote:
<blockquote cite="mid:1266600438.22169.264.camel@localhost" type="cite">
<pre wrap="">On Fri, 2010-02-19 at 11:13 +0000, Ben Clifford wrote:
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">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.
</pre>
</blockquote>
<pre wrap="">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)
</pre>
</blockquote>
<pre wrap=""><!---->
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.
</pre>
<blockquote type="cite">
<pre wrap="">So I don't think deadlocks are a consequence of that.
</pre>
</blockquote>
<pre wrap=""><!---->
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.
</pre>
<blockquote type="cite">
<pre wrap="">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.
</pre>
</blockquote>
<pre wrap=""><!---->
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
<a class="moz-txt-link-abbreviated" href="mailto:Swift-devel@ci.uchicago.edu">Swift-devel@ci.uchicago.edu</a>
<a class="moz-txt-link-freetext" href="http://mail.ci.uchicago.edu/mailman/listinfo/swift-devel">http://mail.ci.uchicago.edu/mailman/listinfo/swift-devel</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
=================================================================
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: <a class="moz-txt-link-abbreviated" href="mailto:iraicu@eecs.northwestern.edu">iraicu@eecs.northwestern.edu</a>
Web: <a class="moz-txt-link-freetext" href="http://www.eecs.northwestern.edu/~iraicu/">http://www.eecs.northwestern.edu/~iraicu/</a>
<a class="moz-txt-link-freetext" href="https://wiki.cucis.eecs.northwestern.edu/">https://wiki.cucis.eecs.northwestern.edu/</a>
=================================================================
=================================================================
</pre>
</div>
_______________________________________________<br>Swift-devel mailing list<br><a href="mailto:Swift-devel@ci.uchicago.edu">Swift-devel@ci.uchicago.edu</a><br>http://mail.ci.uchicago.edu/mailman/listinfo/swift-devel<br></blockquote></div><br></div></body></html>