<div dir="ltr"><div><div><div><div>Agreed, with some of these scripts there are a few questions:<br><br></div>* In what scenarios are there a consistent set of values that could be assigned to data structures?<br></div><div>* In what scenarios does the language specification guarantee that the program makes progress and those values are actually assigned? <br></div><div>* In what scenarios does the implementation actually assign the values?<br><br></div><div>The last two are kind of blurred in Swift since it's not precisely specified.<br><br></div><div>E.g. this script is not sensible because there's no consistent value for the size of the array.<br><br></div><div>int A[];<br></div><div>if (size(A) == 0) {<br></div><div>  A[0] = 1;<br></div><div>}<br><br></div><div>This script could reasonably have size(A) == 1 but I don't think it's reasonable to guarantee progress.<br></div><div><div>int A[];<br></div><div>if (size(A) == 1) {<br></div><div>  A[0] = 1;<br></div>}<br><br></div><div>This script could reasonably have size(A) == 1, and it might be reasonable to guarantee progress, since you could have some system where "intent" to assign the subscript is registered before the subscript is assigned.  I.e. it goes from EMPTY -> WILL_BE_FULL -> FULL.<br><br></div><div>int A[];<br></div><div>A[0] = size(A);<br><br></div><div>Another example might be<br><br></div><div>int A[];<br></div><div>if (contains(A, 0)) {<br></div><div>  A[1] = x;<br></div><div>}<br><br></div><div>This example could make progress if the language was smart enough to infer that A[0] wasn't assigned in the conditional.<br></div><div><br></div>I think to better pin down the specification/implementation we probably need some kind of effect system that models more precisely which bits of code have what effect on the data structures  - <a href="http://en.wikipedia.org/wiki/Effect_system">http://en.wikipedia.org/wiki/Effect_system</a><br><br></div>We have a prototypical effect system with the write reference counting but you can have more granular ones where you track which parts of the array might be modified, etc.<br><br></div>- Tim<br></div><div class="gmail_extra"><br><div class="gmail_quote">On 21 March 2015 at 14:34, 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">One more comment.<br>
<br>
This is not a deadlock that comes from a faulty implementation, so<br>
better software engineering won't fix it.<br>
<br>
This is an algorithmic issue in that the language allows more<br>
flexibility that the algorithms implementing it can analyze to determine<br>
when something that is theoretically deadlock-free would in practice be<br>
deadlock-free. So there are corner cases where the implementation fails<br>
not because of something that was missed, but because I don't quite know<br>
how to do it better.<br>
<span class="HOEnZb"><font color="#888888"><br>
Mihael<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
On Sat, 2015-03-21 at 14:<a href="tel:16%20-0500" value="+61160500">16 -0500</a>, Ketan Maheshwari wrote:<br>
> Thanks Mihael, that clarifies it.<br>
><br>
> Tim, I was thinking from the point of view of avoiding deadlocks. I<br>
> understand the semantics would remain same. I was thinking a self contained<br>
> array/struct in terms of state management (may be it is called actor based<br>
> impl, not sure) would be more robust in terms of avoiding deadlocks.<br>
><br>
> --<br>
> Ketan<br>
><br>
> On Sat, Mar 21, 2015 at 12:28 PM, Hategan-Marandiuc, Philip M. <<br>
> <a href="mailto:hategan@mcs.anl.gov">hategan@mcs.anl.gov</a>> wrote:<br>
><br>
> > On Sat, 2015-03-21 at 10:38 -0500, Ketan Maheshwari wrote:<br>
> > > Hi Tim,<br>
> > ><br>
> > > Thanks for the clarification and code snippet. To clarify, in my<br>
> > > understanding, the implementation is 'extrinsic'.<br>
> > ><br>
> > > To be intrinsic, I imagined the array is implemented as an object which<br>
> > has<br>
> > > a function that monitors and controls its write-once property and gets<br>
> > > invoked every time anything is written to any element of the array.<br>
> ><br>
> > The array is implemented as you describe above. I'm not really sure what<br>
> > extrinsic would be.<br>
> ><br>
> > Calls to an object's methods aren't automatically synchronized or<br>
> > atomic, so I don't think that assumption in your earlier email is<br>
> > correct.<br>
> ><br>
> > Even if they were, having this particular method atomic does not<br>
> > guarantee that there would be no deadlocks. A user can write a[0] =<br>
> > f(a[1]); a[1] = f(a[0]);<br>
> ><br>
> > Mihael<br>
> ><br>
> ><br>
<br>
<br>
</div></div></blockquote></div><br></div>