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.

- Received: 2018-11-02
- Draft #1 published: 2018-11-02
- Draft #2 published: 2018-11-17
- Draft #3 published: 2018-12-07
- Draft #4 published: 2019-03-05
- Draft #5 published: 2019-07-20
- Finalized: 2019-08-08

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.

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

Some notes comparing with SRFI 122:

- SRFI 122 invents more terminology and procedure names, and is less concerned with compatibility with previous SRFIs.
- SRFI 122 has a concept of storage classes.
I believe uniform vectors subsume most of the need,
and
`build-array`

with a`setter`argument can handle the rest. - SRFI 122 has a distinct interval type, which serves the purpose of the specification's shape. There are a number of potentially useful procedures for working with intervals, but it's not clear if they'd be used enough to justify standardization.

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.

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.

An array of rank 2 is frequently called a *matrix*.

Arrays may be mutable or immutable.

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.)

`(array?`

`obj``)`

Returns

`#t`

ifobjis an array, otherwise returns`#f`

. Note this also returns true for a (generalized) vector.

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), andlength. The sequence of values is the same as SRFI 1's`(iota`

.countstartstep)

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

stepmust be positive, and defaults to 1. The impliedlengthis the maximum such that all the valuesxsatisfy`(<`

, orxend)`(<=`

, respectively.xend)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.

`[`

`start` `<:`

`]`

`[`

`start` `by:`

`step``]`

Creates an unbounded (non-finite) range, where

stepdefaults to 1. The result is an infinite sequence of values, starting withstart, and followed by`(+`

,startstep)`(+`

, and so on. For example,start(* 2step))`[3 by: 2]`

is the odd integers starting at 3.

The syntax `[<:]`

or `[>:]`

is a pseudo-range. The `start` value is implicit and context-dependent.

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

The lower bound * b* and the upper bound

`e`

`(<= ``b`

`e`

)

. A valid index along the
dimension is an exact integer `i`

`(<= ``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 `#(`

and `i` 0)`#(`

are respectively the lower bound and upper bound of dimension `i` 1)`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

specifierto 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

is an upper bound, with a zero lower bound. Equivalent to a range with start 0, step 1, and length`e`

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

stepof 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

whose own shape is`S`

`#(`

. For each dimensionr2)(where`k`

`(<=`

and0)`k`

`(<`

), the lower bound`k`

)`r`

is`b`

_{k}`(S`

, and the upper bound0)`k`

is`e`

_{k}`(S`

.1)`k`

Examples:

`#2a((0 2) (0 3))`

and`#2a((1 3) (1 4))`

.

`(shape`

`bound` `...``)`

Returns a shape, in the canonical

`(`

form. The sequencer2)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... is the sequence`bound`

`b0`

...`e0`

`bk`

... of`ek`

pairs of bounds, then a valid index to the array is any sequence`n`

...`j0`

... of`jk`

exact integers where each`n`

satisfies`jk`

`(<=`

and`bk`

)`jk`

`(<`

.`jk`

)`ek`

The shape of a

-dimensional array is a`d`

* 2 array where the element at`d`

contains the lower bound for an index along dimension`k 0`

and the element at`k`

contains the corresponding upper bound, where`k 1`

satisfies`k`

`(<= 0`

and)`k`

`(<`

.`k`

)`d`

`(apply shape`

is equivalent to:)`bounds`

`(apply array (vector (/ (length`

bounds) 2) 2)bounds)

`(array-shape`

`array``)`

Return the shape of

arrayin 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)k0)

`(array-end`

`array` `k``)`

Returns the upper bound for the index along dimension

. The bound is exclusive — i.e. the first integer higher than the last legal index. Same as`k`

`(array-ref (array-shape`

.array)k1)

`(array-size`

`array``)`

Return the total number of elements of

array. This is the product of`(- (array-end`

for every valid`array`

) (array-start`k`

`array`

))`k`

.`k`

See also `array-reshape`

.

`(array`

`shape`

`obj` `...``)`

Returns a new array whose shape is given by

and the initial contents of the elements are`shape`

... in row-major order. The array does not retain a reference to`obj`

.`shape`

`(make-array`

`shape``)`

`(make-array`

`shape` `value...``)`

Returns a newly allocated mutable array whose shape is given by

. If`shape`

is provided, then each element is initialized to it. If there is more than one`value`

, they are used in order, starting over when the`value`

s are exhausted. If there is no`value`

, the initial contents of each element is unspecified. The array does not retain a reference to`value`

.`shape`

⇨ ╔#2a:2:4╗ ║1│2│3│4║ ╟─┼─┼─┼─╢ ║5│1│2│3║ ╚═╧═╧═╧═╝`(make-array #(2 4) 1 2 3 4 5)`

Compatibility:Guile has an incompatible`make-array`

procedure.

`(build-array`

`shape` `getter` [`setter`]`)`

Construct a

virtual arrayof the giventhat uses no storage for the elements. Instead, elements are calculated on demand by calling`shape`

getter, which takes a single argument, an index vector.There is no caching or memoization.

`(build-array #2a((10 12) (0 3))`

`(lambda (ind)`

`(let ((x (vector-ref ind 0)) (y (vector-ref ind 1)))`

⇨ #2a@10:2:3 ║10│ 9│8║ ╟──┼──┼─╢ ║11│10│9║ ╚══╧══╧═╝`(- x y))))`

The resulting array is mutable if a

setteris provided. Thesettertakes two arguments: An index vector, and the new value for the specified element. Below is a simple and space-efficient (but slow) implementation of sparse arrays: Most elements have a default initial value, but you can override specific elements.(define (make-sparse-array shape default-value) (let ((vals '())) ;; association list of (INDEX . VALUE) (build-array shape (lambda (I) (let ((v (assoc I vals))) (if v (cdr v) default-value))) (lambda (I newval) (let ((v (assoc I vals))) (if v (set-cdr! v newval) (set! vals (cons (cons I newval) vals))))))))

`(index-array`

`shape``)`

Return a new immutable array of the specified

where each element is the corresponding row-major index. Same as`shape`

`(array-reshape`

wherershape)sizeis the`array-size`

of the resulting array, andris a range whosestartis 0,stepis 1, and the samesize.⇨ #2a@1:2@2:4 ║0│1│2│3║ ╟─┼─┼─┼─╢ ║4│5│6│7║ ╚═╧═╧═╧═╝`(index-array #2a((1 3) (2 6)))`

Given a rank-2 array * arr* with integer indexes

`i`

`j`

`arr`

`[``i`

`j`

]

.
(array-index-refarrij) (array-refarrij) (array-refarr(vectorij))

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

at index`array`

.... The sequence`k`

... must be a valid index to`k`

. In the second form,`array`

must be a vector (a 0-based 1-dimensional array) containing`index`

....`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

can be either an array or an integer.`index`

If each

indexis an integer, or there is noindex, 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

. An integer is treated as rank-0 array. The shape of the result is the`index`

concatenationof 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

is the result of`marr`

`(array-index-ref`

then:`arr`

`M`

_{1}...)`M`

_{2}(array-refmarr`i`

_{11}...`i`

_{12}`i`

_{21}...)`i`

_{22}is defined as:

(array-ref(array-ref`arr`

`M`

_{1}`i`

_{11}...) (array-ref`i`

_{12}`M`

_{2}`i`

_{21}...) ...)`i`

_{22}Each

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.`M`

_{k}The resulting array

marris a fresh array that does not depend on any of the arguments. Specifically, if`array-ref`

is called onmarrwith 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))`

⇨ ╔#2a@1:3:4══╗ ║10│11│12│13║ ╟──┼──┼──┼──╢ ║20│21│22│23║ ╟──┼──┼──┼──╢ ║30│31│32│33║ ╚══╧══╧══╧══╝`arr`

⇨ 23`(array-index-ref arr 2 3)`

If one index is a vector and the rest are scalar integers, then the result is a vector:

⇨ #(23 21)`(array-index-ref arr 2 #(3 1))`

You can select a “sub-matrix” when all indexes are vectors:

⇨ ╔#2a:2:3═╗ ║23│21│23║ ╟──┼──┼──╢ ║13│11│13║ ╚══╧══╧══╝`(array-index-ref arr #(2 1) #(3 1 3))`

Using ranges for index vectors selects a rectangular sub-matrix.

;; Kawa range syntax — non-normative ⇨ ╔#2a:2:3═╗ ║11│12│13║ ╟──┼──┼──╢ ║21│22│23║ ╚══╧══╧══╝`(array-index-ref arr [1 <: 3] [1 <: 4))`

Using ranges makes for a convenient way to to express common

sliceoperations 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:

⇨ #3a╤══╗ ║23│21║ ╟──┼──╢ ║23│22║ ╠══╪══╣ ║13│11║ ╟──┼──╢ ║13│12║ ╚══╧══╝`(array-index-ref arr #(2 1) #2a((3 1) (3 2)))`

The pseudo-range

`[<:]`

can be used to select all the indexes along a dimension. To select row 2 (1-origin):⇨ #(20 21 22 23)`(array-index-ref arr 2 [<:])`

To reverse the order use

`[>:]`

:⇨ #(23 22 21 20)`(array-index-ref arr 2 [>:])`

To select column 3:

⇨ #2a╗ ║13║ ╟──╢ ║23║ ╟──╢ ║33║ ╚══╝`(array-index-ref arr [<:] [3])`

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:⇨ ╔#2a:3:5═╤══╤══╗ ║13│13│13│13│13║ ╟──┼──┼──┼──┼──╢ ║23│23│23│23│23║ ╟──┼──┼──┼──┼──╢ ║33│33│33│33│33║ ╚══╧══╧══╧══╧══╝`(array-index-ref arr [<:] [3 by: 0 size: 5])`

`(array-set!`

`array` `k` `...` `obj``)`

`(array-set!`

`array` `index` `obj``)`

Stores

in the element of`obj`

at index`array`

.... The result is unspecified. The sequence`k`

... must be a valid index to`k`

. In the second form,`array`

must be either a vector or a 0-based 1-dimensional array containing`index`

....`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

dstis replaced by the corresponding element insrc.

Compatibility:Guile has an`array-copy!`

with the reversed argument order.

`(array-fill!`

`array` `value``)`

Set all the values

to`array`

. You can use`value`

`(array-fill! (array-index-share`

to set a subset of the array.`array`

...)`indexes`

)`value`

applyinga 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`

A view or transform of an array is an array * a*
whose elements come from some other array

`a`_{1}

`T`

`a`_{2}

`a`_{1}

`(array-ref ``a`_{2}

`indexes`

)

is `(array-ref ``a`_{1}

(`T`

`indexes`

))

.
Modifying `a`_{2}

`a`_{1}

`a`_{1}

`a`_{2}

`a`_{2}

`a`_{1}

`a`_{2}

`a`_{1}

`(array-transform`

`array` `shape` `transform``)`

This is a general mechanism for creating a view. The result is a new array with the given

. Accessing this new array is implemented by calling the`shape`

function (which is`transform`

Tabove) on the index vector, which must return a new index vector valid for indexing the original. Here is an example (using the same`array`

`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)`

⇨ #3a:3@1:2:2 ║10│11║ ╟──┼──╢ ║12│13║ ╠══╪══╣ ║20│21║ ╟──┼──╢ ║22│23║ ╠══╪══╣ ║30│31║ ╟──┼──╢ ║32│33║ ╚══╧══╝`(+ (* 2 (- j 1)) k)))))`

The

`array-transform`

procedure is a generalization of`share-array`

in that it does not require theto be affine. Also note the different calling conversions for the`transform`

:`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. If each index is an integer, the result is a rank-0 array that is a view of the selected element (unlike`array`

`array-index-ref`

which would return the selected element directly).

`(array-reshape`

`array` `shape``)`

Creates a new array

of the given`narray`

, such that`shape`

`(array->vector`

and)`array`

`(array->vector`

are equivalent. In other words, the)`narray`

’th element in row-major-order of`i`

is the`narray`

’th element in row-major-order of`i`

. Hence`array`

`(array-size`

(as specified from the)`narray`

) must be equal to`shape`

`(array-size`

. The resulting)`array`

is a view such that modifying`narray`

also modifies`array`

and vice versa. If`narray`

arrayis simple, the result is also simple and uses the same underlying vector asarray.

`(share-array`

`array` `shape` `proc``)`

Returns a new array of

shape that shares elements of`shape`

through`array`

. The procedure`proc`

must implement an affine function that returns indices of`proc`

when given indices of the array returned by`array`

`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

means that each value must be a sum of multiples of the arguments passed to`proc`

, plus a constant.`proc`

Implementation note: arrays have to maintain an internal index mapping from indices

...`k1`

to a single index into a backing vector; the composition of this mapping and`kd`

can be recognised as`proc`

`(`

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.(*`+ n0`

`n1`

) ... (*`k1`

`nd`

))`kd`

Here is an example where the

arrayis 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

in row-major-order.`array`

The result of

`array-flatten`

is a fresh (mutable and simple) copy, not a view. The result of`array->vector`

is a view: Ifis mutable, then modifying`array`

changes the flattened result and vice versa.`array`

If

arrayis simple,`array->vector`

returns the underlying vector. Specifically, ifis a vector then:`vec`

(eq?(array->vector (array-reshape`vec`

`vec`

)))`shape`

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.

Copyright © Per Bothner 2019

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.

Author: Per Bothner Editor: Arthur A. Gleckler