`+` `-` on ranges and domains

[vasslitvinov]

[Update 2021-06-10: asking the same question about domains]

Given a range r and an integer i, what should the following mean?

• r + i
• r - i
• i + r
• i - r

These look like promotion. However, in 70c4746484 we introduced special cases for the first three so that they return an appropriately-modified range. It was in response to @cassella's suggestion - or at least motivated by it - as documented in d1df3ba497. Aside: back then we had open-interval domains (or ranges?) in Chapel, so instead of writing 0..#n we wrote [0..n).

The motivation, rephrased in today's terms, was that given a math expression with a range, we wanted to represent its result also as a range, rather than as an iterable (which would be the outcome of promotion). Perhaps this is so that an array could be sliced with such a math expression just like it can be sliced with a range:

var A = [1, 2, 3, 4, 5];
var r = 1..2;
writeln(A[r*2-1]);

Cf. for some time we had similar special cases for * and /. Those were removed in d515ff7437 with this explanation: "With the introduction of the # operator, they are not nearly as necessary, and they always resulted in certain ambiguities/issues that nobody was terribly comfortable with: e.g., what does r * 0 mean? What does r * -1 mean? What does (1..n by 1) / 2 mean?"

That same commit further stated: "I still believe + and - are important on ranges due to their intuitiveness, cleanness, and the fact that they keep the operations closed on ranges without any confusing cases."

Today, if we removed the special cases for r+i etc., the above array slicing expression would mean a promoted indexing operation.

We rely on this special meaning of + and -, for example, in our rectangular domain maps to "translate" and un-translate domains/ranges when passing the current iteration subspace from the leader to the followers. There, we could instead invoke named methods to achieve the same outcome.

Conclusion?

In today's range module review, we leaned towards removing this special handling of + and -, therefore reverting them to mean a promoted op.

Pro: eliminate confusion about what r + i means and that r-i and i-r work differently.

Con: will require more verbose syntax when the range result is desired, ex. have to spell out r.translate(i).

[bradcray]

I had lost track of how long @cassella's been making contributions to the project!!

If someone wanted to champion keeping + and - on ranges, I haven't been able to come up with a great reason that we couldn't/don't support i-r offhand. Alternatively, we could require the range to be on the LHS for + as well which I think is the common form and might signal that we want to preserve the range-ness.

These look like promotion.

In the meeting this week I said that I thought they behave like promotion too (?). (in the sense that they generate the same indices, simply in a compact form rather than an iterable?). Am I wrong about that?

ex. have to spell out r.translate(i).

Independently of whether we keep +/- on ranges, I liked @mppf's proposal to rename .translate to .shift for brevity and without sacrificing clarity (I think we kicked around .xlate in the past for brevity, but didn't like the abbreviation).

[vasslitvinov]

Thinking some, I see this as a good case for having consistency and avoiding special cases.

That is, I support removing the special case for r+i etc. and redirecting users to .shift if they desire the result to be represented as a range.

[bradcray]

A food-for-thought question: If we switch from focusing on ranges to domains, is it more attractive to support stencils using:

const D = {1..n, 1..n},
           ID = {2..n-1, 2..n-1};
var A, B: [D] real;

var B = A[ID + (-1,0)] + A[ID + (1,0)] + A[ID + (0,1)] + A[ID + (0,-1)];

or

const north=(-1,0), south=(1,0), east=(0,1), west=(0,-1);

var B = A[ID+north] + A[ID+south] + A[ID+east] + A[ID+west];

rather than, say:

var B = A[ID.shift(-1,0)] + A[ID.shift(1,0)] + A[ID.shift(0,1)] + A[ID.shift(0,-1)];

or:

var B = A[ID.shift(north)] + A[ID.shift(south)] + A[ID.shift(east)] + A[ID.shift(west)];

And if so, would continuing to support +/- for domains suggest that we should do so for ranges as well, given their relationship?

And then two cop-outs:

• we could always supply these operators as tertiary operators in a utility module
• if we don't reach clarity, we could defer this decision by having these overloads --warn-unstable

[vasslitvinov]

I agree that +/- overloads should be either on both domains and ranges or on neither of them.

While longer to type, I find ID.shift(north) more clear than ID+north .

[bradcray]

While longer to type, I find ID.shift(north) more clear than ID+north .

Clearly not a ZPLer... :D

[vasslitvinov]

+ != @ :)

[mppf]

I thought that we didn't support + on rectangular domains meaning shift because + adds an element to an associative/sparse domain? It would seem confusing to me to have + on domains behave totally differently based on the flavor of the domain (I am fine with some operations not being supported on some domains; so am happy with + being an error on some).

Regarding shift vs translate, we have a similar method for domains - https://chapel-lang.org/docs/master/builtins/ChapelArray.html#ChapelArray.translate - and presumably we want to keep the names the same (so they both are shift or they both are translate).

[vasslitvinov]

Interesting... imagine this:

• dom += i; makes more sense as "update my domain", less sense as a promoted operation
• dom + i makes more sense as a promoted operation, less sense as "produce a new domain" - because in my mind creating a new domain is a heavy-weight operation

Not sure how to reconcile these two.

[mppf]

It would be OK with me to have the operation to add to a domain's index set not be += but rather add (say). But we have intentionally added "set algebra" operations to associative domains so you can say things like domain1 + domain2 or domain1 & domain2. I think that using + or & or any existing operator that can apply to elements of one of these sets is inherently confusing with promotion (for the same reasons we are talking about here with range). I would prefer it if these union/intersect operations had their own operators (like in math... ∩ and ∪ - but that's probably a bridge too far) or use their own methods like union and intersect. Nonetheless they are convenient in a way and I don't have a strong preference here. (I would be OK with requiring method calls for these or with keeping the status quo).

[vasslitvinov]

There is also a proposal to add @ operator, at least on domains, see #7729

const D = {1..6};
const E = D@7;
writeln(E); // {8..13}

[vasslitvinov]

From today's (2021-06-10) domain module review:

• We expressed a dislike for enabling the "promoted" interpretation of these operations, because we do not lose anything if they return a range or domain instead of an iterable.
• We expressed a preference for consistent behavior of +, - for ranges and rectangular domanis. This may argue for keeping +, - disallowed for rectangular domains (to avoid confusion with +, - on irregular domain, which mean an addition or removal of a single index) and disallowing these two operators on ranges.

[vasslitvinov]

Here are a couple of corner cases to keep in mind:

• - with reverse argument order: what should it mean? 5 - myRange, 5 - myDomain
• shifting a distributed domain is an expensive operation, we may want to help users to stay away from their unintentional use

[bradcray]

shifting a distributed domain is an expensive operation, we may want to help users to stay away from their unintentional use

I didn't buy this argument because I view D-(1,1) as creating a new domain, not shifting D. And while creating new distributed domains isn't free, it also doesn't carry the weight of reallocating arrays, which is where I thought the stated concern was coming from.

I generally buy the argument that if we continue to support + (or usually, += as a way to add new indices to a sparse or associative domain (which I like), that we should continue to not support + as a way to express translation on rectangular domains. And I think we should treat rectangular domains and ranges uniformly in this sense, which would suggest retiring its support for ranges as well.

As with most things, I'd want to understand the impact on existing codes before calling the decision 100% done, though (and would be happy to lead or help with that investigation).

[bradcray]

While resurrecting some jacobi iteration slides and working on them today, I was sad to find that I couldn't write:

Temp[D] = (A[D+(0,-1)] + A[D+(0,1)] + A[D+(-1,0)] + A[D+(1,0)])/4;

instead of the more verbose:

Temp[D] = (A[D.translate((0,-1))] + A[D.translate((0,1))] + A[D.translate((-1,0))] + A[D.translate((1,0))])/4;

[lydia-duncan]

Now that these are marked unstable, I'm removing the 2.0 tag