How should accessing a slice be interpreted?

[bradcray]

Consider the following declaration:

var A: [1..n, 1..n] [1..3, 1..3] real;

This issue asks how expressions like the following should be interpreted:

...A[2..n-1, 2..n-1][2, 2]...

One interpretation, and the one that's implemented on master (call it "slices don't advance the dimension"), would say that the slice of A returns an array expression itself, and then the indexing with [2,2] accesses that resulting array expression resulting in a 3x3 array equivalent to 'A[2,2][1..3, 1..3]'. This interpretation is essentially equivalent to:

ref B = A[2..n-1, 2..n-1];
...B[2, 2]...

The second interpretation (call it "slices advance the dimension") would be that the first set of brackets should be attached to the first array and that the second set should be attached to the inner array elements. Thus, this interpretation would result in a (n-2) x (n-2) array of singleton reals corresponding to the (2,2) element of each of the 3x3 array elements.

[bradcray]

Capturing my current opinions on the matter:

I think in many respects, the second interpretation is the more natural one: Reading the expression, it seems more intuitive to me that this is what it would mean. In fact, in the description of the second interpretation above, I almost typed "it's equivalent to A[2..n-1, 2..n-1][2, 2]" before realizing how tautological that sounded. Moreover, in most cases, Chapel uses zippered interpretation of statements rather than array-oriented interpretations. I.e., we think of:

A = B + C*D;

as being like:

forall (a,b,c,d) in zip(A, B, C, D) do
  a = b + c*d;

rather than like:

var T = C*D;
A = B + T;

so if we think of slicing as being like promoted indexing, it seems a bit odd to use array-oriented semantics here ("evaluate the first array operator (slicing) first, then apply the next one (indexing)") than it does to interpret the entire array expression "at once."

On the other hand, treating slices as promoted indexing doesn't exactly make sense either. For example we couldn't rewrite,

...A[2..4, 2..4][1..2, 1..2]...

as:

forall (ij, kl) in zip({2..4, 2..4}, {1..2, 1..2}) do
  ...A[ij][kl]...

both because the slice expressions can't be zipped (they have different sizes and shapes) and because the "slices advance the dimension" approach should result in more of a nesting/composition semantics than a zippering:

forall ij in {2..4, 2..4} do
  forall kl in {1..2, 1..2} do
    ...A[ij][kl]...

so maybe trying to equate slicing with promotion of indexing is a false goal.

The other thing that the second interpretation has going against it is that I'm not sure how to implement it while also supporting things like passing an array slice to a routine accepting an array. Or maybe more to the point, I don't know how I'd have the compiler distinguish between:

ref B = A[2..n-1, 2..n-1]
...B[2, 2]...

(which I'm reasonably certain should result in a 3x3 array) and

...A[2..n-1, 2..n-1][2, 2]...

without special-casing the latter case in the parser (which raises red flags for me).

So while I consider the second interpretation more intuitive, I'm at a loss for how to bring it about without breaking other aspects of the language (though very open to suggestions).

[benharsh]

My first reaction was that we'd need some kind of special syntax to implement the second interpretation. The first thing that came to mind was this (I acknowledge this is ugly):

A[1..n, 1..n][[2, 2]]

I then began to wonder if we could identify this case by determining if we're slicing a compiler-generated temporary or something the user wrote (a var, ref-var, formal, etc.). I'm not sure our current AST captures that kind of information well enough though. For example the compiler might generate AST spiritually similar to this:

var tmp = A[1..n, 1..n]; // no copy
tmp[2, 2] = ...; // slice/forward to the inner elements

whereas a user might write:

ref B = A[1..n, 1..n];
B[2, 2] = ...; // slicing/indexing a slice

[bradcray]

My concern about relying on a special syntax is that if users don't know about it and write the "obvious" thing, they'll be surprised by the result. Maybe put another way, if we supported special syntax at all, I think it should be for the first case (but I also don't know that that's necessary given that one can capture the slice into a 'ref' variable if that's what you really want; whereas there's no shorthand way to write the second without introducing an explicit forall loop...).

I do like Ben's notion of distinguishing compiler temps from user variables as a means of supporting the second case, though... that seems promising. That said, I haven't looked at the AST to see how hard it would be to recognize this. My thinking is that if we saw a slice/access on a compiler temp representing an array view, we could change it from a normal 'this()' access to a "thisOnSlice()' access which would have different semantics.

[tmacd9]

I've done some thinking and wonder what others think. This all started when I discovered that:

var A: [1..3, 1..3][0..1] int;

A[1..3, 1..3][0] = 4;

does not behave like:

forall (i,j) in {1..3, 1..3} { A[i,j][0] = 4; }

instead:

A[1..3, 1..3][0] = 4;

gives a compile time error:

error: unresolved access of '[domain(2,int(64),false)] [domain(1,int(64),false)] int(64)' by '[0]'

So, I think this is about ambiguity in that, in this case, there's an ambiguity with the

[0]

subscript operator. It could either bind with the slice expression

A[1..3, 1..3]

to access a single element (however [0] is an incorrect subscript for a 2D array - thus the error) or it could subscript the inner array since the inner array has a 0..1 index set. If it binds to the inner array then every element in the outer array is accessed, and the behavior is the same as the forall mentioned above.

The current default behavior is that the compiler binds the [0] subscript operator to the slice (outer array). Thus, there's a difference between the A[1..3, 1..3][0] = 4 statement and the corresponding forall statement mentioned above.

I did some experimenting. Consider an array of records with two fields.

record R { var m1: int; var m2: int; };

var AR : [1..3] R;

AR.m1 = 4; The m1field of each element of ARis modified. This is expected and not surprising.

Consider tuples with two components.

var tup = 2*int;

It's possible to create arrays with elements that are tuples. Consider the following two arrays of tuples:

var At : [1..3] tup; // 1D array of tuples var A2t : [1..3, 1..3] tup; // 2D array of tuples // no error - component 1 of all tuple elements assigned the value 9 A2t(1) = 9;

//error: type mismatch in assignment from int(64) to 2*int(64) At(1) = 9; It seems surprising that the 2D array of tuples example behaves as expected. This modifies every tuple element in the array. The 1D array example gives an error even though it is a similar statement as the 2D array statement. Since the () operator can also be a subscript operator, there is an ambiguity. With a 2D array the compiler determines that

(1)

cannot be a subscript into A2t(thus accesses all tuple components) but with the 1D array the

(1)

is treated as a subscript operator and gives an error. The error occurs because the

9

is not a tuple and is incompatible with the element type. The compiler does not treat the access

At(1)

as accessing all elements in the array. However, with

A2t(1)

every element in A2tis modified.

As mentioned in the beginning, there is also an ambiguity when the element type is itself an array type, as in:

type inner = [0..1] int;

To me, this seems surprising, but I do not have a solution. In every example the element of the array is an object that has two values (record fields, tuple components, and array elements). Yet it feels like there is a lack of closure in the language as the behavior of similar 'look-n-feel' expressions is different.

At one point I considered the following for tuples and arrays:

A.(2) A.[0]

to mimic records. I admit I have not given this idea enough consideration. The. specifies using every element in the array.

[bradcray]

It's notable that Fortran, as a major language from which to learn, does not support arrays of arrays, so arguably doesn't have much to teach us here (and may even suggest we've done the right thing given that we want to support arrays of arrays). This makes me wonder whether maybe the right way to proceed is to have the compiler generate a warning when it finds an index of a slice just to make sure that the user avoids confusion (as several of us have failed to do when writing such idioms).

[bradcray]

The oldest mail in my inbox relates to this issue, so I thought I'd capture it here as food for thought rather than keeping it in my inbox eternally. It's from @tmacd9 and is a variation on his comment above:

new syntax could provide a solution to the question of how do I use array syntax to get forall behavior:

config const n = 4;
record Point { var x: [1..2] int; }

var B: [1..n, 1..n] Point;  // array of records

// The following array syntax statements seem like they should be OK
B.x = 3;
writeln(B);
B.x[1..2] = 4;
writeln(B);
B[1..n, 1..n].x[1..2] = 5;
writeln(B);

// Now consider:

var A: [1..n, 1..n][1..2];   // array of arrays

// similar idea introducing new syntax

A.[1..2] = 3;  // where the '.' implies accessing the element type,
               // and with '.' the element type cannot be primitive

// equivalent to:

forall (i,j,k) in { 1..n, 1..n, 1..2 } do {
  A[i,j][k] = 3;
}

A[1..n,1..n].[1..2] = 4;

// This begs the question about:

A.[] = 5;

Seems like the above [] syntax could work but I'm not convinced it's a good idea.