Grassmann: The Coordinate-Independent Linear Algebra Programming Language
Theadora Fields Collin, Gilbert Bernstein, Oded Stein, Saman Amarasinghe
cs.PL
Oct 30, 2026 · v1
cs.MS
TL;DR
The language's metatheory (soundness of denotational semantics, adequacy of operational semantics, SVD/spectral results) is mechanized in Lean 4 with Mathlib.
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%.
Problem
Practitioners write algorithms using coordinate-independent linear algebra but must translate them into coordinate-dependent array code. NumPy-style tools lack coordinate-independent representations, and existing languages with such constructs cover too little linear algebra, particularly exterior algebra and differential geometry at a point on a manifold.
Approach
Grassmann is a small language with dependent types, linear types, and partially (pseudo-)invertible computation. A sublanguage for bases lets users move between coordinate-free and coordinate-based representations. A denotational semantics gives meaning without coordinates, and an operational semantics lowers programs to array code under a chosen basis. The metatheory is formalized in Lean 4.29.1 with Mathlib, with AI assistants (Claude, Codex) helping to generate proof code.
Results
The main mechanized result is adequacy: operational evaluations agree with the denotational semantics for an arbitrary choice of coordinates. Spectral projection and paired SVD results are also proved in Lean. The implementation generates exterior-algebra kernels whose FLOP counts match or improve on reference implementations, with runtimes at most 10% slower.