<div dir="ltr"><div><div>I'm assuming that the size of a dense array would be specified when its initialized.  Then a dense array of size n behaves the same as n individual variables - there's no reason you have to assign them in order, or iterate over them in order unless that's what you actually want/need to do.  I agree that trying to have dense arrays that automatically expand in a parallel language is a bad idea.<br><br>I think it's really worth considering, because for a lot of standard library functions, bad or confusing things will happen if arguments are sparse arrays.  Of course we can document all of these functions to warn users about doing that, but that requires them to a) actually read the docs b) understand the distinction c) remember this when they're writing code and d) be able to trace weird deadlocks or error messages back to the original cause when they make an inadvertent mistake.  I don't mean this as an insult to users - I could see myself doing all of those things.  It seems very suboptimal.<br><br></div>This is really a separate discussion that doesn't affect the standard library, but I think the updateable idea, at least in the form that was proposed on the phone call, is flawed and actually is equivalent to changing Swift from a language with parallel semantics to a language with sequential semantics that we're trying to auto-parallelise.  I don't think we want to try to solve the autoparallelisation problem. It's easy to autoparallelise trivial examples but as soon as a programmer uses something exotic like an if statement (or an if statement inside a loop, or many more possibilities) it becomes much harder.  I can provide examples that will break any specific approach if needed.  For example, the "versioned" variables idea doesn't work for this code:<br><br></div><div>versioned int x = 1;<br><br></div><div>if (...) {<br></div><div>  x = 2;<br></div><div>}<br></div><div><br></div><div>trace(x);<br><br></div><div>Does x at the bottom refer to version 0 of the variable or version 1 of the variable?  You can't determine that statically.  You might say that you could define the semantics so that the version x it's referring to depends on which branch is taken at runtime.  But then you've reinvented sequential control flow and all that entails.  Once you get loops involved it is much worse too - it's probably not that hard to come up with an extension that works ok for this specific example, but adding loops to the equation breaks it further.<br><br></div><div>- Tim<br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jan 21, 2015 at 1:20 PM, 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">I think this is a general problem with Swift: the inability to have<br>
accumulator variables. It leads to the necessity to use recursion, but<br>
that isn't in itself enough because of the issue with tail(array) that<br>
you mention. So iterators seem like the right choice there.<br>
<br>
You mentioned non-sparse arrays. The only problem with algorithms based<br>
on dense arrays is that they might not be very efficient in swift since<br>
elements are not necessarily generated in order. It may just be that<br>
a[0] will make it into the array last due to parallelism.<br>
<br>
So I think updateables > iterators > dense arrays > tail > nothing.<br>
<br>
The question is whether we would design the standard library differently<br>
if we had either of updateables or iterators vs. what we have right now<br>
(nothing) and whether the differences would be significant enough for us<br>
to suspend the standard library discussion until we have these features.<br>
<br>
Mihael<br>
<span class=""><br>
On Wed, 2015-01-21 at 09:14 -0600, Tim Armstrong wrote:<br>
> I think the ideal scenario might be if we could have these in the standard<br>
> library, but implemented in Swift.<br>
><br>
> I tried tried to write Swift code for the min/max problem and it's really<br>
> revealing some weird interactions/limitations around the sparse arrays and<br>
> iteration constructs provided.<br>
><br>
> The thing is that there's no straightforward way to iterate in order over<br>
> the set of keys in an array, passing a variable from one iteration to the<br>
> next.  My thought process was:<br>
><br>
</span>>    1. Iterate over array with foreach -> doesn't work, since we can't pass<br>
<span class="">>    the max from one iteration to the next<br>
</span>>    2. Sequentially iterate over 0..size(A)-1 with for loop -> doesn't work<br>
<span class="">>    since keys may be sparse or not start at 0<br>
</span>>    3. Fetch the list of keys and iterate over them with foreach -> doesn't<br>
<span class="">>    work, since foreach doesn't let us pass max from one iteration to the next<br>
</span>>    4. Fetch the list of keys, and since we can assume that they're dense,<br>
<span class="">>    iterate over 0..size(A) -1 with a for loop, lookup A[keys[i]], and update<br>
>    the max based on that.<br>
><br>
> So there is a solution, but it's really ugly - I don't think we should have<br>
> to create a copy of the array's keys and do a double indirection just to<br>
> calculate min/max.  It also feels a little clunky that the eventual<br>
> solution depends on implicit contracts about whether an array's keys are<br>
> dense or not.<br>
><br>
> We'd have to assume that most users would give up after #1 or #2.  Also<br>
> Swift/K doesn't support for loops, so you have to resort to using arrays.<br>
> It's also error prone since many users will neglect to consider that there<br>
> may be gaps in the array's key space.<br>
><br>
> I think there's an issue that there is no direct way to get the first item<br>
> in an array, and no direct way to get the successor to an item in the<br>
> array.  head/tail is one solution to that, but seems more natural with<br>
> linked lists than arrays, since the tail operation sort of implies a copy<br>
> of the array, and the tailed array has to support every operation a normal<br>
> array supports.  Supporting iterators over the array might be a good<br>
> alternative.<br>
><br>
> So I have a couple of proposals:<br>
><br>
</span>>    1. Support iterators.  e.g. it = iterator(A); it2 = next(it).<br>
>    2. Support sequential foreach with some accumulator variables passed<br>
<div class="HOEnZb"><div class="h5">>    between iterations.  This would likely be implemented with iterators.<br>
><br>
> Supporting ordered iterators in Swift/T would require work, since we store<br>
> Swift arrays in hash tables and use string keys, wihch presents two<br>
> problems for finding the next integer value after the current one.<br>
><br>
> - Tim<br>
<br>
<br>
</div></div></blockquote></div><br></div>