chickadee » array-morphisms

Array Morphisms

A unified backend for numerical computing combining fusion-based lazy evaluation, Mathematics of Arrays (MoA) index transformations, and automatic memory reuse.

Rationale

Just as the Scheme programming language demonstrates that a small set of orthogonal primitives suffices for all of computation, array morphisms demonstrate that index transformations suffice for most of what we call "matrix operations."

The proliferation of reshape, transpose, slice, and broadcast in numerical multi-dimensional array libraries such as NumPy is an indication that the underlying abstraction, the coordinate-free linear map, is not a first-class citizen. A matrix is a linear mapping plus an arbitrary choice of basis; by making the mapping itself first-class and the coordinate representation derived, operations that appear distinct collapse into a single compositional abstraction over index spaces.

The Mathematics of Arrays (MoA), developed by Lenore Mullin, provides the formal foundation for this approach. MoA treats arrays not as containers of data but as functions from index spaces to values, and array operations as transformations of those index spaces. Libraries such as NumPy already exploit this insight as an internal optimization -- transpose, slice, and reshape can return views backed by the same storage rather than copies. What MoA makes possible, and what array morphisms realize, is promoting these optimizations from private implementation details to first-class abstractions. Index transformation become objects that can be inspected, composed, and extended. Users are no longer dependent on library authors having anticipated a particular combination of operations. Any composition of affine index functions is itself an affine index function, and the index algebra guarantees this closure. MoA's reduction theory (the Psi Calculus) then provides the rules for simplifying chains of such transformations before any data is ever accessed.

Array morphisms are the realization of MoA's index-transformation algebra as first-class Scheme objects. An array morphism pairs a shape, which serves as a description of the index space, with an index function that maps coordinates in that space to coordinates in some underlying storage. Morphisms compose: applying a transpose to a slice to a reshape produces a single new morphism whose index function is the composition of three affine maps, with no intermediate allocation. The representation is stratified: at the bottom lies a flat, contiguous buffer; above it, any number of morphisms may be stacked, each a pure description of how to interpret that buffer. Morphism evaluation, the act of reading or writing data, occurs only when explicitly requested, and only at the coordinates actually needed.

Key Features

Array Morphisms vs. SRFI-231

Index Functions as First-Class Objects
In SRFI-231, the indexer of a specialized array is available through `array-indexer` as a Scheme procedure; the library tracks its affine structure internally, but that structure is not exposed to the programmer as data. Array morphisms make index functions inspectable algebraic data -- tagged records with known structure (affine, window, compute, composed). This makes the composition law programmable.
Unified Abstraction Rather Than Two-Tier Hierarchy
SRFI-231 distinguishes between generalized arrays (domain plus opaque getter/setter) and specialized arrays (domain plus flat buffer plus affine indexer). Array morphisms replace this with a single stratified structure where structural and computational morphisms compose uniformly.
Algebraic Simplification
SRFI-231 already composes the affine indexers of specialized arrays, so a chain of operations such as `array-extract`, `array-permute`, `array-reverse`, and `specialized-array-reshape` yields a single affine indexer. Array morphisms extend this idea to symbolic rewriting over all morphism kinds, including non-affine window and compute morphisms: `reshape(reshape(x, s1), s2)` rewrites to `reshape(x, s2)`; `transpose(transpose(x, p1), p2)` rewrites to the composed permutation, and if the result is identity, the operations cancel entirely.
Zero-Copy Structural Operations
SRFI-231's `specialized-array-reshape` succeeds without copying whenever there is an affine indexer on the new domain that visits the elements of the existing array in the same order; the array need not be contiguous (see the commentary at https://srfi.schemers.org/srfi-231/commentary.html). When no such indexer exists, it signals an error or, if requested, copies the array. Array morphisms treat reshape as an index transformation that is always valid, possibly non-affine, and leave the decision of whether to materialize a copy to the execution strategy.
Deferred Evaluation with Buffer Reuse
SRFI-231 generalized arrays compute elements on demand, and the programmer decides when to materialize them, for example with `array-copy`. Array morphisms add a two-phase execution model with trace/replay and automatic buffer planning via liveness analysis.
Batch Awareness
SRFI-231 has no notion of batch dimension. Array morphisms track the batch axis as a first-class attribute, enabling batch-aware broadcasting, convolution, and reduction.

Type System

Arrays hold one of four element types (dtypes):

'f64 - Double precision floating point (64-bit)
'f32 - Single precision floating point (32-bit)
's64 - 64-bit signed integer
's32 - 32-bit signed integer

How results get their dtype:

morph-cast m dtypeprocedure

Convert each element of m to dtype: to 'f32 it rounds to single precision, and to an integer dtype it truncates.

Core Concepts

Morphisms vs Arrays

Array morphisms represent computation as structure-preserving transformations. There are two types:

Concrete Arrays - Materialized data with shape, dtype, and strides
Abstract Morphisms - Deferred computations represented as expression trees
;; Concrete array - data is stored
(define concrete (morph-from-list '(1.0 2.0 3.0) '(3) 'f64))

;; Abstract morphism - represents computation
(define abstract (morph+ concrete concrete))

;; Realization materializes the morphism
(define result (realize abstract))  ; Now concrete

Index Functions

Index functions describe transformations algebraically:

Affine Index Functions - Pure transformations (reshape, transpose, slice)
Compute Index Functions - Element-wise arithmetic operations
Window Index Functions - Convolution and pooling operations
Reduction Index Functions - Aggregate operations (sum, mean, max)

Zero-Copy Views

Structural operations manipulate array views without copying:

(define x (morph-from-list '(0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0) '(8) 'f64))

;; Non-contiguous slice (stride 2)
(define strided (morph-slice x '(0) '(8) 2))  ; (0.0 2.0 4.0 6.0)

;; Reshape works even on non-contiguous views
(define as-2x2 (morph-reshape strided #(2 2)))  ; ((0.0 2.0) (4.0 6.0))

Installation

chicken-install array-morphisms

Module Imports

(import array-morphisms-core)       ; Core data types and utilities
(import array-morphisms-basic-ops)  ; Arithmetic operations
(import array-morphisms-structural-ops)  ; Reshape, transpose, slice
(import array-morphisms-realization)     ; Materialization
(import array-morphisms-context)         ; Memory reuse contexts
(import array-morphisms-batch-ops)       ; Batch operations
(import array-morphisms-lift)            ; Frame lifting, scans with a procedure as step
(import array-morphisms-blas-exec)       ; BLAS backend records and dispatch
(import array-morphisms-micro-blas-backend) ; Default dependency-free BLAS backend
(import array-morphisms-activation-exec) ; Element-wise kernel backends
(import array-morphisms-scalar-ops-table) ; The scalar-op table (op formulas, as data)
(import array-morphisms-scalar-ops)      ; Combiners and expressions of the scalar ops
(import array-morphisms-segop)           ; Segmented operations and segop backends
(import array-morphisms-grad)            ; Reverse-mode automatic differentiation
(import array-morphisms-grad-check)      ; Numerical gradient checking
(import array-morphisms-ssa)             ; SSA compilation, VJP and replay

Core API

Morphism Creation

morph-from-list lst shape dtypeprocedure

Create a concrete morphism from a nested list.

make-morphism data shape dtype #!key batch-axisprocedure

Create a concrete morphism from a typed vector.

Morphism Properties

morph-shape mprocedure

Get the shape of morphism m.

morph-dtype mprocedure

Get the data type of morphism m.

morph-size mprocedure

Get the total number of elements in morphism m.

morph-rank mprocedure

Get the number of dimensions in morphism m.

concrete-array? mprocedure

Check if morphism is concrete (materialized).

abstract-morphism? mprocedure

Check if morphism is abstract (deferred).

batched? mprocedure

Check if morphism carries a batch dimension.

batch-size mprocedure

Get the batch size (error if not batched).

Realization

realize mprocedure

Materialize morphism to concrete array. Uses context if active.

realize! mprocedure

Alias for realize.

morph->list mprocedure

Convert concrete morphism to nested Scheme list.

Arithmetic Operations

All operations are lazy by default and create morphism expressions.

morph+ m1 m2procedure
morph- m1 m2procedure
morph* m1 m2procedure
morph/ m1 m2procedure
morph-pow m1 m2procedure

Element-wise binary operations with broadcasting.

morph-negate mprocedure
morph-abs mprocedure
morph-sqrt mprocedure
morph-exp mprocedure
morph-log mprocedure
morph-sin mprocedure
morph-cos mprocedure
morph-tan mprocedure
morph-floor mprocedure
morph-ceiling mprocedure

Element-wise unary operations.

Comparison Operations

morph> m1 m2procedure
morph< m1 m2procedure
morph= m1 m2procedure
morph>= m1 m2procedure
morph<= m1 m2procedure

Element-wise comparison (returns 1.0 for true, 0.0 for false).

Functional Operations

morph-map func mprocedure

Apply function element-wise to morphism.

morph-reduce op m #!optional axes keepdims? frame-rankprocedure

Reduce morphism along specified axes. Operations: 'sum, 'mean, 'max, 'min, 'prod. With a frame-rank above 0, the leading frame-rank axes form a frame, and each cell is reduced exactly as it would be on its own (see Frame Lifting below): (morph-reduce 'sum m '(2) #f 1) maps [F M N] to [F M], the row sums of each [M N] cell.

The scans morph-scan, morph-cumsum and morph-cumprod are described in the Scans section below.

Structural Operations

morph-reshape m new-shapeprocedure

Reshape morphism to new shape (zero-copy). Supports -1 for automatic inference.

morph-transpose m #!optional permutationprocedure

Transpose morphism by permuting dimensions. Default reverses all axes.

morph-slice m start end #!optional stepprocedure

Extract subarray via affine transformation. Supports negative indices and step.

morph-stack morphisms axisprocedure

Stack morphisms along new dimension.

morph-concat morphisms axisprocedure

Concatenate morphisms along existing dimension.

morph-squeeze m #!optional axesprocedure

Remove dimensions of size 1.

morph-unsqueeze m axisprocedure

Add dimension of size 1 at specified axis.

morph-pad m padding #!optional mode valueprocedure

Pad morphism with constant, edge, or reflect mode.

Matrix Operations (BLAS)

morph-matmul A Bprocedure

Matrix-matrix multiply morphism: (M,K) x (K,N) -> (M,N).

morph-matmul also multiplies batches. When an operand has rank 3 or more, its leading axes are a frame and its last two axes are the matrices (the cells):

(morph-matmul A B)   ; A [F.. M K], B [F.. K N] -> [F.. M N]
(morph-matmul A W)   ; A [F.. M K], W [K N]     -> [F.. M N]  (W shared by every cell)
(morph-matmul W B)   ; W [M K],     B [F.. K N] -> [F.. M N]

Both operands must have the same frame, unless one of them is a plain matrix shared by every cell. Each cell of the result has exactly the values that the 2-D product of that cell would have, because it runs the same GEMM kernel.

morph-matvec A vprocedure

Matrix-vector multiply morphism: (M,N) x (N,) -> (M,).

morph-dot v1 v2procedure

Vector dot product morphism: (N,) . (N,) -> scalar.

morph-axpy alpha x yprocedure

AXPY morphism: result = alpha * x + y.

Convolution Operations

im2col-morph input kernel-size #!optional stride paddingprocedure

Image-to-column morphism for convolution.

col2im-morph col output-shape kernel-size #!optional strideprocedure

Column-to-image morphism (adjoint of im2col).

Batch Operations

add-batch-dimension m #!optional axisprocedure

Add a size-1 batch dimension to non-batched morphism.

remove-batch-dimension mprocedure

Remove size-1 batch dimension.

extract-batch-element m i #!optional axisprocedure

Extract a single element from the batch dimension (zero-copy).

stack-into-batch morphisms axisprocedure

Stack list of morphisms into a batch.

batch-map func m #!optional axisprocedure

Apply function to each element along batch dimension, as one computation built by morph-lift. When morph-lift cannot lift func, batch-map falls back to batch-map/slices.

batch-map/slices func m #!optional axisprocedure

Apply function to each element slice and stack the results.

batch-reduce op m #!optional keepdims?procedure

Reduce across batch dimension.

batch-zip func m1 m2procedure
batch-zip/slices func m1 m2procedure

Combine two batched morphisms element-wise. batch-zip lifts func as batch-map does, and falls back to batch-zip/slices.

batch-fold func init mprocedure

Fold func over the batch axis, starting from init.

batch-scan func init mprocedure
batch-scan/slices func init mprocedure

Scan func along the batch axis. batch-scan turns the step into one scan with morph-scan/fn, with as many nodes for any batch size. When the step cannot be turned into an expression, or init is not an array of one element's shape and dtype, it runs batch-scan/slices, which applies the step to each slice and stacks the results.

morph-batch-matmul A Bprocedure

Batched matrix multiply; the same node as morph-matmul builds for operands of rank 3 or more.

Memory Reuse Context

make-morphism-contextprocedure

Create execution context for buffer reuse.

realize/ctx ctx mprocedure

Realize morphism using context for buffer planning.

finalize-context! ctxprocedure

Complete trace phase and compute buffer assignment.

reset-context! ctxprocedure

Reset context for replay phase.

context-stats ctxprocedure

Get statistics about allocations in context.

print-context-plan ctxprocedure

Display buffer assignment plan.

BLAS Backend Configuration

Matrix multiply, matrix-vector multiply, dot, axpy and conv2d are dispatched through a pluggable BLAS backend. Four tiers are available:

Pure Scheme
built in; used when no backend is registered.
microBLAS
built in (array-morphisms-micro-blas-backend), with no external dependencies. It is registered automatically at load time if no other backend has been registered first.
System BLAS
the separate egg array-morphisms-blas, which needs the blas egg and a system BLAS library. Opt-in.
crunch
the separate egg array-morphisms-crunch, whose GEMM and convolution kernels are compiled from Scheme to C by the crunch compiler and split across threads. Opt-in.
register-blas-backend! backendprocedure

Register a BLAS backend for accelerated operations, replacing any previously registered backend.

active-blas-backendprocedure

Return the registered BLAS backend, or #f.

blas-enabled?procedure

Check if BLAS optimization is enabled.

enable-blas!procedure

Enable BLAS optimization.

disable-blas!procedure

Disable BLAS optimization (use pure Scheme).

blas-available?procedure

Check if a BLAS backend is registered.

make-blas-backend name gemm-f64 gemm-f32 gemm-strided-f64 gemm-strided-f32 gemv-f64 gemv-f32 dot-f64 dot-f32 axpy-f64 axpy-f32 conv-fwd-im2col-f32 conv-bwd-data-im2col-f32 conv-bwd-weights-im2col-f32 conv-fwd-nhwc-im2col-f32 conv-bwd-data-nhwc-im2col-f32 conv-bwd-weights-nhwc-im2col-f32 #!optional gemm-offset-f64 gemm-offset-f32 dot-offset-f64 dot-offset-f32procedure

Make a backend record from its kernels; each is a procedure or #f. The four optional kernels take matrices and vectors that start at an offset into their vectors:

gemm-offset: (M N K alpha A off-A lda transa B off-B ldb transb beta C off-C)
dot-offset:  (N x off-x y off-y) -> number

With them, the cells of a batched product and the rows of a framed sum are read in place. microBLAS, the system-BLAS egg and the crunch egg supply them. A backend without them still works: each cell is copied into a scratch buffer first, which gives the same values more slowly.

Prepared GEMM

execute-blas-gemm/into! and execute-blas-gemm-strided/into! check their operands (dtype, rank, layout, size) on every call. Code that multiplies arrays of the same shapes, strides and dtype many times can check them once:

prepare-blas-gemm/into A Bprocedure
prepare-blas-gemm-strided/into A Bprocedure

Return a plan that records the backend kernel to call and its arguments.

execute-gemm-plan/into! plan A B result-dataprocedure

Multiply A and B into result-data with plan. The plan is used only while BLAS is enabled and the backend it was made for is still registered; otherwise the matching execute-blas-* procedure runs.

gemm-plan-uses-kernel? planprocedure

Whether plan calls a backend kernel.

SSA replay plans prepare their matrix products this way when they are compiled.

Element-wise Kernel Backends

Module array-morphisms-activation-exec.

Element-wise operations, reductions and strided copies can be handed to a pluggable activation backend, registered separately from the BLAS backend. A backend holds whole-array kernels, one per op and dtype ('f32 or 'f64), for:

When an SSA replay plan is compiled, each element-wise binding is lowered to a segop (see Segmented operations below). A binding that applies one of these ops directly to row-major operands of the output's shape gets the segop/activation-unary or segop/activation-binary executor, which uses the backend's kernel for its op and dtype at execution time. Reductions and strided copies use their kernels wherever arrays are realized. When no backend is registered, no kernel exists for the op and dtype, or the operand and output dtypes differ, the Scheme loops run instead. Kernels must compute exactly what the Scheme loops compute, so a backend changes speed, not results.

No activation backend is registered by default. The array-morphisms-crunch egg provides an unthreaded and a threaded backend; see the example below.

make-activation-backend nameprocedure

Create an activation backend called name (a symbol) with no kernels.

activation-backend? xprocedure
activation-backend-name backendprocedure

Type predicate and name accessor.

activation-backend-add-kernel! backend op dtype kernelprocedure

Install kernel, a procedure (size in out), as the implementation of unary op on dtype arrays. in and out are SRFI-4 vectors of that dtype and may be the same vector. A later call for the same op and dtype replaces the kernel.

activation-backend-add-binary-kernel! backend op dtype kernelprocedure

Install kernel, a procedure (size a b out) computing out[i] = op(a[i], b[i]), as the implementation of binary op on dtype arrays. out may be a or b.

activation-backend-add-reduction-kernel! backend rop axis dtype kernelprocedure

Install kernel, a procedure (rows cols src out), as the reduction rop (sum, mean, max or min) over axis (0 or 1) of a row-major rows x cols array. out receives cols results for axis 0 and rows results for axis 1.

activation-backend-add-copy-kernel! backend dtype kernelprocedure

Install kernel, a procedure (src offset shape strides dst), as the copy of strided dtype arrays of rank at most 4 into row-major order.

activation-backend-add-broadcast-kernel! backend op dtype kernelprocedure

Install kernel, a procedure (rows cols a mode-a b mode-b out), as the broadcast form of binary op (add, sub, mul or div). out is a row-major rows x cols array receiving out[i, j] = op(a[.], b[.]); the mode of an operand says how it is indexed: 0, a rows x cols array; 1, one value per row; 2, one value per column; 3, a single value.

activation-backend-add-scan-kernel! backend op dtype kernelprocedure

Install kernel, a procedure (outer n inner src seed out flags), as the scan with op (sum, prod, max or min). The row-major array [outer, n, inner] is scanned along its middle axis. The bits of flags are 1 for an exclusive scan, 2 for a reversed one, 4 when seed, a row-major [outer, inner] array, holds the values the lines start from, and 8 when each step computes (op element acc).

activation-backend-add-fused-kernel! backend body dtype kernelprocedure

Install kernel, a procedure (size ins out), as the fused kernel for the scalar body, in canonical form (canonical-scalar-body). ins is the list of input vectors, read as (in 0), (in 1), ....

activation-backend-add-colsum-kernel! backend body dtype kernelprocedure

Install kernel, a procedure (rows cols ins mo out), which stores the value of body at each element of a row-major rows x cols array in mo and the sum of each column in out, adding the rows in order.

activation-backend-kernels backendprocedure

List of the (op . dtype) pairs that backend has unary kernels for.

register-activation-backend! backendprocedure

Make backend the active activation backend. #f removes it.

active-activation-backendprocedure

The active activation backend, or #f.

lookup-activation-kernel backend op dtypeprocedure
lookup-binary-kernel backend op dtypeprocedure
lookup-reduction-kernel backend rop axis dtypeprocedure
lookup-copy-kernel backend dtypeprocedure

The corresponding kernel of backend, or #f. backend may be #f.

register-activation-op! opprocedure
activation-op-registered? opprocedure
activation-opsprocedure

Manage the unary op names that get the segop/activation-unary executor. The six activation and derivative names above are registered by default.

register-binary-op! opprocedure
unregister-binary-op! opprocedure
binary-op-registered? opprocedure
binary-opsprocedure

Manage the binary op names that get the segop/activation-binary executor. None are registered by default; backend constructors register the ops they provide. Until then add, sub, mul and div use the ordinary segop/flat-binary executor.

Registering an op name only selects the executor, and only for ops that have an entry in the scalar-op table. For a new activation to appear in differentiable SSA graphs it also needs a table entry, a morph-<op> constructor, a VJP rule in ssa-vjp and a case in rebuild-morphism.

Scans

Module array-morphisms-basic-ops.

A scan computes running results along one axis: element r of the output combines the elements 0 to r of its line.

morph-scan op m axis #!key exclusive? reverse? init neutral auxprocedure
morph-cumsum m axis #!key exclusive? reverse? initprocedure
morph-cumprod m axis #!key exclusive? reverse? initprocedure
op
'sum, 'prod, 'max, 'min, or a combining expression (below). morph-cumsum and morph-cumprod are morph-scan with 'sum and 'prod.
exclusive?
shifts the results by one position: element r combines the elements before r, and element 0 is init or the neutral element (0, 1, or the lowest or highest value of the dtype).
reverse?
scans from the last element down to the first.
init
an array with the shape of m without the scanned axis: the value each line starts from.
neutral
the neutral element of a combining expression, for an exclusive scan without init.
aux
a list of arrays of the shape of m, one per extra variable of a combining expression.

Each output is the previous output combined with one more element and rounded to the result's dtype, exactly as a loop over the elements in order computes it. The first output is the first element itself, so a first element -0.0 or NaN is kept. max replaces the running value only by a greater element, so a NaN after the first element is passed over; min likewise.

Combining expressions

A combining expression (lambda (a b) e) gives the step: a is the value so far and b the next element. e uses the ops of the scalar-op table, numbers, cast, and if with a comparison (<, >, <=, >=, =) as its test. e is computed in double precision and rounded to the result's dtype after every step; (cast f32 ...) rounds an intermediate value. The elements are combined in order, so e does not need to be associative.

An expression may have more than two variables. aux: then gives one array per extra variable, and at each step the variable holds that array's element at the same position.

;; an exponential moving sum: out[r] = 0.9 * out[r-1] + x[r]
(morph-scan '(lambda (a b) (+ (* a 0.9) b)) x 1)

;; a linear recurrence: out[r] = x[r] + c[r] * out[r-1]
(morph-scan '(lambda (a b c) (+ b (* c a))) x 1 aux: (list c))
morph-scan/fn fn m axis #!key exclusive? reverse? init neutralprocedure

Module array-morphisms-lift. Takes the step as a procedure of two morphisms and turns it into a combining expression. The procedure may use element-wise ops of its two arguments and of one-element constants. A procedure that does anything else (morph-map, a reduction, an array captured from outside) signals the lift-unsupported condition. A step that adds or multiplies its two arguments becomes the sum or prod scan.

(morph-scan/fn (lambda (acc x) (morph+ (morph* acc k) x)) m 0 init: m0)  ; k a one-element array

Gradients of scans

ssa-vjp differentiates sum, prod, max and min scans:

sum
the gradient of the scanned array is the scan of the incoming gradient in the opposite direction; that of init is the incoming gradient summed along the axis.
prod
the gradient of element k is the product of the elements before it times a sum over the later outputs, computed as a recurrence from the end of the line. No element is divided by, so zeros give exact gradients.
max, min
each element receives the incoming gradient of the outputs that hold its value. Of two equal elements, the earlier one gets the gradient.

var-scan (array-morphisms-grad) gives the same gradients for backward!. Scans with a combining expression have no gradient; using one on a trainable parameter is an error.

Execution of scans

Scans are never fused with their neighbours. A replay runs each scan on the first of these that applies: a scan kernel of the activation backend (segop/scan-kernel), a kernel generated by the code generator of array-morphisms-crunch (segop/codegen-scan), or Scheme loops (segop/scan, segop/strided-scan). All of them give the same values.

Frame Lifting

Module array-morphisms-lift.

morph-lift fn cell-ranks arg ...procedure

Apply fn, a function on cells, to every cell of a frame as one computation. cell-ranks gives the rank of the cells that fn expects, one per argument or one for all. The leading axes of an argument, beyond its cell rank, are its frame. The longest frame becomes the result's frame, and every other frame must be a prefix of it. An argument with a shorter frame is reused along the frame axes it lacks.

;; x [F B D]: each cell is a [B D] matrix; W and b are shared by every cell
(define y (morph-lift (lambda (xc) (morph-tanh-am (morph+ (morph-matmul xc W) b)))
                      2 x))   ; cell rank 2 -> y [F B D]

morph-lift calls fn once, on placeholder arrays with the cell shapes, and widens the expression fn builds by the frame:

  • element-wise operations stay one element-wise node;
  • a reduction becomes one reduction with a frame rank;
  • a matrix product becomes one batched matrix product;
  • transposes, reshapes, slices, padding, stacks, concatenations and scans keep the frame axes in front;
  • attention takes the frame as leading axes (up to rank 4 in all), and im2col and col2im fold it into the image axis.

Parts of the expression that use no argument, such as W above, are computed once, so the expression has as many nodes for a frame of 4 cells as for 64. Every cell of the result has exactly the values that fn gives for that cell on its own.

fn must only build expressions from the placeholders; it must not read their values.

lift-unsupported? xprocedure
lift-unsupported-op conditionprocedure

morph-lift signals a lift-unsupported condition when fn uses an operation that has no widening rule (such as morph-matvec). lift-unsupported-op gives the operation's name.

var-lift fn cell-ranks var ...procedure

Module array-morphisms-grad. The gradient-tracking form of morph-lift. ssa-vjp derives the gradients of lifted computations, and nanograd's am-training-step/ssa uses it. Each cell gets exactly the gradient that its own program would give. An array shared by every cell gets the sum of the cells' gradients, which agrees with adding up per-cell gradients up to rounding. backward! does not differentiate through var-lift.

Measured in f32, a lifted layer tanh(x W + b) with frames of 8 to 64 cells runs its forward pass 6 to 17 times faster than slice-and-stack, and an SSA training step 1.7 to 37 times faster than one program per cell, depending on the BLAS backend.

SSA Programs

Module array-morphisms-ssa.

morphism-to-ssa compiles a morphism graph into a static single assignment (SSA) program, ssa-vjp adds the backward pass, and ssa-realize/ctx runs the program through a context: the first run traces it, and later runs replay a compiled plan into the context's buffers.

Gradients in SSA programs

ssa-vjp returns one gradient per parameter, in the order of the parameters, each with its parameter's dtype. A parameter that no gradient reaches gets zeros of its shape and dtype.

ssa-vjp raises an error when the input of an operation without a derivative depends on a trainable parameter.

Fusion

ssa-vjp runs a fusion pass on the program it builds, and ssa-realize/ctx fuses a forward program at its first trace. The pass can fuse:

Fusion does not change results: a fused binding rounds each intermediate value to its dtype, as storing it would, and a fused reduction adds in the same order as the unfused one.

segop-fusion #!optional policyparameter

The fusion policy:

#t (the default)
fuses only what some segop backend can run natively, as one compiled kernel: a fused kernel of the activation backend, or a kernel of a code generator such as the one of array-morphisms-crunch. With no such backend, it fuses nothing.
'all
fuses every legal pair.
#f
runs no fusion pass.
segop-fusion-max-rounds #!optional nparameter

The maximum number of rounds of the pass (16 by default).

ssa-fusion-pass-statsprocedure

Statistics of the last run of the pass: the fused bodies formed, the fusions made in each class, and the pairs left unfused, by reason.

ssa-program-fused? progprocedure

Whether prog has been through the pass. Differentiate a forward program before realizing it through a context: ssa-vjp refuses a program with fused bindings.

Segmented operations

Module array-morphisms-segop.

When a replay plan is compiled, every binding except zero-copy views is lowered to a segmented operation (segop). A segop has an iteration space, operands with their layouts and index maps from iteration coordinates to array indices, and a body, a symbolic expression computing one output element, such as (relu (in 0)). There are four kinds:

seg-map
element-wise maps, possibly with several outputs.
seg-reduce
reductions, with a combine spec giving the operator, neutral element, accumulator precision and summation order. Matrix products and convolutions are contractions of this kind.
seg-scan
scans along the last dimension of the space.
seg-lib
named library operations run on the host.

The design follows the segmented operations (SegMap, SegRed, SegScan) of the Futhark compiler. The ops a body can name come from the scalar-op table (array-morphisms-scalar-ops-table). The Scheme combiners and the kernels of array-morphisms-crunch are generated from the same table, so all of them compute the same formula.

Each segop is offered to the segop backends in turn; the first one that accepts it supplies an executor. Two backends are always present: registry, which runs the patterns that have BLAS or activation kernels, and scheme, which runs the rest with Scheme loops. Every replay gives the same values, bit for bit, as the traced run.

segop-backends #!optional backendsparameter

The segop backends, in the order they are tried.

register-segop-backend! backend #!optional positionprocedure

Add backend to the backends: first by default, or at position, such as '(after registry).

make-segop-backend name select #!key kind native?procedure

Make a segop backend. select takes a segop and returns an executor or #f. kind is 'host, 'catalogue or 'codegen. native? tells whether the backend runs a fused segop template as one compiled kernel; the default fusion policy asks it before it fuses.

select-segop-executor segop #!optional afterprocedure

Ask the backends for an executor; with after, only the backends after the one of that name.

segop-interpret segop in-bufs out-bufs #!key params use-fallbackprocedure

Execute a seg-map, seg-reduce or seg-scan directly from its definition. Slow; meant for testing.

replay-plan-stats progprocedure
replay-timing-resultsprocedure

The statistics of a compiled replay plan, and its timing profile. Both name each segop instruction by its pattern, such as segop/activation-unary, segop/gemm, segop/gemm-batched, segop/conv-fwd, segop/scan-kernel or, with the code generator of array-morphisms-crunch, segop/codegen-map.

The values a replay computes live in the context's buffers, and the next replay overwrites them, so copy an output that you want to keep across replays. Convolutions run on the convolution kernels of the BLAS backend; the convolutions of a plan share one image-column buffer per dtype.

Examples

Basic Operations

(import array-morphisms-core
        array-morphisms-basic-ops
        array-morphisms-structural-ops
        array-morphisms-realization)

;; Create arrays
(define a (morph-from-list '(1.0 2.0 3.0 4.0 5.0) '(5) 'f64))
(define b (morph-from-list '(2.0 4.0 6.0 8.0 10.0) '(5) 'f64))

;; Build lazy computation
(define squared (morph-map (lambda (x) (* x x)) a))
(define complex (morph+ squared (morph-map (lambda (x) (* x 2)) b)))

;; Force computation
(morph->list (realize complex))

Layer Normalization

(define (layer-norm x eps)
  (let* ((mean (morph-reduce 'mean x '(0)))
         (centered (morph- x mean))
         (variance (morph-reduce 'mean 
                               (morph* centered centered) 
                               '(0)))
         (std (morph-sqrt (morph+ variance eps))))
    (morph/ centered std)))

;; Create 4x6 activation matrix
(define activations
  (morph-from-list (map (lambda (i) (+ i 1.0)) (iota 24))
                   #(4 6) 'f64))

;; Apply layer normalization
(define normalized (layer-norm activations 1e-5))
(morph->list (realize normalized))

Memory Reuse with Context

(import array-morphisms-context)

;; Create context for repeated computation
(define ctx (make-morphism-context))

;; Trace phase
(define result1 (realize/ctx ctx expensive-morphism))
(finalize-context! ctx)

;; Replay phase - reuses buffers
(reset-context! ctx)
(define result2 (realize/ctx ctx expensive-morphism))

Batched Operations

(import array-morphisms-batch-ops)

;; Create batch of matrices
(define m1 (morph-from-list '(1.0 2.0 3.0 4.0) '(2 2) 'f64))
(define m2 (morph-from-list '(2.0 4.0 6.0 8.0) '(2 2) 'f64))
(define batch (morph-stack (list m1 m2) 0))  ; shape (2 2 2)

;; Batch map: apply function to each matrix
(define doubled (batch-map 
                  (lambda (m) (morph-map (lambda (x) (* x 2)) m))
                  batch))

;; Batch reduce: sum across batch dimension
(define summed (batch-reduce 'sum doubled))

Zero-Copy Structural Chain

(define x (morph-from-list '(0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 
                             8.0 9.0 10.0 11.0 12.0 13.0 14.0 15.0)
                           '(16) 'f64))

;; Stride-2 downsample
(define x-even (morph-slice x '(0) '(16) 2))      ; shape (8)

;; Stride-2 again - composed becomes stride-4
(define x-quarter (morph-slice x-even '(0) '(8) 2)) ; shape (4)

;; Reshape and transpose - all zero-copy views
(define as-2x2 (morph-reshape x-quarter #(2 2)))
(define transposed (morph-transpose as-2x2 '(1 0)))

;; Only when we realize is data accessed
(morph->list (realize transposed))

BLAS Integration

(import array-morphisms-blas-exec)

;; Matrix multiply automatically uses BLAS when available
(define A (morph-from-list '(1.0 2.0 3.0 4.0 5.0 6.0) '(2 3) 'f64))
(define B (morph-from-list '(7.0 8.0 9.0 10.0 11.0 12.0) '(3 2) 'f64))

;; Dispatches to the GEMM of the registered backend; the built-in
;; microBLAS backend is registered by default
(define C (morph-matmul A B))

;; Optionally replace it with the system-BLAS backend
;; (egg array-morphisms-blas) ...
(import array-morphisms-blas-egg-backend)
(register-blas-backend! (make-blas-egg-backend))

;; ... or with the crunch-compiled backend (egg array-morphisms-crunch)
;; (import array-morphisms-crunch-conv-backend)
;; (register-blas-backend! (make-crunch-blas-backend))

(morph->list (realize C))

Element-wise Kernels

(import array-morphisms-activation-exec
        array-morphisms-crunch-activations   ; egg array-morphisms-crunch
        array-morphisms-crunch-threads)

;; Activations, their derivatives, add/sub/mul/div, 2-D reductions and
;; strided copies now run as whole-array kernels split across threads
(register-activation-backend! (make-crunch-threaded-activation-backend))

;; Threading settings, read at every call
(crunch-thread-count 8)          ; threads requested
(crunch-thread-min-chunk 16384)  ; fewest elements per thread

;; Back to the Scheme code, with identical results
(register-activation-backend! #f)

;; Generate, compile and run a kernel for each segop of a replay plan
;; that no other backend runs
(import array-morphisms-crunch-codegen)
(register-crunch-codegen-backend!)

Batched Products and Lifting

(import array-morphisms-lift)

;; x: [8 32 64], a frame of 8 cells of [32 64]; W: [64 16]
(define y (morph-matmul x W))        ; one batched product -> [8 32 16]

;; A whole layer applied to every cell as one computation
(define h (morph-lift (lambda (xc) (morph-tanh-am (morph-matmul xc W))) 2 x))

;; Row sums of each cell: [8 32]
(define r (morph-reduce 'sum h '(2) #f 1))

Scans

(define x (morph-from-list '(1.0 2.0 3.0 4.0) '(4) 'f64))

(morph->list (realize (morph-cumsum x 0)))                 ; (1.0 3.0 6.0 10.0)
(morph->list (realize (morph-cumsum x 0 exclusive?: #t)))  ; (0.0 1.0 3.0 6.0)
(morph->list (realize (morph-scan 'max x 0 reverse?: #t))) ; (4.0 4.0 4.0 4.0)

;; An exponential moving sum
(morph->list (realize (morph-scan '(lambda (a b) (+ (* a 0.5) b)) x 0)))  ; (1.0 2.5 4.25 6.125)

Performance Notes

Author

Ivan Raikov

Repository

https://github.com/iraikov/array-morphisms

Requirements

CHICKEN 6.

Optional companion eggs:

License

LGPL-3

References

Mullin, Lenore M.R. A Mathematics of Arrays. Ph.D. Thesis, Syracuse University, 1988.

The MoA formalism provides the theoretical foundation for index transformations as compositional abstractions.

The segmented operations and the map-reduce fusion follow the design of the Futhark compiler (https://futhark-lang.org):

Version History

3.0
Segmented operations: compiled programs are lowered to segops (array-morphisms-segop), run by pluggable segop backends, with a fusion pass (segop-fusion) that fuses maps, reductions and matrix-product epilogues; the scalar-op table (array-morphisms-scalar-ops-table, array-morphisms-scalar-ops). Scans (morph-scan, morph-cumsum, morph-cumprod, morph-scan/fn) with combining expressions, aux arrays and gradients. Frame lifting (array-morphisms-lift: morph-lift, var-lift); morph-matmul multiplies batches; framed reductions; batch-map, batch-zip and batch-scan build one computation. Optional offset GEMM and DOT kernels in BLAS backends; scan, fused and column-sum kernels in activation backends. Slices, pads, stacks, concatenations and comparisons in SSA programs. Convolutions share their image-column buffers. The ri-activation-unary and ri-activation-binary replay instructions are replaced by segop executors.
2.1
Prepared GEMM plans; broadcast kernels in activation backends
2.0
Pluggable element-wise kernel backends for activations, binary ops and 2-D reductions
1.2
Port to CHICKEN 6
1.1
microBLAS backend; faster convolution, im2col and col2im
1.0
Initial release

Contents »