SRFI 164: Enhanced multi-dimensional Arrays

This SRFI is currently in final status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-164@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Abstract

This SRFI describes the array data type (a generalization of vectors to multiple indexes or dimensions), along with a set of procedures for working on them.

This specification is an extension of SRFI 25, with additions from Racket’s math.array package and other sources. It has been implemented in the Kawa dialect of Scheme.

Rationale

This specification aims for compatibility with SRFI 25 and SRFI 4. It also takes ideas from Racket, Kawa, and Guile.

Specification

Generalized vectors

A generalized vector (gvector) is a subclass of sequences that support random access (O(1) indexing). All standard Scheme vectors are gvectors. Which other types are gvectors is implementation-dependent, but if the implementation supports uniform vectors (also known as homogeneous vectors), they should also be gvectors. This specification assumes that a range is a gvector; ranges need a separate specification — see below.

An implementation may provide other kinds of gvectors, or provide a mechanism to define new gvector types, but that is not part of this specification.

An implementation may generalize standard vector procedures such as vector-ref and vector-length to work on gvectors, but that is not required by this specification.

Array values

Arrays are heterogeneous data structures that generalize vectors to multiple indexes or dimensions. The number of required indexes is the rank or the number of dimensions of an array. In addition, while for gvectors the lowest index is 0, we generalize this to allow any other exact integer to be the lower bound.

Arrays are an extension of gvectors: Every gvector is an array whose rank is 1, and where the (single) lower bound is 0. Conversely, an array whose rank is 1 and where the (single) lower bound is 0 is usually a gvector, but this is not required to always be the case. A library-based implementation of this specification should use the existing vector type for "simple" (see below) rank-1 zero-lower-bound arrays.

A rank-0 array has a single value. It is essentially a box for that value. Functions that require arrays may treat non-arrays as rank-0 arrays containing that value.

The examples use the array literal syntax and format-array helper function of SRFI 163 for illustrative purposes. However, this specification does not require SRFI 163 (or vice versa), though they are designed to work well together.

Row-major or lexicographic order means viewing all the array elements as a sequence, with the right-most index changing more frequently. The row-major index of an element is its position (starting with 0) when the elements are considered in row-major order.

A simple array has all its elements stored contiguously in row-major order. Which arrays are simple depends on the implementation, but all arrays created by array literals, make-array, or array are simple. A vector created by a vector literal, or standard R7RS or SRFI 4 procedures (such as make-vector or f32vector) is a simple vector and thus a simple array. In addition, if the first argument to array-reshape or array->vector is simple, so is the result. Typically (i.e. in many implementations), a simple array is a simple transformation (row-major order, as if using array-reshape) of an underlying (simple) vector. (The underlying vector of a simple vector is itself.)

Ranges (non-normative)

A range is an immutable linear sequence of values, defined in terms of a start value, the difference between successive elements or step, and an optional length. The range is unbound (non-finite) if length is missing. The start and step values are usually exact integers (and must be so when used for indexing), but generally can be any real numbers (or more generally taken from an enumerable set). The value of element i is start + i * step, as long as i < length. It is strongly recommended (but not required) that there be a separate gvector type for ranges that only stores length, step, and length.

Ranges are convenient way to specify slices and other regular array sections. This specification does not define an API for ranges, but some of the later examples make use of the syntax for Kawa ranges, purely for illustrative purposes. We summarize this syntax here.

[ start [by: step] size: length]

Create a range with the specified start, step (which defaults to 1), and length. The sequence of values is the same as SRFI 1's (iota count start step).

Instead of specifying a length directly, it is sometimes more convenient to specify a final value, or an upper/lower bound:

[ start [by: step] <: end]

[ start [by: step] <=: end]

In these cases, the sequence counts up: The step must be positive, and defaults to 1. The implied length is the maximum such that all the values x satisfy (< x end), or (<= x end), respectively.

To count down, use >: or >=: in place of <: or <=:, with step: defaulting to -1.

If the length is unspecified, the result is an unbounded or non-finite range. When used for array indexing, they can be treated as a short-hand for a context-dependent length: The longest range such that the index values are valid.

The syntax [<:] or [>:] is a pseudo-range. The start value is implicit and context-dependent.

Array shape

The shape of an array consists of bounds for each index.

The lower bound b and the upper bound e of a dimension are exact integers with (<= b e). A valid index along the dimension is an exact integer i that satisfies both (<= b i) and (< i e). The length of the array along the dimension is the difference (- e b). The size of an array is the product of the lengths of its dimensions.

There is no separate data type for a shape. The canonical representation for a shape (a canonical shape) is a rank-2 array where the first index is the dimension (zero-based), and the second index is 0 or 1: Elements #(i 0) and #(i 1) are respectively the lower bound and upper bound of dimension i.

For convenience, the procedures in this specification that require a shape can accept a shape-specifier, as if converted by the procedure ->shape. For example (array-reshape array shape) is equivalent to (array-reshape array (->shape shape)).

(->shape specifier)

Convert the shape specifier specifier to a canonical shape. We use as examples a 2*3 array with lower bounds 0 and a 3*4 array with lower bounds 1.

A vector of simple integers. Each integer e is an upper bound, with a zero lower bound. Equivalent to a range with start 0, step 1, and length e.
Examples: #(2 3), and the second is not expressible.

A vector of lists of length 2. The first element of each list is the lower bound, and the second is the upper bound.
Examples: #((0 2) (0 3)) and #((1 3) (1 4)).

A vector of simple ranges, one for each dimension, all of which are bounded (finite), consist of integer values, and have a step of 1. Each range expresses the bounds of the corresponding dimension.
Examples, using the Kawa syntactic sugar: `#(,[0 <: 2] ,[0 <=: 2]) and `#(,[1 <: 3] ,[1 size: 4]).

A vector consisting of a mix of integers, length-2 lists, and ranges.
Examples: #(2 (0 3)) and `#((1 3) ,[1 size: 4]).

A canonical shape: A rank-2 array S whose own shape is #(r 2). For each dimension k (where (<= k 0) and (< k r)), the lower bound b_k is (S k 0), and the upper bound e_k is (S k 1).
Examples: #2a((0 2) (0 3)) and #2a((1 3) (1 4)).

(shape bound ...)

Returns a shape, in the canonical (r 2) form. The sequence bound ... must consist of an even number of exact integers that are pairwise not decreasing. Each pair gives the lower and upper bound of a dimension. If the shape is used to specify the dimensions of an array and bound ... is the sequence b0 e0 ... bk ek ... of n pairs of bounds, then a valid index to the array is any sequence j0 ... jk ... of n exact integers where each jk satisfies (<= bk jk) and (< jk ek).

The shape of a d-dimensional array is a d * 2 array where the element at k 0 contains the lower bound for an index along dimension k and the element at k 1 contains the corresponding upper bound, where k satisfies (<= 0 k) and (< k d).

(apply shape bounds) is equivalent to: (apply array (vector (/ (length bounds) 2) 2) bounds)

(array-shape array)

Return the shape of array in the canonical (r 2) form. It is an error to attempt to modify the shape array.

(array-rank array)

Returns the number of dimensions of array.
(array-rank
  (make-array (shape 1 2 3 4)))
Returns 2.

(array-start array k)

Returns the lower bound (inclusive) for the index along dimension k. This is most commonly 0. Same as (array-ref (array-shape array) k 0).

(array-end array k)

Returns the upper bound for the index along dimension k. The bound is exclusive — i.e. the first integer higher than the last legal index. Same as (array-ref (array-shape array) k 1).

(array-size array)

Return the total number of elements of array. This is the product of (- (array-end array k) (array-start array k)) for every valid k.

Array construction

Array indexing

Given a rank-2 array arr with integer indexes i and j, the following all get the element of arr at index [i j].

(array-index-ref arr i j)
(array-ref arr i j)
(array-ref arr (vector i j))

Using array-index-ref (but not plain array-ref) you can do generalized APL-style slicing and indirect indexing.

(array-ref array k ...)

(array-ref array index)

Returns the contents of the element of array at index k .... The sequence k ... must be a valid index to array. In the second form, index must be a vector (a 0-based 1-dimensional array) containing k ....
(array-ref (array #(2 3)
              'uno 'dos 'tres
              'cuatro 'cinco 'seis))
   1 0)
Returns cuatro.
(let ((a (array (shape 4 7 1 2) 3 1 4)))
   (list (array-ref a 4 1)
         (array-ref a (vector 5 1))
         (array-ref a (array (shape 0 2)
                         6 1))))
Returns (3 1 4).

(array-index-ref array index ...)

Generalized APL-style array indexing, where each index can be either an array or an integer.

If each index is an integer, or there is no index, then the result is the same as array-ref.

Otherwise, the result is an immutable array whose rank is the sum of the ranks of each index. An integer is treated as rank-0 array. The shape of the result is the concatenation of the shapes of indexes: The lower bounds are the concatenation of the lower bounds of the indexes, and similar for the upper bounds. (If an index is an unbounded range, it is truncated as needed to not cause an error.)

If marr is the result of (array-index-ref arr M₁ M₂ ...) then:
(array-ref marr i₁₁ i₁₂ ... i₂₁ i₂₂ ...)
is defined as:
(array-ref arr (array-ref M₁ i₁₁ i₁₂ ...) (array-ref M₂ i₂₁ i₂₂ ...) ...)
Each M_k gets as many indexes as its rank. If M_k is an integer, then it we use it directly without any indexing, as if it were a rank-0 array.

The resulting array marr is a fresh array that does not depend on any of the arguments. Specifically, if array-ref is called on marr with valid indexes (within its shape), then no error is possible; any potentially invalid indexes must be caught by array-index-ref.
Here are some examples, starting with simple indexing.
(define arr (array #2a((1 4) (0 4))
                   10 11 12 13 20 21 22 23 30 31 32 33))
arr ⇨
╔#2a@1:3:4══╗
║10│11│12│13║
╟──┼──┼──┼──╢
║20│21│22│23║
╟──┼──┼──┼──╢
║30│31│32│33║
╚══╧══╧══╧══╝
(array-index-ref arr 2 3) ⇨
23
If one index is a vector and the rest are scalar integers, then the result is a vector:
(array-index-ref arr 2 #(3 1)) ⇨
#(23 21)
You can select a “sub-matrix” when all indexes are vectors:
(array-index-ref arr #(2 1) #(3 1 3)) ⇨
╔#2a:2:3═╗
║23│21│23║
╟──┼──┼──╢
║13│11│13║
╚══╧══╧══╝
Using ranges for index vectors selects a rectangular sub-matrix.
(array-index-ref arr [1 <: 3] [1 <: 4)) ;; Kawa range syntax — non-normative
⇨
╔#2a:2:3═╗
║11│12│13║
╟──┼──┼──╢
║21│22│23║
╚══╧══╧══╝
Using ranges makes for a convenient way to to express common slice operations while still keeping the API simple. Implementations are encouraged to optimize the case when all indexes are either integers or ranges.

You can add new dimensions:
(array-index-ref arr #(2 1) #2a((3 1) (3 2))) ⇨
#3a╤══╗
║23│21║
╟──┼──╢
║23│22║
╠══╪══╣
║13│11║
╟──┼──╢
║13│12║
╚══╧══╝
The pseudo-range [<:] can be used to select all the indexes along a dimension. To select row 2 (1-origin):
(array-index-ref arr 2 [<:]) ⇨
#(20 21 22 23)
To reverse the order use [>:]:
(array-index-ref arr 2 [>:]) ⇨
#(23 22 21 20)
To select column 3:
(array-index-ref arr [<:] [3]) ⇨
#2a╗
║13║
╟──╢
║23║
╟──╢
║33║
╚══╝
You can also repeat a column by repeating its index. For example since [3 by: 0 size: 5] is equivalent to #(3 3 3 3 3) (though possibly more efficient), you can expand column 3 to 5 equal columns thus:
(array-index-ref arr [<:] [3 by: 0 size: 5]) ⇨
╔#2a:3:5═╤══╤══╗
║13│13│13│13│13║
╟──┼──┼──┼──┼──╢
║23│23│23│23│23║
╟──┼──┼──┼──┼──╢
║33│33│33│33│33║
╚══╧══╧══╧══╧══╝

Modifying arrays

(array-set! array k ... obj)

(array-set! array index obj)

Stores obj in the element of array at index k .... The result is unspecified. The sequence k ... must be a valid index to array. In the second form, index must be either a vector or a 0-based 1-dimensional array containing k ....
(let ((a (make-array
            (shape 4 5 4 5 4 5))))
   (array-set! a 4 4 4 "huuhkaja")
   (array-ref a 4 4 4))
Returns "huuhkaja".

Compatibility: SRFI 47, Guile and Scheme-48 have array-set! with a different argument order.

(array-copy! dst src)

Both arguments must have the same shape. Every element in dst is replaced by the corresponding element in src.

Compatibility: Guile has an array-copy! with the reversed argument order.

(array-fill! array value)

Set all the values array to value. You can use (array-fill! (array-index-share array indexes...) value) to set a subset of the array.

Array as procedure (non-normative)

An optional extension (implemented in Kawa) is to allow applying a vector or array as a procedure. In such an implementation (vec i) is the same as (vector-ref vec i), and it is suggested that (array index ...) should be equivalent to (array-index-ref array index ...).

An implementation that also supports SRFI 17 (generalized set!) should allow set! to modify one or multiple elements. To modify a single element:

(set! (arr index ...) new-value)

should be equivalent to:

(array-set! arr index ... new-value)

You can set a slice (or all of the elements). In that case:

(set! (arr index ...) new-array)

is equivalent to:

(array-copy! (array-index-share arr index ...) new-array)

Transformations and views

A view or transform of an array is an array a₂ whose elements come from some other array a₁ given some transform function T that maps a₂ indexes to a₁ indexes. Specifically, (array-ref a₂ indexes) is (array-ref a₁ (T indexes)). Modifying a₂ causes a₁ to be modified; modifying a₁ may modify a₂ (depending on the transform function). The shape of a₂ is in general different than that of a₁. The result a₂ is mutable if and only if a₁ is, with the same element type restrictions, if any.

(array-transform array shape transform)

This is a general mechanism for creating a view. The result is a new array with the given shape. Accessing this new array is implemented by calling the transform function (which is T above) on the index vector, which must return a new index vector valid for indexing the original array. Here is an example (using the same arr as in the array-index-ref example):
(define arr (array #2a((1 4) (0 4))
                   10 11 12 13 20 21 22 23 30 31 32 33))
(array-transform arr #2a((0 3) (1 3) (0 2))
  (lambda (ix) (let ((i (vector-ref ix 0)) (j (vector-ref ix 1)) (k (vector-ref ix 2)))
                 (vector (+ i 1)
                         (+ (* 2 (- j 1)) k))))) ⇨
#3a:3@1:2:2
║10│11║
╟──┼──╢
║12│13║
╠══╪══╣
║20│21║
╟──┼──╢
║22│23║
╠══╪══╣
║30│31║
╟──┼──╢
║32│33║
╚══╧══╝
The array-transform procedure is a generalization of share-array in that it does not require the transform to be affine. Also note the different calling conversions for the transform: array-transform takes a single argument (a vector of indexes), and returns a single result (a vector of indexes); share-array takes one argument for each index, and returns one value for each index. The difference is historical.

(array-index-share array index ...)

This does the same generalized APL-style indexing as array-index-ref. However, the resulting array is a modifiable view into the argument array. If each index is an integer, the result is a rank-0 array that is a view of the selected element (unlike array-index-ref which would return the selected element directly).

(array-reshape array shape)

Creates a new array narray of the given shape, such that (array->vector array) and (array->vector narray) are equivalent. In other words, the i’th element in row-major-order of narray is the i’th element in row-major-order of array. Hence (array-size narray) (as specified from the shape) must be equal to (array-size array). The resulting narray is a view such that modifying array also modifies narray and vice versa. If array is simple, the result is also simple and uses the same underlying vector as array.

(share-array array shape proc)

Returns a new array of shape shape that shares elements of array through proc. The procedure proc must implement an affine function that returns indices of array when given indices of the array returned by share-array. The array does not retain a reference to shape.
(define i_4
   (let* ((i (make-array
                (shape 0 4 0 4)
                0))
          (d (share-array i
                (shape 0 4)
                (lambda (k)
                   (values k k)))))
      (do ((k 0 (+ k 1)))
          ((= k 4))
         (array-set! d k 1))
      i))
Note: the affinity requirement for proc means that each value must be a sum of multiples of the arguments passed to proc, plus a constant.

Implementation note: arrays have to maintain an internal index mapping from indices k1 ... kd to a single index into a backing vector; the composition of this mapping and proc can be recognised as (+ n0 (* n1 k1) ... (* nd kd)) by setting each index in turn to 1 and others to 0, and all to 0 for the constant term; the composition can then be compiled away, together with any complexity that the user introduced in their procedure.

Here is an example where the array is an f64vector (a vector of 64-bit floats, from SRFI-4):
(share-array
  (f64vector 1.0 2.0 3.0 4.0 5.0 6.0)
  (shape 0 2 0 3)
  (lambda (i j) (+ (* 2 i) j)))
   ⇨  #2f64((1.0 2.0 3.0) (4.0 5.0 6.0))

(array-flatten array)

(array->vector array)

Return a vector consisting of the elements of the array in row-major-order.

The result of array-flatten is a fresh (mutable and simple) copy, not a view. The result of array->vector is a view: If array is mutable, then modifying array changes the flattened result and vice versa.

If array is simple, array->vector returns the underlying vector. Specifically, if vec is a vector then:
(eq? vec (array->vector (array-reshape vec shape)))

Implementation

The following describes how this API is implemented in Kawa. The implementation is a mix of Java and the Kawa dialect of Scheme. This overview should be enough to implement the specification, but studying the Kawa implementation adds useful detail.

A simple vector (the abstract class SimpleVector) is a wrapper around a simple fixed-size native array of the appropriate type. There are sub-classes for different element types: General (simple) vectors (the class FVector which extends SimpleVector) uses an object array (Object[]), while an F32 vector (the class F32Vector) uses an array of floats (a float[]).

By default, there is a 1-to-1 mapping from the vector index to the index in the native array, but in some cases the mapping can be slightly more complex: A mutable vector may change its length, and this is implemented as a gap buffer, so the index calculation must adjust for the unused elements in the gap. A slice (sub-vector) may share the underlying native array with another vector, so the index calculation must adjust for the start offset.

Therefore we separate the index mapping logic (method effectiveIndex) from the code for accessing the native array (getRaw). Thus (vector-ref vec i) is implemented as vec.get(i), which in turn is implemented as vec.getRaw(vec.effectiveIndex(i)).

Mutating an element is similar: (vector-set! vec i value) is implemented as vec.set(i, value), which in turn is implemented as vec.setRaw(vec.effectiveIndex(i), value). In the following, for simplicity we'll mostly ignore mutation.

The same logic is used for uniform vectors. An F32 vector (F32Vector) additionally has getFloat and getFloatRaw methods that return unboxed float values. The vec.getFloat(i) method is vec.getFloatRaw(vec.effectiveIndex(i)). If the compiler knows it is dealing with an F32 vector, it generates a call to getFloat, avoiding boxing. For simplicity we'll mostly ignore uniform vectors in the following, but non-vector arrays can be similarly optimized.

All arrays (including vectors) implement the Array interface. The get method is generalized to take an array of indexes, but is still uses effectiveIndex, but generalized to take a vector of indexes (actually int[], a native int array). Thus arr.get(ivec) is still arr.getRaw(arr.effectiveIndex(ivec)).

With a few exceptions (such as the result of build-array) arrays that are not vectors are represented as transformations of other arrays, usually simple vectors, using the abstract class TransformedArray. In this case getRaw indirects to the base array: arr.getRaw(effi) is arr.base.getRaw(effi), and therefore arr.get(ivec) is arr.base.getRaw(arr.effectiveIndex(ivec)).

Both the get and effectiveIndex methods are overloaded to take 0, 1, 2, or many indexes. The is to avoid having to allocate an index array unnecessarily, but in the following we'll ignore this optimization.

A GeneralArray is a TransformedArray that takes a base array along with an offset and a stride vector. The effectiveIndex multiples each index by the corresponding stride, adds the offset, and then uses the result to call effectiveIndex on the base. A simple non-vector array, as allocated by the make-array or the array procedures returns a GeneralArray, using as the base a simple vector containing the elements in row-major order. The share-array procedure returns a GeneralArray. The bounds and strides are calculated from the shape and proc. If the argument array is a GeneralArray, the latter's base is used as an optimization.

The general case of array-index-share returns a ComposedArray, which is a TransformedArray that has a reference to the index arrays as well as the base array. See the resolve method in ComposedArray.java for the calculation used by effectiveIndex. If all of the indexes are linear (simple integers or integer ranges) then the result is optimized to a GeneralArray.

The implementation of array-index-ref is basically doing index-array-share and then making a simple (GeneralArray) immutable copy of the result. However, there are some optimizations and special cases. To implement index-array we just wrap a GeneralArray around a simple range.

The result of array-transform is a ProcTransformedArray, which is a TransformedArray that calls the supplied transform procedure in the effectiveIndex method.

A FlattenedArray is used to implement array->vector. It is a TransformedArray whose effectiveIndex maps the argument index to the raw-major-order effective index of the base array. If the argument array is a simple GeneralArray (that wraps a SimpleVector) it returns the latter's base, as an optimization. The array-reshape procedure first creates a FlattenedArray from the argument, and then wraps that in a GeneralArray. Implementing array-flatten is just creating a fresh mutable vector (possible a uniform vector) and then copying the elements in row-major order.

The BuiltArray class (which does not extend TransformedArray) is used to implement build-array by having get call the procedure on each access.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Title

Author

Status