TOC »
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
- Index Functions as First-Class Objects - Inspectable, composable, and extensible algebraic data
- Unified Abstraction - No split between "generalized" and "specialized" arrays; all operations compose uniformly
- Zero-Copy Views - Structural operations (reshape, transpose, slice) via affine index functions
- Memory Reuse - Two-phase trace/replay execution with buffer planning via graph coloring
- BLAS Integration - Transparent dispatch to optimized linear algebra kernels, including batched matrix products
- Element-wise Kernel Backends - Pluggable whole-array kernels for activations, binary arithmetic, reductions, scans and copies, with results identical to the Scheme code they replace
- Segmented Operations - Compiled programs are lowered to segmented operations (segops), data that kernel backends and code generators can read, fuse and compile
- Scans - Cumulative sums, products, maxima and minima along an axis, and scans with a custom combining expression, each equal to a plain loop
- Frame Lifting - A function on one cell applied to every cell of a frame (every example of a batch, or every attention head) as one computation
- Type Safety - Four element types (f64, f32, s64, s32) with automatic promotion
- Category-Theoretic Foundation - Morphisms as structure-preserving transformations between arrays
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:
- An operation on two dtypes gives the one that comes first in the order f64, f32, s64, s32 (so s64 with f32 gives f32).
- Transcendental functions and activations (exp, log, sin, relu, ...) of integers give f64.
- Reductions keep the dtype, except that a mean of integers gives f64.
- 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:
- the activations relu, sigmoid and tanh, and the derivative ops relu-deriv, sigmoid-deriv and tanh-deriv emitted by the backward pass;
- the binary ops add, sub, mul and div, on operands of the output's shape or broadcast by row, column or scalar;
- reductions of row-major 2-D arrays over axis 0 or 1;
- scans (sum, prod, max, min) of row-major arrays along any axis;
- copies of strided views into row-major order;
- fused kernels, each computing a whole segop body of several ops in one pass (see Fusion below).
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.
- Slices, constant pads, stacks and concatenations pass their gradients back to their inputs. A slice with a step above 1, and edge or reflect padding, have no derivative.
- Comparisons give 0.0 and 1.0 and pass no gradient to their inputs.
- A morph-map procedure has no derivative.
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:
- an element-wise binding into the element-wise binding that consumes it;
- an element-wise binding with other readers into one of them, kept as a second output for the others;
- two element-wise bindings that read a common input (horizontal fusion);
- an element-wise binding into the reduction that reads it (Futhark's redomap);
- an element-wise binding that reads only a reduction's result, as the reduction's final step;
- element-wise bindings that read only a matrix product's result, as its epilogue.
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
- Lazy Evaluation: Operations build expression trees, materialize once
- Zero-Copy Views: Structural operations (reshape, transpose, slice) are free
- Memory Reuse: Use contexts for repeated computations to enable buffer planning
- Batch Operations: Process multiple arrays together for efficiency
- BLAS Dispatch: Automatically uses optimized kernels for large operations
- Element-wise Kernels: Register an activation backend to run activations, binary arithmetic, reductions and scans as compiled, optionally threaded, whole-array kernels
- Code Generation: With the code generator of array-morphisms-crunch registered, the default fusion policy fuses passes over the same data and compiles a kernel for each segop that no catalogue kernel runs
- Frame Lifting: Lift a function over a frame instead of slicing and stacking; the lifted expression has as many nodes for any frame size
Author
Repository
https://github.com/iraikov/array-morphisms
Requirements
CHICKEN 6.
- datatype
- matchable
- random-mtzig
- srfi-1
- srfi-4
- srfi-69
Optional companion eggs:
- array-morphisms-blas: system-BLAS backend (needs a BLAS library)
- array-morphisms-crunch: crunch-compiled BLAS, convolution and element-wise kernels, and a segop code generator (needs the crunch egg)
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):
- T. Henriksen, N. G. Serup, M. Elsman, F. Henglein and C. E. Oancea. Futhark: Purely Functional GPU-Programming with Nested Parallelism and In-Place Array Updates. PLDI, 2017.
- T. Henriksen, F. Thorøe, M. Elsman and C. E. Oancea. Incremental Flattening for Nested Data Parallelism. PPoPP, 2019.
- T. Henriksen, K. F. Larsen and C. E. Oancea. Design and GPGPU Performance of Futhark's Redomap Construct. ARRAY, 2016.
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