Broadcasting, mutability, and non-strict arrays in math/array

General
1

TL;DR version:

Applying array broadcasting to mutable or non-strict arrays can be very difficult to reason about, so should one restrict broadcasting to strict, immutable arrays? or ignore the difficulties and learn to love array broadcasting because it's useful and can be efficient?

Some examples and questions follow.

I've been trying to understand how the features of array broadcasting, mutability, and non-strict arrays interact in math/array, and how they might interact in other frameworks.

For example, one might make the bare call with explicit broadcasting

(define brr0 (array-broadcast arr0 ds))

or have a call with implicit broadcasting

(define brr1 (array-map * arr1 arr2 arr3))

where arr1, arr2, and arr3 are arrays with different, but compatible, shapes for broadcasting.

First, if brr0 is mutable (meaning that arr0 is mutable, which in math/array means arr0 is strict), then

(array-set! brr0 #(1 2) val)

may happen to change all entries of brr0 with first index 1, or second index 2, or change the values of all entries of brr0 entirely.

It is nearly impossible to reason about programs where this can happen, so perhaps broadcasting should be limited to immutable arrays.

In the second example, if arr1, arr2, or arr3 are broadcast, then the broadcast version is "consumed" by (array-map * ...), and array-set! cannot be applied directly to the broadcast arguments.

But here now if a non-strict array arr1 is broadcast, and computing an element of arr1 has side effects, then computing

(array-all-sum brr1)

may cause those side effects may be executed an undetermined number of times.

Which again may lead to unclear exceptions and behavior that about which it is difficult to reason.

Or should we not worry about such things, say that some uses of such forms are very convenient, and learn not to ask such questions.

2

(With the caveat that I have used math/array, but I don't consider myself a power-user of array programming in general:)

I agree that mutability makes it harder to reason about programs in general, and I see a lot of appeal to purely functional languages and libraries. But both the Scheme family of languages and (though I speak of this with less confidence) the universe of array libraries fundamentally allow side-effects. It's not clear to me how broadcasting makes these examples more difficult to reason about than allowing mutation and side-effects in general.

Again, broadcasting seems unrelated to the complexity of side-effects from accessing non-strict array elements, and Scheme allows us to write ill-advised effectful code. (Indeed, I don't see how you could enforce a ban on side-effects in an impure language, short of making all nonstrict arrays lazy.) For example, these alternative implementations of a double function don't use broadcasting, but access elements of their argument different numbers of times:

(define (double a)
  (array-scale a 2))
(define (double a)
  (array+ a a))

The math/array docs for nonstrict arrays have this to say:

One downside to nonstrict arrays is that it is more difficult to reason about the performance of operations on them. Another is that the user must decide which arrays to make strict. Fortunately, there is a simple rule of thumb:

Make arrays strict when you must refer to most of their elements more than once or twice.

Having to name an array is a good indicator that it should be strict.

3

Thank you for your comments. I think I'm beginning to come around to your attitude of ''caveat programmer'', but I'll try to explain better my misgivings.

One example in the SRFI 231 test file that I am thinking of begins at

srfi-231/test-arrays.scm at 5fd225c8e3a366b9be0916bd6a9fddd7612712d7 · scheme-requests-for-implementation/srfi-231 · GitHub

where I define what would be in math/array a non-strict array to read PGM data from a file to get the array elements, which I then pass to array-copy to assign those elements, in order, to a strict array.

This is an extreme (and somewhat silly) example, but if the original non-strict array were broadcast implicitly along a third axis, then the program would attempt to read the data file many times over, yet the calling sequence with implicit broadcasting may be something like

(array- three-d-stack-of-images two-d-image)

and doesn't make explicit that the implicit duplication of the second argument can happen.

In SRFI 231's sample implementation a good deal of effort was put into making sure that the "right thing" would be done even if the procedure of a non-strict array captured and reentered its continuation multiple times. In other words, even if a non-strict array's procedure's continuation was reentered, it would not affect the entries of previously returned results.

In the above example, how is one to understand what is to happen when two-d-image's procedure captures a continuation if the 2-d array is implicitly broadcast to match the shape of the 3-d first argument, and the 2-d array's procedure captures its continuation an unknown number of times, depending on the length of the third axis of three-d-stack-of-images?

Sometimes I think that math/array's restriction that mutable arrays must be strict comes from worrying about how mutation interacts with other language features, but I don't know. I don't see how to make a mutable sparse matrix, for example. Perhaps to make a mutable sparse matrix, one is to modify the sparse arary's procedure outside the framework of math/array.

4

I've put together a revised proposal for array broadcasting in the SRFI 231 followup, which is described here

The proposal uses SRFI 231's terminology (strict<->specialized, non-strict<->generalized). Also, while math/array has array-strict! that modifies its argument, SRFI 231 has array-copy and array-copy! to copy generalized arrays to specialized arrays, leaving the argument unchanged.

The specifics of the proposal may not be of particular interest to Racket users, but I solicit comments from anyone. I discuss there my understanding of Racket's math/array, so corrections are very welcome, too.

1 Like