Classical array algebra | tali

\[\gdef\op#1{\operatorname{#1}} \gdef\tuple#1{\left(#1\right)} \gdef\ang#1{\left⟨#1\right⟩} \gdef\list#1{\left[ \mkern{1pt} #1 \mkern{1pt} \right]} \gdef\fs#1#2#3{#1\mathbin{:}#2\mathbin{ \to }#3}\]

Classical array algebra

Introduction

The goal of this first post is to clearly explain what multidimensional arrays are, and how they are manipulated in classical array programming. To this end I’ll introduce some notational devices for writing multidimensional arrays and expressing their operations. I’ll set out a general mathematical framework for reasoning about these arrays and their operations that is independent of the details of particular frameworks like NumPy or Torch.

The perspective I’m promoting here is to think about arrays as functions from indices to values. This view is starting to be adopted in practice – it’s a key design principle of the deep learning research language Dex. The “arrays as functions” perspective also naturally leads us to a kind of diagrammatic notation that is inherited from category theory, though I won’t elaborate on those connections here.

The followup post builds on this foundation to present an alternative paradigm called rainbow array algebra. In that post, I draw on color as a way of labelling array axes, instead of the traditional way we use a fixed axis order. But the principle is the same as named axes that are proposed in the Sasha Rush’s excellent “Tensors considered harmful”. In my view, this alternative paradigm simplifies and unifies many of the constructions we’ll see below, and offers a better foundation for array programming in the coming decades.

Array programming

Array programming, meaning computation on multidimensional arrays, is a foundational component of signal processing, data science, data visualization, and machine learning. Popular software libraries for doing array programming include Numpy, Scipy, R, Pandas, Torch, Tensorflow, JAX, XArray, and Julia. But the first array language was arguably Ken Iverson’s APL, which has modern descendents like K, J, and BQN.

Multidimensional arrays are used to represent time series, multimedia data, sensor measurements, system logs, financial transactions, medical outcomes, user behavior, neural network activity and a large number of other domain-specific data.

Software programs that manipulate arrays I’ll call array programs. We’ll aim to capture what array programs are doing at a conceptual level. The target audience is broad, including software practitioners interested in mathematical formalisms as well as mathematicians interested in array programming. It is unavoidable that some details will be redundant for some readers – please skip sections as appropriate.

Abstract nonsense

The constructions in array algebra can be understood within the framework of category theory. We won’t elaborate on this connection here, and leave this to a future blogpost. Briefly, arrays themselves can be seen as morphisms in a Cartesian closed category, with objects being part spaces and the Cartesian product of part spacing forming key spaces. This makes array circuit into string diagrams, which when “framed” exhibit array programs as lambda abstractions. The existence of an internal hom is what enables us to represent arrays themselves as values, see nesting. Our bubble notation resembles Ghica and Zanasi’s notation, see also Baez’s bubble and clasp notation.

Basic theory

Core concepts

At a high level, an array is a container of values. These values are organized in a particularly regular way – along axes . The number of axes of an array – the arity of the array – largely determines how the array can be processed and combined with other arrays.

Here’s a simple visual depiction of arrays with 0 through 3 axes, along with the shapes that describe the dimensions or sizes of the successive axes.

Each of the cubes above is called a cell , and contains a single value – integers in these cases.

The arity counts the number of axes of an array: a scalar has no axes, a vector has one axis, a matrix has two axes (rows and columns), etc. An array with n axes will be called an n-array.

Terminology

Let’s focus on a matrix – an array with two axes – to illustrate our terms.

The terms we’ll use for the rest of this post are defined below:

array<br>a collection of cells

cell<br>a slot in an array<br>labeled by a key<br>filled with a value

key<br>position of a cell in an array<br>a tuple of parts

axis<br>a label for a part<br>an integer in 1..n

value<br>the contents of a cell

Notation

As the vast majority of programming languages do, we&rsquo;ll use the convention of nested lists to write arrays with multiple axes. More deeply nested lists correspond to higher-numbered axes.

For example, the 3-vector V = [1 2 3] has one axis and has three cells, each containing an integer value.

A...