[Swift-devel] Semantics of multidimensional arrays in Swift

[Michael Wilde]

I agree with Ben's general sense here, but feel we need to define this more clearly. And there are a few subtleties that I think are not yet captured in those examples.

Array behavior can be best understood if you follow these rules:

- arrays are really hash tables (hence they can be sparse)
- multi dimension arrays are simply nested hash tables
- every element of every array follows single-assignment semantics
- the elements of all but the leaf elements of multi-diemnsion arrays are just hash tables

I think that the semantics needs to define nesting in terms of references rather than copies, because if you set an element of an array, that value should be visible through any variable (or collection slot) that refers to the array object. At least hats the way Swift behaves in most cases Ive seen and scripts Ive written, and that seems useful and (largely) consistent.

At the moment I think some of our test examples are clouded by bugs, including non-deterministic behavior, lack of appropriate double-assignment runtime error messages, Java exceptions, and ill-behaved trace() output (which is perhaps due to one of the above errors).  I filed a ticket and can pay more attention to this when I return from SC.

- Mike



----- Original Message -----
> From: "Ben Clifford" <benc at hawaga.org.uk>
> To: "Tim Armstrong" <tim.g.armstrong at gmail.com>
> Cc: "swift-devel" <swift-devel at ci.uchicago.edu>
> Sent: Friday, November 18, 2011 1:52:53 AM
> Subject: Re: [Swift-devel] Semantics of multidimensional arrays in Swift
> The below is based on my gut feeling for how things *should* work, at
> least assuming the existence of array assignment syntax, not how the
> implementation does work.
> 
> Remember this is a declarative language. So then:
> 
> > I initially assumed that 2d arrays were effectively arrays of
> > references to arrays, so that the semantics would be as follows:
> >
> > int a[][];
> > int b[];
> >
> > a[0] = b; // Pointer to b in first slot of array a
> > a[0][1] = 2; // insert into b
> 
> First you say "the value of a[0] is fully described by b" and then
> secondly you say "the value of a[0] is partially described by the
> statement 'element [1] is 2'". Those are contradictory statements.
> 
> Maybe it would be ok to say:
> 
> a[0]=b
> b[1]=2
> 
> If you're using verbs like "insert" it suggests you haven't smoked
> enough swift-crack and are still thinking too imperatively...
> 
> > a[1][1] = 2; // invalid because no array inserted into a[1]
> 
> One interpretation of this working is that declaring an array int
> a[][] means that you have a structure that is indexed by pairs of
> co-ordinates, rather than a structure indexed by one co-ordinate
> containing a bunch of other structures indexed by the other
> co-ordinate.
> 
> So if you have tuple syntax (x,y) then you are really writing:
> 
> a[(1,1)] = 2
> 
> which is fine, just like a[(0,1)] = 2 is.
> 
> But in that view, what does a[0] means? something like a[(0,?)] ?
> mostly I think it would mean "select the subset of values that have
> left co-ordinate 0": if you're using it for extracting a value, you
> get a 1d array out of it. If you're using it for setting values, then:
> 
> a[0] = b
> 
> would be something like:
> 
> foreach i in b { a[0][i] = b[i]; }
> 
> 
> Whether this is implemented by copying a pointer to b or by copying
> individual values shouldn't affect the end result, as long as its
> implemented properly, and as long as you don't write invalid programs
> which are awkward to detect.
> 
> In my opinion, your program below is invalid, because you are making
> two contradictory declarations of the value of a[0] - on that its
> entire value is determined by b, and another that one of its values is
> 30.
> 
> If the above model is how things should work, then really you should
> get a runtime error when trying to do this:
> 
> > a[0][3] = 30;
> > a[0] = b;
> 
> and non-deterministic outcome 2 below is incorrect.
> 
> but that this:
> 
> 
> > a[1][0] = 123;
> 
> should work just fine - there is no concept of "declaring" a[1] to
> exist separate from using it.
> 
> A slightly different way for this to work would be for a[0] = b to
> explicitly be a copy of b elements into a[0], which *would* allow you
> to assign other entries to other a[0][x] positions, as long as they
> did not conflict with elements that came from b. (the usual "can't
> assign an element twice" rule). But maybe that would be less efficient
> to implement.
> 
> Sorry that the above sounds rather disconnected from implementation
> and abstract - but you are asking about abstract semantics ;) Feel
> free to demand I explain my views more...
> 
> Ben
> 
> >
> > But a[1][1] = 2 actually succeeds. As far as I can work out, what
> > actually happens is:
> > 	• A[i][j] = x;
> > 		• A[i] is uninitialised, a new array C is created, and x assigned
> > 		to C[j]
> > 		• A[i] is initialised with array C, x is assigned to C[j]
> > 	• A[i] = B;
> > 		• A[i] is uninitialised, A[i] is then a reference to B
> > 		• A[i] is initialised and points to array C, all members of B are
> > 		copied to the corresponding index in C
> > Is this the intended behaviour? Am I understanding this correctly?
> >
> > In the swift implementation I tested it on, this leads to some
> > nondeterminism:
> >
> > int a[][];
> > int b[] = [1,2,3];
> >
> > a[0][3] = 30;
> > a[0] = b;
> > a[1][0] = 123;
> >
> > trace(a[0][0]);
> > trace(a[0][3]);
> > trace(a[1][0]);
> >
> >
> > Nondetermistic outcome 1
> > ====================
> > SwiftScript trace: 1
> > SwiftScript trace: 123
> > Execution failed:
> >     Invalid path ([3]) for a.[0][]/3
> >
> > Nondetermistic outcome 2
> > ====================
> > SwiftScript trace: 1
> > SwiftScript trace: 30
> > SwiftScript trace: 123
> >
> > - Tim
> > _______________________________________________
> > Swift-devel mailing list
> > Swift-devel at ci.uchicago.edu
> > https://lists.ci.uchicago.edu/cgi-bin/mailman/listinfo/swift-devel
> 
> _______________________________________________
> Swift-devel mailing list
> Swift-devel at ci.uchicago.edu
> https://lists.ci.uchicago.edu/cgi-bin/mailman/listinfo/swift-devel

-- 
Michael Wilde
Computation Institute, University of Chicago
Mathematics and Computer Science Division
Argonne National Laboratory