Exposing the stride and offset John Cowan 11 Aug 2015 21:17 UTC Re: Exposing the stride and offset Pierpaolo Bernardi 11 Aug 2015 21:48 UTC Re: Exposing the stride and offset Bradley Lucier 26 Sep 2015 18:28 UTC

Re: Exposing the stride and offset Bradley Lucier 26 Sep 2015 18:28 UTC

Thank you for this suggestion.

> On Aug 11, 2015, at 5:17 PM, John Cowan <xxxxxx@mercury.ccil.org> wrote:
>
> But we can do a much more thorough job of factoring by precomputing a
> vector of *strides*.  S_k is the kth stride, and represents the number
> of storage elements between successive elements that differ in the kth
> index by 1.  So in a 3 x 4 zero-based matrix, S is #(4 1); note that
> the highest value of S is always 1.  The offset V represents the index
> of the storage element whose index tuple is (0) or (0, 0) or (0, 0, 0)
> or ...  Now the algorithm is simply V + \sigma S_k * I_k.

Internally, I use basically V + \sigma S_k * (I_k - L_k) (different V, of course) to lessen the chance of index computations straying into bignum territory when the natural limits (L_k, U_k) are large.

>
> If the stride-offset representation were purely internal, it wouldn't
> matter to this SRFI.  But the ability to specify an array using the body
> of an existing array but with different strides and offset makes a huge
> difference to what can be done to the array.  For example, transposing
> a matrix just requires reversing the stride: with a stride vector of
> #(1 4) instead of #(4 1), we have effectively exchanged the roles of
> the row index and the column index without further ado.

I decided to explore how similar things can be expressed using this SRFI.

In this SRFI transposing a mutable “matrix” (I put it in quotes because I would like to keep the notion of arrays and matrices distinct) would involve something like

(let ((domain (array-domain a))
(getter (array-getter a))
(setter (array-setter a)))
(array (interval (vector (interval-lower-bound domain 1)
(interval-lower-bound domain 0))
(vector (interval-upper-bound domain 1)
(interval upper-bound domain 1)))
(lambda (i j)
(getter j i))
(lambda (v i j)
(setter v i j))))

This reuses the getter and setter of the old array.  Or, a specialized array could be transposed with

(let ((domain (array-domain a)))
(specialized-array-share!
a
(interval (vector (interval-lower-bound domain 1)
(interval-lower-bound domain 0))
(vector (interval-upper-bound domain 1)
(interval upper-bound domain 1)))
(lambda (i j)
(values j i))))

(Again we’re reusing the old array instead of generating a new one.)

Or, one could generate a new array with

(array->specialized-array
(let ((domain (array-domain a)))
(specialized-array-share!
a
(interval (vector (interval-lower-bound domain 1)
(interval-lower-bound domain 0))
(vector (interval-upper-bound domain 1)
(interval upper-bound domain 1)))
(lambda (i j)
(values j i)))))

Among the extensive list of operations in Racket’s math/array package are the functions array-axis-swap (which in two dimensions implements a transpose) and array-axis-permute (which allows general permutations, not just a swap).

http://docs.racket-lang.org/math/array_transform.html

I find it interesting that the general permutation group can be generated by these swaps.

The clumsiness of my implementation of these examples seems to imply that permutation operators on intervals and arrays alike may be useful.

>  Similarly, we
> can reverse a zero-based vector whose V is 0 and whose stride is #(1),
> by letting V be the vector length and S be #(-1).

(let* ((domain (array-domain a))
(n (interval-upper-bound domain 0))
(getter (array-getter a)))
(array domain
(lambda (i)
(getter (- n i 1)))))

>   There are a lot more
> transformations we can do on an array by returning
>  the same body with
> new values of S and V.

I included in this SRFI operations that I have found to be useful, and have been rather sparing in adding other operations.

Given how clumsy it seems to permute the “axes” using the operations in this SRFI, should built-in operations be offered?