[Swift-devel] Standard Library Proposal/Discussion Page

[Mihael Hategan]

On Wed, 2015-01-21 at 17:02 -0600, Tim Armstrong wrote:
> I see your point with dense/sparse array errors - there is the prospect of
> confusing errors in either case.  I think with dense arrays, the intent is
> clearer - the users knows they have to assign elements [0..N-1] and the
> function knows it can expect elements [0..N-1].  With sparse arrays the
> user has might readily expect the function to "do the right thing" with the
> input, since the types check out - getting back to the root cause of the
> problem would require more steps of inference to get back to the root
> problem - that the function doesn't do what they expect.

I agree that a fixed-size array is slightly less error-prone in certain
scenarios because there is more information known. But it is also easier
to check a sparse array for completeness because length(array) will
guarantee that all counted elements exist. So I think they are just
about the same: an imperfect solution to a complex problem.

> 
> That transformation of adding an implicit else branch is really just a way
> of implementing sequential semantics by adding data dependencies to
> implement the sequential control dependency.  The other example of closing
> an array is a pure data dependency on the entire value of A rather than a
> control flow dependency.
> 
> I don't see Swift as a sequential language that we're autoparallelising
> though.  For one, we let statements with side-effects execute out of order
> as a general rule.  Constructs like foreach are also explicitly allowed to
> execute out of order.  I.e. there is no total order in the program in which
> statements have to execute, there's just a partial order defined by data
> flow.  To work out which version of a variable is being referred to
> requires defining a total order.

Right. The data flow provides a total ordering in this case, for a
sub-set of statements. These are basically inductive algorithms for
which we require indices be spelled out. Ultimately the user only needs
to spell out the induction step and the initial (and perhaps final)
condition. Perhaps I agree with you in a sense: either spell out all the
steps and then require specific indices, or require only initial_value,
final_condition and inductive_step and let some library function unfold
the whole thing. Probably cleaner, less error-prone, and easier to
implement.

So, new proposal: lambda arguments and a nice functional set of
reduction functions?

> 
> For example, if we involve loops:
> 
> versioned x = 1;
> 
> foreach i in A {
>    if (rand()) {
>      x = i;
>    }
> }
> 
> I'm going to assume the intended behavior is that the loop iterations
> execute in some sequential order and each iteration depends on the
> previous.  But this requires that a) the keys of A have a defined order,
> and b) we don't start iterating over A until we know what the "first"
> element is, i.e. essentially until A is closed.
> 
> But that doesn't really square with the idea that iterations of a foreach
> loop are independent that previously existed.

Right. It doesn't. If you introduce dependencies between iterations,
then iterations are not independent. And there are algorithms that
require such dependencies.

>    This seems to require that
> the presence of a variable of a particular type changes the semantics of an
> enclosing control flow structure. This is really bizarre from a language
> design point of view.

I disagree. Without data dependencies the order of execution has always
been unspecified in Swift and is explicitly disconnected from the
official semantics. We can choose to serialize everything as long as
data dependencies are enforced. And we certainly do so if calling apps
and only allowing one executable at a time (or if we set
foreachMaxThreads to 1). Parallelism is only used for performance and
the exact details are left to the implementation to decide/optimize. The
only guarantee is that whether serial or parallel or somewhere
in-between, swift will produce the same results if the apps are well
behaved.

The involvement of foreach here is not relevant. One can unfold the
foreach completely and say things like a[0] = 1; a[1] = f(a[0]); a[2] =
f(a[1]); etc. The results are the same (you can technically write a very
large number of these guarded by termination conditions to deal with the
fact that a dynamic version of these has a statically unknown number of
steps).

Mihael