New Range Methods to Yield Index-Neutral Sub-Ranges

[damianmoz]

I am thinking of recommending something like the following

inline proc range.after(i : integral) where !this.stridable return (i + 1):this.idxType .. this.high;

inline proc range.before(i : integral) where !this.stridable return this.low .. (i - 1):this.idxType;

inline proc range.afterAndIncl(i : integral) where !this.stridable return i:this.idxType .. this.high;

inline proc range.beforeAndIncl(i : integral) where !this.stridable return this.low .. i:this.idxType;

inline proc range.after(i : integral) where this.stridable return (i + this.stride) .. this.high by this.stride;

inline proc range.before(i : integral) where this.stridable return this.low .. (i - this.stride) by this.stride;

inline proc range.afterAndIncl(i : integral) where this.stridable return i:this.idxType .. this.high by this.stride;

inline proc range.beforeAndIncl(i : integral) where this.stridable return this.low .. i:this.idxType by this.stride;

inline proc range.afterFirst return this.after(this.first);

inline proc range.beforeLast return this.before(this.last);

inline proc range.backwards return this.low .. this.high by -this.stride;

I am loathe to use these names because other methods are nouns and verbs. The above are prepositions. But they seem natural.

With methods like the above, and a two dimensional array say a[?aD] and some ranges defined as

const (rows, columns) = aD.dims();

If a was defined as **a[1..m, 1..n] mathematical indices, a for loop which operates on everything except the first column (in reverse order) would conventionally be written like

for i in 2 .. n by (-1) do

This could also be written using the above methods as

for i in columns.afterFirst.backwards do

So, when somebody comes along with an array having bounds defined with memory offsets a[0..<m,0..<n], the for loop above needs no change, i.e. it is index-neutral!!!

This also allows one to define things like

const offDiagonal = columns.after(i); // Off-Diagonal, all columns subsequent to a[i, i] for row i -- i+1 .. nb
const subDiagonal = rows.after(i); // Sub-Diagonal, all rows below a[i, i] for column i -- i+1 .. m
const diagPlusSubDIagonal = rows.afterAndIncl(i); // the diagonal at column i and all elements below it -- i .. m

again in an index-neutral fashion.

Comments, ridicule, constructive suggestions. All welcome.

Until somebody sorts out the compiler to detect ranges with a stride of 1 where this stride is known at compile time, I might overload those functions a little more. But that can wait.

[damianmoz]

If the above really should be associated with another issue, please move it. But it needs the Index-Neutral issue highlighted.

Also, if the stridable method eventually gets a better name such as might be mooted by #17131, the above will reflect this.

[damianmoz]

I did some preliminary testing and the index-neutral seem to work, at least for the example I tried.

I used a routine for an in-place LU decomposition of a matrix. It is is fed space for the pivot vector whose domain must be consistent with the matrix. So it is not a drop-in replacement for lu from LinearAlgebra. Three (3) lines from the original needed to change and they were those associated with range definitions for mathematical indices, the so-called 1-based indexes. The routine now accepts 2D arrays defined using array subscripts which are either mathematical indices like A[1..n, 1..n] or memory offsets like A[0..<n, 0..<n]. it produces the correct results in both cases. No need for a reindex. .

For now, the input matrices are assumed to be consistent. But it is technically possible to handle a matrix which is part of a larger matrix, i.e. decompose just A[-19..+10, 21..50] with a pivot vector defined over a range 1..30. But that starts to get more complex and means more than just 3 lines change. Do you really want to do that in a library routine?

Just looking at an SVD. This algorithm is 4-5 times more complex than LU decomposition. I seems like 4-5 times the number of lines will need to change so at least the concept scales nicely. I will test that later.

I will document the approach a bit more. Input anybody? Do the methods seem complete enough? We need to figure out the overheads. How do I integrate them into ChapelRange.chpl? Then we can release it into the wild.

[damianmoz]

The LU factorization test case can be (re)written fractionally less clearly but with less lines without those methods.

So I think I will retire them unless anybody thinks otherwise.

Mind you, index neutral programming is certainly achievable.