Intervals and Generalized arrays
Bradley J. Lucier
This SRFI is currently in ``draft'' status. To see an
explanation of each status that a SRFI can hold, see
here.
It will remain in draft status until 2005/XX/XX, or as amended. To
provide input on this SRFI, please
mailto:srfi-XX@srfi.schemers.org
See instructions here
to subscribe to the list. You can access previous messages via
the archive of the mailing list.
This SRFI specifies an array mechanism for Scheme. Arrays as defined here are quite general, and benefit from a data type called intervals, which encapsulate the cross product of non-empty intervals of exact integers. These intervals specify the domain information for arrays. An array is then characterized as a mapping from multi-indices of exact integers (i0,...,id-1) contained in an interval to Scheme values. Additionally, specialized variants of arrays are specified to provide portable programs with efficient representations for common use cases.
An array, as commonly understood, provides a mapping from multi-indices (i0,...,id-1) of exact integers in a non-empty, rectangular, d-dimensional interval [l0, u0) x [l1, u1) x ... x [ld-1, ud-1) to Scheme objects. Thus, two things are necessary to specify an array: an interval and a mapping.
Since these two things are often sufficient for certain algorithms, we introduce in this SRFI a minimal set of interfaces for dealing with such arrays.
Specifically, an Array specifies a nonempty, multi-dimensional interval, called its domain, and a mapping from this domain to (single) Scheme objects. This mapping is called the getter of the array.
If this mapping can be changed, the array is said to be mutable and the mutation is effected by the array's setter. We call an object of this type a Mutable-array.
In general, we leave the implementation of arrays completely open. They may be defined simply by closures, or they may have hash tables or databases behind an implementation. If the getter and setter functions of a Mutable-array are defined by accessing and setting elements of a one-dimensional (heterogeneous or homogeneous) vector that are determined by a one-to-one function from the domain of the Array into the integers between 0 (inclusive) and the length of the backing-store vector (exclusive), the array is said to be fixed; a Fixed-array is an example of a Mutable-array.
Thus, we need the concept of an indexer, which is a one-to-one mapping whose domain is an Interval and whose range is contained in another Interval. Conceptually, an indexer is itself an Array that returns multiple values. An important subset of indexers are affine mappings (linear mappings plus constants) from one domain to another. We do not encapsulate indexers, with their domain Interval, range Interval, and multi-valued mapping, into a distinct type. Thus our Fixed-arrays are a slightly generalized form of Bawden-style arrays in that we allow non-affine indexers into the backing store of the array.
The backing store of a Fixed-array, which may be a heterogeneous or homogeneous vector, is created, accessed, etc., via the components of objects we call Fixed-array-manipulators. We define their properties below.
make-vector
, make-string
, etc., as low-level memory
allocators with little computation going on behind the scenes. Instantiating the objects of this SRFI may require non-trivial
computation behind the scenes, so I didn't want to name the instantiation routines make-whatever.(build-Interval lower-bounds: l0 l1 ... upper-bounds: u0 u1 ...)
comes closes, but it would take a lot of computation to check properly , and this isn't even a valid DSSSL argument list.
In the end I decided to just require the lower and upper bound arguments to be vectors. Interval-lower-bounds->list
. I think of this routine not as an getter (Interval-lower-bounds
would be an getter) but as a converter, like
vector->list
. I don't want to expose the inner storage mechanism for lower and upper bounds of Intervals, so I don't provide an getter, only these converters.Fixed-array-share!
and indexer to build-Fixed-array
are conceptual indexers,
the first multiple-valued and the second single-valued.Array-curry
gets its name from the
curry operator in programming---we are currying the getter of the Array and keeping careful track of the domains.
Interval-curry is simply given a parallel name (although it can be thought of as currying the
characteristic function of the interval, encapsulated here as Interval-contains-multi-index?
). Similarly,
Array-lazy-distinguish-one-axis
makes sense for Arrays, but the parallel function for Intervals is not very natural.(Interval-offset interval o0 o1 ...)
and
(Interval-cross-product interval1 interval2 ...)
(the inverse of Interval-curry
) and
(Interval-intersect interval1 interval2 ...)
which don't seem terribly natural for Arrays. If you could use these functions in your programs, tell me (windowing systems, etc.?).eq?
).). The only relation R where X is the empty set is the empty relation consisting
of no ordered pairs at all. Since there are no ordered pairs, there are no values in the range set Y, i.e., Y is the empty set. So the getter of an Array with
an empty interval as a domain would be able to return no values at all. So I don't understand constructions that allow Arrays with empty Intervals as domains to return a single value.
Since I don't understand it, I don't allow it.Intervals are sets of all multi-indices (i1,...,ik) such that l1<=i1<u1, ..., lk<=ik<uk, where the lower bounds (l1,...,lk) and the upper bounds (u1,...,uk) are specified as multi-indices of exact integers. The positive integer k is the dimension of the interval. It is required that l1<u1, ..., lk<uk.
Procedure: build-Interval lower-bounds upper-bounds
Create a new interval; lower-bounds
and upper-bounds
are nonempty vectors (of the same length) of exact integers that satisfy
(< (vector-ref lower-bounds i) (vector-ref upper-bounds i))
for
0<=i
<(vector-length lower-bounds)
. It is an error if
lower-bounds
and upper-bounds
do not satisfy these conditions.
Procedure: Interval? obj
Returns #t
if obj
is an interval, and #f
otherwise.
Procedure: Interval-dimension interval
If interval
is an interval built with
(build-Interval lower-bounds upper-bounds)
then Interval-dimension
returns (vector-length lower-bounds)
. It is an error to call Interval-dimension
if interval
is not an interval.
Procedure: Interval-lower-bound interval i
If interval
is an interval built with
(build-Interval lower-bounds upper-bounds)
and i
is an exact integer that satisfies
0 <=theni
<(vector-length lower-bounds)
,
Interval-lower-bound
returns
(vector-ref lower-bounds i)
. It is an error to call Interval-lower-bound
if interval
and i
do not satisfy these conditions.
Procedure: Interval-upper-bound interval i
If interval
is an interval built with
(build-Interval lower-bounds upper-bounds)
and i
is an exact integer that satisfies
0 <=theni
<(vector-length lower-bounds)
,
Interval-upper-bound
returns
(vector-ref upper-bounds i)
. It is an error to call Interval-upper-bound
if interval
and i
do not satisfy these conditions.
Procedure: Interval-lower-bounds->list interval
If interval
is an interval built with
(build-Interval lower-bounds upper-bounds)
then Interval-lower-bounds->list
returns (vector->list lower-bounds)
. It is an error to call
Interval-lower-bounds->list
if interval
does not satisfy these conditions.
Procedure: Interval-upper-bounds->list interval
If interval
is an interval built with
(build-Interval lower-bounds upper-bounds)
then Interval-upper-bounds->list
returns (vector->list upper-bounds)
. It is an error to call
Interval-upper-bounds->list
if interval
does not satisfy these conditions.
Procedure: Interval-volume interval
If interval
is an interval built with
(build-Interval lower-bounds upper-bounds)
then Interval-volume
returns
(apply * (map - (Interval-upper-bounds->list interval) (Interval-lower-bounds->list interval))
It is an error to call Interval-volume
if interval
does not satisfy this condition.
Procedure: Interval= interval1 interval2
If interval1
and interval2
are intervals built with
(build-Interval lower-bounds1 upper-bounds1)
and
(build-Interval lower-bounds2 upper-bounds2)
respectively, then Interval=
returns
(and (equal? lower-bounds1 lower-bounds2) (equal? upper-bounds1 upper-bounds2)
It is an error to call Interval=
if interval1
or interval2
do not satisfy this condition.
Procedure: Interval-subset? interval1 interval2
If interval1
and interval2
are intervals of the same dimension built with
(build-Interval lower-bounds1 upper-bounds1)
and
(build-Interval lower-bounds2 upper-bounds2)
respectively, then Interval-subset?
returns
(and (equal? (map >= (vector->list lower-bounds1) (vector->list lower-bounds2)) (map (lambda (x) #t) (vector->list lower-bounds1))) (equal? (map <= (vector->list upper-bounds1) (vector->list upper-bounds2)) (map (lambda (x) #t) (vector->list lower-bounds1))))
It is an error to call Interval-subset?
if interval1
or interval2
do not satisfy this condition.
Procedure: Interval-contains-multi-index? interval index-0 ...
If interval
is an Interval with dimension d and index-0
, ..., form a multi-index of length d,
then Interval-contains-multi-index?
returns #t
if and only if
(Interval-lower-bound interval j) <= index-j < (Interval-lower-bound interval j)
for 0<= j < d.
Procedure: Interval-curry interval left-dimension
Conceptually, Interval-curry
takes a d-dimensional interval [l0, u0) x [l1, u1) x ... x [ld-1, ud-1)
and splits it into two parts
[l0, u0) x [l1, u1) x ... x [lleft-dimension - 1, uleft-dimension - 1)and
[lleft-dimension, uleft-dimension) x ... x [ld-1, ud-1)This function, the inverse of Cartesian products or cross products of intervals, is used to keep track of the domains of curried arrays.
More precisely, if interval
is an Interval and left-dimension
is an exact integer that satisfies
0 < left-dimension < (Interval-dimension interval)
then Interval-curry
returns two intervals:
(values (build-Interval (vector (Interval-lower-bound interval 0) ... (Interval-lower-bound interval (- left-dimension 1))) (vector (Interval-upper-bound interval 0) ... (Interval-upper-bound interval (- left-dimension 1)))) (build-Interval (vector (Interval-lower-bound interval left-dimension) ... (Interval-lower-bound interval (- (Interval-dimension interval) 1))) (vector (Interval-upper-bound interval left-dimension) ... (Interval-upper-bound interval (- (Interval-dimension interval) 1)))))
It is an error to call Interval-curry
if its arguments do not satisfy these conditions.
Note: This operation projects the original interval onto complementary sets of axes. It is not the most
general projection possible, but it is the projection useful in implementing various currying operations on
arrays, so we named it Interval-curry
rather than a name associated with projections.
Procedure: Interval-distinguish-one-axis interval index
There are many natural operations on Arrays that work along a single axis of the domain of an Array.
If you have an Array where one axis represents time, for example, and the other axes represent space, then you may want to do
time-series analysis along the time axis for each point in space. In another example,
one way to compute a two-dimensional Fourier or wavelet transform is to compute one-dimensional transforms along each row, then
one-dimensional transforms along each column. (Transforms that have this computational structure are called "separable".) Interval-curry
is used to transform a d-dimensional Interval into multiple (in fact, a d-1 dimensional Interval) one-dimensional intervals (which we call "pencils") along a given axis.
If interval
is an interval and
(Interval-dimension interval)
is greater than one, and
0 <= index < (Interval-dimension interval)
then Interval-distinguish-one-axis
returns
(values (build-Interval (vector (Interval-lower-bound interval 0) ... ; leaving out (Interval-lower-bound interval index) (Interval-lower-bound interval (- left-dimension 1))) (vector (Interval-upper-bound interval 0) ... ; leaving out (Interval-upper-bound interval index) (Interval-upper-bound interval (- left-dimension 1)))) (build-Interval (vector (Interval-lower-bound interval index)) (vector (Interval-upper-bound interval index))))
It is an error to call Interval-distinguish-one-axis
if its arguments do not satisfy these conditions.
Note: This operation projects the original interval onto complementary sets of axes. It is not the most
general projection possible, but it is the projection useful in implementing Array-lazy-distinguish-one-axis
, so we named
it Interval-distinguish-one-axis
rather than a name associated with projections.
Procedure: Interval-for-each f interval
Procedure: Interval-for-each-serial f interval
These routines assume that interval
is an interval and f
is a routine whose domain includes elements of interval
. It is an error to call
Interval-for-each
if interval
and f
do not satisfy these conditions.
Interval-for-each
calls f
on each element of interval
; Interval-for-each
assumes that f
is thread-safe.
Interval-for-each-serial
calls f
on each element of interval
in lexicographical order.
Procedure: Interval-reduce f operator identity interval
Procedure: Interval-reduce-serial f operator identity interval
If interval
is an interval and f
is a routine whose domain includes elements of interval
, then
Interval-reduce-serial
returns
(... (operator (operator (operator identity (f multi-index1)) (f multi-index2)) (f multi-index3)) ...)
where multi-index1
, multi-index2
, ... are the multi-indices in interval
in lexicographical order.
Interval-reduce
returns the same value when operator is associative and thread-safe, and f is thread-safe, and
it may assume these properties.
It is an error to call Interval-reduce
or Interval-reduce-serial
if interval
and f
do not satisfy these conditions.
Procedure: build-Array domain getter
If domain
is an Interval and getter
is a function from
domain
to Scheme objects, then build-Array
return an array with domain domain
and getter getter
. It is an error to call build-Array
if domain
and getter
do not satisfy these conditions.
Example:
(define a (build-Array (build-Interval '#(1 1) '#(11 11)) (lambda (i j) (if (= i j) 1 0))))defines an Array that returns 1 when i=j and 0 otherwise.
Procedure: Array? obj
Returns #t
if and only if obj
is an Array.
Procedure: Array-domain array
If array
is an Array built by
(build-Array domain getter)
then Array-domain
returns domain
.
It is an error to call Array-domain
if array
is not an Array.
Procedure: Array-getter array
If array
is an Array built by
(build-Array domain getter)
then Array-getter
returns getter
.
It is an error to call Array-getter
if array
is not an Array.
Example:
(define a (build-Array (build-Interval '#(1 1) '#(11 11)) (lambda (i j) (if (= i j) 1 0)))) ((Array-getter a) 3 3) => 1 ((Array-getter a) 2 3) => 0 ((Array-getter a) 11 0) => is an error, which may be signaled
Procedure: Array-lazy-map f array . arrays
If array
, (car arrays)
, ... all have the same domain, then Array-lazy-map
returns a new Array with the same domain and getter
(lambda multi-index (apply f (map (lambda (g) (apply g multi-index)) (map Array-getter (cons array arrays)))))
Procedure: Array-lazy-curry array outer-dimension
If array
is an Array and outer-dimension
is an exact integer that satisfies
0 < outer-dimension < (Interval-dimension (Array-domain array))
then Array-lazy-curry
returns
(call-with-values (lambda () (Interval-curry (Array-domain array) outer-dimension)) (lambda (outer-interval inner-interval) (build-Array outer-interval (lambda outer-multi-index (build-Array inner-interval (lambda inner-multi-index (apply (Array-getter array) (append outer-multi-index inner-multi-index))))))))
It is an error to call Array-lazy-curry
if its arguments do not satisfy these conditions.
Notes: This function currys (Array-getter array)
while keeping track of the
domains of the outer and inner lambdas.
It is expected that Array-lazy-curry
will specialize the construction of
(lambda outer-multi-index (build-Array inner-interval (lambda inner-multi-index (apply (Array-getter array) (append outer-multi-index inner-multi-index)))))
and
(lambda inner-multi-index (apply (Array-getter array) (append outer-multi-index inner-multi-index)))
Example:
(define a (build-Array (build-Interval '#(0 0) '#(10 10)) list)) ((Array-getter a) 3 4) => (3 4) (define curried-a (Array-lazy-curry a 1)) ((Array-getter ((Array-getter curried-a) 3)) 4) => (3 4)
Procedure: Array-lazy-distinguish-one-axis array index
If array
is an Array and
(Interval-dimension (Array-domain interval))
is greater than one, and
0 <= index < (Interval-dimension (Array-domain interval))
then Array-lazy-distinguish-one-axis
returns
(call-with-values (lambda () (Interval-distinguish-one-axis (Array-domain array) index)) (lambda (outer-interval inner-interval) (build-Array outer-interval (lambda outer-multi-index (build-Array inner-interval (lambda (m) (apply (Array-getter array) (insert-arg-into-arg-list m outer-index index))))))))
where we define
(define (insert-arg-into-arg-list arg arg-list index) (define (helper arg-list i) (if (= i 0) (cons arg arg-list) (cons arg (helper (cdr arg-list) (- i 1))))) (helper arg-list index))
It is an error to call Array-lazy-distinguish-one-axis
if its arguments do not satisfy these conditions.
Notes: This function is introduced to facilitate distinguishing one-dimensional "pencils" in the domains of Arrays. This is useful because it simplifies programming separable multi-dimensional signal processing algorithms (including the Discrete Fourier Transform and Discrete Wavelet Transforms) and time-series algorithms.
It is expected that Array-lazy-distinguish-one-axis
will specialize the construction of
(lambda outer-multi-index (build-Array inner-interval (lambda (m) (apply (Array-getter array) (insert-arg-into-arg-list m outer-index index)))))
and
(lambda (m) (apply (Array-getter array) (insert-arg-into-arg-list m outer-index index)))
Procedure: Array-for-each f array . arrays
If array
, (car arrays)
, ... all have the same domain domain
, then Array-for-each
calls
(Interval-for-each (lambda multi-index (apply f (map (lambda (g) (apply g multi-index)) (map Array-getter (cons array arrays))))) (Array-domain array))
It is expected that Array-lazy-map
and Array-for-each
will specialize the construction of
(lambda multi-index (apply f (map (lambda (g) (apply g multi-index)) (map Array-getter (cons array arrays)))))
Procedure: Array-reduce operator identity array
If array is an Array then Array-reduce
calls (Interval-reduce (Array-getter array) operator identity (Array-domain array))
.
Procedure: build-Mutable-array domain getter setter
Assume that domain
is an Interval of dimension n
and that getter
and
setter
are two routines that satisfy: If
(i1,...,in) != (j1,...,jn)
are elements of domain
and
(getter j1 ... jn) => x
then "after"
(setter v i1 ... in)
we have
(getter j1 ... jn) => x
and
(getter i1,...,in) => v
Then build-Mutable-array
builds a Mutable-array with domain domain
, getter getter
and
setter setter
. A Mutable-array is an Array. It is an error to call build-Mutable-array
if its arguments do not satisfy these conditions.
Procedure: Mutable-array? obj
Returns #t
if and only if obj
is a Mutable-array. Note: Mutable-arrays are Arrays.
Procedure: Mutable-array-domain array
If array
is a Mutable-array built by
(build-Mutable-array domain getter setter)
then Mutable-array-domain
returns domain
. It is an error to call Mutable-array-domain
if array
is not a Mutable-array.
Procedure: Mutable-array-getter array
If array
is a Mutable-array built by
(build-Mutable-array domain getter setter)
then Mutable-array-getter
returns getter
. It is an error to call Mutable-array-getter
if array
is not a Mutable-array.
Procedure: Mutable-array-setter array
If array
is a Mutable-array built by
(build-Mutable-array domain getter setter)
then Mutable-array-setter
returns setter
. It is an error to call Mutable-array-setter
if array
is not a Mutable-array.
Example:
(define sparse-array (let ((domain (build-Interval '#(0 0) '#(1000000 1000000))) (sparse-rows (make-vector 1000000 '()))) (build-Mutable-array domain (lambda (i j) (cond ((assv j (vector-ref sparse-rows i)) => cdr) (else 0.0))) (lambda (v i j) (cond ((assv j (vector-ref sparse-rows i)) => (lambda (pair) (set-cdr! pair v))) (else (vector-set! sparse-rows i (cons (cons j v) (vector-ref sparse-rows i))))))))) ((Mutable-array-getter sparse-array) 12345 6789) => 0. ((Mutable-array-getter sparse-array) 0 0) => 0. ((Mutable-array-setter sparse-array) 1.0 0 0) => undefined ((Array-getter sparse-array) 12345 6789) => 0. ((Array-getter sparse-array) 0 0) => 1.
Procedure: Mutable-array-lazy-curry array outer-dimension
If array
is a Mutable-array and outer-dimension
is an exact integer that satisfies
0 < outer-dimension < (Interval-dimension (Mutable-array-domain array))
then Mutable-array-lazy-curry
returns
(call-with-values (lambda () (Interval-curry (Mutable-array-domain array) outer-dimension)) (lambda (outer-interval inner-interval) (build-Array outer-interval (lambda outer-multi-index (build-Mutable-array inner-interval (lambda inner-multi-index (apply (Mutable-array-getter array) (append outer-multi-index inner-multi-index))) (lambda (v . inner-multi-index) (apply (Mutable-array-setter array) v (append outer-multi-index inner-multi-index))))))))
It is an error to call Mutable-array-lazy-curry
if its arguments do not satisfy these conditions.
Notes: This function currys (Mutable-array-getter array)
and (Mutable-array-setter array)
while keeping track of the
domains of the outer and inner lambdas.
It is expected that Mutable-array-lazy-curry
will specialize the construction of
(lambda outer-multi-index (build-Mutable-array inner-interval (lambda inner-multi-index (apply (Mutable-array-getter array) (append outer-multi-index inner-multi-index))) (lambda (v . inner-multi-index) (apply (Mutable-array-setter array) v (append outer-multi-index inner-multi-index)))))
and
(lambda inner-multi-index (apply (Mutable-array-getter array) (append outer-multi-index inner-multi-index)))
and
(lambda (v . inner-multi-index) (apply (Mutable-array-setter array) v (append outer-multi-index inner-multi-index)))
Procedure: Mutable-array-lazy-distinguish-one-axis array index
If array
is a Mutable-array and
(Interval-dimension (Mutable-array-domain interval))
is greater than one, and
0 <= index < (Interval-dimension (Mutable-array-domain interval))
then Mutable-array-lazy-distinguish-one-axis
returns
(call-with-values (lambda () (Interval-distinguish-one-axis (Mutable-array-domain array) index)) (lambda (outer-interval inner-interval) (build-array outer-interval (lambda outer-multi-index (build-Mutable-array inner-interval (lambda (m) (apply (Mutable-array-getter array) (insert-arg-into-arg-list m outer-index index))) (lambda (v m) (apply (Mutable-array-setter array) v (insert-arg-into-arg-list m outer-index index))))))))
where we define
(define (insert-arg-into-arg-list arg arg-list index) (define (helper arg-list i) (if (= i 0) (cons arg arg-list) (cons arg (helper (cdr arg-list) (- i 1))))) (helper arg-list index))
It is an error to call Mutable-array-lazy-distinguish-one-axis
if its arguments do not satisfy these conditions.
Notes: This function is introduced to facilitate distinguishing one-dimensional "pencils" in the domains of Mutable-arrays. This is useful because it simplifies programming separable multi-dimensional signal processing algorithms (including the Discrete Fourier Transform and Discrete Wavelet Transforms) and time-series algorithms.
It is expected that Mutable-array-lazy-distinguish-one-axis
will specialize the construction of
(lambda outer-multi-index (build-Mutable-array inner-interval (lambda (m) (apply (Mutable-array-getter array) (insert-arg-into-arg-list m outer-index index))) (lambda (v m) (apply (Mutable-array-setter array) v (insert-arg-into-arg-list m outer-index index)))))
and
(lambda (m) (apply (Mutable-array-getter array) (insert-arg-into-arg-list m outer-index index)))
and
(lambda (v m) (apply (Mutable-array-setter array) v (insert-arg-into-arg-list m outer-index index)))
Procedure: build-Fixed-array-manipulators getter setter maker length default
Here we assume the following relationships between the arguments of build-Fixed-array-manipulators
. Assume that the "elements" of
the backing store are of some "type", either heterogeneous (all Scheme types) or homogeneous (of some restricted type).
(maker n value)
returns an object containing n
elements of value value
.v
is an object created by (maker n value)
and 0 <= i
< n
, then (getter v i)
returns the value of the i
'th element of v
.v
is an object created by (maker n value)
and 0 <= i
< n
, then (setter v i val)
sets the value of the i
'th element of v
to val
.v
is an object created by (maker n value)
then (length v)
returns n
.In this case, build-Fixed-array-manipulators
returns an object of type Fixed-array-manipulators. Otherwise, it is an error to call build-Fixed-array-manipulators
Note that we assume that getter
and setter
generally take O(1) time to execute.
Procedure: Fixed-array-manipulators-getter m
If m
is an object created by
(build-Fixed-array-manipulators getter setter maker length default)
then Fixed-array-manipulators-getter
returns getter
. Otherwise, it is an error to call Fixed-array-manipulators-getter
.
Procedure: Fixed-array-manipulators-setter m
If m
is an object created by
(build-Fixed-array-manipulators getter setter maker length default)
then Fixed-array-manipulators-setter
returns setter
. Otherwise, it is an error to call Fixed-array-manipulators-setter
.
Procedure: Fixed-array-manipulators-maker m
If m
is an object created by
(build-Fixed-array-manipulators getter setter maker length default)
then Fixed-array-manipulators-maker
returns maker
. Otherwise, it is an error to call Fixed-array-manipulators-maker
.
Procedure: Fixed-array-manipulators-length m
If m
is an object created by
(build-Fixed-array-manipulators getter setter maker length default)
then Fixed-array-manipulators-length
returns length
. Otherwise, it is an error to call Fixed-array-manipulators-length
.
Procedure: Fixed-array-manipulators-default m
If m
is an object created by
(build-Fixed-array-manipulators getter setter maker length default)
then Fixed-array-manipulators-default
returns default
. Otherwise, it is an error to call Fixed-array-manipulators-default
.
The following Fixed-array-manipulators are defined:
(define generic-array-manipulators (build-Fixed-array-manipulators vector-ref vector-set! make-vector vector-length #f))
Furthermore, sX-array-manipulators
are defined for X
=8, 16, 32, and 64 (which have default values 0 and
manipulate exact integer values between -2X-1 and
2X-1-1 inclusive),
uX-array-manipulators
are defined for X
=1, 8, 16, 32, and 64 (which have default values 0 and manipulate exact integer values between 0 and
2X-1 inclusive), and
fX-array-manipulators
are defined for X
= 32 and 64 (which have default value 0.0 and manipulate 32- and 64-bit floating-point numbers). Each of these
could be defined simply as generic-array-manipulators, but it is assumed that implementations with homogeneous arrays will give definitions
that either save space, avoid boxing, etc., for the specialized arrays.
Procedure: affine-indexer= indexer1 indexer2 interval
If indexer1
and indexer2
are one-to-one affine mappings from interval
to the interval [0,K)
for some K
, then affine-indexer=
returns #t
if indexer1
and indexer2
take the same values on all elements of interval
;
otherwise affine-indexer=
returns #f
. It is an error to call affine-indexer=
if its
arguments don't satisfy these conditions.
Procedure: build-Fixed-array domain: domain manipulators: manipulators [ body: body ] [ indexer: indexer ] [ initializer-value: initializer-value ] [ affine: affine? ]
Builds a Fixed-array. domain
must be an Interval; manipulators
must
be Fixed-array-manipulators; if body
is given, it must be of the same type as that returned by
(Fixed-array-manipulators-maker manipulators)
; if initializer-value
is given, it must be storable
in body
; at most one of initializer-value
and body
can be given; if indexer
is given, it must be a one-to-one mapping from domain
to
[0,((Fixed-array-manipulators-length manipulators) body)
); affine
must be a list of booleans,
with length (Interval-dimension domain)
;
the getter and setter of the result are defined by
(lambda (i_0 ... i_n-1) ((Fixed-array-manipulators-getter manipulators) body (indexer i_0 ... i_n-1)))and
(lambda (v i_0 ... i_n-1) ((Fixed-array-manipulators-setter manipulators) body (indexer i_0 ... i_n-1) v))The default values for arguments that are omitted are as follows:
Initializer-value: (Fixed-array-manipulators-default manipulators)
Body:
((Fixed-array-manipulators-maker manipulators) (Interval-volume domain) initializer-value)
Indexer: The one-to-one mapping of elements of domain
to [0,(Interval-volume domain)
) in
lexicographical order. Note that this default mapping is affine.
Affine: The default is a list of #t
of the appropriate length
if the default indexer is used, otherwise the default list consists entirely of #f
.
Procedure: Fixed-array? obj
Returns #t
if obj
is a Fixed-array, and #f
otherwise. A Fixed-array is a Mutable-array, and hence an Array.
Procedure: Fixed-array-domain array
If array
is a Fixed-arraythen Fixed-array-domain
returns its domain. It is an error to call Fixed-array-domain
if array
is not a Fixed-array.
Procedure: Fixed-array-getter array
If array
is a Fixed-array
then Fixed-array-getter
returns its getter. It is an error to call Fixed-array-getter
if array
is not a Fixed-array.
Procedure: Fixed-array-setter array
If array
is a Fixed-array
then Fixed-array-setter
returns its setter . It is an error to call Fixed-array-setter
if array
is not a Fixed-array.
Procedure: Fixed-array-body array
Returns the body of array
. It is an error to call Fixed-array-body
with an argument that is not a Fixed-array.
Procedure: Fixed-array-indexer array
Returns the indexer of array
. It is an error to call Fixed-array-indexer
with an argument that is not a Fixed-array.
Procedure: Fixed-array-manipulators array
Returns the manipulators of array
. It is an error to call Fixed-array-manipulators
with an argument that is not a Fixed-array.
Procedure: Fixed-array-affine array
Returns a list of booleans. (list-ref (Fixed-array-affine array) i)
is true if and only if
(Fixed-array-indexer array)
is affine in its i
'th argument.
It is an error to call Fixed-array-affine?
with an argument that is not a Fixed-array.
Procedure: Fixed-array-share! array new-domain new-domain->old-domain new-domain->old-domain-is-affine
Constructs a new Fixed-array that shares the body of the Fixed-array array
.
The default value of new-domain->old-domain-is-affine
is #t. Returns an object that
is behaviorally equivalent to
(build-Fixed-array domain: new-domain manipulators: (Fixed-array-manipulators array) body: (Fixed-array-body array) indexer: (lambda multi-index (call-with-values (lambda () (apply new-domain->old-domain multi-index)) (Fixed-array-indexer array))) affine?: (and (Fixed-array-affine? array) new-domain->old-domain-is-affine))
new-domain->old-domain
must be a one-to-one mapping from (Array-domain array)
to
new-domain
; new-domain->old-domain-is-affine
must be a boolean variable that is #t
only if new-domain->old-domain
is an affine mapping
Note: It is assumed that if new-domain->old-domain
and (Fixed-array-indexer array)
are both
affine, then this affine structure will be used to simplify
(lambda multi-index (call-with-values (lambda () (apply new-domain->old-domain multi-index)) (Fixed-array-indexer array)))
Procedure: Fixed-array-lazy-curry array outer-dimension
It is an error to call Fixed-array-lazy-curry
unless
array
is a Fixed-array
and outer-dimension
is an exact integer that satisfies
0 < outer-dimension < (Interval-dimension (Fixed-array-domain array)).
If array
has an affine indexer then Fixed-array-lazy-curry
returns
(call-with-values (lambda () (Interval-curry (Fixed-array-domain array) outer-dimension)) (lambda (outer-interval inner-interval) (build-Array outer-interval (lambda outer-multi-index (Fixed-array-share! array outer-interval (lambda inner-multi-index (apply values (append outer-multi-index inner-multi-index))))))))
If array
does not have an affine indexer then Fixed-array-lazy-curry
returns
(Mutable-array-lazy-curry array outer-dimension)
.
Notes: This function currys (Fixed-array-getter array)
and (Fixed-array-setter array)
while keeping track of the
domains of the outer and inner lambdas.
It is expected that Fixed-array-lazy-curry
will specialize the construction of
(lambda outer-multi-index
(Fixed-array-share! array
outer-interval
(lambda inner-multi-index
(apply values (append outer-multi-index inner-multi-index)))))
Procedure: Fixed-array-lazy-distinguish-one-axis array index
It is an error to call Fixed-array-lazy-curry
unless
array
is a Fixed-array and
(Interval-dimension (Fixed-array-domain interval))
is greater than one, and
0 <= index < (Interval-dimension (Fixed-array-domain array))
If array
has an affine indexer then Fixed-array-lazy-distinguish-one-axis
returns
(call-with-values (lambda () (Interval-distinguish-one-axis (Fixed-array-domain array) index)) (lambda (outer-interval inner-interval) (build-Array outer-interval (lambda outer-multi-index (Fixed-array-share! array inner-interval (lambda (m) (apply values (insert-arg-into-arg-list m outer-index index))))))))
where we define
(define (insert-arg-into-arg-list arg arg-list index) (define (helper arg-list i) (if (= i 0) (cons arg arg-list) (cons arg (helper (cdr arg-list) (- i 1))))) (helper arg-list index))
If array
does not have an affine indexer then Fixed-array-lazy-distinguish-one-axis
returns (Mutable-array-lazy-distinguish-one-axis array index)
.
Notes: This function is introduced to facilitate distinguishing one-dimensional "pencils" in the domains of Fixed-arrays. This is useful because it simplifies programming separable multi-dimensional signal processing algorithms (including the Discrete Fourier Transform and Discrete Wavelet Transforms) and time-series algorithms.
It is expected that Fixed-array-lazy-distinguish-one-axis
will specialize the construction of
(lambda outer-multi-index (Fixed-array-share! array inner-interval (lambda (m) (apply values (insert-arg-into-arg-list m outer-index index)))))
Procedure: Array->Fixed-array result-manipulators array
Procedure: Array->Fixed-array-serial result-manipulators array
If array
is an Array whose elements can be manipulated by the Fixed-array-manipulators
result-manipulators
, then the Fixed-array returned by Array->Fixed-array
can be defined by:
(let ((result (build-Fixed-array domain: (Array-domain array) manipulators: result-manipulators))) (Interval-for-each (lambda multi-index (apply (Fixed-array-setter result) (apply (Array-getter array) multi-index) multi-index)) (Array-domain array)) result)
Thus, Array->Fixed-array
assumes that (Array-getter array)
is thread-safe, and does not specify
the order in which (Array-getter array)
is applied to the multi-indices in (Array-domain array)
.
Similarly, the Fixed-array returned by Array->Fixed-array-serial
can be defined by:
(let ((result (build-Fixed-array domain: (Array-domain array) manipulators: result-manipulators))) (Interval-for-each-serial (lambda multi-index (apply (Fixed-array-setter result) (apply (Array-getter array) multi-index) multi-index)) (Array-domain array)) result)
Thus, Array->Fixed-array-serial
evaluates (Array-getter array)
to the multi-indices in
(Array-domain array)
in lexicographical order.
Procedure: Array-map result-manipulators f array . arrays
If array
, (car arrays)
, etc., are all Arrays with the same domain, then
Array-map
returns
(Array->Fixed-array result-manipulators (build-Array (Array-domain array) (lambda multi-index (apply f (map (lambda (g) (apply g multi-index)) (map Array-getter (cons array arrays)))))))
Note: I'd like to redefine this function so that it doesn't necessarily call Array->Fixed-array
, so the getter is not
necessarily called in strict lexicographical order.
We provide an implemenation in Gambit-C; the nonstandard techniques used
in the implementation are: DSSSL-style optional and keyword arguments; a
unique object to indicate absent arguments; define-structure
;
and define-macro
.
Final SRFIs 25, 47, 58, and 63 deal with "Multi-dimensional Array Primitives", "Array", "Array Notation", and "Homogeneous and Heterogeneous Arrays", respectively. Each of these previous SRFIs deal with what we call in this SRFI Fixed-arrays. Many of the functions in these previous SRFIs have corresponding forms in this SRFI. For example, from SRFI 63, we can translate:
(array? obj)
(Array? obj)
(Array-rank a)
(Domain-dimension (Array-domain obj))
(make-array prototype k1 ...)
(build-Fixed-array (build-Interval (vector 0 ...) (vector k1 ...)) manipulators)
.(make-shared-array array mapper k1 ...)
(Fixed-array-share! array (build-Interval (vector 0 ...) (vector k1 ...)) mapper)
(array-in-bounds? array index1 ...)
(Interval-contains-multi-index? (Array-domain array) index1 ...)
(array-ref array k1 ...)
((Array-getter array) k1 ...)
(array-set! array obj k1 ...)
((Array-setter array) obj k1 ...)
At the same time, this SRFI has some special features:
(define make-pgm cons) (define pgm-greys car) (define pgm-pixels cdr) (define (read-pgm file) (define (read-pgm-object port) (skip-white-space port) (let ((o (read port))) (read-char port) ; to skip the newline or next whitespace (if (eof-object? o) (error "reached end of pgm file") o))) (define (skip-to-end-of-line port) (let loop ((ch (read-char port))) (if (not (eq? ch #\newline)) (loop (read-char port))))) (define (white-space? ch) (case ch ((#\newline #\space #\tab) #t) (else #f))) (define (skip-white-space port) (let ((ch (peek-char port))) (cond ((white-space? ch) (read-char port) (skip-white-space port)) ((eq? ch #\#) (skip-to-end-of-line port)(skip-white-space port)) (else #f)))) (call-with-input-file file (lambda (port) (let* ((header (read-pgm-object port)) (columns (read-pgm-object port)) (rows (read-pgm-object port)) (greys (read-pgm-object port))) (make-pgm greys (Array->Fixed-array generic-array-manipulators (build-Array (build-Interval '#(0 0) (vector rows columns)) (cond ((or (eq? header 'p5) ;; pgm binary (eq? header 'P5)) (if (< greys 256) (lambda (i j) ;; one byte/pixel (char->integer (read-char port))) (lambda (i j) ;; two bytes/pixel, little-endian (let* ((first-byte (char->integer (read-char port))) (second-byte (char->integer (read-char port)))) (+ (* second-byte 8) first-byte))))) ((or (eq? header 'p2) ;; pgm ascii (eq? header 'P2)) (lambda (i j) (read port))) (else (error "read-pgm: not a pgm file"))))))))))
(define c32-array-manipulators (build-Fixed-array-manipulators (lambda (body i) ;; getter (make-rectangular (f32vector-ref body (* 2 i)) (f32vector-ref body (+ (* 2 i) 1)))) (lambda (body i obj) ;; setter (f32vector-set! body (* 2 i) (real-part obj)) (f32vector-set! body (+ (* 2 i) 1) (imag-part obj))) (lambda (n val) ;; maker (let ((l (* 2 n)) (re (real-part val)) (im (imag-part val))) (let ((result (make-f32vector l))) (do ((i 0 (+ i 2))) ((= i l) result) (f32vector-set! result i re) (f32vector-set! result (+ i 1) im))))) (lambda (body) ;; length (quotient (f32vector-length body) 2)) 0.+0.i ;; default ))