Title

Intervals and Generalized arrays

Author

Bradley J. Lucier

Status

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.

• Received 2005/XX/XX

Abstract

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 (i₀,...,i_d-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.

Rationale

An array, as commonly understood, provides a mapping from multi-indices (i₀,...,i_d-1) of exact integers in a non-empty, rectangular, d-dimensional interval [l₀, u₀) x [l₁, u₁) x ... x [l_d-1, u_d-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 accessor 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 accessor 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.

Issues and Notes

• Capitalization convention. This SRFI specifies an object and class system without mentioning objects and classes. Conceptually, Fixed-arrays are a subclass of Mutable-arrays, which in turn are a subclass of Arrays. I follow Queinnec in his practice of naming classes beginning with capital letters in Meroon.
• Fixed-arrays. Bawden-style arrays have their elements stored in a heterogeneous or homogeneous vector. A single vector can contain the elements of several conceptually separate arrays. I needed a name for this type of array implementation, and I think of the backing-store vector that contains the array elements as "fixed", sitting somewhere out of sight. Thus the name "Fixed-array". If you can come up with a better name, good.
• "build-object" vs. "make-object". I think of 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.
• Specifying intervals. I couldn't, for the life of me, figure out the most "natural" way to specify Intervals. Perhaps

  (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 accessor (Interval-lower-bounds would be an accessor) 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 accessor, only these converters.
• Indexers. Both the arguments new-domain->old-domain to Fixed-array-share! and indexer to build-Fixed-array are conceptual indexers, the first multiple-valued and the second single-valued.
• Source of function names. The function Array-curry gets its name from the curry operator in programming---we are currying the accessor 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.
• Choice of functions on Intervals. The choice of functions for both Arrays and Intervals was motivated almost solely by what I needed for Arrays. There are natural operations on Intervals, like

  (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.?).
• "Lazy" functions. The use of the term "lazy" in function names does not correspond to its usual meaning, that a value is computed the first time it is needed and them memoed; it means that the value is recomputed each time it is needed. If you can come up with a better name, tell me.
• Non-affine indexers. I'm not convinced that non-affine indexers are terribly important. There are applications (doing time-series analysis on two subsets of an array, for example) but there are also other ways to do these applications. It appears that recording whether an indexer is affine in each coordinate is more useful, but I haven't worked out completely how that would work.
• Redundancy of procedures. Currently I take the position, for example, that there should be three separate routines Array-curry, Mutable-array-curry, and Fixed-array-curry that build Arrays, Mutable-arrays, or Fixed-arrays, respectively, as their results. I may not want to build a curried Fixed-array, including setters, indexers, ..., even if the object I'm applying the curry operator to is a Fixed-array. Additionally, routines like Mutable-array-domain and Fixed-array-domain are truly redundant (except for the restrictions in their respective domains) but they are here because when I didn't have them and Array-domain was the only way to access the domain of Arrays, Mutable-arrays, and Fixed-arrays, I kept writing the incorrect

  (let ((setter   (Mutable-array-setter a))
        (domain   (Mutable-array-domain a))
        (accessor (Mutable-array-accessor a)))
    ...)

  instead of the currect

  (let ((setter   (Mutable-array-setter a))
        (domain   (Array-domain a))
        (accessor (Array-accessor a)))
    ...)

  This decision may need to be revisited.
• No empty Intervals or Arrays. Mathematically, a functions f(x) is a relation R, which is a set of ordered pairs {(x,y)} for x in some domain set X and y in some range set Y, for which (x1,y1) and (x2, y2) are in R and x1=x2 implies y1=y2. (Here we assume that f is onto Y, in other words that Y consists precisely of the second coordinates of the ordered pairs in R, and "=" means "identical", i.e., y1 and y2 are the same objects (in the sense of 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 accessor 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.

Specification

Intervals

build-Interval, Interval?, Interval-dimension, Interval-lower-bound, Interval-upper-bound, Interval-lower-bounds->list, Interval-upper-bounds->list, Interval-volume, Interval=, Interval-subset?, Interval-contains-multi-index?, Interval-curry, Interval-distinguish-one-axis, Interval-for-each, Interval-reduce.

Arrays

build-Array, Array?, Array-domain, Array-accessor, Array-lazy-map, Array-lazy-curry, Array-lazy-distinguish-one-axis, Array-for-each, Array-reduce.

Mutable Arrays

build-Mutable-array, Mutable-array?, Mutable-array-domain, Mutable-array-accessor, Mutable-array-setter, Mutable-array-lazy-curry, Mutable-array-lazy-distinguish-one-axis.

Fixed Array Manipulators

build-Fixed-array-manipulators, Fixed-array-manipulators-accessor, Fixed-array-manipulators-setter, Fixed-array-manipulators-maker, Fixed-array-manipulators-length, Fixed-array-manipulators-default.

Indexers

generic-indexer=, affine-indexer=.

Fixed Arrays

build-Fixed-array, Fixed-array?, Fixed-array-domain, Fixed-array-accessor, Fixed-array-setter, Fixed-array-body, Fixed-array-indexer, Fixed-array-manipulators, Fixed-array-lazy-curry, Fixed-array-lazy-distinguish-one-axis, Array->Fixed-array, Fixed-array-share!, Array-map.

Intervals

Intervals are sets of all multi-indices (i₁,...,i_k) such that l₁<=i₁<u₁, ..., l_k<=i_k<u_k, where the lower bounds (l₁,...,l_k) and the upper bounds (u₁,...,u_k) are specified as multi-indices of exact integers. The positive integer k is the dimension of the interval. It is required that l₁<u₁, ..., l_k<u_k.

Procedures

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)

Procedure: Interval-lower-bound interval i

If interval is an interval built with

(build-Interval lower-bounds upper-bounds)

0 <= i < (vector-length lower-bounds),

Procedure: Interval-upper-bound interval i

If interval is an interval built with

(build-Interval lower-bounds upper-bounds)

0 <= i < (vector-length lower-bounds),

Procedure: Interval-lower-bounds->list interval

If interval is an interval built with

(build-Interval lower-bounds upper-bounds)

Procedure: Interval-upper-bounds->list interval

If interval is an interval built with

(build-Interval lower-bounds upper-bounds)

Procedure: Interval-volume interval

If interval is an interval built with

(build-Interval lower-bounds upper-bounds)

(apply * (map - (Interval-upper-bounds->list interval) (Interval-lower-bounds->list interval))

Procedure: Interval= interval1 interval2

If interval1 and interval2 are intervals built with

(build-Interval lower-bounds1 upper-bounds1)

(build-Interval lower-bounds2 upper-bounds2)

(and (equal? lower-bounds1 lower-bounds2) (equal? upper-bounds1 upper-bounds2)

Procedure: Interval-subset? interval1 interval2

If interval1 and interval2 are intervals of the same dimension built with

(build-Interval lower-bounds1 upper-bounds1)

(build-Interval lower-bounds2 upper-bounds2)

(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 [l₀, u₀) x [l₁, u₁) x ... x [l_d-1, u_d-1) and splits it into two parts

[l₀, u₀) x [l₁, u₁) x ... x [l_{left-dimension - 1}, u_{left-dimension - 1})

[l_{left-dimension}, u_{left-dimension}) x ... x [l_d-1, u_d-1)

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

If interval is an interval and f is a routine whose domain includes elements of interval, then Interval-for-each calls f on each element of interval in lexicographical order. It is an error to call Interval-for-each if interval and f do not satisfy these conditions.

Procedure: Interval-reduce f operator identity interval

If interval is an interval and f is a routine whose domain includes elements of interval, then Interval-reduce returns

(... (operator (operator (operator identity (f multi-index1)) (f multi-index2)) (f multi-index3)) ...)

It is an error to call Interval-reduce if interval and f do not satisfy these conditions.

Arrays

Procedures

Procedure: build-Array domain accessor

If domain is an Interval and accessor is a function from domain to Scheme objects, then build-Array return an array with domain domain and accessor accessor. It is an error to call build-Array if domain and accessor do not satisfy these conditions.

Example:

(define a (build-Array (build-Interval '#(1 1) '#(11 11))
		       (lambda (i j)
			 (if (= i j)
			     1
			     0))))

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

Procedure: Array-accessor array

If array is an Array built by

(build-Array domain accessor)

Example:

(define a (build-Array (build-Interval '#(1 1) '#(11 11))
		       (lambda (i j)
			 (if (= i j)
			     1
			     0))))
((Array-accessor a) 3 3) => 1
((Array-accessor a) 2 3) => 0
((Array-accessor 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 accessor

(lambda multi-index
  (apply f (map (lambda (g) (apply g multi-index)) (map Array-accessor (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-accessor 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-accessor 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-accessor array) (append outer-multi-index inner-multi-index)))))

and

(lambda inner-multi-index (apply (Array-accessor array) (append outer-multi-index inner-multi-index)))

Example:

(define a (build-Array (build-Interval '#(0 0) '#(10 10))
		       list))
((Array-accessor a) 3 4)  => (3 4)
(define curried-a (Array-lazy-curry a 1))
((Array-accessor ((Array-accessor 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-accessor 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-accessor array) (insert-arg-into-arg-list m outer-index index)))))

and

(lambda (m) (apply (Array-accessor 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-accessor (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-accessor (cons array arrays)))))

Procedure: Array-reduce operator identity array

If array is an Array then Array-reduce calls (Interval-reduce (Array-accessor array) operator identity (Array-domain array)).

Mutable Arrays

Procedures

Procedure: build-Mutable-array domain accessor setter

Assume that domain is an Interval of dimension n and that accessor and setter are two routines that satisfy: If

(i1,...,in) != (j1,...,jn)

(accessor j1 ... jn) => x

(setter v i1 ... in)

(accessor j1 ... jn) => x

(accessor i1,...,in) => v

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 accessor setter)

Procedure: Mutable-array-accessor array

If array is a Mutable-array built by

(build-Mutable-array domain accessor setter)

Procedure: Mutable-array-setter array

If array is a Mutable-array built by

(build-Mutable-array domain accessor setter)

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-accessor sparse-array) 12345 6789)  => 0.
((Mutable-array-accessor sparse-array) 0 0) => 0.
((Mutable-array-setter sparse-array) 1.0 0 0) => undefined
((Array-accessor sparse-array) 12345 6789)  => 0.
((Array-accessor 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-accessor 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-accessor 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-accessor 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-accessor 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-accessor 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-accessor 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-accessor 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)))

Fixed Array Manipulators

Procedures

Procedure: build-Fixed-array-manipulators accessor 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.
• If v is an object created by (maker n value) and 0 <= i < n, then (accessor v i) returns the value of the i'th element of v.
• If 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.
• If 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 accessor and setter generally take O(1) time to execute.

Procedure: Fixed-array-manipulators-accessor m

If m is an object created by

(build-Fixed-array-manipulators accessor setter maker length default)

Procedure: Fixed-array-manipulators-setter m

If m is an object created by

(build-Fixed-array-manipulators accessor setter maker length default)

Procedure: Fixed-array-manipulators-maker m

If m is an object created by

(build-Fixed-array-manipulators accessor setter maker length default)

Procedure: Fixed-array-manipulators-length m

If m is an object created by

(build-Fixed-array-manipulators accessor setter maker length default)

Procedure: Fixed-array-manipulators-default m

If m is an object created by

(build-Fixed-array-manipulators accessor setter maker length 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))

Indexers

Procedures

Procedure: generic-indexer= indexer1 indexer2 interval

If indexer1 and indexer2 are one-to-one mappings from interval to the interval [0,K) for some K, then generic-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: 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.

Note: affine-indexer= will generally take advantage of the affine structure of indexer1 and indexer2 to be faster than generic-indexer=.

Fixed Arrays

Procedures

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 boolean; the accessor and setter of the result are defined by

(lambda (i_0 ... i_n-1)
  ((Fixed-array-manipulators-accessor manipulators)
   body
   (indexer i_0 ... i_n-1)))

(lambda (v i_0 ... i_n-1)
  ((Fixed-array-manipulators-setter manipulators)
   body
   (indexer i_0 ... i_n-1)
   v))

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 #t if the default indexer is used, otherwise the default is #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-accessor array

If array is a Fixed-array then Fixed-array-accessor returns its accessor. It is an error to call Fixed-array-accessor 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 whether the indexer of array is affine. 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))

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-accessor 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

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-accessor array) multi-index) multi-index))
		     (Array-domain array))
  result)

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-accessor (cons array arrays)))))))

Note: I'd like to redefine this function so that it doesn't necessarily call Array->Fixed-array, so the accessor is not necessarily called in strict lexicographical order.

Implementation

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.

Relationship to other SRFIs

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-accessor array) k1 ...)

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

((Array-setter array) obj k1 ...)

At the same time, this SRFI has some special features:

• Intervals, used as the domains of Arrays in this SRFI, are useful objects in their own rights, with their own procedures. We make a sharp distinction between the domains of Arrays and the Arrays themselves.
• Intervals can have nonzero lower bounds in each dimension.
• Intervals cannot be empty.
• Arrays must have an accessor, but may have no setter. For example, on a system with eight-bit chars, one can write a function to read greyscale images in the PGM format of the netpbm package as follows. The lexicographical order in Array->Fixed-array guarantees the the correct order of execution of the input procedures:

  (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"))))))))))

• The set of homogeneous Fixed-arrays is extensible. For example, manipulators for Fixed-arrays that contain complex numbers with 32-bit floating-point real and imaginary parts could be defined using SRFI-4 as:

  (define c32-array-manipulators
    (build-Fixed-array-manipulators (lambda (body i)                                         ;; accessor
  				    (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
  				  ))

• We allow nonaffine indexers in Fixed-arrays. Affine indexers are a special case that allows certain optimizations.

References

1. "multi-dimensional arrays in R5RS?", by Alan Bawden.
2. SRFI 4: Homogeneous Numeric Vector Datatypes, by Marc Feeley.
3. SRFI 25: Multi-dimensional Array Primitives, by Jussi Piitulainen.
4. SRFI 47: Array, by Aubrey Jaffer.
5. SRFI 58: Array Notation, by Aubrey Jaffer.
6. SRFI 63: Homogeneous and Heterogeneous Arrays, by Aubrey Jaffer.