← All papers
First page of Composable Rewrites for Layouts of Algebraic Data Types

Composable Rewrites for Layouts of Algebraic Data Types

Christophe Gyurgyik, Alexander J Root, Benjamin Driscoll, Gabriel Radanne, Fredrik Kjolstad, Clément Pit-Claudel

cs.PL Nov 14, 2026 · v2
The layout language, rewrite rules, local refinement criterion, soundness and storage-recovery theorems are mechanized in Lean, with each formal statement cross-referenced to a Lean declaration.
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.

Physical layouts of algebraic data types strongly affect performance and memory footprint, and no single layout is best for every workload. Exploring the space of layouts requires composable layout transformations that provably preserve program semantics.

A layout language and local rewrite rules (padding, boxing, commuting, splitting, tagging) transform a canonical layout derived from the ADT declaration. A local refinement criterion, proved via reconstruction functions over structural representations, is lifted through contexts and recursive bindings so that rewritten layouts stay faithful. A codec recovery property connects these representations to bits. The development is mechanized in Lean and implemented in Isomer, a pure functional language whose compiler specializes construction, matching and reference counting to the chosen layouts.

Every layout reachable by valid rewrites is proved faithful, and storage recovery holds under the stated codec conditions. Isomer's default layouts perform competitively with established functional compilers, and workload-specific rewrites improve performance further, reaching representations that prior work cannot express without source changes.