Multidimensional arrays in Scheme

[Alaric Snell-Pym]

Dear Marco and Bradley,

In the ongoing work of Scheme standardisation for R7RS, the question of
standardising multidimensional arrays in Scheme has arisen, including
such thorny questions as: Do we adopt Bradley's SRFI-231, or might it be
in some way incompatible with "Heisig's JIT approach"?

We would therefore be honoured if you would both attend our next meeting
to discuss this; or if not, offer your opinions via email in advance of
the meeting so we can choose the best path forward (I have Cc:ed our
mailing list - postings to it from non-members may be moderated for
anti-spam reasons, but they'll be manually approved in due course)

We are currently choosing the time for our next meeting (they're held
online in IRC - no travel budget required!):

https://terminplaner6.dfn.de/p/dab5fb151bc65c155fbbd8961cccec7e-1650649

If you would be willing and able to join us, please put your
availabilities in the poll!

As some background, here are the minutes of the meeting where we decided
to postpone the discussion until we had expert opinions:

https://codeberg.org/scheme/r7rs/wiki/Minutes+2025-11-21.-

Many thanks for your time,

Alaric Snell-Pym
(Acting chair of R7RS WG2)

--
Alaric Snell-Pym (M0KTN neé M7KIT)
http://www.snell-pym.org.uk/alaric/

[Alaric Snell-Pym]

Bradley and Marcio are both happy to join us!

-------- Forwarded Message --------
Subject: Re: Multidimensional arrays in Scheme
Date: Thu, 12 Mar 2026 15:13:49 +0000
From: Bradley J Lucier <luc...@purdue.edu>
To: Alaric Snell-Pym <ala...@snell-pym.org.uk>
CC: Bradley J Lucier <luc...@purdue.edu>, marco....@mpl.mpg.de
<marco....@mpl.mpg.de>, scheme-re...@googlegroups.com
<scheme-re...@googlegroups.com>

Thank you for the invitation to your next meeting, I have noted the
times I can participate.

I have been working to refine SRFI 231 to make it more suitable for
standardization; the most important changes are to remove the notion of
“safe” and “unsafe” arrays (all arrays are now safe, but the sample
implementation removes unnecessary safety checks in the built-in “bulk”
array operations), and to add both explicit and implicit array
broadcasting in the style of NumPy in Python or Racket’s math/array
library. This update (which includes several new extended examples) can
be found at

https://github.com/gambiteer/srfi-231/tree/231-bis

The changes from SRFI 231 are listed after my signature.

I read the wiki notes from the recent R7RS committee meetings. I’ll
comment now briefly that SRFI 231 (and the followup) adds no new syntax
for arrays, and I believe that operations with what SRFI 231 calls
“specialized” arrays are compatible with Marco’s JIT compilation
approach in PetaLisp.

Brad Lucier


This SRFI differs from the finalized SRFI
231<https://srfi.schemers.org/srfi-231/> in the following ways:

* The implementation no longer specifies, or implements, a
difference between "safe" and "unsafe" arrays. The getters and setters
of all arrays made in the library check array indices for correctness;
the setters of mutable specialized arrays check that the objects they
store into arrays are of the correct type. (Internally, the sample
implementation maintains "unsafe" setters and getters that are used in
"bulk" array operations where the arguments are known to be
appropriate.) So procedure arguments that specify whether array results
are "safe" have been removed, as has the parameter
specialized-array-default-safe?.
* The calling sequences for interval-fold-left and
interval-fold-right have been changed.
* array-freeze! has been removed as a user-visible procedure.
Because array setters are reified and can be stored in structures,
passed as arguments, etc., one cannot truly "freeze" a mutable array to
make an immutable array.
* The default entry for arrays of generic-storage-class is now
0, not #f, which we find to be more useful.
* The routines array-outer-product and array-inner-product are
now specified to copy generalized array arguments to specialized arrays,
evaluating all elements of such an array in an unspecified order. The
procedure array-inner-productnow returns a specialized, not a
generalized, array result.
* Both explicit and implicit array broadcasting are specified in
this SRFI extension.
* The parameter array-broadcasting? has been added to the SRFI.
* The routines interval-every, interval-any, interval-rebase,
array-rebase, interval-insert-axis, object->array, array-insert-axis,
compute-broadcast-interval, array-broadcast have been added to the SRFI.


On Mar 12, 2026, at 5:43 AM, Alaric Snell-Pym <ala...@snell-pym.org.uk>
wrote:

[You don't often get email from ala...@snell-pym.org.uk. Learn why this
is important at https://aka.ms/LearnAboutSenderIdentification ]

---- External Email: Use caution with attachments, links, or sharing
data ----

[Wolfgang Corcoran-Mathe]

On 2026-03-12 17:09 +0000, Alaric Snell-Pym wrote:
> Bradley and Marcio are both happy to join us!

Thanks, Alaric! That's great news.

--
Wolfgang Corcoran-Mathe <w...@sigwinch.xyz>

[Alaric Snell-Pym]

Thanks both for coming today!

The following link leads to the final message in the logs, so if either
of you wish to refer back to all that was said, go here and scroll back
as far as necessary: http://snailgeist.com/irc-logs/?message_id=282008

We left it with, as I understand it, one open question: the explicit
control of laziness in Petalisp's compute operation compared to the
ability for an implementation of SRFI-231 to have implicit laziness.

Does an explicit "compute" step give users a useful ability to control
where the "heavy lifting" occurs?

I presume that lazy array operations will take O(1) time or maybe
O(number of dimensions) - "heavy lifting" being any operation that
actually materialises an array representation so will take time that's
O(f(size of the data)), (where "size of the data" may be much less than
the product of the dimensions in the case of a sparse array, but still
very large); and f will hopefully be at worse linear; logarithmic would
be nice (but something like an FFT ends up being O(N log N), of course).
I won't try and risk defining a definitive boundary between the time
cost of lazy operations versus materialising an array, but I think it's
clear the former will scale at worst with the dimensionality of the
array while the latter will scale with some function of the number of
elements in the array (not forgetting sparseness).

As I understand it a lazy SRFI-231 implementation *could* provide
at-most-O(number of dimensions) implementations for all the operations
that create arrays from other arrays in some form, and only do the
"heavy lifting" when the user first calls array-copy (which by my
reading explicitly materialises an array), array->list[*],
array->vector[*], or calling an array-getter (directly or via
array-ref). Presumably such an implementation would also cache the
materialised form to avoid having to recreate it.

Marco's experiences with Petalisp imply that such laziness - compressing
a stack of array operations into one larger operation - is useful for
performance reasons; I can certainly imagine it would reduce
garbage-collector pressure by avoiding creating unnecessary intermediate
arrays and there's probably a lot of operations that are composable in
ways that collapse a sequence of such operations into a single
operation. But that holds whether the laziness is explicit or implicit.

And there is also the possibility that making such laziness explicit has
some value in allowing applications to create "array recipes" with a low
expectation of cost, particularly if a way of inspecting such a
resulting recipe other than just calling (compute) on it is available -
perhaps one can query the dimensions of the resulting array, or query
the expected time complexity of calling (compute) on it, or directly
expose the underlying graph?

On the other hand, having an explicit compute operation to turn a recipe
into an array is a "performance wart" that users have to think about,
rather than just telling the implementation what they want done and
trusting the implementation to do it - it slightly leaks implementation
details in ways that are only helpful in some specific cases (and the
only case that comes to mind for me for wanting to control when
materialisation occurs is that we might give a user an interactive UI
for constructing an array recipe, assuming all those operations complete
in somewhat bounded time so can be allowed to block the UI, while
(compute) is run in a thread while the user is shown a progress bar).

So - I suspect that WG2 will probably be interested in adopting
SRFI-231bis, because it's already in SRFI form and based on Scheme
idioms and so on; this isn't "Do we pick SRFI-231 or Petalisp?" so much
as "Does SRFI-231 need to be modified to allow implementations to do all
the good stuff Marco developed in Petalisp?"; so I think what we're
asking is for you two good people to work out how to make SRFI-231 as
good as it can be so that we can adopt it, if you're OK with that, and
we'll gladly do anything we can to help :-)

Many thanks for your time,

[John Cowan]

On Mon, Mar 23, 2026 at 1:35 PM Alaric Snell-Pym <ala...@snell-pym.org.uk> wrote:

As I understand it a lazy SRFI-231 implementation *could* provide
at-most-O(number of dimensions) implementations for all the operations
that create arrays from other arrays in some form, and only do the
"heavy lifting" when the user first calls array-copy (which by my
reading explicitly materialises an array), array->list[*],
array->vector[*], o

That's pretty much the case already: SRFI 231 is fairly characterized as "mostly lazy". 

r calling an array-getter (directly or via
array-ref).

Actually, that's not the case.  In SRFI 231 terms, there are specialized arrays, which have backing storage of one or another storage class, and generalized arrays, which just have a getter and optionally a setter.  (Of course, both types have array dimensions. but that is metadata.)

So if you call (for example) `array-map` on an array of either kind, you get back a generalized array whose getter will call the underlying array's getter and then apply the mapping function to the result.  There is no setter, because the mapping function is not necessarily invertible.

Here is the complete list of non-lazy procedures (that is, the result is always a specialized array) that  take array argi,emts, from SRFI 231bis:

• array-copy: Evaluates the argument array at all valid indices and stores those objects into a new specialized array.
• array-assign!: Evaluates the argument array at all valid indices and assigns the resulting objects to the elements of an existing array. In the Gaussian Elimination example below, we combine array-map, array-outer-product, array-extract, and array-assign! to do one step of the elimination.
• array-stack: Like taking the individually rendered frames of an animated movie and combining them in time to make a complete video. Can be considered a partial inverse to array-curry. Returns a specialized array.
• array-decurry: Takes a "curried" array of arrays, and returns a single array with the same elements. An inverse to array-curry; a multi-dimensional version of array-stack.
• array-append: Like concatenating a number of images left to right, or top to bottom. Returns a specialized array. A partial inverse to array-tile.
• array-block: Assumes that an array has been decomposed into blocks by cuts perpendicular to each coordinate axis; takes an array of those blocks as an argument, and returns a reconstructed array. An inverse to array-tile; a multi-dimensional version of array-append.
• array-inner-product: Like APL's inner product; multiplying two matrices is an example of an operation implemented using array-inner-product.

In addition there is `specialized-array-share`, which applies only to specialized arrays and returns them, and applies an arbitrary transformation to the domain of the array. The SRFI says this could be extended to generalized arrays as a compatible upward extension.

The procedures array-extract, array-translate, array-permute, array-broadcast, and maybe a few more return specialized arrays when their arguments are specialized arrays.

Presumably such an implementation would also cache the
materialised form to avoid having to recreate it.

There are no hidden caches. If you perform an operation on an array, you get back another array, and the SRFI specifies whether it is generalized or specialized.  Generalized arrays require only O(d) space.

[Alaric Snell-Pym]

On 23/03/2026 20:54, John Cowan wrote:

>> r calling an array-getter (directly or via
>> array-ref).
>
> Actually, that's not the case. In SRFI 231 terms, there are specialized
> arrays, which have backing storage of one or another storage class, and
> generalized arrays, which just have a getter and optionally a setter. (Of
> course, both types have array dimensions. but that is metadata.)

You're right! Sorry, I should have looked closer.

Thanks,