betaFeedback

WorksComputer Science

Decoupling Data Layouts from Algebraic Data Types

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.

Introduction

Algebraic data types (ADTs) describe data by composing products and sums: a product type holds a value of each of its component types, and a sum type holds a value of exactly one of its alternatives. This abstraction supports type-safe construction and pattern matching independently of any physical representation, and thus the same logical values can be represented using many different memory layouts.

The choice among these layouts can substantially affect runtime performance and memory footprint, motivating extensive research on ADT layout optimizations in functional programming languages [6, 14, 23, 24, 25, 28, 33, 50, 61, 70, 78]. For example, packing small fields into a word can save space but may require additional instructions or unaligned loads when they are read, while boxing a large, rarely accessed field places it behind a pointer, keeping frequently accessed data compact at the cost of a pointer dereference for infrequently accessed data. These choices are interdependent; the benefits of boxing depend in turn on how the remaining fields are packed and ordered.

Furthermore, layouts are necessarily entangled with the language implementation. Field widths and alignment affect instruction selection and vectorization [7, 28, 96, 97], while the sizes of allocated objects constrain opportunities for memory reuse [56, 57, 73]. A layout therefore cannot be evaluated in isolation: its performance depends on which optimizations it enables and which of those optimizations the compiler applies. More broadly, a program’s construction and destruction patterns, characteristics of its input data, and the target architecture shape the Pareto frontier between runtime performance and memory footprint, leaving no universally best layout [28].

Language implementations presently address these costs through both automatic layout selection and explicit representation control. MLton and Morphic select representations through compiler analyses [9, 10, 95]. Haskell and OCaml expose representation choices through type system extensions [11, 24, 51, 70]. More recently, layout description languages make the separation of data type and data layout explicit and programmable [6, 14, 28].

We build on the decoupled approach of prior work [6, 14, 28], introducing composable rewrite rules over a layout language for deriving ADT representations independently of a particular source language or bit-level encoding. Rather than writing each candidate layout in full, as required by layout description languages [6, 14, 28], a programmer or an automated search procedure starts from a canonical layout induced by the source type, and transforms it through incremental rewrites. A layout is faithful when every source value has a representation and no representation corresponds to two distinct values. Our key insight is that a local criterion is enough to preserve faithfulness: each rewrite rule need only satisfy it on the part of the layout it changes. For a core calculus, we derive construction and destruction for rewritten layouts and prove that valid rewrite sequences preserve the result of terminating programs. Adding a new rewrite rule requires only a reconstruction function that establishes the local correctness criterion.

We implement these rewrite rules in Isomer, a pure functional programming language and compiler that embodies a separation of concerns: changing a layout never requires modifying the program. The compiler specializes construction, destruction, and memory management (reference counting) to the rewritten layouts. To support different layouts across program phases, Isomer also provides a coerce scheduling directive, which inserts a change of representation at a selected variable binding while leaving the source code unchanged. Our primary contributions are:

  • Composable layout rewrite rules that, independent of a particular source language or machine, express a broad range of layouts and support extension with new rules.

  • A formal model of layouts that separates structural representation from any particular bit-level encoding. Per-rule proofs compose to show that valid rewrites keep layouts faithful and preserve the scalar results of terminating programs.

  • Isomer, a new pure functional programming language that decouples layout rewrites from the source program, and a compiler that automatically specializes with respect to rewritten layouts. Isomer additionally supports transformations of ADT layouts at arbitrary program points.

Our evaluation demonstrates that Isomer is competitive with state-of-the-art functional languages, and our decoupled abstraction incurs no performance overhead. In three case studies, we examine composing rewrites, memoizing compute without editing the source code, and changing layouts between program phases. With an automatically selected layout, Isomer achieves geomean speedups of 1.32×1.32 \times over Morphic [9] and 1.46×1.46 \times over MLton [95], whose compilers automatically select representations. We also perform layout design space exploration, where the fastest measured layout per benchmark gives a 1.25×1.25 \times (geomean) speedup over the default, and the layout with the lowest peak memory reduces memory by 25%. We compare Isomer with Ribbit [6], a layout description language for general-purpose ADTs and the closest prior work. Isomer’s code generation yields a 1.53×1.53 \times (geomean) speedup when matching Ribbit’s layouts. Lastly, we show layout control complements automatic memory management: with equivalent layouts, Isomer uses at most the peak memory of Koka’s fully-in-place programs [57], and further rewrites lower peak memory by an additional 20%.

Finally, we clarify the scope of this work. First, we assume finite trees and monomorphization in our implementation. Although monomorphization typically bars features such as polymorphic recursion and separate compilation, runtime specialization [41] could relax this restriction. Second, we focus on data representation, which is orthogonal to the execution strategies that user-schedulable languages decouple from algorithms [30, 32, 71]. Combining the two in a general-purpose functional language would be a natural direction for future work. Third, our formalism covers a formal model of layouts, program preservation under layout rewrites, and recovery from physical encodings under explicit conditions. It does not establish end-to-end correctness of the Isomer compiler.

Optimizing Layouts of Red-Black Trees

Consider a programmer implementing an ordered set as a red-black tree [65]:

Color=Red∣Black\mathrm{Color} = \mathrm{Red} \mid\mathrm{Black} \qquad Tree=Leaf∣Node(c:Color,l:Tree,k:u64,r:Tree)\mathrm{Tree} = \mathrm{Leaf} \mid\mathrm{Node}(c : \mathrm{Color}, l : \mathrm{Tree}, k : u_{64}, r : \mathrm{Tree})

Throughout this section, the type and source code stay fixed while the physical layout changes. The layout of Tree is defined recursively and each child field, ll and rr, uses the same layout. We assume little-endian byte order, 64-bit pointers and 8-byte aligned allocations. Our diagrams place storage offsets in increasing order from left to right, with each field’s least significant bit (LSB) on the left. Adjacency (xx\boxed{\phantom{x}}\boxed{\phantom{x}}) represents contiguous memory, braces ({t∣⋯ }\{t \mid\cdots\}) distinguish arms discriminated by a value tt, arrows (⟶\longrightarrow) lead from pointers to heap cells, and zero bits (00) are marked separately from padding (□\square), whose contents are undefined.

A rewrite makes one elementary change to a layout, e.g., inserting unused bits before a field (pad), moving a field into a heap cell (box), or swapping two adjacent fields (commute):

c→pad□ck→boxx⟶kk c l→commutel cc \xrightarrow{\mathrm{pad}} \square c \qquad k \xrightarrow{\mathrm{box}} \boxed{\phantom{x}}\longrightarrow k \qquad k\ c\ l \xrightarrow{\mathrm{commute}} l\ c

Each layout below is realized with a sequence of such rewrites. We start with the layout that Morphic [9, 10] automatically selects for this type and explore alternative layouts. This initial layout follows a C-style tagged union with natural alignment, in which a tree value is a byte tag (or discriminant) beside a pointer to a separately allocated heap cell. Fields are aligned, and those that are less than one word are padded to a full word (8 bytes). A tree value therefore occupies 16 bytes, and the node’s fields occupy 48 bytes, including both 16-byte children.

Tree={tag t  ∣  paddingif t∈Leaf,tag t  ∣  pointer⟶(c  ∣  padding  ∣  l  ∣  k  ∣  r)if t∈Node.(1)\begin{aligned} \mathrm{Tree} &= \begin{cases} \text{tag }t\;|\;\text{padding} & \text{if }t \in\mathrm{Leaf},\\ \text{tag }t\;|\;\text{pointer}\longrightarrow(c\;|\;\text{padding}\;|\;l\;|\;k\;|\;r) & \text{if }t \in\mathrm{Node}. \end{cases} \tag*{(1)} \end{aligned}

While this layout permits aligned memory loads, nearly half of the bits in the Node’s fields are zero or padding. Systems programmers reclaim such bits by hand. The Linux kernel’s implementation of a red-black tree, for example, stores a Node’s color in an unused low bit of its parent pointer [87]. This decision also exposes clever instruction selection. Red is encoded as zero, so a red Node’s parent field stores exactly its parent’s address, and tree insertion can dereference it without masking [52]. Similarly, a pointer to a black node can be effectively encoded as p+1p+1 where pp is the pointer address, resulting in a single instruction, lea, on x86 [27]. The same opportunity exists in our tree: moving each child’s tag into a low bit of its pointer shrinks each to one word. We also hoist the color of each Node into a second low bit of the pointer that references it, resulting in a 24-byte cell:

Tree={tag t  ∣  paddingif t∈Leaf,tag c  ∣  pointer⟶(l  ∣  k  ∣  r)if t∈Node.(2)\begin{aligned} \mathrm{Tree} &= \begin{cases} \text{tag }t\;|\;\text{padding} & \text{if }t \in\mathrm{Leaf},\\ \text{tag }c\;|\;\text{pointer}\longrightarrow(l\;|\;k\;|\;r) & \text{if }t \in\mathrm{Node}. \end{cases} \tag*{(2)} \end{aligned}

The layout applies recursively to both children: each occupies one word, consisting of a one-bit tag followed by either a color bit and a 62-bit pointer for a Node or 63 bits of padding for a Leaf. An additional benefit is that red-black tree rebalancing can test children’s colors directly without first dereferencing a pointer.

But we can go further: by default, x86-64 Linux places user allocations below 2472^{47} [84], leaving the upper 17 bits of their 64-bit addresses zero. An 8-byte-aligned address thus needs only bits [3,47)[3,47). This enables a double-ended bit stealing technique [25], where a pointer is stored in just 44 bits. Consequently, a child now occupies only 47 bits of space, and some additional padding keeps each cell’s fields at byte boundaries:

{46 bits of paddingif t∈Leaf,1-bit color+1-bit padding+44-bit pointerif t∈Node.(3)\begin{cases} \text{46 bits of padding} & \text{if } t \in\text{Leaf},\\ \text{1-bit color}+\text{1-bit padding}+\text{44-bit pointer} & \text{if } t \in\text{Node}. \tag*{(3)} \end{cases}

So far, these rewrites reclaim unused bits in an effort to reduce the memory footprint. The tag can also distinguish more interesting tree shapes, which lets a layout store such shapes more compactly. Consider a Node whose children are both Leaf, such as the one each insertion creates for its new key. Layout 3 still reserves 47+47=9447+47=94 bits for these two children, even though they provide no additional information. We can instead give this shape an arm of its own, Node(Leaf, Leaf), similar to prior work in acceleration structure design [7]. Within this arm, an unfold rewrite expands each child’s layout, and, since the layout of Leaf is empty, l and r do not need to be stored. With the color already in the reference, this arm’s cell then holds only its key, in exactly 8 bytes. With three arms, the tag widens to two bits, and every other Node(∙,∙\mathord{\bullet},\mathord{\bullet}) shape falls back to the general Node layout. Its cell is unchanged, and the wider tag takes the place of the padding bit before its pointer:

{45 bits of paddingif t∈Leaf,1-bit color+44-bit pointer+64-bit keyif t∈Node(Leaf, Leaf),1-bit color+44-bit pointer+1-bit padding+47-bit l+1-bit padding+47-bit r+1-bit padding+64-bit kif t∈Node.(4)\begin{cases} \text{45 bits of padding} & \text{if } t \in\text{Leaf},\\ \text{1-bit color}+\text{44-bit pointer}+\text{64-bit key} & \text{if } t \in\text{Node(Leaf, Leaf)},\\ \text{1-bit color}+\text{44-bit pointer}+\text{1-bit padding}+\text{47-bit }l+\text{1-bit padding}+\text{47-bit }r+\text{1-bit padding}+\text{64-bit }k & \text{if } t \in\text{Node}. \tag*{(4)} \end{cases}

Further rewrites can exploit properties of the data. Keys may be drawn from a much smaller distribution than the type admits. A refine rewrite gives the specialized Node whose keys are below 2322^{32} an arm of their own, which stores the key in 32 bits. As the color already sits in the reference, an unbox rewrite can store the key there too, in place of the pointer, leaving this arm with no cell at all. The layout maintains the full u64 domain, but incurs a cost of checking whether the key fits in 32 bits when constructing a node:

{45 bits of paddingif t∈Leaf,1-bit color+5-bit padding+32-bit k+7-bit paddingif t∈Node(Leaf, Leaf)∧k<232,1-bit color+44-bit pointer+64-bit kif t∈Node(Leaf, Leaf)∧k≥232,1-bit color+44-bit pointer+1-bit padding+47-bit l+1-bit padding+47-bit r+1-bit padding+64-bit kif t∈Node.(5)\begin{cases} \text{45 bits of padding} & \text{if } t \in\text{Leaf},\\ \text{1-bit color}+\text{5-bit padding}+\text{32-bit }k+\text{7-bit padding} & \text{if } t \in\text{Node(Leaf, Leaf)} \land k<2^{32},\\ \text{1-bit color}+\text{44-bit pointer}+\text{64-bit }k & \text{if } t \in\text{Node(Leaf, Leaf)} \land k\ge2^{32},\\ \text{1-bit color}+\text{44-bit pointer}+\text{1-bit padding}+\text{47-bit }l+\text{1-bit padding}+\text{47-bit }r+\text{1-bit padding}+\text{64-bit }k & \text{if } t \in\text{Node}. \tag*{(5)} \end{cases}

Finally, layouts also interact with memory management. Rebalancing a tree consumes and rebuilds nodes, and the compiler can reuse the allocation of a consumed cell for a rebuilt node if they share the same size [73, 89]. In Layout 5, a Node(Leaf, Leaf) with a 64-bit key outgrows its 8-byte cell when an insertion replaces one of its Leaf children, forcing a fresh allocation. A pad rewrite restores reuse by growing these cells to 20 bytes, which prior work on reference counting achieves by modifying the source program itself [57].

We express optimizations beyond this example, such as array inlining [96] and memoizing values that are expensive to recompute [67]. Each layout exploits a semantics-preserving transformation of the program, and the best combination depends on the workload in ways that fixed compiler heuristics cannot easily realize. A functional programmer today can express only a handful of these layouts, and even those often require manipulating types or the source program itself [57, 58, 70].

Overview

We now present a general framework for expressing and composing such layout transformations. § 4 introduces a layout language that can describe each layout above, together with rewrite rules that each make a local change, e.g., swapping two fields or placing a field behind a pointer. Layout rewriting starts from a source type’s canonical layout, which mirrors its type declaration.

§ 5 to § 7 develop the formalism. § 5 defines the structural representations a layout permits for each source value, which describe how the layout organizes the value before it is encoded as bits. § 6 proves each rule correct on the part of the layout it changes and lifts this guarantee through enclosing and recursive layouts, so every layout reached from the canonical one by valid rewrites is faithful, and terminating programs in a core calculus compute the same scalar results. § 7 gives conditions under which a model encoder and decoder recover source values from memory. The development is mechanized in Lean1[64], and references identify Lean declarations corresponding to formal statements and grammars, e.g., Lean: WF. Appendix I indexes the complete set of definitions, theorems, and worked examples.

§ 8 describes the implementation, Isomer, a new functional language that uses our rewrites to derive data layouts. Its compiler specializes construction, destruction, and reference counting to the resulting layouts, and its coerce directive changes a value’s layout between program phases that favor different layouts. Finally, we evaluate the runtime performance and memory footprint of Isomer programs in § 9, through case studies and comparisons with state-of-the-art functional languages.

Layout Language

A layout describes how the values of a source type are represented (grammar in Figure 1). Before defining the individual constructs, we express Layout 3 from § 2 in the layout language:

Grammar of the layout language

ℓ::=ϵ∣π:ℓ\ell::= \epsilon\mid\pi: \ell — empty, name ℓ::=pad⁡n∣zero⁡n∣un∣⟨e⟩\ell::= \operatorname{pad}_{n} \mid\operatorname{zero}_{n} \mid u_{n} \mid\langle e \rangle — leaves ℓ::=&n(ℓ)\ell::= \&_{n}(\ell) — pointer ℓ::=ref⁡ T\ell::= \operatorname{ref}\ T — recursive reference ℓ::=ℓ0×ℓ1\ell::= \ell_{0} \times\ell_{1} — product ℓ::={ϕj⇒ℓj}\ell::= \{\phi_{j} \Rightarrow\ell_{j}\} — sum ℓ::={(cj,ϕj)⇒ℓj}\ell::= \{(c_{j},\phi_{j}) \Rightarrow\ell_{j}\} — disjoint sum

π::=ϵ∣x.π∣π[i,j)\pi::= \epsilon\mid x.\pi\mid\pi[i,j) — names and bit subsets e::=n∣π∣e⊕ee ::= n \mid\pi\mid e \oplus e — memoized expressions ϕ::=⊤∣⊥∣π↦K∣π↦c\phi::= \top\mid\bot\mid\pi\mapsto K \mid\pi\mapsto c — provenance; constructor, scalar ϕ∩ϕ∣ϕ∪ϕ\phi\cap\phi\mid\phi\cup\phi — intersection, union Δ::=∅∣Δ,T↦ℓ\Delta::= \varnothing\mid\Delta, T \mapsto\ell — layout environment

x,T,K∈Id,n,i,j,c∈Nx,T,K \in\mathrm{Id}, \quad n,i,j,c \in\mathbb{N}

Figure 1. Grammar of the layout language. Lean: Layout, Path, Expr, Prov, LayoutEnv.

ℓ:u1×⨆{(0,Leaf)⇒pad⁡46,(1,Node)⇒c:ref⁡ Color×pad⁡1×&44(l:ref⁡ Tree×pad⁡1×r:ref⁡ Tree×pad⁡1×k:u64)}\ell: u_1 \times\bigsqcup\left\{ (0,\mathrm{Leaf}) \Rightarrow\operatorname{pad}_{46}, \\ (1,\mathrm{Node}) \Rightarrow c : \operatorname{ref}\ \mathrm{Color} \times\operatorname{pad}_{1} \times\&_{44}(l : \operatorname{ref}\ \mathrm{Tree} \times\operatorname{pad}_{1} \times r : \operatorname{ref}\ \mathrm{Tree} \times\operatorname{pad}_{1} \times k : u_{64}) \right\}

Read from left to right, a tree stores a one-bit tag tt, followed by the arm that tt selects, code 0 for a Leaf and 1 for a Node. A Leaf stores 46 bits of padding, while a Node stores its color, a bit of padding, and a 44-bit pointer to its remaining fields. The color cc refers to the layout of Color, which stores only a one-bit tag. Each child refers back to the layout of Tree, thus each occupies 1+1+1+44=471 + 1 + 1 + 44 = 47 bits. The rest of this section defines these constructs and the rewrite rules that derive this layout from the one induced by the source type.

Values and Paths

Source values are unsigned scalars and finite constructor trees K(v1,…,vn)K(v_1,\ldots,v_n), with fields in the order originally given by the source type. We write V\mathcal{V} for all source values and Vτ⊆V\mathcal{V}_{\tau} \subseteq\mathcal{V} for all source values of an algebraic data type τ\tau. We call the source value that a layout represents its subject. A path π\pi selects a subvalue, or a range of bits of a scalar, and write v.πv.\pi for the value that $\pi selects from vv, when it exists. The empty path ϵ\epsilon selects vv itself, the path xx selects its field xx, and x[i,j)x[i,j) selects bits [i,j)[i,j) of that field, counting from the least significant bit. For example, in node v=Node⁡(Black⁡,Leaf⁡,5,Leaf⁡)∈VTreev = \operatorname{Node}(\operatorname{Black}, \operatorname{Leaf}, 5, \operatorname{Leaf}) \in V_{\mathrm{Tree}}, the path k selects the key, v.k=5v.\mathrm{k} = 5, and k[0,2)\mathrm{k}[0,2) selects its two low bits, v.k[0,2)=1v.\mathrm{k}[0,2) = 1. For simplicity, we assume that a field name shared by constructors always has the same type.

Provenances

A layout can exploit knowledge of a value’s constructors to specialize its representation [7, 78]. Following Baudon et al. [6], we call this knowledge a provenance. We depart from their patterns by taking each provenance to be the set of values it denotes, so that provenances form a lattice. The provenance π↦K\pi\mapsto K denotes the source values whose subvalue at path π\pi has constructor KK, and we abbreviate ϵ↦K\epsilon\mapsto K as KK. Since a path can be arbitrarily long, a provenance can test a subvalue at any depth, such as l.r↦Leaf⁡\mathrm{l.r} \mapsto\operatorname{Leaf} for a node whose left child’s right child is a Leaf. A scalar guard π↦c\pi\mapsto c similarly selects the values with scalar cc at path π\pi, e.g., Layout 5 guards its small keys by ⋃i=0232−1k↦i\bigcup_{i=0}^{2^{32}-1} \mathrm{k} \mapsto i. As sets of values, provenances form a lattice bounded by ⊤=V\top= \mathcal{V} and ⊥=∅\bot= \varnothing, with intersection as meet, union as join, and inclusion as order. Two provenances are equal when they denote the same values. Appendix § 12 provides the complete depth-one lattice of the red-black Tree. Such provenances readily model patterns on ADTs, e.g.,

Node⁡(_,Node⁡(Black⁡,_,_,_),_,_)≡(ϵ↦Node⁡∩l↦Node⁡∩l.c↦Black⁡).\operatorname{Node}(\_,\operatorname{Node}(\operatorname{Black},\_,\_,\_),\_,\_) \equiv(\epsilon\mapsto\operatorname{Node} \cap\mathrm{l} \mapsto\operatorname{Node} \cap\mathrm{l.c} \mapsto\operatorname{Black}).

Each layout must represent a set A⊆VA \subseteq\mathcal{V} of admitted subjects, the source values that can reach it. An arm has a condition ϕ\phi, its guard, and a layout for the values in A∩ϕA \cap\phi, its payload. A sum offers several arms, whose guards must together cover AA. We additionally allow overlapping guards as an explicit design decision, since some optimizations rely on this [7, 31].

Layouts

To let rewrites target individual layout choices, the language makes explicit how a value is stored. A named layout π:ℓ\pi: \ell makes v.πv.\pi the subject of ℓ\ell, and ϵ\epsilon is the empty layout, which stores nothing. Leaves describe scalar storage: pad⁡n\operatorname{pad}_{n} reserves nn bits with unconstrained contents, and zero⁡n\operatorname{zero}_{n} requires them to be zero. Layout 11, for instance, follows its one-bit tag with zero⁡7\operatorname{zero}_{7} to fill a byte. unu_{n} stores its scalar subject in nn bits. A memoized expression ⟨e⟩\langle e \rangle stores the result of evaluating ee on the subject, at the width of its resulting type. Expressions use integer literals, scalar path reads, and supplied binary operations, but can’t use arbitrary layout components. A pointer &n(ℓ)\&_{n}(\ell) places the representation described by ℓ\ell behind an nn-bit address. A layout environment Δ\Delta maps type names to layouts. An entry Δ(T)=ℓ\Delta(T) = \ell is a layout definition, with body ℓ\ell, and a reference ref⁡ T\operatorname{ref}\ T stands for that body.

Products ℓ0×ℓ1\ell_{0} \times\ell_{1} are binary and ordered; we omit the parentheses of right-associated products. Their components occupy increasing bit offsets from left to right, and offsets restart at zero in each pointee. The cell of Layout 3 places ℓ\ell at offset 0, r\mathrm{r} at 48, and k\mathrm{k} at 96. An ordinary sum ⋃{ϕj⇒ℓj}\bigcup\{\phi_{j} \Rightarrow\ell_{j}\} has arms with distinct guards and represents a subject by the payload of any arm whose guard it satisfies; we name each arm by its guard. A disjoint sum ⨆π{(cj,ϕj)⇒ℓj}\bigsqcup^{\pi}\{(c_j,\phi_j)\Rightarrow\ell_j\} instead selects its arm by the scalar at path π\pi, using arm jj for every subject whose scalar at π\pi equals the code cjc_j. Its codes are distinct, and each guard ϕj\phi_j must contain every admitted subject with code cjc_j.

The double-ended layout of Layout 3 starts as an ordinary sum over Leaf and Node, and tagging turns it into a disjoint sum keyed by its tag field tt (Figure 3). A tag under path tt names the scalar function that computes each value’s code. The tag lists kk guards, guards⁡(t)\operatorname{guards}(t), and a selector sts_t that maps each value vv in their union to the index jj of a guard ϕj\phi_j containing vv. The path tt selects this index, v.t=st(v)v.t=s_t(v), and is undefined on every other value. The selector resolves overlapping guards, so their order imposes no priority. A tag field t:u∣t∣t:u_{\lvert t\rvert} stores the code in ∣t∣=⌈log⁡2k⌉\lvert t\rvert=\lceil\log_2 k\rceil bits.

Figure 3. Rewrites from the canonical body of Tree to Layout 3, abbreviating each field by its name. Each arrow rewrites the preceding layout at its bolded focus.

Finally, source types induce a straightforward canonical layout environment Δcan\Delta_{\mathrm{can}}. It binds each declared type to a sum with one arm per constructor K, whose payload is the product of the constructor’s named fields, or ϵ\epsilon if there are none, and a field of a declared type refers to that type. For the original red-black Tree, we write

Δcan(Tree)=⨆{Leaf⇒ϵ, Node⇒c:ref⁡ Color×l:ref⁡ Tree×k:u64×r:ref⁡ Tree}.\Delta_{\mathrm{can}}(\mathrm{Tree})=\bigsqcup\{\mathrm{Leaf}\Rightarrow\epsilon,\ \mathrm{Node}\Rightarrow c:\operatorname{ref}\ \mathrm{Color}\times l:\operatorname{ref}\ \mathrm{Tree}\times k:u_{64}\times r:\operatorname{ref}\ \mathrm{Tree}\}.

Layout Rewrites

Figure 2 lists a representative subset of rewrite rules used in our implementation, each of which makes one local change to a layout. Commuting fields places data that is read together side by side, and boxing moves rarely read fields out of line behind a pointer. Tagging stores the choice of arm in a tag field that subsequent rewrites can transform like any other field, and memoizing an expression stores a computed result within the layout so that a program reads the result in place of recomputing it. Each rule carries premises, which Appendix C states in full. For example, splitting an nn-bit field at kk requires k≤nk\le n, and pruning an arm requires the remaining arms to cover every admitted subject. Crucially, the rule set is extensible because its proofs are modular. As § 6.3 shows, a new rewrite rule only needs a proof for the part of the layout it changes.

A rewrite applies a rule to one occurrence of a sublayout, its focus, and leaves the rest of the layout fixed. A layout context C[□]C[\square] is the surrounding layout with the focus replaced by a hole, and filling the hole with ℓ\ell gives C[ℓ]C[\ell]. The grammar is

C::=□∣π:C∣&n(C)∣C×ℓ∣ℓ×C∣⨆{ϕ⇒C,Ω}∣⨆π{(c,ϕ)⇒C,Ω}.C::=\square\mid\pi:C\mid\&_{n}(C)\mid C\times\ell\mid\ell\times C\mid\bigsqcup\{\phi\Rightarrow C,\Omega\}\mid\bigsqcup^{\pi}\{(c,\phi)\Rightarrow C,\Omega\}.

For example, C[□]=k:u64×□C[\square]=k:u_{64}\times\square keeps the field k fixed while rewriting the component in the hole. A rule that replaces ℓ0\ell_0 by ℓ1\ell_1 takes C[ℓ0]C[\ell_0] to C[ℓ1]C[\ell_1], and its premises are checked on the subjects that reach the hole through the context’s field selections and guards. We write ℓ0→∗ℓk\ell_0 \to^{*} \ell_k for a finite sequence of rewrites.

Rewriting the body of a type updates the layout environment. An update Δ′=Δ[T↦ℓ1]\Delta' = \Delta[T \mapsto\ell_1] replaces the body assigned to T and leaves other entries unchanged, so every reference ref T, including recursive references, then uses ℓ1\ell_1. Figure 3 derives Layout 3 this way, rewriting the canonical body of Tree one focus at a time, and § 6.2 gives the conditions under which replacements in contexts and updates to definitions preserve faithfulness.

Structural Representation Semantics

To reason about rewrites locally without tying correctness to a particular bit-level encoding, we first reason about structural representations: finite trees that retain the layout’s components and their organization. An encoder then places these components in bits and heap blocks, and a decoder recovers them. Because a structural representation keeps boundaries between components explicit, we show rewrites can be proved correct without reasoning about memory in § 6. In § 7, we encode these representations in bits, where boundaries are implicit, and discuss limitations.

Structural Representations

Structural representations η∈S\eta\in S are defined by the grammar

η::=k∣()∣(η0,η1)∣cons⁡ϕ(η)∣ptr⁡(α,η).\eta::= k \mid() \mid(\eta_0,\eta_1) \mid\operatorname{cons}_{\phi}(\eta) \mid\operatorname{ptr}(\alpha,\eta).

Scalars k∈Nk \in\mathbb{N} hold source data, padding, tags or the results of memoized expressions, at widths supplied by the layout. A product contributes a pair, and a pointer records an address α\alpha together with its pointee’s representation. An ordinary sum contributes a marker cons⁡ϕ(η)\operatorname{cons}_{\phi}(\eta) naming the selected arm by its guard. The marker has no physical counterpart; it keeps arms distinguishable until a tag rewrite stores the choice in a field. A disjoint sum contributes the pair (c,η)(c,\eta) of its selected code and payload; physical encoding stores the code only in the tag field.

For a layout ℓ\ell under environment Δ\Delta, WℓΔ(v)\mathcal{W}^{\Delta}_{\ell}(v) is the set of structural representations of subject vv (defined in Figure 4). Sets accommodate unspecified padding and addresses, as well as overlapping arms. The canonical layout gives a node exactly one structural representation, e.g.,

Structural interpretation of layouts

Figure 4. Structural interpretation of layouts. WℓΔ(v)\mathcal{W}_{\ell}^{\Delta}(v) is the set of structural representations permitted by layout ℓ\ell for source value vv. The layout environment Δ\Delta maps declared types to layout bodies. We write VunV_{u_n} to represent the set {0,…,2n−1}\{0,\ldots,2^n-1\}, and WℓΔ(v)=∅\mathcal{W}_{\ell}^{\Delta}(v)=\varnothing when evaluation is undefined. Lean: Rep

W(Node⁡(Black⁡,Leaf⁡,5,Leaf⁡))={cons⁡Node⁡((cons⁡Black⁡(()),cons⁡Leaf⁡(()),5,cons⁡Leaf⁡(())))}.\mathcal{W}(\operatorname{Node}(\operatorname{Black},\operatorname{Leaf},5,\operatorname{Leaf})) = \{\operatorname{cons}_{\operatorname{Node}}((\operatorname{cons}_{\operatorname{Black}}(()),\operatorname{cons}_{\operatorname{Leaf}}(()),5,\operatorname{cons}_{\operatorname{Leaf}}(())))\}.

Faithfulness

To preserve programs over different layouts, a layout must be total, representing every source value, and absolutely injective, giving distinct values disjoint sets of representations. Totality ensures that a valid construction policy exists, one that chooses a permitted representation for every value a program builds. Absolute injectivity ensures that destruction has a unique answer.

Definition 1 (Faithfulness Lean: Faithful). A layout ℓ\ell faithfully represents τ\tau under Δ\Delta if, for all v,w∈Vτv,w \in V_{\tau},

WℓΔ(v)≠∅\mathcal{W}_{\ell}^{\Delta}(v) \ne\varnothing

(totality),

v≠w⟹WℓΔ(v)∩WℓΔ(w)=∅v \ne w \mathrel{\Longrightarrow} \mathcal{W}_{\ell}^{\Delta}(v) \cap\mathcal{W}_{\ell}^{\Delta}(w) = \varnothing

(absolute injectivity).

Notably, absolute injectivity is analogous to the “no confusion” property of Diatchki et al. [22]. Since WℓΔ\mathcal{W}_{\ell}^{\Delta} is a relation, one value may have several representations, and absolute injectivity only forbids two values from sharing one. A representation η\eta determines vv when it represents vv and no other value of its type. Under a faithful layout, each permitted representation determines its source value. We write MℓΔ(η)=v\mathcal{M}_{\ell}^{\Delta}(\eta) = v for this partial recovery function, reminiscent of the representation function of Hoare [34].

Well-Formedness

Injectivity alone cannot keep values from being lost, e.g., pruning the Leaf arm from the body of Tree maintains absolute injectivity, yet every tree ends in leaves, so every tree loses its representation. The judgment A⊢ℓ wfA \vdash\ell\ \mathrm{wf} establishes totality syntactically, checking each component only on the subjects that reach it. Its rules, defined in Appendix § 13, require, e.g., that field selections are defined, memoized expressions fit their widths, and sum arms cover every admitted subject.

A reference, on the other hand, defers its check to the corresponding layout definition. The environment Δ\Delta is well formed when each body is well formed on all values of its type, Vτ⊢Δ(T) wfV_{\tau} \vdash\Delta(T)\ \mathrm{wf}. We require layout definitions to be structurally recursive, so each reference applies to a smaller source value. Syntactically, every reference in a body must occur within a named layout whose path begins with a field name, e.g., ℓ:ref Tree\ell: \mathrm{ref}\ \mathrm{Tree} applies the ref Tree\mathrm{ref}\ \mathrm{Tree} layout to the left child. We package the assumptions as one invariant, Inv\mathrm{Inv}, and prove that well-formedness suffices for totality.

Definition 2 (Environment invariant Lean: Core.Inv). We write Inv(Δ)\mathrm{Inv}(\Delta) when Δ\Delta is well formed and structurally recursive.

Lemma 3 (Well-formedness implies totality Lean: WF.totality). If Inv(Δ)\mathrm{Inv}(\Delta) and A⊢ℓ wfA \vdash\ell\ \mathrm{wf}, then WℓΔ(v)≠∅\mathcal{W}_{\ell}^{\Delta}(v) \ne\varnothing for every v∈Av \in A.

Correctness of Layout Rewrites

We prove each rewrite locally, then lift its guarantee through the surrounding layout and recursive definitions. The local requirement compares the focus before and after the rewrite. Importantly, a focus need not faithfully represent its whole subject, e.g., the field ℓ:ref Tree\ell: \mathrm{ref}\ \mathrm{Tree} alone cannot distinguish nodes with equal left children but different keys.

Local Refinement

Write v≈ℓΔwv \mathrel{\approx_{\ell}^{\Delta}} w when vv and ww have a common representation under ℓ\ell, that is, WℓΔ(v)∩WℓΔ(w)≠∅W_{\ell}^{\Delta}(v) \cap W_{\ell}^{\Delta}(w) \ne\varnothing. Layout ℓ′\ell' under Δ′\Delta' refines ℓ\ell under Δ\Delta on subjects AA when

∀v,w∈A.v≈ℓ′Δ′w⟹v≈ℓΔw.\forall v,w \in A.\quad v \mathrel{\approx_{\ell'}^{\Delta'}} w \mathrel{\Longrightarrow} v \mathrel{\approx_{\ell}^{\Delta}} w.

Refinement thus preserves absolute injectivity.

Definition 4 (Local refinement Lean: Core.LocalRefinement). Under Δ\Delta, layout ℓ1\ell_1 locally refines ℓ0\ell_0 on subjects AA, written ℓ0⪯ℓ1\ell_0 \preceq\ell_1, if both layouts are well formed on AA and ℓ1\ell_1 refines ℓ0\ell_0 on AA.

Each primitive rule proves refinement, a reflexive and transitive relation, with a reconstruction function f:S⇀Sf : S \rightharpoonup S. For every v∈Av \in A and η′∈Wℓ1Δ(v)\eta' \in W_{\ell_1}^{\Delta}(v), it returns f(η′)∈Wℓ0Δ(v)f(\eta') \in W_{\ell_0}^{\Delta}(v). Refinement then follows at once, i.e., if vv and ww share η′\eta' after the rewrite, they share f(η′)f(\eta') before it. For example, padding reconstructs by dropping the added component, commutation by swapping the pair, and split⁡k\operatorname{split}_k by joining its two scalars as (b0,b1)↦b0+2kb1(b_0,b_1) \mapsto b_0 + 2^k b_1. Composing a derivation’s reconstruction functions with the canonical decoder gives a decoder for the rewritten layout, although such a decoder may be inefficient if naively implemented.

Lifting Local Refinement

Since a rewrite leaves the rest of the layout unchanged, the distinctions that local refinement preserves at the focus carry over to the whole layout. Updating a layout definition is subtler: local refinement is proved with the old body at recursive references, but the update changes those references too.

Theorem 5 (Contextual replacement Lean: Core.LocalRefinement.context). Let C[ℓ0]C[\ell_0] be well formed on BB, and let AA be the subjects that CC assigns to its hole from BB. If ℓ0⪯ℓ1\ell_0 \preceq\ell_1 on AA, then C[ℓ0]⪯C[ℓ1]C[\ell_0] \preceq C[\ell_1] on BB.

Lemma 6 (Recursive binding Lean: Core.LocalRefinement.bind). Let Δ\Delta wf, Δ(T)=ℓ0\Delta(T) = \ell_0, and Δ′=Δ[T↦ℓ1]\Delta' = \Delta[T \mapsto\ell_1]. If ℓ0⪯ℓ1\ell_0 \preceq\ell_1 on VTV_T under Δ\Delta and ℓ\ell is well formed on BB, then ℓ\ell under Δ′\Delta' refines ℓ\ell under Δ\Delta on BB.

The proof inducts on one subject’s representation under Δ′\Delta' and compares the other subject’s derivation of the same representation. At a reference to TT, the induction hypothesis yields a shared representation of ℓ1\ell_1 under Δ\Delta, and local refinement gives a shared representation of ℓ0\ell_0. A valid rewrite satisfies local refinement at its focus and either replaces that focus under the premises of Theorem 5, or updates a definition under the premises of Lemma 6 while preserving structural recursion.

Theorem 7 (Soundness of local rewrites Lean: Core.Rewrite.sound). Suppose Inv⁡(Δ)\operatorname{Inv}(\Delta) and A⊢ℓ wfA \vdash\ell\ \mathrm{wf} under Δ\Delta. Every valid rewrite from (Δ,ℓ)(\Delta,\ell) to (Δ′,ℓ′)(\Delta',\ell') establishes Inv⁡(Δ′)\operatorname{Inv}(\Delta') and A⊢ℓ′ wfA \vdash\ell'\ \mathrm{wf} under Δ′\Delta', and ℓ′\ell' under Δ′\Delta' refines ℓ\ell under Δ\Delta on AA.

If ℓ\ell faithfully represents τ\tau and A=VτA = V_{\tau}, the preserved invariant and well-formedness give totality by Lemma 3, and refinement preserves absolute injectivity. Thus the new layout remains faithful. By transitivity, every layout reached from a canonical layout by valid rewrites is faithful.

Adding a Rewrite Rule

The rewrite rules of Figure 2 are sound but not complete, i.e., not every faithful layout can be derived. The rule set can be extended to express novel layouts, provided each new rule establishes local refinement (Definition 4) with a reconstruction function. Theorems 7 and 9 then apply to it unchanged. As a concrete example, we realize an optimization used in Scion for storing an interval as an offset and a count [28 Fig. 5]. When k<nk < n, an interval [lo,hi)[lo, hi) can store its start and length,

Layout rewrites

Figure 2. Layout rewrites, with premises omitted. See Appendix C for rules with premises (Lean: Core.Step).

lo:un×hi:un⟶lo:un×⟨(hi−lo):uk⟩lo : u_n \times hi : u_n \longrightarrow lo : u_n \times\langle(hi - lo) : u_k \rangle

Lean: Core.Interval.rewrite

on admitted subjects with lo≤hi<2nlo \le hi < 2^n and hi−lo<2khi - lo < 2^k. The reconstruction f(b,d)=(b,b+d)f(b,d) = (b,b+d) recovers the original pair, and, together with well-formedness, this establishes local refinement.

Program Preservation

Layout rewrites should change how programs represent data while preserving what they compute. We prove this for a pure language with constructors, matching, let bindings, and recursive calls, under call-by-value big-step semantics [40]. We compare terminating programs by their scalar results, the observations on which all layouts agree (details in Appendix § 18); this does not verify generated code.

A program evaluates over source values, P;ρ⊢e⇓vP; \rho\vdash e \Downarrow v, or over represented values, Δ,b,ι;P;ρ⊢e⇓r\Delta, b, \iota; P; \rho\vdash e \Downarrow r, where a construction policy bb picks a representation for each new value and a destruction policy ι\iota reads one back. The policies are valid when bb succeeds exactly on values of the requested type and returns a permitted representation, and ι\iota recovers each such value from every permitted representation. We write r∼Δvr \sim_{\Delta} v when rr represents vv, relate environments that bind the same variables to related values, and call Δ\Delta faithful when ref⁡T\operatorname{ref} T faithfully represents TT for every type TT.

Theorem 8 (Representation independence Lean: Programs.representation_independence). Suppose Δ0\Delta_0 and Δ1\Delta_1 are faithful. For valid policies (b0,ι0)(b_0,\iota_0) at Δ0\Delta_0 and (b1,ι1)(b_1,\iota_1) at Δ1\Delta_1 and related inputs ρ0∼Δ0ρ\rho_0 \sim_{\Delta_0} \rho and ρ1∼Δ1ρ\rho_1 \sim_{\Delta_1} \rho, every program PP, expression ee, and scalar k∈Nk \in\mathbb{N} satisfies

Δ0,b0,ι0;P;ρ0⊢e⇓k⟺Δ1,b1,ι1;P;ρ1⊢e⇓k.(6)\Delta_0, b_0, \iota_0; P; \rho_0 \vdash e \Downarrow k \Longleftrightarrow\Delta_1, b_1, \iota_1; P; \rho_1 \vdash e \Downarrow k. \tag*{(6)}

Theorem 9 (Program preservation Lean: Core.BodyRewriteSeq.{observations,roots}). Suppose Inv⁡(Δ0)\operatorname{Inv}(\Delta_0), Δ0\Delta_0 binds every declared type, and Δ0\Delta_0 is faithful. If Δ0⟶∗Δ1\Delta_0 \longrightarrow^* \Delta_1 is a finite sequence of valid updates to layout definitions, then Δ1\Delta_1 is faithful, and (6) holds for all valid policies at the two endpoints and all related inputs.

For rewritten layouts, the final layout yields a valid construction policy bb (under Lemma 3). A valid destruction policy ι\iota is recovered by inverting the rewrite rules through their reconstruction functions (§ 6.1).

From Structural Representation to Bits

Structural representations retain component boundaries and pointee contents, but a bit-level encoding that discards this information can be ambiguous even when the layout is faithful. Recovery from memory therefore requires a separate guarantee from an encoder and decoder, together called a codec. Prior work has studied the construction and verification of binary codecs extensively [4, 21, 26, 90, 100]. We connect this work to layout rewriting by stating the recovery property a codec must satisfy, then give a simple codec satisfying it under explicit premises.

Recovery from Physical Storage

A physical encoding m=(β,H)∈Mm = (\beta, H) \in\mathcal{M} consists of a finite top-level bit vector β\beta and a finite heap HH from addresses to bits (or a layout ℓ\ell under Δ\Delta), an encoder and a decoder are partial functions

encode⁡ℓ:S⟶M,decode⁡ℓ:M⟶S,\operatorname{encode}_{\ell} : \mathcal{S} \longrightarrow\mathcal{M}, \qquad\operatorname{decode}_{\ell} : \mathcal{M} \longrightarrow\mathcal{S},

and we leave Δ\Delta implicit in their notation. The storage recovery property requires decoding to preserve the represented source value. For all v∈Vτv \in\mathcal{V}_{\tau}, η∈S\eta\in\mathcal{S}, and m∈Mm \in\mathcal{M},

η∈WℓΔ(v)∧encode⁡ℓ(η)=m⟹∃η′∈WℓΔ(v). decode⁡ℓ(m)=η′.(7)\eta\in\mathcal{W}^{\Delta}_{\ell}(v) \land\operatorname{encode}_{\ell}(\eta) = m \quad\Longrightarrow\quad\exists\eta' \in\mathcal{W}^{\Delta}_{\ell}(v).\ \operatorname{decode}_{\ell}(m) = \eta'. \tag*{(7)}

The decoder receives only the memory; it may return another representation of vv, so recovery does not require identical padding, and it is unconstrained on memories that no encoding produces.

Theorem 10 (Recovery after rewriting and encoding Lean: Core.storage_recovery). Suppose Inv⁡(Δ)\operatorname{Inv}(\Delta) and ℓ\ell is well formed on VτV_{\tau} and faithfully represents τ\tau under Δ\Delta. Let (Δ′,ℓ′)(\Delta',\ell') be obtained by a finite sequence of valid rewrites. If an encoder and a decoder for ℓ′\ell' under Δ′\Delta' satisfy Equation (7), then for every v∈Vτv \in V_{\tau}, η∈Wℓ′Δ′(v)\eta\in W_{\ell'}^{\Delta'}(v), and successful encoding encode⁡ℓ′(η)=m\operatorname{encode}_{\ell'}(\eta)=m, the decoder returns a representation that determines vv, so Wℓ′Δ′(decode⁡ℓ′(m))=vW_{\ell'}^{\Delta'}(\operatorname{decode}_{\ell'}(m))=v.

The theorem guarantees recovery of the source value provided that encoding succeeded. For an end-to-end instance, the mechanization supplies a simple forward encoder and decoder, which place scalars, products, and pointers in a bit vector and heap and reads them back left to right. Encoding succeeds when every ordinary sum has been tagged, every tag field is stored whole in its scope, and there are enough addresses for the pointers. Decoding inverts every successful encoding when, in addition, each tag field precedes its payload. Recovery of the source value then follows from Theorem 10; the mechanization carries this out for Layout 2, and Appendix § 17 elaborates on the conditions.

Decoding Limitations

Recovery from storage also depends on factors beyond faithfulness. For example, commuting a tag after the arm it selects preserves faithfulness, but the forward decoder is required to read the arm before learning which arm it is. On the other hand, a backward decoder, i.e., one that reads fields in reverse order, could still recover the values. Moreover, variable-width arms can make the encoding itself ambiguous. Consider the type S=A(x:u1)∣B(z:u2)S=A(x:u_1)\mid B(z:u_2) with initial layout t:u1×{(0,A)⇒x:u1,(1,B)⇒z:u2}t:u_1\times\{(0,A)\Rightarrow x:u_1,(1,B)\Rightarrow z:u_2\}, and then store a pair of SS values with the first component’s tag after its payload and the second component’s tag before. Then,

(A(1),B(1))↦10∥101=10101,(A(1),B(1))\mapsto10\mathbin{\|}101=10101,
(B(2),A(1))↦101∥01=10101(B(2),A(1))\mapsto101\mathbin{\|}01=10101

so no decoder can recover both pairs. Both tags lie at the boundary between the components, but only a tag reveals where that boundary is. Narcissus resolves such ambiguities by fixing boundaries from the surrounding format [21 Sec. 3.1]. Local rewrites thus preserve faithfulness but not physical recoverability, which depends on the layout as a whole.

The Isomer Programming Language

The preceding sections define how a layout organizes data in memory. The compiler must abide by this specification, but, importantly, is free to choose how construction, destruction, and memory management are realized. We next describe how Isomer exploits this to generate efficient code.

Core Language and Layout Selection

Figure 5 gives the grammar of the monomorphic, first-order core of Isomer. The frontend monomorphizes generic definitions and defunctionalizes closures into ADTs, so every value has a concrete type. Scalars are signed integers, unsigned integers, and floating-point numbers. Variable-length arrays [x]τ[x]\tau are first-class, with an in-scope scalar length xx [37, 68]. The formalism models a finite array as a sum with one constructor per length, indexed by its length; the implementation provides an explicit array construct for simplicity.

Monomorphic, first-order core of Isomer

Figure 5. Monomorphic, first-order core of Isomer.

For types without rewrites applied, Isomer uses a default layout. Fields keep their declared order, fixed-size fields are inlined, recursively defined fields sit behind a pointer, and tags are rounded up to whole bytes. When a sum is stored inline within another value its arms are padded to a common size, so that following fields have statically known offsets. For heap-allocated values, we size cells per constructor rather than padding them to a common size; each cell includes a 32-bit reference count. § 9.4 and § 9.5 show that this simple policy strikes a balance between layout compactness and runtime performance.

Layout-Directed Compilation

Well-formedness. Before generating code, the compiler verifies the machine can realize each layout. This machine well-formedness requires that tags and array lengths are recoverable, fields admit an acyclic reading order satisfying their offset dependencies, every cycle in the storage graph crosses a pointer, and storage sizes meet allocation constraints. Pointer compression, for example, must comply with the requirements of the target architecture. These conditions are in part intended to exclude the ambiguous encodings of § 7.2.

Construction and destruction. Unlike layout description languages [6, 14, 28] which decode a value by inverting its layout specification, Isomer generates code by following a layout’s rewrites from a canonical layout. Each rewrite updates two artifacts, (1) the layout’s decoder, a function from a value’s stored form to the source value, and (2) a storage plan that records each stored component’s physical metadata, e.g., its offset and width. Construction proceeds by reading the storage plan, while destruction, i.e., pattern matching and field access, queries the decoder. A new rule thus requires supplying only its reconstruction function and its changes to the storage plan.

Producer and consumer specialization. Compiling pattern matches and constructions field by field, as the source writes them, can make a program asymptotically slower under a rewritten layout. Each field the source binds or supplies is a value of its own, while the layout may keep that value only inside a larger component. For example, when an unfolded list stores two elements per cell, matching Cons(h, t) binds t to a tail with no standalone representation. Rebuilding that tail means repacking the entire suffix, and doing so at every step turns a linear traversal quadratic. Isomer instead specializes consumers and producers to the layout through a source-to-source translation that combines deforestation [94] and partial evaluation [39] techniques to avoid this asymptotic slowdown when possible. The algorithms are discussed further in Appendix § 16.

Specialized pattern matching is then lowered to decision trees [60] whose tests read physical encodings, and branch provenance removes tests whose outcome is already known. Unlike the formalism, the implementation treats the arms of a sum as an ordered list, and a rule that commutes arms lets programmers choose which guard construction tests first2.

Instruction selection. Naively executing a decoder for every query would rebuild an entire source value just to read a single field. The compiler instead optimizes the decoder, using the storage plan to simplify instruction selection. Knowledge of field positions and widths lets the compiler combine representation operations with the instructions that use their results. For example, once a branch establishes that a pointer carries the low-bit tag tt, untagging folds into each field access, as in GHC’s pointer tagging [61], so a field at byte offset dd from the untagged pointer is read at offset d−td-t from the tagged word, without a separate mask instruction. Finally, Isomer lowers the specialized program to SSA [20, 75], applies standard compiler optimizations [1, 18, 48, 69], and emits LLVM IR [45].

Reference Counting

Isomer manages memory with ownership-based reference counting, following the compiler-based approach of prior work [57, 73, 89]. In Isomer, however, the count is itself part of the layout. The rewrite rule rc n prepends an unsigned nn-bit count to the focused layout, a field that the compiler manages but other rewrites treat like any other, so a count can be narrowed, moved, or removed entirely. Omitting the count asserts that each instance of the type has a single owner, which Isomer verifies after reference count optimizations are applied. As in Koka [73 Sec. 2.7.2], counts are sticky, so an nn-bit count saturates once its high bit is set, and its cell is then neither reclaimed nor reused.

Layout control lets programmers choose cell sizes that enable reuse and omit reference counts when ownership permits. Dynamic reuse (rc-1) updates a dying cell in place when its count is one at run time [10, 73]. It enables cells of the same size to be reused between constructors of the same or different types, and arrays with a single owner to be updated in place. Layout rewrites let programmers choose between per-arm allocation sizes and a common cell size. Per-arm sizes avoid padding smaller arms, while padding all arms to a common size enables cell reuse across all constructors of the type. Additionally, the programmer can entirely omit the reference count field from a layout, which the compiler accepts only when static ownership analysis verifies unique ownership; we call this optimization rc-0. The kk-d tree case study, the layout design space exploration, and the Ribbit comparison exercise rc-0 (§ 9.2, § 9.5 and § 9.6).

Layout Coercion

One layout rarely suits every phase of a program, since construction and traversal can favor different representations of the same ADT. The scheduling directive coerce changes a value’s representation at a chosen binding without changing the program. Logically, the conversion is a catamorphism hh [62] that converts a value’s children and rebuilds each constructor in the target representation,

h(K0(aˉ,tˉ1,…,tˉk))=K1(aˉ,hˉ(t1),…,h(tk)).h\left(K_0\left(\bar{a}, \bar{t}_1, \ldots, \bar{t}_k\right)\right) = K_1\left(\bar{a}, \bar{h}(t_1), \ldots, h(t_k)\right).

Here aˉ\bar{a} are the nonrecursive fields, and subscripts 0 and 1 mark the source and target representations. Because both sides share one ADT, the fold’s constructor functions are fixed, and the compiler implements them by specializing construction to the target layout and matching to the source layout. Conversion thus reuses the machinery of § 8.2. The 2-3 tree and kk-d tree case studies evaluate coerce between their construction and query phases (§ 9.2).

Using Memoized Expressions

A layout can also store what a program would otherwise recompute. A memoized expression moves work from queries to construction. For example, given the type T = T(a : i32, b : i32), the rewrite memoize (a + b) stores the sum of fields a and b in a new field, which the generated constructors compute. During destruction, the compiler annotates each cache load with the expression it represents. After canonicalization, common-subexpression elimination (CSE) [18] replaces matching computations with the cached value. Memoized expressions may also be recursive; the interval-tree case study (§ 9.2) evaluates such an instance.

Evaluation

Our evaluation demonstrates that Isomer achieves competitive performance against existing implementations using automatically selected default layouts, and that composing rewrites can improve runtime and reduce peak memory further. Layout control also complements automatic memory management by shrinking allocations that reuse does not eliminate. We substantiate these findings with measurements of runtime and peak memory.

Experimental Methodology

All benchmarks run single-threaded on an Apple M2 Pro with 10 cores and 16 GiB of memory, running macOS 26.0. Isomer emits LLVM IR, which Clang 19.1.7 compiles with -O3 -mcpu=native. We compare against MLton [95], Morphic [9, 10], Ribbit [5, 6], and Koka [47, 57].3 Every timed system measures wall-clock time, and each configuration runs in fresh processes, with 2 discarded warm-ups followed by 14 measured runs. We report the mean of the 10 runs left after discarding the 2 fastest and 2 slowest, with approximate 95% error bars. For memory, we report the median peak resident set size (RSS). Unless noted, we use mimalloc 3.4.5 [49], and Appendix § 19.§ 4 repeats the results with the system allocator. We verify every configuration computes the same answer and Isomer has no memory leaks. Experiments below describe any remaining setup.

AI Use. AI [3, 66] assisted with implementation of the Isomer compiler from an initial prototype, proof mechanization, the benchmark harness, paper figures, and the layout search of § 9.5.

Case Studies

Three case studies measure what layout rewrites gain in runtime and memory within a single program, by composing successive rewrites on a kk-d tree, memoizing an expression in an interval tree, and changing layouts between the insertions and range scans of a 2-3 tree.

Composing Rewrites on k-d Trees

KdTree = Leaf (xx, yy, zz : f32) | Node(minx_x, miny_y, minz_z, maxx_x, maxy_y, maxz_z : f32, ll : KdTree, rr : KdTree)

We explore the interaction of layout rewrites through two-point correlation counting [63]. The program counts points within a query radius, using a kk-d tree [8] to accelerate the query. We build a tree over 2202^{20} points and issue 2202^{20} queries. Starting from Isomer’s default layout, each configuration in Figure 6 adds one optimization to the layout before it, realized through a short sequence of rewrites. The results show that effective layouts can be reached incrementally by composing simple rewrites, and additionally expose a tradeoff between runtime performance and memory use.

Figure 6. Lower is better. Runtime and peak RSS across kk-d tree layouts. The line denotes successive composition of rewrite rules. • marks minimum runtime, • minimum RSS, and ◦ the observed Pareto frontier.

Because the tree is built once and then only read, 1–unique can drop the reference count, which ownership analysis confirms no cell needs (rc-0, § 8.3), and every leaf moves to an allocation bin half the size. 2–hoist then moves the tag into low bits of each pointer [6, 25, 61, 95], so a traversal dispatches on bits it already holds instead of loading a byte, and a leaf is just the three coordinates. Next, most nodes near the bottom of the tree have two leaf children, and 3–LL unfolds both into their parent [7, 31, 78], turning three cells into one 48-byte cell and eliminating two pointer dereferences. 4–NN unfolds two Node children the same way, which barely moves either metric but places two levels of the tree in one cell for later steps to reshape. 5–soa then reorders the inlined leaf coordinates and the bounding-box fields for vectorized arithmetic [7, 97, 101], so one 2-wide comparison tests both leaves, and 6–LT inlines a lone Leaf child while keeping its sibling behind a pointer. The last two incremental steps trade runtime for memory. 7–narrow refines pointers to 48 bits, moving two-Node cells from the 112- to the 96-byte allocation bin [15, 46] at the cost of a slower load for every child, and 8-LN also inlines the Node sibling of a lone leaf, reaching the smallest footprint.

The final layout 19-adopt-pad performs a coerce step (included in the timed region) between the construction and query phases. This scheduling directive builds the tree under a layout that keeps children boxed and steals bits for the tag, then converts it to an unfolded, alignment-friendly layout for better instruction selection during the queries. It also builds the point buffer’s array inline in the counted cell, and then pads leaves in the read layout within their existing allocation bin. Of the layouts shown, 19-adopt-pad is the fastest, 1.56× faster than the default, and 8-LN has the smallest peak RSS, 31% below the default’s. Importantly, the fastest and smallest layouts differ, thus no single layout is optimal across both runtime and peak memory use.

Memoized Expressions in Interval Trees.

Tree=Leaf∣Node(l:Tree, r:Tree, lo:i64, hi:i64)\mathrm{Tree} = \mathrm{Leaf} \mid\mathrm{Node}(l : \mathrm{Tree},\ r : \mathrm{Tree},\ lo : i64,\ hi : i64)

An interval-tree query uses the maximum upper endpoint in a subtree to choose its next branch [19 Sec. 15.3]. An unaugmented tree recomputes this maximum by traversing the left subtree of each node that a query visits, so a query can take time linear in the number of intervals. Augmenting the maximum at every tree node instead makes a query take time proportional to the tree’s height. The cached maximum is defined recursively,

μ(t)={0,t∈Leafmax⁡(μ(l),μ(r),hi),t∈Node(l,r,lo,hi).\mu(t) = \begin{cases} 0, & t \in\mathrm{Leaf} \\ \max(\mu(l), \mu(r), hi), & t \in\mathrm{Node}(l,r,lo,hi). \end{cases}

Memoized expressions cache this value directly in the ADT, analogous to the reduction annotations in Bonsai [74 Sec. 4]. Isomer realizes this augmentation through layout rewrites over the unaugmented source. MLton and Morphic reach the same asymptotic cost only by changing the source, so all three systems also run a hand-augmented program that stores the maximum in every constructor. We time the queries alone, issuing 128,000 point queries to trees of 2n2^n intervals for n∈[6,19)n \in[6, 19), with the compiler configurations of § 9.4. Across all tree sizes, the memoized Isomer layout is 1.53× faster than hand-augmented Morphic and 1.09× faster than hand-augmented MLton (geomean) as shown in Figure 7 (left). The memoized layout also performs similarly to hand-augmented Isomer program at every size, showing that expressing the augmentation as a layout rewrite adds no overhead.

Interval-tree query time and total runtime plots. Left legend: Isomer (memoized layout), Isomer (augmented), MLton (augmented), Morphic (augmented); axes: Query time (ms), Intervals in the tree ($n$). Right legend: default layout, insert-optimized, read-optimized, coerced; axes: Total time (ms), range scans ($k \times 10^3$).

Figure 7. Lower is better. Interval-tree query time with memoized expressions in Isomer and with a hand-augmented source in Isomer, MLton, and Morphic (left), and total runtime for 2–3 tree insertion and range scans, including data structure translation (right).

Changing Layouts in 2-3 Trees.

Tree=Leaf∣Two(l:Tree,k:u64,r:Tree)∣Three(l:Tree,k1:u64,m:Tree,k2:u64,r:Tree)\mathrm{Tree} = \mathrm{Leaf} \mid\mathrm{Two}(l : \mathrm{Tree}, k : u64, r : \mathrm{Tree}) \mid\mathrm{Three}(l : \mathrm{Tree}, k_1 : u64, m : \mathrm{Tree}, k_2 : u64, r : \mathrm{Tree})

The interval-tree cache moves recursive work from queries to construction; a complementary opportunity arises when construction and traversal favor different representations. The coerce directive lets a program convert once between phases and use a compact layout for repeated scans. A 2-3 tree [42 Sec. 6.2.4] is a balanced search tree whose internal nodes hold one or two keys and have two or three children, respectively, with all leaves at the same depth. We insert 1.6×1061.6 \times10^{6} keys, then issue 103×k10^{3} \times k range scans for k∈{16,64,128,256,384,512}k \in\{16, 64, 128, 256, 384, 512\} and a final reduction. Figure 7 (right) compares the default layout with three configurations. insert-optimized pads Two cells to match Three cells for reuse, read-optimized inlines empty Leaf children in leaf-level nodes, and coerced builds with insert-optimized and then translates via coerce to read-optimized before scanning. The best fixed layout depends on the workload, switching from insert-optimized to read-optimized between 128,000 and 256,000 scans. coerced pays for one conversion but is faster than both throughout the sweep. At 512,000 scans, it is 2.20× faster than the best fixed layout. The coerce directive thus turns layout choice from a program-wide decision [28] into a phase-specific one.

Comparison with Monomorphizing Languages

MLton and Morphic are whole-program compilers that monomorphize and, unlike Isomer, do not offer user control of layouts. Morphic computes strongly connected components (SCCs) over datatype-size dependencies and boxes an arm when its payload refers to a type in its own SCC. MLton’s representation emerges from interacting whole-program passes, including monomorphization, unboxing, argument flattening, and representation selection [95]. Figure 8 shows the layout each system chooses for tmap’s Tree ADT. Morphic opts for aligned fields at the cost of unused bits, while MLton employs more advanced layouts automatically, e.g., bit stealing techniques.

Layouts for Tree in tmap

Tree = Leaf | Bin(ll : Tree, xx : i32i_{32}, rr : Tree)

Morphic: t:u1×zero7×pad56×{(0,Leaf)⇒pad64, (1,Bin)⇒δ64(rc:u64×l:refTree×x:i32×pad32×r:refTree)}t:u_{1} \times zero_{7} \times pad_{56} \times\lbrace(0,\mathrm{Leaf}) \Rightarrow pad_{64},\ (1,\mathrm{Bin}) \Rightarrow\delta_{64}(rc:u_{64} \times l:\mathrm{refTree} \times x:i_{32} \times pad_{32} \times r:\mathrm{refTree}) \rbrace

MLton: t:u2×{(1,Leaf)⇒zero62, (0,Bin)⇒δ62(gc_metadata:u64×l:i64×r:refTree×x:refTree)}t:u_{2} \times\lbrace(1,\mathrm{Leaf}) \Rightarrow zero_{62},\ (0,\mathrm{Bin}) \Rightarrow\delta_{62}(gc\_metadata:u_{64} \times l:i_{64} \times r:\mathrm{refTree} \times x:\mathrm{refTree}) \rbrace

Isomer (default): δ64(rc:u32×t:u8×{(0,Leaf)⇒ε, (1,Bin)⇒l:refTree×x:i32×r:refTree})\delta_{64}(rc:u_{32} \times t:u_{8} \times\lbrace(0,\mathrm{Leaf}) \Rightarrow\varepsilon,\ (1,\mathrm{Bin}) \Rightarrow l:\mathrm{refTree} \times x:i_{32} \times r:\mathrm{refTree} \rbrace)

Isomer (optimized): ⊔t{(0,Leaf)⇒pad56, (1,Bin)⇒δ56(l:refTree×r:refTree×rc:u32×x:i32)}×zero7×t:u1\sqcup^{t}\lbrace(0,\mathrm{Leaf}) \Rightarrow pad_{56},\ (1,\mathrm{Bin}) \Rightarrow\delta_{56}(l:\mathrm{refTree} \times r:\mathrm{refTree} \times rc:u_{32} \times x:i_{32}) \rbrace\times zero_{7} \times t:u_{1}

Figure 8. Layouts for Tree in tmap. Optimized Isomer is paired-high-tags discussed in § 9.5.

The suite is the union of the 15 benchmarks evaluated in both Morphic papers [9, 10] in addition to kd-tree, tree23 (§ 9.2), and tmap (§ 9.7). The benchmark primes-iter declares no ADTs but remains in the suite for completeness. Following the AST-based translation of Morphic [9], we generate each MLton and Morphic program from the same Isomer source, so the comparison measures code generation and data representation rather than how each program was written. Both reference compilers check every array access, so we enable Isomer’s optional bounds checks.

Isomer’s arrays are immutable, whereas SML’s are mutable. A direct AST translation to MLton therefore cannot safely update an array in place unless no other reference observes the original. For each benchmark, we time four MLton array implementations and use the fastest whose output agrees (Appendix § 19.§ 5). Morphic uses borrow-based reference counting [10] with a 64-bit count. We acknowledge that cross-language comparison is inherently contrived, and provide these results as a baseline that places Isomer relative to the state of the art.

Default layouts. With default layouts, Isomer is 1.46× faster than MLton and 1.32× faster than Morphic (geomean, Figure 9). Against MLton, both extremes come from garbage collection, whose copying is costly on the large live sets of rbtree and rbtree-ck, but whose bump allocation beats Isomer on programs with many short-lived objects, e.g., lisp. Against Morphic, which updates unique arrays in place but never reuses a constructor’s cell, dynamic reuse likely contributes to Isomer’s lead. Appendix § 19.§ 2 compares peak RSS, which for MLton includes its garbage-collected heap.

Figure 9. Lower is better. Runtime relative to default Isomer. The best-runtime layout is selected independently for each benchmark. Arrows indicate ratios beyond the displayed range.

Parity layouts. To separate layout from code generation, we also run Isomer at Morphic’s own layouts, derived with our rewrite rules and matched bit for bit, in 18 comparisons (Appendix § 19.§ 3). Isomer remains 1.27× faster (geomean), suggesting its lead comes from additional compiler optimizations across instruction selection and memory management.

Layout Design Space Exploration

We now turn to exploration of layouts. Holding each program’s source and the compiler fixed, we measure 145 layout configurations across the 18 benchmarks of § 9.4. Following Helion’s approach of combining language-model proposals with search [16], we use language models to propose rewrite sequences and further refine the resulting layouts with a straightforward search procedure [59]. Selecting the fastest measured layout for each benchmark gives a 1.25× geometric-mean speedup over Isomer with a default layout, ranging from none on primes-iter (no ADTs) to 3.51× on tree23. Independently selecting the lowest-RSS layouts reduces peak RSS by 25% (geomean). Figure 10 shows the frontiers of three benchmarks, and Appendix § 19.§ 1 shows the frontier of every benchmark with a non-default Pareto-optimal layout.

Runtime–RSS tradeoffs for selected benchmarks

Figure 10. Lower is better. Runtime–RSS tradeoffs for selected benchmarks. Axis break marks indicate nonzero origins. ◆ marks the default Isomer layout, and ▪ marks a rewritten Isomer layout on the Pareto frontier.

The three frontiers of Figure 10 come from different mechanisms. In words-trie, a node’s children and count are often empty, and both frontier layouts store an empty child or count as a zero immediate, thus only present counts and nonempty nodes allocate. The array-adopt layout also builds each node’s child array directly in the cell that keeps it, which removes a temporary array and a copy at every node an insertion visits. In derv, the fast layouts cache each subexpression’s leaf count, as the interval tree caches its maximum, so counting reads one field, and immediates keeps small constants inside the pointer word, which saves a heap cell per constant and reduces peak memory by 48%. Finally, in tmap, uniform-frame-tags refines small keys from 32 to 24 bits and matches tree and continuation-frame cell sizes for reuse. The faster paired-high-tags layout

(displayed in Figure 8) keeps child references adjacent and places the tree tag in the highest bit of the reference word.

Comparison with a Data-Description Language

Ribbit [5, 6] is a layout description language for general-purpose ADTs. We pair Ribbit’s fastest measured layout on the three benchmarks of Baudon et al. [6] with the corresponding Isomer layout, and compile both to LLVM IR. Ribbit has no automatic memory management, while Isomer’s layouts drop reference counting through the rc-0 optimization for two benchmarks, and uses reference counting for third. Isomer achieves a 1.53×\times geometric-mean speedup (Figure 11); the gap lies in code generation. For example, Ribbit compiles every function in destination-passing style [5 Sec. 5.2] so every iteration makes an out-of-line call that returns through a pointer, while Isomer keeps these values in registers. We therefore report the speedup as a comparison of the two implementations, rather than a claim about the performance potential of Ribbit’s layout language.

Bar charts comparing runtime relative to Ribbit and peak RSS relative to koka-fip

Figure 11. Lower is better. Runtime relative to Ribbit with corresponding layouts (left), and peak RSS relative to koka-fip (right). In Isomer (ℓ\ell), ℓ\ell denotes the layout used, e.g., Isomer (koka) uses Koka’s layout.

Allocation and Reuse with Koka

We test whether layout control composes with the reference counting optimizations of Koka [47], in which a constructor reuses the cell of a same-sized owned value that has just been destructed [73]. We run 4 of the 5 benchmarks of Lorenzen et al. [57] with n=100,000n = 100{,}000, omitting ftree because it requires polymorphic recursion. We compile Koka with -O3, and both systems use Koka’s allocator.

Using Koka’s exact layouts, Isomer’s peak memory is at most that of Koka’s fully in-place versions, koka-fip, on every benchmark (9% lower peak RSS, geomean; Figure 11). Notably, the fully in-place versions of msort and qsort give different constructors the same size by adding Pad fields to the source [57 Sec. 4.3], whereas Isomer changes cell sizes solely through layout rewrites. The qsort program shows the largest gap, which partly is a result of tail recursion modulo cons (TRMC) [48], which Isomer applies to mutually recursive functions while Koka does not. Further rewrites, such as the bit stealing of tmap in § 9.5, lower peak memory by an additional 20% (geomean), demonstrating that our layout rewrites can complement reuse by reducing the size of allocations that are not optimized away.

Related Work

Automatic and type-driven layouts. MLton [95] and Morphic [9, 10] automatically select ADT layouts through whole-program analyses. Gibbon and its successors [43, 80, 92, 93] compile recursive ADTs to dense, serialized buffers. Such analyses could select among the layouts our rewrites express. OCaml [11, 51] and Rust [85, 86] annotations select from a fixed set of layouts without changing application code. Haskell [70] and OxCaml [38, 58] expose unboxed types, with levity polymorphism [24] allowing Haskell code to abstract over representation. These choices often require changes to the source code.

Decoupled layouts and schedules. Ribbit [6], Dargent [14], and Scion [28] separate layouts from type declarations but specify the target layout directly. Recently, Rig [88] proposed layout transformations for finite ADTs from type isomorphisms. We instead optimize layouts of recursive ADTs via composable rewrite rules. A layout description language checks each target layout as a whole and decodes it by inverting its final form, so it admits only encodings its checker can validate and its compiler can invert. Our rules carry local proofs and reconstruction functions that compose; a new rule need only satisfy a local correctness criterion rather than modification of a monolithic validation checker. Rewrites also let a programmer or search procedure move between valid layouts incrementally. Dense [29, 44, 79, 83, 98, 102] and sparse [2, 17, 54, 55, 91, 99] array languages expose layouts for nn-dimensional arrays. In the same spirit, Halide and related systems separate algorithms from execution schedules for a specific domain [12, 13, 71, 77]. Hall et al. [32] identify layout and data movement as further directions. Lift [81], Elevate [30], Exo [35, 36], and ATL [53, 54] compose rewrites for verifiability and extensibility, a principle we apply to data representation.

Data representations and codecs. Hoare [34] proves correctness through a function from concrete to abstract values, the role of our recovery function. Data description languages generate parsers, printers, and other tools from a format description [4, 26], and a verified Protocol Buffer compiler proves every serializer and deserializer it generates correct [100]. EverParse proves its generated parsers correct [72, 82] and each message’s encoding unique [72]. Narcissus [21] derives verified codecs via local proofs; our destruction policy is likewise assembled from local proofs over structural representations instead of bits. Its formats, like our layouts, may admit several representations per value and must remain injective. These systems verify executable codecs, each for a given format. Similar to our rewrite rules, van Geest and Swierstra [90] chain verified conversions toward binary encodings, for formats built from fixed-width words, products, and dependent fields.

References

Provenance Lattice

Figure 12 shows the depth-one provenance lattice of the red-black tree’s Node and Leaf constructors. Equality of provenances is decidable (Lean: Prov.decidableEquiv); two provenances read finitely many paths, constructors, and literals, and projecting a value onto these reads preserves both.

Constructor provenance lattice of the children of a Node

Figure 12. Constructor provenance of the children ll and rr of a Node of the red-black Tree, abbreviating Leaf as LL and Node as NN. Triangles denote arbitrary subtrees. Each matrix shades the admitted child pairs, its cell ABAB standing for children AA and BB, and edges order the matrices by inclusion. The examples, which require (i) a left leaf, (ii) two node children, or (iii) at least one leaf child, share the colors of their matrices.

Well-Formedness

The judgment A⊢ℓ wfA \vdash\ell\ \mathrm{wf} checks a layout ℓ\ell on its admitted subjects AA, the source values that can reach ℓ\ell (§ 4.2). A layout definition for T is verified on all values of its type, VTV_T, and each rule checks every immediate sublayout on the subjects that can reach it. The judgment therefore guarantees every admitted subject has at least one representation (totality, Lemma 3). The rules of Figure 13 define the well-formedness judgment of § 5.3, which every rewrite judgment of Appendix § 14 requires of both sides.

Well-formedness rulesVector (PDF)
ℓ∈{ε,pad⁡n,zero⁡n}A⊢ℓ wfA⊆VunA⊢un wfA⊆dom⁡⟦e⟧A⊢⟨e⟩ wf\frac{\ell\in\{\varepsilon,\operatorname{pad}_{n},\operatorname{zero}_{n}\}}{A \vdash\ell\ \mathrm{wf}} \qquad \frac{A \subseteq\mathcal{V}_{u_n}}{A \vdash u_n\ \mathrm{wf}} \qquad \frac{A \subseteq\operatorname{dom}\llbracket e\rrbracket}{A \vdash\langle e\rangle\ \mathrm{wf}}
A⊆dom⁡πA.π⊢ℓ wfA⊢π:ℓ wfA⊢ℓ wfA⊢&n(ℓ) wfA⊢ℓ0 wfA⊢ℓ1 wfA⊢ℓ0×ℓ1 wfT∈dom⁡ΔA⊆VTA⊢ref⁡ T wf\frac{A \subseteq\operatorname{dom}\pi\qquad A.\pi\vdash\ell\ \mathrm{wf}}{A \vdash\pi:\ell\ \mathrm{wf}} \qquad \frac{A \vdash\ell\ \mathrm{wf}}{A \vdash\&_{n}(\ell)\ \mathrm{wf}} \qquad \frac{A \vdash\ell_0\ \mathrm{wf}\qquad A \vdash\ell_1\ \mathrm{wf}}{A \vdash\ell_0\times\ell_1\ \mathrm{wf}} \qquad \frac{T\in\operatorname{dom}\Delta\qquad A\subseteq\mathcal{V}_{T}}{A\vdash\operatorname{ref}\ T\ \mathrm{wf}}
A⊆⋃jϕjA∩ϕj⊢ℓj wfA⊢⋃{ϕj⇒ℓj} wfA⊆⋃iAπ=ciAπ=ci⊆ϕiAπ=ci⊢ℓi wfA⊢⋃{(ci,ϕi)⇒ℓi} wf\frac{A\subseteq\bigcup_j\phi_j\qquad A\cap\phi_j\vdash\ell_j\ \mathrm{wf}}{A\vdash\bigcup\{\phi_j\Rightarrow\ell_j\}\ \mathrm{wf}} \qquad \frac{A\subseteq\bigcup_i A_{\pi=c_i}\qquad A_{\pi=c_i}\subseteq\phi_i\qquad A_{\pi=c_i}\vdash\ell_i\ \mathrm{wf}}{A\vdash\bigcup\{(c_i,\phi_i)\Rightarrow\ell_i\}\ \mathrm{wf}}
∀T∈dom⁡Δ, VT⊢Δ(T) wfΔ wf\frac{\forall T\in\operatorname{dom}\Delta,\ \mathcal{V}_T\vdash\Delta(T)\ \mathrm{wf}}{\Delta\ \mathrm{wf}}

Figure 13. Well-formedness on the admitted subjects AA, under the layout environment Δ\Delta. We write dom⁡⟦e⟧\operatorname{dom}\llbracket e\rrbracket for the values on which ee is defined and dom⁡π\operatorname{dom}\pi for those on which v.πv.\pi is defined. A named layout passes the selected subjects A.πA.\pi to its payload. We write Aπ=ciA_{\pi=c_i} for the admitted subjects whose key π\pi is defined and equals cic_i. In the mechanization, a disjoint sum keyed by a tag takes its guards from the tag’s declaration, so Aπ=ci⊆ϕiA_{\pi=c_i}\subseteq\phi_i follows from the selector’s soundness. Lean: WF, WF.{sumMap_iff, taggedMap_iff}, LayoutEnv.WF

Rewrite Judgments

Figure 14 states the rules of Figure 2 as judgments A⊢Δℓ0⟶ℓ1A\vdash_{\Delta}\ell_0\longrightarrow\ell_1 on admitted subjects AA under the layout environment Δ\Delta, each establishing local refinement (Definition 4). A judgment with ⟷\longleftrightarrow abbreviates both directions. Besides the displayed premises, each rule requires both sides to be well formed on AA (Appendix § 13). Here j,k,m,n∈Nj,k,m,n\in\mathbb{N}. Ω\Omega and Ψ\Psi are arbitrary lists of arms, and an indexed arm ϕj⇒ℓj\phi_j\Rightarrow\ell_j stands for a list of arms indexed from 0. In tag, the arms may be listed in any order, and guards⁡(t)\operatorname{guards}(t) lists their guards in that order (§ 4).

A⊢Δℓ⟶pad⁡n×ℓpad⁡nA⊢Δℓ⟶zero⁡n×ℓzero⁡nA⊢Δℓ⟶&n(ε)×ℓptr⁡n\frac{A\vdash_{\Delta}\ell\longrightarrow\operatorname{pad}_{n}\times\ell}{\operatorname{pad}_{n}} \qquad \frac{A\vdash_{\Delta}\ell\longrightarrow\operatorname{zero}_{n}\times\ell}{\operatorname{zero}_{n}} \qquad \frac{A\vdash_{\Delta}\ell\longrightarrow\&_{n}(\varepsilon)\times\ell}{\operatorname{ptr}_{n}}
A⊢Δℓ⟶⟨e⟩×ℓmemoize⁡eA⊢Δ&n(ℓ0)×ℓ1⟶&n(ℓ0×ℓ1)box⁡A⊢Δ&n(ℓ)⟶ℓunbox⁡\frac{A\vdash_{\Delta}\ell\longrightarrow\langle e\rangle\times\ell}{\operatorname{memoize}_{e}} \qquad \frac{A\vdash_{\Delta}\&_{n}(\ell_0)\times\ell_1\longrightarrow\&_{n}(\ell_0\times\ell_1)}{\operatorname{box}} \qquad \frac{A\vdash_{\Delta}\&_{n}(\ell)\longrightarrow\ell}{\operatorname{unbox}}
A⊢Δℓ0×ℓ1⟶ℓ1×ℓ0commute⁡A⊢Δ(ℓ0×ℓ1)×ℓ2⟷ℓ0×(ℓ1×ℓ2)assoc⁡A⊢Δε×ℓ⟷ℓunit⁡\frac{A\vdash_{\Delta}\ell_0\times\ell_1\longrightarrow\ell_1\times\ell_0}{\operatorname{commute}} \qquad \frac{A\vdash_{\Delta}(\ell_0\times\ell_1)\times\ell_2\longleftrightarrow\ell_0\times(\ell_1\times\ell_2)}{\operatorname{assoc}} \qquad \frac{A\vdash_{\Delta}\varepsilon\times\ell\longleftrightarrow\ell}{\operatorname{unit}}
k≤nA⊢Δπ:un⟶π[0,k):uk×π[k,n):un−kA⊢Δ⋃{ϕ⇒ℓ}⟶ℓcollapse⁡\frac{k\le n}{A\vdash_{\Delta}\pi:u_n\longrightarrow\pi[0,k):u_k\times\pi[k,n):u_{n-k}} \qquad \frac{A\vdash_{\Delta}\bigcup\{\phi\Rightarrow\ell\}\longrightarrow\ell}{\operatorname{collapse}}
A⊢Δun⟶⋃{Vum⇒um, ⊤⇒un}refine⁡umA⊢Δℓ⟶⋃{ϕ⇒ℓ, ⊤⇒ℓ}refine⁡ϕ\frac{A\vdash_{\Delta}u_n\longrightarrow\bigcup\{\mathcal{V}_{u_m}\Rightarrow u_m,\ \top\Rightarrow u_n\}}{\operatorname{refine}_{u_m}} \qquad \frac{A\vdash_{\Delta}\ell\longrightarrow\bigcup\{\phi\Rightarrow\ell,\ \top\Rightarrow\ell\}}{\operatorname{refine}_{\phi}}
A⊢Δℓ×{Ω}⟶⋃{ℓ×Ω}distribute⁡Ω≠∅A⊢Δ⋃{ℓ×Ω}⟶ℓ×⋃{Ω}factor⁡\frac{A\vdash_{\Delta}\ell\times\{\Omega\}\longrightarrow\bigcup\{\ell\times\Omega\}}{\operatorname{distribute}} \qquad \frac{\Omega\ne\varnothing}{A\vdash_{\Delta}\bigcup\{\ell\times\Omega\}\longrightarrow\ell\times\bigcup\{\Omega\}}{\operatorname{factor}}
A⊆⋃jϕjA⊢Δ⋃{ϕj⇒ℓj,ϕ⇒ℓ}⟶⋃{ϕj⇒ℓj}prune⁡A⊢Δ⋃{Ω,ϕ⇒⋃{Ψ}}⟶⋃{Ω,ϕ∩Ψ}flatten⁡\frac{A\subseteq\bigcup_j\phi_j}{A\vdash_{\Delta}\bigcup\{\phi_j\Rightarrow\ell_j,\phi\Rightarrow\ell\}\longrightarrow\bigcup\{\phi_j\Rightarrow\ell_j\}}{\operatorname{prune}} \qquad \frac{A\vdash_{\Delta}\bigcup\{\Omega,\phi\Rightarrow\bigcup\{\Psi\}\}\longrightarrow\bigcup\{\Omega,\phi\cap\Psi\}}{\operatorname{flatten}}
\frac{\Delta\ \mathrm{wf}\ ({\xref}\text{Section 5.3})}{A\vdash_{\Delta}\operatorname{ref}\ T\longrightarrow\Delta(T)} \qquad \frac{\operatorname{guards}(t)=(\phi_j)}{A\vdash_{\Delta}\bigcup\{\phi_j\Rightarrow\ell_j\}\longrightarrow t:u_{\lvert t\rvert}\times\bigcup\{(j,\phi_j)\Rightarrow\ell_j\}}
Rewrite judgments

Figure 14. Rewrite judgments, named as in Figure 2. Lean: Core.Step

Layout Interpretation

Consider T=A(x:u1,y:u1)∣B(y:u1,x:u1)T = A(x : u_1, y : u_1) \mid B(y : u_1, x : u_1), whose two constructors declare the same one-bit fields but in opposite orders. The derivation below computes the structural representations of B(0,1)B(0, 1) under a rewritten variant of the canonical layout that stores its field xx behind a two-bit pointer. Since this layout refers to no type, we interpret it in the empty environment ∅\varnothing. We use blue to denote an evaluation step.

The structural representations of B(0, 1), computed one evaluation step at a time
W⋃{A⇒x:u1×y:u1, B⇒y:u1×&2(x:u1)}∅(B(0,1))={cons⁡B(η)∣η∈Wy:u1×&2(x:u1)∅(B(0,1))}={cons⁡B(η)∣η∈Wy:u1∅(B(0,1))×W&2(x:u1)∅(B(0,1))}={cons⁡B(η)∣η∈Wy:u1∅(B(0,1))×W&2(x:u1)∅(B(0,1))}={cons⁡B(η)∣η∈{0}×W&2(x:u1)∅(B(0,1))}={cons⁡B(η)∣η∈{0}×W&2(x:u1)∅(B(0,1))}={cons⁡B(η)∣η∈{0}×{ptr⁡(α,k)∣α∈{0,1,2,3}, k∈Wx:u1∅(B(0,1))}}={cons⁡B(η)∣η∈{0}×{ptr⁡(α,k)∣α∈{0,1,2,3}, k∈Wx:u1∅(B(0,1))}}={cons⁡B(η)∣η∈{0}×{ptr⁡(0,1),ptr⁡(1,1),ptr⁡(2,1),ptr⁡(3,1)}}={cons⁡B(η)∣η∈{0}×{ptr⁡(0,1),ptr⁡(1,1),ptr⁡(2,1),ptr⁡(3,1)}}={cons⁡B(0,ptr⁡(0,1)), cons⁡B(0,ptr⁡(1,1)),cons⁡B(0,ptr⁡(2,1)), cons⁡B(0,ptr⁡(3,1))}\begin{aligned} &\mathcal{W}^{\varnothing}_{\bigcup\{A \Rightarrow x : u_1 \times y : u_1,\ B \Rightarrow y : u_1 \times\&_{2}(x : u_1)\}}(B(0,1)) \\ ={}& \left\{\operatorname{cons}_{B}(\eta)\mid\eta\in\mathcal{W}^{\varnothing}_{y:u_1\times\&_{2}(x:u_1)}(B(0,1))\right\}\\ ={}& \left\{\operatorname{cons}_{B}(\eta)\mid\eta\in\mathcal{W}^{\varnothing}_{y:u_1}(B(0,1))\times\mathcal{W}^{\varnothing}_{\&_{2}(x:u_1)}(B(0,1))\right\}\\ ={}& \left\{\operatorname{cons}_{B}(\eta)\mid\eta\in\mathcal{W}^{\varnothing}_{y:u_1}(B(0,1))\times\mathcal{W}^{\varnothing}_{\&_{2}(x:u_1)}(B(0,1))\right\}\\ ={}& \left\{\operatorname{cons}_{B}(\eta)\mid\eta\in\{0\}\times\mathcal{W}^{\varnothing}_{\&_{2}(x:u_1)}(B(0,1))\right\}\\ ={}& \left\{\operatorname{cons}_{B}(\eta)\mid\eta\in\{0\}\times\mathcal{W}^{\varnothing}_{\&_{2}(x:u_1)}(B(0,1))\right\}\\ ={}& \left\{\operatorname{cons}_{B}(\eta)\mid\eta\in\{0\}\times\{\operatorname{ptr}(\alpha,k)\mid\alpha\in\{0,1,2,3\},\ k\in\mathcal{W}^{\varnothing}_{x:u_1}(B(0,1))\}\right\}\\ ={}& \left\{\operatorname{cons}_{B}(\eta)\mid\eta\in\{0\}\times\{\operatorname{ptr}(\alpha,k)\mid\alpha\in\{0,1,2,3\},\ k\in\mathcal{W}^{\varnothing}_{x:u_1}(B(0,1))\}\right\}\\ ={}& \left\{\operatorname{cons}_{B}(\eta)\mid\eta\in\{0\}\times\{\operatorname{ptr}(0,1),\operatorname{ptr}(1,1),\operatorname{ptr}(2,1),\operatorname{ptr}(3,1)\}\right\}\\ ={}& \left\{\operatorname{cons}_{B}(\eta)\mid\eta\in\{0\}\times\{\operatorname{ptr}(0,1),\operatorname{ptr}(1,1),\operatorname{ptr}(2,1),\operatorname{ptr}(3,1)\}\right\}\\ ={}& \left\{\operatorname{cons}_{B}(0,\operatorname{ptr}(0,1)),\ \operatorname{cons}_{B}(0,\operatorname{ptr}(1,1)),\right.\\ &\qquad\left.\operatorname{cons}_{B}(0,\operatorname{ptr}(2,1)),\ \operatorname{cons}_{B}(0,\operatorname{ptr}(3,1))\right\} \end{aligned}

Figure 15. The structural representations of B(0,1)B(0, 1), computed one evaluation step at a time.

Producer and Consumer Specialization

Specialization makes matches read and constructions write the chosen layouts before lowering (§ 8.2). A binder is inline when its fields lie directly in the cell, and stored when the cell holds it as a scalar or pointer. A construction makes an arm selectable when its explicit constructors and literals satisfy the arm’s guard. We write π\pi for a path and κ\kappa for the known provenance (§ 4.1 and § 4.2).

In the running example, the layout unfolds a list’s tail into the head’s cell, giving arms Nil, Cons(hh, Nil), and Cons(hh, Cons(h′h', t′t')) with t′t' behind a pointer. Specialization rewrites map on the left into the function on the right.

fn map(xs: List): List =
  match xs {
    Nil => Nil,
    Cons(h, t) => Cons(h + 1, map(t))
  }
fn map(xs: List): List =
  match xs {
    Nil => Nil,
    Cons(h, Nil) => Cons(h + 1, Nil),
    Cons(h, Cons(h', t')) =>
      Cons(h + 1, Cons(h' + 1, map(t')))
  }

Consumer specialization. Algorithm 1 compiles matches into decision trees against the layout [60]. It tests positions demanded by the first live clause in position order, extending κ\kappa without a test when only one layout arm remains. Reify groups tests within a cell into sibling arms; tests behind a pointer become a nested match. Resolve recompiles matches on inline binders at their paths, inlining one step of a callee that matches the binder. Thus map(tt) becomes Cons(h′+1h' + 1, map(t′t')); the call on the stored t′t' remains.

Producer specialization. Algorithm 2 exposes constructors needed to select an arm. Expand inlines a call in a constructor argument and moves the enclosing construction into each resulting match branch. For example, Cons(nn, range(n−1n - 1)) cannot select an arm until the tail’s constructor is known. One step yields Cons(nn, Nil) and Cons(nn, Cons(n−1n - 1, range(n−2n - 2))), each selecting an arm. Expansion may continue toward a more specific arm; otherwise, Dispatch tests the child’s constructor and respells it in each branch. Stored pointers pass through under aliases recording their constructors. Dispatch requires inline children to decompose into scalars, pointers, or inline constructors that have no further dispatch.

Bounds. Inlining a recursive call may expose another call without revealing the constructor the layout needs. To ensure compilation terminates, a budget bounds this compile-time work, not runtime recursion or input size. Expansion spends one unit per inlined call, starting from Bℓ=dℓ(c+1)B_\ell= d_\ell(c + 1). Here dℓd_\ell is the largest number of positions within a value that any one guard tests, excluding the root. In the list layout, the only test beyond the root asks whether the tail is Nil or Cons, so dℓ=1d_\ell= 1. The parameter cc is the size of the largest group of functions connected by tail calls outside constructions. The factor c+1c + 1 allows cc calls that build nothing plus one that exposes a constructor. Let-bound values restart with their own layout’s budget. When expansion runs out, dispatch may expose the missing constructors by runtime tests; it starts from Qℓ=dℓ+1Q_\ell= d_\ell+ 1 and spends one unit per child destruction. If dispatch cannot supply the fields safely, compilation rejects the construction.

Notably, these bounds can reject valid programs. For example, suppose drop traverses a list by tail calls before returning Nil. Expanding Cons(hh, drop(tt)) exhausts the budget while one branch still contains a recursive call. Under the two-element layout, dispatch cannot safely extract the packed child’s fields, so compilation rejects the construction.

Algorithm 1 Consumer specialization.

  1. function SpecializeMatch(clauses CC, path π\pi) ⊲ in the current cell ℓ\ell, under facts κ\kappa

  2. &nbsp;&nbsp;&nbsp;&nbsp;return Reify(the decision tree of CC at π\pi, against ℓ\ell under κ\kappa)

  3. function Reify(TT)

  4. &nbsp;&nbsp;&nbsp;&nbsp;if TT is a leaf (e,σ)(e, \sigma) then return Resolve(ee, σ\sigma) ⊲ σ\sigma: binders to paths

  5. &nbsp;&nbsp;&nbsp;&nbsp;return a match with one reified arm per outcome of TT

  6. function Resolve(ee, σ\sigma)

  7. &nbsp;&nbsp;&nbsp;&nbsp;if e=match⁡ y {…}e = \operatorname{match}\ y\ \{\ldots\} and yy is inline then

  8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return SpecializeMatch(the clauses of ee, σ(y)\sigma(y))

  9. &nbsp;&nbsp;&nbsp;&nbsp;else if e=g(…,y,…)e = g(\ldots, y, \ldots), the body of gg matches that parameter, and yy is inline then

  10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return SpecializeMatch(the clauses of gg, σ(y)\sigma(y)) ⊲ inline one step of gg

  11. &nbsp;&nbsp;&nbsp;&nbsp;else if e=ye = y and yy is stored then

  12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return the field or pointer that stores yy

  13. &nbsp;&nbsp;&nbsp;&nbsp;else if e=ye = y and yy is inline as K(a1,…,an)K(a_1,\ldots,a_n) with every aia_i stored or constant then

  14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return K(a1,…,an)K(a_1,\ldots,a_n) ⊲ rebuild one constructor

  15. &nbsp;&nbsp;&nbsp;&nbsp;else if e=ye = y then

  16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;reject ⊲ rebuilding yy would copy its structure

  17. &nbsp;&nbsp;&nbsp;&nbsp;end if

  18. &nbsp;&nbsp;&nbsp;&nbsp;return ee with Resolve applied to each subexpression

Algorithm 2 Producer specialization.

  1. function Expand(ee, cell layout ℓ\ell, budget bb) ⊲ initially b=Bℓb = B_\ell

  2. &nbsp;&nbsp;&nbsp;&nbsp;if e=match⁡ s {pi⇒ei}ie = \operatorname{match}\ s\ \{p_i \Rightarrow e_i\}_i then

  3. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return match⁡ s {pi⇒Expand⁡(ei,ℓ,b)}i\operatorname{match}\ s\ \{p_i \Rightarrow\operatorname{Expand}(e_i,\ell,b)\}_i

  4. &nbsp;&nbsp;&nbsp;&nbsp;else if e=let⁡ x:ℓx=v in⁡ e′e = \operatorname{let}\ x : \ell_x = v\ \operatorname{in}\ e' then

  5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return let⁡ x:ℓx=Expand⁡(v,ℓx,Bℓx) in⁡ Expand⁡(e′,ℓ,b)\operatorname{let}\ x : \ell_x = \operatorname{Expand}(v,\ell_x,B_{\ell_x})\ \operatorname{in}\ \operatorname{Expand}(e',\ell,b)

  6. &nbsp;&nbsp;&nbsp;&nbsp;else if ee is a construction and some arm of ℓ\ell is selectable then

  7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return ee

  8. &nbsp;&nbsp;&nbsp;&nbsp;else if e=K(…,g(uˉ),…)e = K(\ldots,g(\bar{u}),\ldots) for a known function gg then

  9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if b>0b > 0 then

  10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e′←ee' \leftarrow e with gg inlined and KK pushed into the arms of its match

  11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return Expand(e′,ℓ,b−1e',\ell,b-1)

  12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else if Dispatch cannot expose the hidden constructor then

  13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;reject

  14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end if

  15. &nbsp;&nbsp;&nbsp;&nbsp;end if

  16. &nbsp;&nbsp;&nbsp;&nbsp;return ee

  17. function Dispatch(ee, cell layout ℓ\ell, budget qq) ⊲ initially q=Qℓq = Q_\ell

  18. &nbsp;&nbsp;&nbsp;&nbsp;if q=0q = 0, ee is not a construction, or an arm is selectable then return ee

  19. &nbsp;&nbsp;&nbsp;&nbsp;i←i \leftarrow the first argument whose constructor a guard of ℓ\ell constrains

  20. &nbsp;&nbsp;&nbsp;&nbsp;for all constructors CC of eie_i's type do

  21. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;eC←Dispatch⁡(e[i←C(yˉ)],ℓ,q−1)e_C \leftarrow\operatorname{Dispatch}(e[i \leftarrow C(\bar{y})],\ell,q-1) ⊲ yˉ\bar{y} fresh

  22. &nbsp;&nbsp;&nbsp;&nbsp;end for

  23. &nbsp;&nbsp;&nbsp;&nbsp;return match⁡ ei {C(yˉ)⇒eC}C\operatorname{match}\ e_i\ \{C(\bar{y}) \Rightarrow e_C\}_C

Physical Encoding and Decoding

The encoder and decoder of § 7.1 satisfy the following sufficient conditions.

Discriminant Closure

The judgment Γ⊢ℓ disc\Gamma\vdash\ell\ \mathrm{disc} checks that each tag is stored whole in its scope. Γ\Gamma records available scalar paths, not run-time values. Write ∣π∣|\pi| for a path’s declared scalar width. The paths stored whole unconditionally in ℓ\ell are (Lean: Stored):

S(π:un)={{π},∣π∣ is defined and at most n,∅,otherwise,S(\pi: u_n) = \begin{cases} \{\pi\}, & |\pi|\text{ is defined and at most }n,\\ \varnothing, & \text{otherwise}, \end{cases}
S(&n(ℓ))=S(ℓ),S(\&_{n}(\ell)) = S(\ell),
S(ℓ0×ℓ1)=S(ℓ0)∪S(ℓ1),S(\ell_0 \times\ell_1) = S(\ell_0) \cup S(\ell_1),
S(ℓ)=∅for all other forms.S(\ell) = \varnothing\qquad\text{for all other forms.}

At a product ℓ0×ℓ1\ell_0 \times\ell_1, check both components with Γ∪S(ℓ0×ℓ1)\Gamma\cup S(\ell_0 \times\ell_1). Pointers preserve Γ\Gamma; names reset it to ∅\varnothing. Check every sum arm with Γ\Gamma, additionally requiring a tagged sum’s tag path to belong to Γ\Gamma. Leaves need no further check; reference bodies are checked separately from ∅\varnothing. The forward variant Γ⊢ℓ disc→\Gamma\vdash\ell\ \mathrm{disc}\to instead checks ℓ0\ell_0 with Γ\Gamma and ℓ1\ell_1 with Γ∪S(ℓ0)\Gamma\cup S(\ell_0), so a tag must precede its payload. Importantly, other decoding orders could relax this requirement when tag locations can be determined without first decoding the payloads they select.

Encoding and Decoding Guarantees

The encoder emits scalars at their widths, most significant bit first, concatenates product components, selects disjoint-sum arms by their tags, and stores each pointer as an address whose heap block contains the pointee. The decoder reads components from left to right. Its sufficient condition is the forward judgment ∅⊢ℓ disc→\varnothing\vdash\ell\ \mathrm{disc}\to of Appendix § 17.§ 1, where each tag field must be stored whole before its payload in the same scope. Both functions take a recursion bound nn (fuel), written encode⁡ℓn\operatorname{encode}_{\ell}^{n} and decode⁡ℓn\operatorname{decode}_{\ell}^{n}.

A layout is concrete for τ\tau when the representations of Vτ\mathcal{V}_{\tau} contain no markers of ordinary sums. For a minimum pointer width ww, a value vv satisfies the address-capacity bound when some η0∈WΔℓ(v)\eta_0 \in W_{\Delta}^{\ell}(v) has ∣η0∣ρ≤2w|\eta_0|_{\rho} \le2^w, where ∣η∣ρ|\eta|_{\rho} counts the pointer occurrences in η\eta, so that the encoder can give every occurrence a distinct address.

Theorem 11 (Encoding within address capacity Lean: Physical.encoding_exists_direct). Suppose Inv⁡(Δ)\operatorname{Inv}(\Delta), ℓ\ell is well formed on Vτ\mathcal{V}_{\tau} under Δ\Delta and concrete for τ\tau, ∅⊢ℓ disc\varnothing\vdash\ell\ \mathrm{disc}, and ∅⊢Δ(T) disc\varnothing\vdash\Delta(T)\ \mathrm{disc} for every T∈dom⁡ΔT \in\operatorname{dom}\Delta. Suppose every pointer in ℓ\ell and the bodies bound by Δ\Delta has width at least ww. For every v∈Vτv \in\mathcal{V}_{\tau} satisfying the address-capacity bound, the encoder succeeds at some fuel on some permitted representation,

∃η∈WℓΔ(v), n∈N, m∈M.encode⁡ℓn(η)=m.\exists\eta\in W_{\ell}^{\Delta}(v),\ n \in\mathbb{N},\ m \in\mathcal{M}.\quad\operatorname{encode}_{\ell}^{n}(\eta) = m.

Lemma 12 (Recovery by forward decoding Lean: Physical.roundTrip_direct). If Δ\Delta and ℓ\ell are well formed, ∅⊢ℓ disc→\varnothing\vdash\ell\ \mathrm{disc}\to, and ∅⊢Δ(T) disc→\varnothing\vdash\Delta(T)\ \mathrm{disc}\to for every T∈dom⁡ΔT \in\operatorname{dom}\Delta, then at every fuel nn the decoder decode⁡ℓn\operatorname{decode}_{\ell}^{n} returns η\eta for every successful encoding encode⁡ℓn(η)\operatorname{encode}_{\ell}^{n}(\eta) of a permitted representation η\eta, and so does every larger fuel. Each such pair therefore satisfies the storage recovery property Equation (7).

Program Preservation

Programs consist of first-order function definitions over source values, with the expression syntax

(Lean: Programs.{Expr, Prog})

x,f,K∈Idk∈Nop:N×N⇀Nx, f, K \in\mathrm{Id} \qquad k \in\mathbb{N} \qquad op : \mathbb{N} \times\mathbb{N} \rightharpoonup\mathbb{N}
e::=x∣k∣op(e,e)∣K(eˉ)∣f(eˉ)∣let x=e in e∣match e with {Ki(xˉi)⇒ei}\begin{aligned} e &::= x \mid k \mid op(e,e) \mid K(\bar{e}) \mid f(\bar{e})\\ &\mid\text{let }x=e\text{ in }e \mid\text{match }e\text{ with }\{K_i(\bar{x}_i)\Rightarrow e_i\} \end{aligned}
P::={fi(xˉi)=ei}.P ::= \{f_i(\bar{x}_i)=e_i\}.

For simplicity, function and match-arm lookup select the first matching name. Both interpretations evaluate arguments from left to right before construction or a call. A call requires the declared arity and evaluates the function body in a fresh environment containing only its parameter bindings; recursive calls use the same PP. Variables, literals, scalar operations, and let bindings have their usual call-by-value meaning. An undefined lookup or scalar operation supplies no evaluation derivation.

Source evaluation P;ρ⊢e⇓vP;\rho\vdash e\Downarrow v uses the values of § 4.1. Construction evaluates its arguments to vˉ\bar{v} and forms K(vˉ)K(\bar{v}), provided this value belongs to the constructor’s declared type. Matching selects the arm for the evaluated constructor and binds its fields to the branch variables in declaration order, with equal arities. Structural evaluation uses the same program and scalar operations, but uses represented datatype values, defined below.

The datatype interface. Represented values comprise scalars and datatype handles. For a relation r∼vr\sim v from represented values to source values, the interface provides partial operations

construct⁡(K,rˉ),destruct⁡(r).\operatorname{construct}(K,\bar{r}),\qquad\operatorname{destruct}(r).

Scalars relate only to the same scalar, datatype handles relate only to constructor values, and each represented value relates to at most one source value. For componentwise-related arguments rˉ∼vˉ\bar{r}\sim\bar{v}, construction succeeds exactly when K(vˉ)K(\bar{v}) is admitted by the declaration, including its field types and arity; its result relates to K(vˉ)K(\bar{v}). Destruction of a handle related to K(vˉ)K(\bar{v}) succeeds with (K,rˉ)(K,\bar{r}) where rˉ∼vˉ\bar{r}\sim\bar{v} in declaration order. These conditions give both directions of the constructor and match cases in evaluation correspondence.

The remainder instantiates this interface with faithful layouts, through a construction policy bb and a destruction policy ι\iota satisfying

bT(v)∈Wref TΔ(v),ιT(η)=vfor v∈VT and η∈Wref TΔ(v).b_{\mathsf{T}}(v)\in\mathcal{W}^{\Delta}_{\mathrm{ref}\,\mathsf{T}}(v),\qquad\iota_{\mathsf{T}}(\eta)=v\quad\text{for }v\in\mathcal{V}_{\mathsf{T}}\text{ and }\eta\in\mathcal{W}^{\Delta}_{\mathrm{ref}\,\mathsf{T}}(v).

A valid bb meets the left condition on every admitted value and returns nothing for any other value, and a valid ι\iota meets the right one.

Computable policies. The encoder of Lemma 3 gives a computable valid bb under Inv⁡(Δ)\operatorname{Inv}(\Delta) when Δ\Delta binds every declared type, and the canonical decoder, composed with the reconstruction functions of further rewrites, gives a valid ι\iota. These are computable functions of the model; implementing them as generated code requires a separate proof of the same interface laws.

Theorem 13 (Derived policies) (Lean: Core.UpdateSeq.{decoder_decodes, observations}). Let Δ0\Delta_0 be a canonical environment and Δ0⟶∗Δ1\Delta_0\longrightarrow^{*}\Delta_1 a finite sequence of valid updates that keep their reconstruction functions. Undoing the updates in reverse order, each by applying its function at every reference to the updated type and then applying the canonical decoder gives a valid destruction policy ι1\iota_1 for Δ1\Delta_1. (6) holds with the encoder of Lemma 3 at both endpoints, the canonical decoder at Δ0\Delta_0, and ι1\iota_1 at Δ1\Delta_1, for all related inputs.

Views and related inputs. A represented value has the form

r::=k∣⟨T,η,π⟩.r ::= k \mid\langle T,\eta,\pi\rangle.

The type TT describes the value represented by η\eta; the path π\pi selects a datatype subvalue of that value, possibly of another type. Scalars represent themselves. A view represents a constructor value ww exactly when an admitted root has that representation and selects ww:

k∼Δv  ⟺  v=k,k \sim_{\Delta} v \iff v = k,
⟨T,η,π⟩∼Δw  ⟺  w is a constructor value and\langle T, \eta, \pi\rangle\sim_{\Delta} w \iff w\text{ is a constructor value and}
∃u∈VT. η∈Wref⁡TΔ(u) ∧ u.π=w.\exists u \in\mathcal{V}_{T}.\ \eta\in\mathcal{W}^{\Delta}_{\operatorname{ref} T}(u)\ \land\ u.\pi= w.

Environments ρ′∼Δρ\rho' \sim_{\Delta} \rho have the same domain and satisfy ρ′(x)∼Δρ(x)\rho'(x) \sim_{\Delta} \rho(x) at each bound variable. Thus related inputs provide both evaluations with the same source values, while their structural representations may differ.

A destruction policy ι\iota induces the partial reader

αι(k)=k,αι(⟨T,η,π⟩)=(ιT(η)).π.\alpha_{\iota}(k) = k,\qquad\alpha_{\iota}(\langle T,\eta,\pi\rangle) = (\iota_{T}(\eta)).\pi.

Under a valid ι\iota, related values satisfy r∼Δv  ⟹  αι(r)=vr \sim_{\Delta} v \implies\alpha_{\iota}(r) = v. Structural construction first evaluates its arguments to rˉ\bar{r} and reads vˉ=αι(rˉ)\bar{v} = \alpha_{\iota}(\bar{r}) componentwise. For v=K(vˉ)∈VTv = K(\bar{v}) \in\mathcal{V}_{T}, the policy bb returns a permitted representation and construction produces

⟨T,bT(v),ϵ⟩.\langle T, b_{T}(v), \epsilon\rangle.

The policies are fixed for an evaluation. We represent each as a partial function on arbitrary type names and values or representations; validity of bb requires a permitted result for every value of each declared type and no result for any other value. The functions bTb_{T} above are its total restrictions to those values.

Matching evaluates its scrutinee to ⟨T,η,π⟩\langle T,\eta,\pi\rangle and obtains its constructor through αι\alpha_{\iota}. For declared fields fi:τif_i : \tau_i, it binds scalar fields to their recovered scalar values and datatype fields to ⟨T,η,π.fi⟩\langle T,\eta,\pi.f_i\rangle. It then evaluates the selected branch in the extended environment. The extended views keep η\eta and need no separately constructed representation of a field. The branch variables must match the declared field count. These operations and the common rules define Δ\Delta, bb, ι\iota; PP; ρ′⊢e⇓r\rho' \vdash e \Downarrow r.

Lemma 14 (Evaluation correspondence Lean: Programs.evaluation_value_iff). Suppose Δ\Delta is faithful. For valid policies bb and ι\iota and related environments ρ′∼Δρ\rho' \sim_{\Delta} \rho,

P;ρ⊢e⇓v  ⟺  ∃r. Δ,b,ι;P;ρ′⊢e⇓r∧r∼Δv.P;\rho\vdash e \Downarrow v \iff\exists r.\ \Delta,b,\iota;P;\rho' \vdash e \Downarrow r \land r \sim_{\Delta} v.

Applying correspondence to both environments gives Theorem 8. Preserving faithfulness of the environment then gives Theorem 9. A view of a field continues to refer to its enclosing representation, so this argument requires no agreement between source match depth and layout unfolding depth.

Additional Evaluation Results

Complete Layout Frontiers

Figure 16. Lower is better. Mimalloc runtime–RSS frontiers for benchmarks with a non-default Pareto-optimal layout. Each panel plots runtime (ms, vertical) against peak RSS (MiB, horizontal). ⋄\diamond marks a default Isomer layout; ■\blacksquare marks an Isomer layout optimized via rewrites on the frontier (■\blacksquare) and traces the frontier (⋯\cdots). Triangles mark MLton (△\triangle) and Morphic (▽\triangledown). Dominated layouts are omitted.

Peak RSS (Mimalloc)

We report whole-process peak resident set size (RSS), normalized to Isomer with its default layout. For MLton, this measure includes its GC-managed heap.

Figure 17. Lower is better. Mimalloc peak RSS relative to default Isomer. The best-RSS layout is selected independently for each benchmark. Arrows indicate ratios beyond the displayed range.

Parity Layouts with Morphic

We run Isomer with Morphic’s own layouts, derived with our rewrite rules and matched bit for bit, so that only the compilers differ. One program, primes-iter, declares no ADTs. Isomer is 1.27× faster (geomean).

Figure 18. Lower is better. Mimalloc runtime relative to Morphic, with Isomer at Morphic’s layouts.

System Allocator Results

We repeat the workloads and sampling protocol of § 9.1 with the system allocator. MLton uses its own tracing heap, so its measurements are shared across allocator comparisons. Isomer with default layout achieves speedups (geomean) of 0.91×0.91\times versus MLton and 1.21×1.21\times versus Morphic, using 0.27×0.27\times and 0.94×0.94\times their peak RSS, respectively. Morphic-style layouts give a 1.42×1.42\times speedup over Morphic across all 18 benchmarks. Against Ribbit on pcf, option, and rb-tree, Isomer achieves speedups of 1.15×1.15\times, 1.45×1.45\times, and 2.15×2.15\times, respectively, or 1.53×1.53\times (geomean).

Figure 19. Lower is better. System-allocator runtime (top) and peak RSS (bottom) relative to default Isomer, using the conventions of Figure 9. The best-runtime and best-RSS layouts are selected independently for each benchmark. Arrows indicate ratios beyond the displayed range.

MLton Array Representations

For each benchmark, calibration selects the fastest of four MLton array implementations whose output agrees with the reference on the checked workload. The selected implementation is recorded and used for every timed run. primes-iter and tmap contain no source arrays.

ModeArray ImplementationBenchmarks
mutatemutablenqueens-iterative, parse-json, primes-sieve, quicksort, text-stats, unify, kd-tree, tree23
copyFlat, copied on updatecalc, lisp
rerootPersistent, update chainsderiv, nqueens-functional, rbtree-ck, words-trie
trie32Persistent, 32-way triecfold, rbtree

Table 1. MLton array implementations selected for the comparison benchmarks.

I Mechanization

Table 2 lists, in paper order, every definition, lemma, and theorem of § 4 to § 7 and of the appendices, together with the mechanized examples of § 2 and § 8.1. Files are relative to the root of the Lean development, with the prefix Ismr/ omitted. We additionally provide Paper.lean, which restates each numbered result. Propositional extensionality and quotient soundness are the only axioms used in this formalization.

PaperFileLean
§ 2<br>Listings (1), (2), (4) and (5),<br>derived by the rules and faithfulExamples/Motivation.leanExamples.Motivation.{morphic_core,lowBits_core,shape_core,terminal_core,morphic_stores,morphic_faithful,lowBits_faithful,shape_faithful,terminal_faithful}
§ 4
§ 4.1, values, typing, and pathsSource.leanValue,Values,Value.select,Decls.WF
§ 4.2, provenances as sets of values, admitted subjectsSource.leanProv.holds
Provenance.leanProv.Equiv
Figure 1, layoutsLayout/Basic.leanDomain
Layout/Basic.leanLayout,LayoutEnv
Source.leanPath,Prov
Expr.leanExpr
Arms and their guardsLayout/SumArm.leanSumArm, Prov.Unique
Layout/ArmMaps.leanArmMap
Tags, selectors, and code widthsSource.leanDecls.lookupTag,ArmSelector,ArmSelector.{sound,complete},codeWidth,Decls.tagWidth
Canonical layout environmentLayout/Canonical.leanCanonical.env
§ 4.4, layout contextsLayout/Context.leanCtxt,Ctxt.{fill,holeDom}
Figure 2, rules and certificatesCore/Rules.leanStep,Step.{certificate,local}
Core/Local.leanRuleCertificate
Layout/Flatten.leanrefineArms,flattenArms,WF.flatten,Rule.flattenRecon,Rule.flattenRecon_rep
Provenance/KeepFirst.leanProv.keepFirst,Prov.{keepFirst_pairwise,keepFirst_covers,find?_guard_of_mem_keepFirst}
Definition updatesLayout/Basic.leanLayoutEnv.set
Figure 3, the double-ended layoutExamples/Motivation.leanExamples.Motivation.{doubleEnded_core,doubleEnded_stores,doubleEnded_faithful}
§ 5
§ 5.1, structural representationsLayout/Semantics.leanEnc
§ 5.1, the canonical representation of the example nodeExamples/Worked.leanExamples.Worked.{canonical_node,canonical_node_only}
Figure 4, interpretationLayout/Semantics.leanRep
Definition 1, faithfulness and determinationCorrectness/Faithfulness.leanFaithful,Total,AbsoluteInjective,Determines,AbsoluteInjective.determines
§ 5.3 and Figure 13, well-formednessLayout/WellFormed.leanWF,LayoutEnv.WF
Layout/ArmMaps.leanWF.sumMap_iff
Layout/TaggedArms.leanWF.taggedMap_iff
Core/Local.leanInv
Definition 2, environment invariantLayout/WellFormed.leanLayoutEnv.WF
Layout/Structural.leanLayoutEnv.Descent
Lemma 3, totality by a computable encoderCorrectness/Totality.leanWF.totality,represent_total
Layout/Represent.leanrepresent,represent_sound
§ 6
§ 6.1, sharing, refinement, and its lawsCore/Local.leanShares, absoluteInjective_iff_shares, Refines, Refines.{refl,trans,faithful}
Definition 4, local refinementCore/Local.leanLocalRefinement
§ 6.1, reconstruction functionsCore/Local.leanReconstructs, Reconstructs.refines, LocalRefinement.of_reconstructs
Core/Rules.leanStep.certificate
Core/StorageRules.leanRecon.{dropFirst,swap,join}
Theorem 5, contextual replacementCore/Contextual.leanRefines.context,LocalRefinement.context
PaperFileLean
Lemma 6, recursive bindingCore/Recursive.leanLocalRefinement.bind, Refines.bind
Theorem 7, valid rewrites and soundnessCore/Correctness.leanRewrite, RewriteSeq, Rewrite.sound, RewriteSeq.sound
Section 6.2, composition and canonical startsCore/Correctness.leanRewriteSeq.faithful
Layout/Canonical.leanCanonical.body_wf
Layout/CanonicalDecode.leanCanonical.{faithful,decode_rep}
Core/Canonical.leancanonical_rewrites_faithful
Section 6.3, interval encodingCore/Interval.leanInterval.{Bounds,certificate,local_refinement,rewrite}
Section 6.4, the two evaluations, valid policies, related valuesPrograms/SourceSemantics.leanPrograms.Eval
Programs/StructuralSemantics.leanPrograms.StructuralEval
Programs/Views.leanPrograms.{Builder,Decoder,Builds,Decodes,Represents,FaithfulRoots}
Correctness/ProgramPreservation.leanPrograms.EnvRel
Theorem 8, representation independenceCorrectness/ProgramPreservation.leanPrograms.representation_independence
Correctness/ProgramPreservation.leanPrograms.view_laws
Programs/Interface.leanPrograms.Interface.independence
Theorem 9, program preservationCore/Programs.leanBodyRewriteSeq.{observations,roots}
Layout/Structural.leanLayoutEnv.Binds
Section 6.4, computable policiesPrograms/Construct.leanPrograms.Builds.construct
Programs/CanonicalDecoder.leanPrograms.Decodes.canonical
Core/Policies.leanUpdateSeq.{decoder,decoder_decodes}
Section 7
Equation (7), storage recoveryPhysical/Semantic.leanPhysical.{SemanticRoundTrip,RoundTrip}, Physical.RoundTrip.semantic
Theorem 10, recovery, loaded inputsCore/Storage.leanstorage_recovery
Physical/Semantic.leanPhysical.SemanticRoundTrip.recovery
Programs/SemanticStorage.leanPrograms.loaded_evaluation_iff
Section 7.1, the forward codec and a stored nodePhysical/Coding.leanPhysical.{encodeLayout,decodeLayout}
Physical/Direct.leanPhysical.{encoding_exists_direct,roundTrip_direct}
Examples/Motivation.leanExamples.Motivation.{lowBits_encode,lowBits_round_trip,lowBits_recovery}
Section 7.2, read order, ambiguityPhysical/Counterexamples.leanPhysical.Limits.{read_order,encoding_ambiguity,no_value_decoder}
Physical/Semantic.leanPhysical.SemanticRoundTrip.injective
Section 8
Section 8.1, a finite array as a sum indexed by its lengthExamples/Array.leanExamples.Array.{arms,sized,tagSize,updates,sized_faithful,construct_a79,round_trip}
Appendix A
Appendix A, deciding provenance equalityProvenance/Decide.leanProv.{decidableEquiv,equivCheck_iff,counterexample,counterexample_sound,counterexample_complete}
Provenance/Finite.leanObservation.{proj,proj_mem,holds_proj}
Appendix C
Figure 14, rule judgmentsCore/Rules.leanStep
Appendix D
Figure 15, the representations of B(0, 1)Examples/Worked.leanExamples.Worked.b01_representations
Appendix F
Appendix F.1, discriminant closureLayout/Stored.leanStored, TagAccess, TagsStored
Fuel-indexed codecPhysical/Coding.leanPhysical.{encodeLayout,decodeLayout,encodeLayout_mono_le,decodeLayout_mono_le}
Theorem 11, encoding within capacityPhysical/Direct.leanPhysical.encoding_exists_direct
Physical/Existence.leanPhysical.{ConcreteOn,AddressCapacity}
Lemma 12, forward decodingPhysical/Direct.leanPhysical.roundTrip_direct
Physical/Words.leanPhysical.Direct
Appendix G
ProgramsPrograms/Syntax.leanPrograms.{Expr,Prog}
Theorem 13, derived policiesCore/Policies.leanUpdateSeq.{decoder,decoder_decodes,observations}
Core/Inversion.leanBodyUpdate, BodyUpdate.{undo,undo_decodes}
, UpdateSeq, UpdateSeq.{undo,undo_decodes}, Ctxt.recon
Lemma 14, evaluation correspondenceCorrectness/ProgramPreservation.leanPrograms.evaluation_value_iff

Table 2. The definitions, theorems, and claims of the paper and its appendices.

References

  1. [1]Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2006. Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley, Boston, MA, USA.
  2. [2]Willow Ahrens, Daniel Donenfeld, Fredrik Kjolstad, and Saman Amarasinghe. 2023. Looplets: A Language for Structured Coiteration. In Proceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization (Montréal, QC, Canada) (CGO ’23). Association for Computing Machinery, New York, NY, USA, 41–54. doi:10.1145/3579990.3580020DOI
  3. [3]Anthropic. 2026. Claude. https://claude.ai. Large language model (Opus 5.5, Fable 5.1).
  4. [4]Julian Bangert and Nickolai Zeldovich. 2014. Nail: a practical tool for parsing and generating data formats. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (Broomfield, CO) (OSDI’14). USENIX Association, USA, 615–628.
  5. [5]Thaïs Baudon. 2024. Algebraic Data Types for High-Performance Computing. Theses. Ecole normale supérieure de lyon - ENS LYON. doi:10.7675/7bb95f1e?689?4cb5z8d80z794397b5f052DOI
  6. [6]Thaïs Baudon, Gabriel Radanne, and Laurent Gonnord. 2023. Bit-Stealing Made Legal: Compilation for Custom Memory Representations of Algebraic Data Types. Proc. ACM Program. Lang. 7, ICFP, Article 216 (2023), 34 pages. doi:10.1145/3607858DOI
  7. [7]Carsten Benthin, Ingo Wald, Sven Woop, and Attila T Áfra. 2018. Compressed-leaf bounding volume hierarchies. In Proceedings of the Conference on High-Performance Graphics. 1–4. doi:10.1145/3231578.3231581DOI
  8. [8]Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (Sept. 1975), 509–517. doi:10.1145/361002.361007DOI
  9. [9]William Brandon, Benjamin Driscoll, Frank Dai, Wilson Berkow, and Mae Milano. 2023. Better Defunctionalization through Lambda Set Specialization. Proc. ACM Program. Lang. 7, PLDI, Article 146 (2023), 24 pages. doi:10.1145/3591260
  10. [10]William Brandon, Benjamin Driscoll, Frank Dai, Jonathan Ragan-Kelley, Mae Milano, and Alex Aiken. 2026. Fully-Automatic Type Inference for Borrows with Lifetimes. Proc. ACM Program. Lang. 10, OOPSLA1 (2026), 597–623. doi:10.1145/3798221
  11. [11]Nicolas Chataing, Stephen Dolan, Gabriel Scherer, and Jeremy Yallop. 2024. Unboxed Data Constructors: Or, How cpp Decides a Halting Problem. Proc. ACM Program. Lang. 8, POPL, Article 51 (2024), 31 pages. doi:10.1145/3632893DOI
  12. [12]Chun Chen, Jacqueline Chame, and Mary Hall. 2008. CHIL-L: A framework for composing high-level loop transformations. Technical Report 08-897. University of Southern California.
  13. [13]Tianqi Chen, Thierry Moreau, Zhiheng Jiang, Lianmin Zheng, Eddie Yan, Meghan Cowan, Haichen Shen, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. TVM: an automated end-to-end optimizing compiler for deep learning. In Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation (Carlsbad, CA, USA) (OSDI’18). USENIX Association, USA, 579–594.arxiv.org/abs/1802.04799
  14. [14]Zilin Chen, Ambroise Lafont, Liam O’Connor, Gabrielle Keller, Craig McLaughlin, Vincent Jackson, and Christine Rizkallah. 2023. Dargent: A Silver Bullet for Verified Data Layout Refinement. Proc. ACM Program. Lang. 7, POPL, Article 47 (2023), 27 pages. doi:10.1145/3571240
  15. [15]Trishul M Chilimbi, Bob Davidson, and James R Larus. 1999. Cache-conscious structure definition. In Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation. 13–24. doi:10.1145/301618.301635
  16. [16]Jongseok Choi, Ethan Che, Jason Ansel, and Oguz Ulygen. 2026. From Minutes to Seconds: LLVM-Guided Autotuning for Helion Kernels. PyTorch Blog. https://pytorch.org/blog/from-minutes-to-seconds-llm-guided-autotuning-for-helion-kernels/
  17. [17]Stephen Chou, Fredrik Kjolstad, and Saman Amarasinghe. 2018. Format Abstraction for Sparse Tensor Algebra Compilers. Proc. ACM Program. Lang. 2, OOPSLA, Article 123 (2018), 30 pages. doi:10.1145/3276493DOI
  18. [18]John Cocke. 1970. Global Common Subexpression Elimination. In Proceedings of a Symposium on Compiler Optimization. Association for Computing Machinery, New York, NY, USA, 20–24. doi:10.1145/800028.808480DOI
  19. [19]Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA, USA.
  20. [20]Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. 1991. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph. ACM Trans. Program. Lang. Syst. 13, 4 (Oct. 1991), 451–490. doi:10.1145/115372.115320
  21. [21]Benjamin W. Aditya, Sorawit Suriyakarn, Clément Pit-Claudel, Qianchuan Ye, and Adam Chlipala. 2019. Narcissus: correct-by-construction derivation of decoders and encoders from binary formats. Proc. ACM Program. Lang. 3, ICFP, Article 82 (July 2019), 29 pages. doi:10.1145/3341686DOI
  22. [22]Iavor S. Diachkti, Mark P. Jones, and Rebekah Leslie. 2005. High-level views on low-level representations. In Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (Tallinn, Estonia) (ICFP ’05). Association for Computing Machinery, New York, NY, USA, 168–179. doi:10.1145/1086365.1086387
  23. [23]Paul Downen, Zena M. Ariola, Simon Peyton Jones, and Richard A. Eisenberg. 2020. Kinds are calling conventions. Proc. ACM Program. Lang. 4, ICFP, Article 104 (Aug. 2020), 29 pages. doi:10.1145/3408986DOI
  24. [24]Richard A. Eisenberg and Simon Peyton Jones. 2017. Lovely Polymorphism. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2017). Association for Computing Machinery, New York, NY, USA, 525–539. doi:10.1145/3062341.3062357
  25. [25]Martin Elsman. 2024. Double-Ended Bit-Stealing for Algebraic Data Types. Proc. ACM Program. Lang. 8, ICFP, Article 239 (Aug. 2024), 33 pages. doi:10.1145/3674628DOI
  26. [26]Kathleen Fisher and Robert Gruber. 2005. PADS: a domain-specific language for processing ad hoc data. SIGPLAN Not. 40, 6 (June 2005), 295–304. doi:10.1145/1064978.1065046DOI
  27. [27]Noah Goldstein. 2023. [PATCH v1] lib/rbtree: Use ‘+’ instead of ‘|’ for setting color. Linux kernel mailing list. https://lore.kernel.org/linux-kernel/2023/04/04/1522
  28. [28]Christophe Gyurgyik, Alexander J Root, and Fredrik Kjolstad. 2026. Decoupling Data Layouts from Bounding Volume Hierarchies. Proc. ACM Program. Lang. 10, PLDI, Article 175 (June 2026), 26 pages. doi:10.1145/3808253DOI
  29. [29]Bastian Hagedorn, Archibald Samuel Elliott, Henrik Barthels, Rastislav Bodik, and Vinod Grover. 2020. Fireiron: A Data-Movement-Aware Scheduling Language for GPUs. In Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques (Virtual Event, GA, USA) (PACT ’20). Association for Computing Machinery, New York, NY, USA, 71–82. doi:10.1145/3410463.3414623
  30. [30]Bastian Hagedorn, Johannes Lenfers, Thomas Koehler, Xueying Qin, Sergei Gorlatch, and Michel Steuwer. 2020. Achieving High-Performance the Functional Way: A Functional Pearl on Expressing High-Performance Optimizations as Rewrite Strategies. Proc. ACM Program. Lang. 4, ICFP, Article 92 (2020), 29 pages. doi:10.1145/3408974DOI
  31. [31]Cordelia V Hall. 1994. Using Hindley-Milner type inference to optimise list representation. In Proceedings of the 1994 ACM conference on LISP and functional programming. 162–172. doi:10.1145/182409.156781DOI
  32. [32]Mary Hall, Kosmin E. Oancea, Anne C. Elster, Ari Rasch, Sameer Ali, Amir Mohammad Tavakkoli, and Richard Schulze. 2025. Scheduling Language Chronology: Past, Present, and Future. ACM Trans. Archit. Code Optim. 22, 3, Article 100 (Sept. 2025), 31 pages. doi:10.1145/3743135DOI
  33. [33]Robert Harper and Greg Morrisett. 1995. Compiling polymorphism using intensional type analysis. In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (San Francisco, California, USA) (POPL ’95). Association for Computing Machinery, New York, NY, USA, 130–141. doi:10.1145/199448.199475DOI
  34. [34]C. A. R. Hoare. 1972. Proof of correctness of data representations. Acta Inform. 4, 1 (1972), 271–281. doi:10.1007/BF00289507
  35. [35]Yuka Ikarashi, Gilbert Louis Bernstein, Alex Reinking, Hasan Genc, and Jonathan Ragan-Kelley. 2022. Exocompilation for Productive Programming of Hardware Accelerators. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2022). Association for Computing Machinery, New York, NY, USA, 703–718. doi:10.1145/3519939.3523446DOI
  36. [36]Yuka Ikarashi, Kevin Qian, Samir Droubi, Alex Reinking, Gilbert Louis Bernstein, and Jonathan Ragan-Kelley. 2025. Exo 2: Growing a Scheduling Language. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1 (Rotterdam, Netherlands) (ASPLOS ’25). Association for Computing Machinery, New York, NY, USA, 426–444. doi:10.1145/3669940.3707218DOI
  37. [37]International Organization for Standardization 1999. ISO/IEC 9899:1999: Programming Languages – C. International Organization for Standardization, Geneva, Switzerland.
  38. [38]Jane Street. 2025. OxCaml: Unboxed Types. https://oxcaml.org/documentation/unboxed-types/intro/. Accessed 2026-10-16.
  39. [39]Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. 1993. Partial evaluation and automatic program generation. Prentice-Hall, Inc., USA.
  40. [40]G. Kahn. 1987. Natural semantics. In STACS ’87, Franz J. Brandenburg, Guy Vidal-Naquet, and Martin Wirsing (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 22–39. doi:10.1007/BFb0039592
  41. [41]Andrew Kennedy and Don Syme. 2001. Design and Implementation of Generics for the .NET Common Language Runtime. In Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation (PLDI ’01). Association for Computing Machinery, New York, NY, USA, 1–12. doi:10.1145/378795.378797DOI
  42. [42]Donald E. Knuth. 1998. Sorting and Searching (2nd ed.). The Art of Computer Programming, Vol. 3. Addison-Wesley, Reading, MA, USA.
  43. [43]Chaitanya Koparkar, Mike Rainey, Michael Vollmer, Milind Kulkarni, and Ryan R. Newton. 2021. Efficient tree-traversals: reconciling parallelism and dense data representations. Proc. ACM Program. Lang. 5, ICFP, Article 91 (Aug. 2021), 29 pages. doi:10.1145/3473596DOI
  44. [44]Mahesh Lakshminarasimhan, Oscar Antepara, Tuowen Zhao, Benjamin Sepanski, Protonu Basu, Hans Johansen, Mary Hall, and Samuel Williams. 2024. Bricks: A high-performance portability layer for computations on block-structured grids. Int. J. High Perform. Comput. Appl. 38, 6 (Nov. 2024), 549–567. doi:10.1177/10943420241268288DOI
  45. [45]Chris Lattner and Vikram Adve. 2004. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Proceedings of the International Symposium on Code Generation and Optimization: Feedback-Directed and Runtime Optimization (Palo Alto, California) (CGO ’04). IEEE Computer Society, USA, 75–86. doi:10.1109/CGO.2004.1281665DOI
  46. [46]Chris Lattner and Vikram S Adve. 2005. Transparent pointer compression for linked data structures. In Proceedings of the 2005 workshop on Memory system performance. 24–35. doi:10.1145/1111583.1111587DOI
  47. [47]Daan Leijen. 2014. Koka: Programming with Row Polymorphic Effect Types. In Proceedings 5th Workshop on Mathematically Structured Functional Programming, Grenoble, France, 12 April 2014 (Electronic Proceedings in Theoretical Computer Science, Vol. 153), Paul Levy and Neel Krishnaswami (Eds.). Open Publishing Association, 100–126. doi:10.4204/EPTCS.153.8DOI
  48. [48]Daan Leijen and Anton Lorenzen. 2023. Tail Recursion Modulo Context: An Equational Approach. Proc. ACM Program. Lang. 7, POPL, Article 40 (Jan. 2023), 30 pages. doi:10.1145/3571233DOI
  49. [49]Daan Leijen, Benjamin Zorn, and Leonardo De Moura. 2019. Mimalloc: Free list sharding in action. In Asian Symposium on Programming Languages and Systems. Springer, 244–265. doi:10.1007/978-3-030-34175-6_13DOI
  50. [50]Xavier Leroy. 1992. Unboxed Objects and Polymorphic Typing. In Proceedings of the 19th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’92). Association for Computing Machinery, New York, NY, USA, 177–188. doi:10.1145/143165.143205DOI
  51. [51]Daan Leijen. 2025. The OCaml System Release 5.4: Documentation and User’s Manual. Inria. https://ocaml.org/manual/5.4/
  52. [52]Michel Lespinasse. 2012. [PATCH v2 08/12] rbtree: low level optimizations in rb_insert_color(). Linux kernel mailing list. https://lkml.iu.edu/1207.1/03044.html
  53. [53]Amanda Liu, Gilbert Louis Bernstein, Adam Chlipala, and Jonathan Ragan-Kelley. 2022. Verified Tensor-Program Optimization via High-Level Scheduling Rewrites. Proc. ACM Program. Lang. 6, POPL, Article 55 (2022), 28 pages. doi:10.1145/3498717DOI
  54. [54]Amanda Liu, Gilbert Louis Bernstein, Shoaib Kamil, Adam Chlipala, and Jonathan Ragan-Kelley. 2026. A Mechanized Algebra of Verified Data Structures for Optimizing Sparse Tensor Programs. Proc. ACM Program. Lang. 10, PLDI, Article 183 (June 2026), 23 pages. doi:10.1145/3808261DOI
  55. [55]Jie Liu, Zhongyuan Zhao, Zijian Ding, Benjamin Brock, Hongbo Rong, and Zhiru Zhang. 2024. UniSparse: An Intermediate Language for General Sparse Format Customization. Proc. ACM Program. Lang. 8, OOPSLA1, Article 99 (2024), 29 pages. doi:10.1145/3649816DOI
  56. [56]Anton Lorenzen and Daan Leijen. 2022. Reference Counting with Frame Limited Reuse. Proc. ACM Program. Lang. 6, ICFP, Article 93 (2022), 24 pages. doi:10.1145/3547634DOI
  57. [57]Anton Lorenzen, Daan Leijen, and Wouter Swierstra. 2023. FP²: Fully in-Place Functional Programming. Proc. ACM Program. Lang. 7, ICFP, Article 198 (Aug. 2023), 30 pages. doi:10.1145/3607840DOI
  58. [58]Anton Lorenzen, Leo White, Stephen Dolan, Richard A. Eisenberg, and Sam Lindley. 2024. Oxidizing OCaml with Modal Memory Management. Proc. ACM Program. Lang. 8, ICFP, Article 253 (Aug. 2024), 30 pages. doi:10.1145/3674642DOI
  59. [59]Bruce T. Lowerre. 1976. The HARPY Speech Recognition System. Ph. D. Dissertation. Carnegie Mellon University. https://www.csd.cs.cmu.edu/academics/doctoral/degrees-conferred/ bruce-lowerre
  60. [60]Luc Maranget. 2008. Compiling pattern matching to good decision trees. In Proceedings of the 2008 ACM SIGPLAN Workshop on ML (Victoria, BC, Canada) (ML ’08). Association for Computing Machinery, New York, NY, USA, 35–46. doi:10.1145/1411304.1411311DOI
  61. [61]Simon Marlow, Alexey Rodriguez Yakushev, and Simon Peyton Jones. 2007. Faster Laziness Using Dynamic Pointer Tagging. In Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming (ICFP ’07). Association for Computing Machinery, New York, NY, USA, 277–288. doi:10.1145/1291151.1291194DOI
  62. [62]Erik Meijer, Maarten Fokking, and Ross Paterson. 1991. Functional programming with bananas, lenses, envelopes and barber wire. In Conference on functional programming languages and computer architecture. Springer, 124–144. doi:10.1007/3540543961_7DOI
  63. [63]Andrew W. Moore, Andy J. Connolly, Chris Genovese, Alex Gray, Larry Grone, Nick Kanidoris II, Robert C. Nichol, Jeff Schneider, Alex S. Szalay, Istvan Szapudi, et al. 2001. Fast algorithms and efficient statistics: N-point correlation functions. In Mining the Sky: Proceedings of the MPA/ESO/MPE Workshop Held in Garching, Germany, July 31–August 4, 2000. Springer, 71–82. doi:10.1007/10849171_5DOI
  64. [64]Leonardo de Moura and Sebastian Ullrich. 2021. The Lean 4 Theorem Prover and Programming Language. In Automated Deduction – CADE 28: 28th International Conference on Automated Deduction, Virtual Event, July 12–15, 2021. Proceedings. Springer-Verlag, Berlin, Heidelberg, 625–635. doi:10.1007/978-3-030-79876-5_37DOI
  65. [65]Chris Okasaki. 1999. Red-Black Trees in a Functional Setting. Journal of Functional Programming 9, 4 (1999), 471–477. doi:10.1017/S0956796899003494DOI
  66. [66]OpenAI. 2026. ChatGPT. https://chatgpt.com. Large language model (GPT-6.1)..
  67. [67]OpenJDK. 2025. java.util.HashMap. OpenJDK JDK 25. https://github.com/openjdk/jdk/blob/jdk-25-ga/src/java.base/share/classes/java/util/HashMap.java src/java.base/share/classes/java/util/HashMap.java.
  68. [68]Adam Paszke, Daniel J. Johnson, David Duvenaud, Dimitrios Vytiniotis, Alexey Radul, Matthew J. Johnson, Jonathan Ragan-Kelley, and Dougall Maclaurin. 2021. Getting to the Point: Index Sets and Parallelism-Preserving Autodiff for Pointful Array Programming. Proc. ACM Program. Lang. 5, ICFP, Article 88 (Aug. 2021), 29 pages. doi:10.1145/3473593
  69. [69]Mikael Pettersson. 1992. A term pattern-match compiler inspired by finite automata theory. In International Conference on Compiler Construction. Springer, 258–270. doi:10.1007/3-540-55984-1_24DOI
  70. [70]Simon L. Peyton Jones and John Launchbury. 1991. Unboxed Values as First Class Citizens in a Non-Strict Functional Language. In Functional Programming Languages and Computer Architecture (Lecture Notes in Computer Science, Vol. 523). Springer, Berlin, Heidelberg, 636–666. doi:10.1007/3540543961_30
  71. [71]Jonathan Ragan-Kelley, Connelly Barnes, Andrew Adams, Sylvain Paris, Frédo Durand, and Saman Amarasinghe. 2013. HADiLe: A Language and Compiler for Optimizing Parallelism, Locality, and Recomputation in Image Processing Pipelines. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’13). Association for Computing Machinery, New York, NY, USA, 519–530. doi:10.1145/2491950.2462176
  72. [72]Tahina Ramanandranarivo, Antoine Delignat-Lavaud, Cédric Fournet, Nikhil Swamy, Tej Chajed, Nadim Kobeissi, and Jonathan Protzenko. 2019. EverParse: Verified Secure Zero-Copy Parsers for Authenticated Message Formats. In 28th USENIX Security Symposium (USENIX Security ’19). USENIX Association, Santa Clara, CA, 1465–1482. https://www.usenix.org/conference/usenixsecurity19/presentation/delignat-lavaud
  73. [73]Alex Reinking, Ningning Xie, Leonardo de Moura, and Daan Leijen. 2021. Perceus: Garbage Free Reference Counting with Reuse. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2021). Association for Computing Machinery, New York, NY, USA, 96–111. doi:10.1145/3453483.3454032DOI
  74. [74]Alexander J Root, Christophe Gyurgyik, Purvi Goel, Kayvon Fatahalian, Jonathan Ragan-Kelley, Andrew Adams, and Fredrik Kjolstad. 2026. Bonsai: Compiling Queries to Pruned Tree Traversals. Proc. ACM Program. Lang. 10, PLDI, Article 178 (June 2026), 27 pages. doi:10.1145/3808256DOI
  75. [75]Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. 1988. Global Value Numbers and Redundant Computations. In Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’88). Association for Computing Machinery, New York, NY, USA, 12–27. doi:10.1145/73560.73562DOI
  76. [76]Kevin Scott and Norman Ramsey. 2000. When Do Match-compilation Heuristics Matter? Technical Report. USA. doi:10.18130/v3gb4mDOI
  77. [77]Ryan Sennayake, Changwan Hong, Zhiheng Wang, Amalee Wilson, Stephen Chou, Shoaib Kamil, Saman Amarasinghe, and Fredrik Kjolstad. 2020. A sparse iteration space transformation framework for sparse tensor algebra. Proc. ACM Program. Lang. 4, OOPSLA, Article 158 (Nov. 2020), 30 pages. doi:10.1145/3428226
  78. [78]Zhong Shao, John H. Reppy, and Andrew W. Appel. 1994. Unrolling lists. In Proceedings of the 1994 ACM Conference on LISP and Functional Programming (Orlando, Florida, USA) (LFP ’94). Association for Computing Machinery, New York, NY, USA, 185–195. doi:10.1145/182409.182453DOI
  79. [79]Jun Shirako and Vivek Sarkar. 2022. An Affine Scheduling Framework for Integrating Data Layout and Loop Transformations. In Languages and Compilers for Parallel Computing: 33rd International Workshop, LCPC 2020, Virtual Event, October 14–16, 2020, Revised Selected Papers. Springer-Verlag, Berlin, Heidelberg, 3–19. doi:10.1007/978-3-030-95953-1_1DOI
  80. [80]Vidush Singhal, Chaitanya Koparkar, Joseph Zullo, Artem Pelenitsyn, Michael Vollmer, Mike Rainey, Ryan Newton, and Milind Kulkarni. 2024. Optimizing Layout of Recursive Datatypes with Marmoset: Or, Algorithms + Data Layouts = Efficient Programs. In 38th European Conference on Object-Oriented Programming (ECOOP 2024) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 313), Jonathan Aldrich and Guido Salv... Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 38:1–38:28. doi:10.4230/LIPIcs.ECOOP.2024.38
  81. [81]Michel Steuwer, Toomas Remmelg, and Christophe Dubach. 2017. A functional data-parallel IR for high-performance GPU code generation. In 2017 IEEE/ACM International Symposium on Code Generation and Optimization (CGO). 74–85. doi:10.1109/CGO.2017.7863730DOI
  82. [82]Nikhil Swamy, Tahina Ramanandro, Aseem Rastogi, Irina Spiridonova, Haobin Ni, Dmitry Malloy, Juan Vazquez, Michael Tang, Omar Cardona, and Arti Gupta. 2022. Hardening attack surfaces with formally proven binary format parsers. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2022). Association for Computing Machinery, New York, NY, USA, 31–45. doi:10.1145/3519939.3523708
  83. [83]Amir Mohammad Tavakkoli, Cosmin E. Oancea, and Mary Hall. 2026. LEGO: A Layout Expression Language for Code Generation of Hierarchical Mapping. In 2026 IEEE/ACM International Symposium on Code Generation and Optimization (CGO). 228–241. doi:10.1109/CGO68049.2026.11394846DOI
  84. [84]The Linux Kernel Documentation. 2026. 5-Level Paging. The Linux Kernel Documentation, x86-64. https://docs.kernel.org/arch/x86/x86_64/5level-paging.html Accessed: 2026-10-28.
  85. [85]The Rust Project Developers. 2026. Attribute repr. The Rust Standard Library Documentation. https://doc.rust-lang.org/nightly/std/attr/attribute.repr.html Nightly documentation. Accessed: 2026-10-23.
  86. [86]The Rust Project Developers. 2026. repr(Rust). The Rustonomicon. https://doc.rust-lang.org/nomicon/repr-rust.html Accessed: 2026-10-23.
  87. [87]Linus Torvalds. 2026. Red-Black Trees in Linux. The Linux Kernel, version 7.2. https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/rbtree_types.h?h=v7.2 include/linux/rbtree_types.h.
  88. [88]Emma Tye. 2026. A Rig of Transformations. arXiv:2608.12409 [cs.PL]. doi:10.48550/arXiv.2608.12409 Extended abstract presented at the Workshop on Type-Driven Development (TyDe 2026).DOI
  89. [89]Sebastian Ullrich and Leonardo de Moura. 2019. Counting immutable beans: Reference counting optimized for purely functional programming. In Proceedings of the 31st Symposium on Implementation and Application of Functional Languages. 1–12. doi:10.1145/3412932.3412935
  90. [90]Marcell van Geest and Wouter Swierstra. 2017. Generic packet descriptions: verified parsing and pretty printing of low-level data. In Proceedings of the 2nd ACM SIGPLAN International Workshop on Type-Driven Development (Oxford, UK) (TyDe 2017). Association for Computing Machinery, New York, NY, USA, 30–40. doi:10.1145/3122975.3122979DOI
  91. [91]Anand Venkat, Mary Hall, and Michelle Strout. 2015. Loop and data transformations for sparse matrix code. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (Portland, OR, USA) (PLDI ’15). Association for Computing Machinery, New York, NY, USA, 521–532. doi:10.1145/2737924.2738003DOI
  92. [92]Michael Vollmer, Chaitanya Koparkar, Mike Rainey, Laith Sakka, Milind Kulkarni, and Ryan R. Newton. 2019. LoCal: a language for programs operating on serialized data. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (Phoenix, AZ, USA) (PLDI 2019). Association for Computing Machinery, New York, NY, USA, 48–62. doi:10.1145/3314221.3314631DOI
  93. [93]Michael Vollmer, Sarah Spall, Buddhika Chamith, Laith Sakka, Chaitanya Koparkar, Milind Kulkarni, Sam Tobin-Hochstadt, and Ryan R. Newton. 2017. Compiling Tree Transforms to Operate on Packed Representations. In 31st European Conference on Object-Oriented Programming (ECOOP 2017) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 74), Peter Müller (Ed.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 26:1–26:29. doi:10.4230/LIPIcs.ECOOP.2017.26DOI
  94. [94]Philip Wadler. 1990. Deforestation: transforming programs to eliminate trees. Theoretical Computer Science 73, 2 (1990), 231–248. doi:10.1016/0304-3975(90)90147-ADOI
  95. [95]Stephen Weeks. 2006. Whole-Program Compilation in MLton. In Proceedings of the 2006 Workshop on ML (ML ’06). Association for Computing Machinery, New York, NY, USA, 1. doi:10.1145/1159876.1159877DOI
  96. [96]Christian Wimmer and Hanspeter Mössenböck. 2008. Automatic array inlining in java virtual machines. In Proceedings of the 6th Annual IEEE/ACM International Symposium on Code Generation and Optimization (Boston, MA, USA) (CGO ’08). Association for Computing Machinery, New York, NY, USA, 14–23. doi:10.1145/1356058.1356061DOI
  97. [97]Sven Woop, Carsten Benthin, Ingo Wald, Gregory S. Johnson, and Eric Tejic. 2014. Exploiting Local Orientation Similarity for Efficient Ray Traversal of Hair and Fur. In Eurographics/ACM SIGGRAPH Symposium on High Performance Graphics. The Eurographics Association. doi:10.2312/hpg.20141092DOI
  98. [98]Rohan Yadav, Alex Aiken, and Fredrik Kjolstad. 2022. DISTAL: the distributed tensor algebra compiler. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (San Diego, CA, USA) (PLDI 2022). Association for Computing Machinery, New York, NY, USA, 286–300. doi:10.1145/3519939.3523437DOI
  99. [99]Rohan Yadav, Alex Aiken, and Fredrik Kjolstad. 2022. SpDISTAL: compiling distributed sparse tensor computations. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis (Dallas, Texas) (SC ’22). IEEE Press, Article 59, 15 pages. doi:10.1109/SC41404.2022.00064DOI
  100. [100]Qianchuan Ye and Benjamin Delaware. 2019. A verified protocol buffer compiler. In Proceedings of the 8th ACM SIGPLAN International Conference on Certified Programs and Proofs (Cascais, Portugal) (CPP 2019). Association for Computing Machinery, New York, NY, USA, 222–233. doi:10.1145/3293880.3294105DOI
  101. [101]Henri Vlitis, Tero Karras, and Samuli Laine. 2017. Efficient incoherent ray traversal on GPUs through compressed wide BVHs. In Proceedings of High Performance Graphics, 1–13. doi:10.1145/3105762.3105773
  102. [102]Keren Zhou, Mario Lezcano-Casado, Adam P. Goucher, Akhmed Rakhmati, Jeff Niu, Justin Lebar, Pawel Szczerbuk, Peter Bell, Phil Tillett, Thomas Raoux, and Zahi Moulallal. 2025. Linear Layouts: Robust Code Generation of Efficient Tensor Computation Using F_2. In Proceedings of the 31st ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1 (Pittsburgh, PA, USA) (ASPLOS ’26). Association for Computing Machinery, New York, NY, USA, 132–146. doi:10.1145/3760250.3762221DOI

Paper details

vlnc:W_vuxyxmfq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents