CS Paper Radar

Grassmann: The Coordinate-Independent Linear Algebra Programming Language

Theadora Fields Collin, Gilbert Bernstein, Oded Stein, Saman Amarasinghe

cs.PL cs.MS ·submitted 2026-10-30 15:52 UTC · v1

Abstract

Scientists, engineers, and mathematicians often formulate algorithms using coordinate-independent linear algebra because its tools are composable and harder to misuse. For numerical processing, however, users must translate these ideas into coordinate-dependent array code. Most practitioners do so prematurely because tools such as NumPy lack coordinate-independent representations, while existing languages with such constructs do not model enough linear algebra for the situations where they matter. We propose Grassmann, a small language bridging coordinate-independent linear algebra and coordinate-dependent implementations. It uses dependent types, linear types, and partially (pseudo-)invertible computation to model situations arising in exterior algebra and differential geometry. It targets the linear algebra at a point on a manifold, a prerequisite for many specifications in scientific computing and computer graphics. A language for coordinates lets users move between these representations. We give a denotational semantics assigning meaning without coordinates and an operational semantics translating Grassmann to array code under a choice of coordinates. Our main metatheoretic result shows that operational evaluations agree with the denotational semantics under an arbitrary choice of coordinates. This models how practitioners translate linear algebra for computers and suggests an approach to algorithmic optimization at a high level of abstraction. Our optimized implementation generates code for exterior algebra operations with overheads no more than 10%.

Comment
147 pages, including references and appendices

Closest papers

Nearest neighbours by meaning across the whole index.

Scenes: A Meta-Logical Algebra for Mutable State

cs.LO ·2026-09-24 ·Simon Foster, Carlos Isasa, Christian Pardillo Laursen
hot direction similarity 0.65
Abstract · Submitted to MFCS 2026, rejected. Plan to revise and resubmit elsewhere

Modelling of mutable state spaces and precisely describing how variables are manipulated in a program is a fundamental problem in compositional verification. Though we can make use of the embedded abstract syntax of a program for such analysis, this runs contrary to the shallow-embedding approach, and hampers efficient proof automation. On the other hand, lenses and prisms provide an elegant algebraic foundation for modelling state, which provide sufficient structure to provide meta-logical program analysis, but without requiring a deep embedding. Nevertheless lenses, as complex algebraic objects, cannot easily be combined, complemented, or collected in sets. In this paper we contribute an accompanying algebraic structure called the scene, which allows us to characterise the set of variables, or coordinates, in a state space. Scenes intuitively correspond to sets of lenses, but like lenses they are purely semantic algebraic objects. We demonstrate that scenes provide us with sufficient structure to characterise the lens-based meta-logical properties, like independence and equivalence. Moreover, we introduce the notion of a scene space, analogous to a vector space, which allows us to recover a set-like algebraic structure. Finally, we show how scenes allow us to characterise the free and bound variables of expressions and programs, without any need for syntax, and demonstrate their use for reasoning about programs by deriving reasoning principles for the parallel composition operator.

0.34

Coordinate-Free Automatic Differentiation

cs.LG cs.MSmath.DG ·2026-10-08 ·Alex Guerra, Joshua Aduol, Yaqian Tang, Daniel Williams, Ryan P. Adams +1 more
similarity 0.61
Abstract · 34 pages, 18 figures

Automatic differentiation (AD) is a cornerstone of modern machine learning. Since all AD frameworks implicitly fix a basis of Euclidean space to define gradients and Jacobians, they natively process mathematical objects that are arrays of a fixed set of coordinates. This makes it awkward to express objects such as rotations, volume forms, and curvatures that arise, for example, in applications of AI to science. Bespoke workarounds lack reusability. We show that (i) a single, basis-independent derivative operator can represent many geometric differential operations, and (ii) this operator can be expressed entirely in terms of existing AD primitives. This reusable transformation can be composed with JAX batching, compilation, and hardware acceleration. Geometry enters as algebraic data. We experimentally demonstrate its reuse across different manifold operators, its composition through a spacetime inverse-problem pipeline, and its use in optimization over different rotor subgroups.

0.27

Composable Rewrites for Layouts of Algebraic Data Types

cs.PL ·2026-11-14 ·Christophe Gyurgyik, Alexander J Root, Benjamin Driscoll, Gabriel Radanne, Fredrik Kjolstad +1 more
similarity 0.59
Abstract

Algebraic data types (ADTs) decouple the logical structure of data from physical layout choices that affect performance. For example, packing small fields into a word improves spatial locality, while storing co-accessed fields contiguously can enable vectorization. Such choices reinforce or undermine one another, with ramifications for compiler optimizations and memory management. Their interplay creates a combinatorial space of layouts with different runtime costs and memory footprints. The most favorable layout depends on the program's construction and destruction patterns, the characteristics of input data, and the target machine. Exploring this space requires control over layout decisions and a way to compose them while preserving program semantics. We provide both through rewrite rules over layouts, independent of any particular source language or bit-level encoding. Starting from a canonical layout derived from the ADT, these rules transform its representation while leaving the source program intact. We identify a local refinement criterion for proving each rewrite rule correct, so that layouts continue to represent every value and keep distinct values apart. Adding a new rule therefore only requires a proof satisfying this local criterion. We realize these rules in Isomer, a new pure functional programming language whose compiler specializes construction, pattern matching, and memory management to the chosen layouts. Using a default layout for all ADTs, Isomer achieves competitive performance against established functional compilers that automatically select layouts. Our rewrites further improve performance by tailoring layouts to each workload, permitting representations that prior work cannot attain or can only achieve through explicit changes to the source code.

0.44

Expressing NumPy Broadcasting via Verb Rank in J

cs.PL cs.MS ·2026-09-13 ·Marcin Żołek
similarity 0.58
Abstract

The array programming paradigm applies operations to entire arrays rather than individual elements, eliminating explicit loops and abstracting many low-level details of computation. Two influential approaches have shaped array programming: NumPy's broadcasting and Kenneth Iverson's array-oriented notation, with the latter first introduced in APL and later developed in the J language. Although NumPy's array programming model was influenced by Iverson's work, the two systems formalize array operations differently: NumPy primarily through array shapes and broadcasting, and J through verb rank. This paper establishes a formal correspondence between NumPy broadcasting and J rank and presents an implementation of NumPy broadcasting in J. The results provide a formal connection between two influential approaches to array-oriented computation and show how they address the common problem of applying operations to arrays with differing shapes without explicit loops.

0.28

Mechanising Denotational Semantics in Agda

cs.PL ·2026-10-10 ·Peter D. Mosses, Jesper Cockx, Bernhard Reus
published similarity 0.58
Abstract · 23 pages, excl. references. To be published in Proceedings of MFPS 2026

Mechanisation of a mathematical definition (also referred to as formalisation) has many benefits. Here, we focus on mechanising denotational semantic definitions of programming languages by embedding them in the Agda language. The Agda type-checker detects and reports any issues with the wellformedness and type correctness of the embedded definitions. To minimise the effort required, and to facilitate correlation of the original definition with its Agda embedding, mechanisation should not involve significant reformulation or extension. Here, we show how to embed conventional Scott-Strachey denotational definitions in Agda with almost no changes to $λ$-notation or domain equations. Agda notation for definitions of types and functions corresponds closely to the conventional meta-notation of denotational semantics. We have developed a collection of Agda modules with postulated types for commonly used domain constructors and their associated operations. We illustrate our approach with mechanisations of three denotational definitions: a model of the untyped $λ$-calculus, Plotkin's denotational semantics of PCF, and a semantics of a sublanguage of Scheme. In previous work, similar mechanisations in Agda have revealed several unsuspected wellformedness issues in published denotational definitions. Some of the postulated properties of our definitions are inconsistent with a classical set-theoretic interpretation of Agda. We conjecture that they would be consistent with an interpretation of Agda in a higher-order intuititionistic logic, such as that used by Simpson in his work on synthetic domain theory. After recalling previous work on mechanising domain theory, we consider the possibility of mechanising synthetic domain theory in Agda.

0.30

Representing Tensors as Compositions for Efficient Computation on Sparse and Structured Data

cs.LG cs.MScs.PL ·2026-11-07 ·Valérian Rey, Praneth Paruchuri
code/data similarity 0.57
Abstract · 15 pages, 6 figures

We propose a new mathematical formalism in which all kinds of tensors and of operations on those tensors are represented as simple function compositions. Tensors are functions from indices to values. An element-wise operation (e.g. an activation function) is a composition with a function applied to values; re-indexing (e.g. reshape, transposition) is a composition with a function applied to indices; and a reduction is a composition with both an index function, mapping each index to several indices, and a reduction operation (e.g. product, sum, max). Combined with tensor stacking, these compositions can represent most interesting kinds of tensors (e.g. dense, jagged, all kinds of sparsity patterns, matrix factorizations), as well as lazy versions of almost every operation available in modern tensor computation frameworks, including einsums between tensors of any kind. Identities between compositions can then be used to rewrite such expressions into equivalent ones, without evaluating them. For instance, the product of two sparse matrices can be rewritten so that only products between non-zero values are computed, turning a sparse problem into a dense one. Using this algebra as the intermediate representation of a tensor computation engine would shift the focus from defining operations on tensors (e.g. einsum between sparse tensors) to defining an algebra on index functions. This should reduce the codebase complexity from $\mathcal{O}(mn^2)$, with $m$ the number of binary operations between tensors and $n$ the number of tensor types, to $\mathcal{O}(m + k^2)$, with $k$ the number of types of index functions. A draft implementation of a tensor computation framework based on this algebra is publicly available.

0.21

A Simplified Layout Algebra for GPU Kernels

cs.PL ·2026-10-09 ·Nan An, Xiaotian Zhou
similarity 0.57
Abstract

The layout algebra behind NVIDIA's CuTe library describes how tensor tiles map onto threads and memory. A layout is a shape with a stride for each entry, so a coordinate's address is the sum of its indices times their strides. As formalized by Shah and by Cecka, its central operations (e.g., composition, complement, division, product) are guarded by at least six interacting admissibility conditions. We show that this complexity is an artifact of a representational choice, not of the domain. We present a layout algebra in which every layout names the space its inputs and outputs live in: logical, physical, or thread-value indices. A layout into logical or thread-value space must be a bijection from its $N$ coordinates onto $[0,N)$. A layout into physical space must be alias-free: distinct coordinates land on distinct addresses, except under broadcast, where many threads read one value on purpose and the layout must mark where. Nothing maps out of a physical index. Composing $f$ with $g$ requires only that $f$'s range be exactly $g$'s flattened coordinate set. The index arithmetic can always be emitted naively: compute $f$, split the result by division and remainder into $g$'s coordinates, and apply $g$. Often the composite simplifies to a layout; we show that when it does, there is a coarsest such form, whose digits every other one refines, and we emit that. A warp's or thread's slice is a \emph{restriction}. A restricted layout is no longer composable, which forces the user to settle the whole view of a tile before taking slices. We validate the algebra by reproducing within it CuTe's operations, such as composition, complement, and division. We implement it in OCaml and use the implementation to rederive CuTe's atoms and usage patterns. The decision procedure is proved correct in Rocq.

0.19

A Rig of Transformations

cs.PL ·2026-08-11 ·Emma Tye
similarity 0.56
Abstract

In high-level functional languages, the compiler often gives users little control over the runtime representation of data types. Yet how we model data structures at the program level can be different to how we want to represent them at the binary level, for efficiency or legacy reasons. Hence being able to describe data layouts and their transformations for data types is a useful and necessary part of programming, but difficult to do correctly, efficiently and ergonomically. We present a model of finite algebraic data types as a commutative rig (a ring without additive inverses), where the rig-equalities are modelled by isomorphisms between data. Using this approach, we can also model embedding a data type into a larger type (e.g. bit-padding) as a partial isomorphism.

0.04