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
email@example.com. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.
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:
build-arraywith a setter argument can handle the rest.
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
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,
array are simple.
A vector created by a vector literal, or standard R7RS or SRFI 4 procedures
is a simple vector and thus a simple array.
In addition, if the first argument to
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.)
#tif obj is 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 [
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 [
[ start [
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
>=:in place of
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.
Creates an unbounded (non-finite) range, where step defaults to 1. The result is an infinite sequence of values, starting with start, and followed by
(+ start step),
(+ start (* 2 step)), and so on. For example,
[3 by: 2]is the odd integers starting at 3.
[>:] 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 of a dimension are
exact integers with
(<= . A valid index along the
dimension is an exact integer
i that satisfies both
The length of the array along the dimension is the difference
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:
#(i 0) and
are respectively the lower bound and upper bound of dimension i.
For convenience, the procedures in this specification that
can accept a shape-specifier, as if converted by
(array-reshape array shape)
is equivalent to
(array-reshape array (->shape shape)).
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
eis an upper bound, with a zero lower bound. Equivalent to a range with start 0, step 1, and length e.
#(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.
#((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.
#(2 (0 3))and
`#((1 3) ,[1 size: 4]).
A canonical shape: A rank-2 array
Swhose own shape is
#(r 2). For each dimension
(<), the lower bound
(S, and the upper bound
#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
npairs of bounds, then a valid index to the array is any sequence
nexact integers where each
The shape of a
d-dimensional array is a
d* 2 array where the element at
k 0contains the lower bound for an index along dimension
kand the element at
k 1contains the corresponding upper bound, where
(apply shapeis equivalent to:
(apply array (vector (/ (length bounds) 2) 2) bounds)
Return the shape of array in the canonical (r 2) form. It is an error to attempt to modify the shape array.
Returns the number of dimensions of
array.(array-rank (make-array (shape 1 2 3 4)))
(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).
Return the total number of elements of array. This is the product of
(- (array-endfor every valid
shape obj ...
Returns a new array whose shape is given by
shapeand the initial contents of the elements are
obj... in row-major order. The array does not retain a reference to
(make-array shape value...
Returns a newly allocated mutable array whose shape is given by
valueis provided, then each element is initialized to it. If there is more than one
value, they are used in order, starting over when the
values are exhausted. If there is no
value, the initial contents of each element is unspecified. The array does not retain a reference to
(make-array #(2 4) 1 2 3 4 5)⇨ ╔#2a:2:4╗ ║1│2│3│4║ ╟─┼─┼─┼─╢ ║5│1│2│3║ ╚═╧═╧═╧═╝
Compatibility: Guile has an incompatible
(build-array shape getter [setter]
Construct avirtual arrayof the given
shapethat uses no storage for the elements. Instead, elements are calculated on demand by calling getter, which takes a single argument, an index vector.
There is no caching or memoization.
(build-array #2a((10 12) (0 3))
(let ((x (vector-ref ind 0)) (y (vector-ref ind 1)))
(- x y))))⇨ #2a@10:2:3 ║10│ 9│8║ ╟──┼──┼─╢ ║11│10│9║ ╚══╧══╧═╝
The resulting array is mutable if a setter is provided. The setter takes 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))))))))
Return a new immutable array of the specified
shapewhere each element is the corresponding row-major index. Same as
(array-reshape r shape)where size is the
array-sizeof the resulting array, and r is a range whose start is 0, step is 1, and the same size.
(index-array #2a((1 3) (2 6)))⇨ #2a@1:2@2:4 ║0│1│2│3║ ╟─┼─┼─┼─╢ ║4│5│6│7║ ╚═╧═╧═╧═╝
Given a rank-2 array
arr with integer indexes
j, the following all get the element of
(array-index-ref arr i j) (array-ref arr i j) (array-ref arr (vector i j))
(but not plain
array-ref) you can do generalized APL-style
slicing and indirect indexing.
(array-ref array k ...
Returns the contents of the element of
k.... The sequence
k... must be a valid index to
array. In the second form,
indexmust be a vector (a 0-based 1-dimensional array) containing
k....(array-ref (array #(2 3) 'uno 'dos 'tres 'cuatro 'cinco 'seis)) 1 0)
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))))
(3 1 4).
(array-index-ref array index ...
Generalized APL-style array indexing, where each
indexcan 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
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 theconcatenationof 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.)
marris the result of
is defined as:(array-ref
Mkgets as many indexes as its rank. If
Mkis 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-refis called on marr with valid indexes (within its shape), then no error is possible; any potentially invalid indexes must be caught by
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 commonsliceoperations 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║ ╚══╧══╝
[<:]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 [<:] )⇨ #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║ ╚══╧══╧══╧══╧══╝
(array-set! array k ... obj
(array-set! array index obj
objin the element of
k.... The result is unspecified. The sequence
k... must be a valid index to
array. In the second form,
indexmust 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))
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
value. You can use
(array-fill! (array-index-shareto set a subset of the array.
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! to modify one or multiple elements.
To modify a single element:
should be equivalent to:
You can set a slice (or all of the elements). In that case:
is equivalent to:
A view or transform of an array is an array
whose elements come from some other array
given some transform function
T that maps
a1 to be modified;
a1 may modify
(depending on the transform function).
The shape of
a2 is in general different than that of
mutable if and only if
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
transformfunction (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
arras in the
(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║ ╚══╧══╝
array-transformprocedure is a generalization of
share-arrayin that it does not require the
transformto be affine. Also note the different calling conversions for the
array-transformtakes a single argument (a vector of indexes), and returns a single result (a vector of indexes);
share-arraytakes 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-refwhich would return the selected element directly).
(array-reshape array shape
Creates a new array
narrayof the given
shape, such that
(array->vectorare equivalent. In other words, the
i’th element in row-major-order of
i’th element in row-major-order of
(array-size(as specified from the
shape) must be equal to
(array-size. The resulting
narrayis a view such that modifying
narrayand 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
shapeshape that shares elements of
proc. The procedure
procmust implement an affine function that returns indices of
arraywhen 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
procmeans 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
kdto a single index into a backing vector; the composition of this mapping and
proccan be recognised as
(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.
k1) ... (*
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))
Return a vector consisting of the elements of the
The result of
array-flattenis a fresh (mutable and simple) copy, not a view. The result of
array->vectoris a view: If
arrayis mutable, then modifying
arraychanges the flattened result and vice versa.(eq?
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
SimpleVector) uses an object array (
while an F32 vector (the class
uses an array of floats (a
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
from the code for accessing the native array (
(vector-ref vec i) is implemented
vec.get(i), which in turn is implemented as
Mutating an element is similar:
(vector-set! vec i value) is implemented
vec.set(i, value), which in turn is implemented as
In the following, for simplicity we'll mostly ignore mutation.
The same logic is used for uniform vectors.
An F32 vector (
F32Vector) additionally has
that return unboxed
vec.getFloat(i) method is
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
get method is generalized to take
an array of indexes, but is still uses
but generalized to take a vector of indexes (actually
arr.get(ivec) is still
With a few exceptions (such as the result of
arrays that are not vectors are represented as
transformations of other arrays, usually simple vectors,
using the abstract class
In this case
getRaw indirects to the base array:
are overloaded to take 0, 1, 2, or
The is to avoid having to allocate an index array unnecessarily,
but in the following we'll ignore this optimization.
GeneralArray is a
that takes a
base array along with an
effectiveIndex multiples each index by the
stride, adds the
offset, and then
uses the result to call
effectiveIndex on the
A simple non-vector array, as allocated by the
array procedures returns a
using as the
base a simple vector containing the
elements in row-major order.
share-array procedure returns a
The bounds and strides are calculated from the shape
If the argument array is a
base is used as an optimization.
The general case of
ComposedArray, which is a
that has a reference to the index arrays as well as the base array.
resolve method in
for the calculation used by
If all of the indexes are
linear (simple integers or integer ranges)
then the result is optimized to a
The implementation of
array-index-ref is basically
index-array-share and then making a simple
GeneralArray) immutable copy of the result.
However, there are some optimizations and special cases.
index-array we just
GeneralArray around a simple range.
The result of
array-transform is a
ProcTransformedArray, which is a
that calls the supplied transform procedure
FlattenedArray is used to implement
It is a
maps the argument index to the raw-major-order effective index
base array. If the argument array is a
GeneralArray (that wraps a
it returns the latter's
base, as an optimization.
array-reshape procedure first creates a
FlattenedArray from the argument, and then
wraps that in a
array-flatten is just creating a fresh
mutable vector (possible a uniform vector) and then copying the
elements in row-major order.
BuiltArray class (which does not extend
TransformedArray) is used to implement
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.