[Swift-devel] Semantics of multidimensional arrays in Swift

[Ben Clifford]

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