[Swift-devel] Standard Library Proposal/Discussion Page

[Tim Armstrong]

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.

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.

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:

versioned int x = 1;

if (...) {
  x = 2;
}

trace(x);

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.

- Tim

On Wed, Jan 21, 2015 at 1:20 PM, Mihael Hategan <hategan at mcs.anl.gov> wrote:

> I think this is a general problem with Swift: the inability to have
> accumulator variables. It leads to the necessity to use recursion, but
> that isn't in itself enough because of the issue with tail(array) that
> you mention. So iterators seem like the right choice there.
>
> You mentioned non-sparse arrays. The only problem with algorithms based
> on dense arrays is that they might not be very efficient in swift since
> elements are not necessarily generated in order. It may just be that
> a[0] will make it into the array last due to parallelism.
>
> So I think updateables > iterators > dense arrays > tail > nothing.
>
> The question is whether we would design the standard library differently
> if we had either of updateables or iterators vs. what we have right now
> (nothing) and whether the differences would be significant enough for us
> to suspend the standard library discussion until we have these features.
>
> Mihael
>
> On Wed, 2015-01-21 at 09:14 -0600, Tim Armstrong wrote:
> > I think the ideal scenario might be if we could have these in the
> standard
> > library, but implemented in Swift.
> >
> > I tried tried to write Swift code for the min/max problem and it's really
> > revealing some weird interactions/limitations around the sparse arrays
> and
> > iteration constructs provided.
> >
> > The thing is that there's no straightforward way to iterate in order over
> > the set of keys in an array, passing a variable from one iteration to the
> > next.  My thought process was:
> >
> >    1. Iterate over array with foreach -> doesn't work, since we can't
> pass
> >    the max from one iteration to the next
> >    2. Sequentially iterate over 0..size(A)-1 with for loop -> doesn't
> work
> >    since keys may be sparse or not start at 0
> >    3. Fetch the list of keys and iterate over them with foreach ->
> doesn't
> >    work, since foreach doesn't let us pass max from one iteration to the
> next
> >    4. Fetch the list of keys, and since we can assume that they're dense,
> >    iterate over 0..size(A) -1 with a for loop, lookup A[keys[i]], and
> update
> >    the max based on that.
> >
> > So there is a solution, but it's really ugly - I don't think we should
> have
> > to create a copy of the array's keys and do a double indirection just to
> > calculate min/max.  It also feels a little clunky that the eventual
> > solution depends on implicit contracts about whether an array's keys are
> > dense or not.
> >
> > We'd have to assume that most users would give up after #1 or #2.  Also
> > Swift/K doesn't support for loops, so you have to resort to using arrays.
> > It's also error prone since many users will neglect to consider that
> there
> > may be gaps in the array's key space.
> >
> > I think there's an issue that there is no direct way to get the first
> item
> > in an array, and no direct way to get the successor to an item in the
> > array.  head/tail is one solution to that, but seems more natural with
> > linked lists than arrays, since the tail operation sort of implies a copy
> > of the array, and the tailed array has to support every operation a
> normal
> > array supports.  Supporting iterators over the array might be a good
> > alternative.
> >
> > So I have a couple of proposals:
> >
> >    1. Support iterators.  e.g. it = iterator(A); it2 = next(it).
> >    2. Support sequential foreach with some accumulator variables passed
> >    between iterations.  This would likely be implemented with iterators.
> >
> > Supporting ordered iterators in Swift/T would require work, since we
> store
> > Swift arrays in hash tables and use string keys, wihch presents two
> > problems for finding the next integer value after the current one.
> >
> > - Tim
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/swift-devel/attachments/20150121/2d26bd18/attachment.html>