CS Paper Radar

A Rig of Transformations

Emma Tye

cs.PL ·submitted 2026-08-11 16:17 UTC · v2

Abstract

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

Closest papers

Nearest neighbours by meaning across the whole index.

Composable Rewrites for Layouts of Algebraic Data Types

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

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

0.44

An Algebraic Framework for Data Systems: Classification and Optimization of Algebraic Structures for Data Organization and Coding

cs.IT math.RA ·2026-08-31 ·Kendy Inoa
similarity 0.63
Abstract · 26 pages, 7 tables, 22 references. Presented as a poster at ICM 2026, Philadelphia, PA, USA. Revised: assumptions clarified, theorems correc…

Modern data systems are commonly studied through computational and information-theoretic methods, while their algebraic properties remain largely unexplored. This paper introduces a mathematical framework for modelling data systems using algebraic codes over finite groups, organized by an \emph{axiom signature}: each algebraic axiom of the data domain is shown to be \emph{sufficient} for a specific coding-theoretic capability, and each implication is given its precise reading (MDS parameters do not require a field; quotients require normality, not commutativity). Three types of results are presented. Proved: a Gilbert-Varshamov existence bound over arbitrary finite groups, commutative or not; explicit direct-sum codes over the elementary divisors of any finite abelian group; that transactions preserving a validity predicate form a submonoid of the full transformation monoid, which is not a group; that schema-preserving transformations form a finite group whose orbits are counted by Burnside's lemma; and that the constraint-preserving bijections of a data system form a finite group whose orbits partition the valid configurations. Demonstrated: an explicit code construction over $\mathbb{F}_5$, with known codes over $\mathbb{Z}_4$ and $(2^U,\triangle)$ cited to situate the framework. Proposed: an encoding efficiency measure Ef and an optimization functional $Φ$ with tunable weights, both evaluated at declared coding instances. Weight-independent comparison holds under componentwise dominance; in general the weight simplex decomposes into polyhedral chambers on which the induced order is constant.

0.20

Cambria: Resource Abstraction for Parametrized Algebraic Effects and Handlers

cs.PL ·2026-08-28 ·Jack Liell-Cock, Sam Staton
theory similarity 0.62
Abstract

The algebraic effects and handlers paradigm separates the concerns of the interface and implementation of computational effects in programming languages. We present Cambria, a language that extends this framework to the parametrized setting. Effect signatures may use abstract parameter types that are instantiated by the handler along with the operation implementations. Parameters abstract over resources, such as memory locations or thread IDs, permitting algebraic effects to encode dynamic allocation. They are first-class in the type system but erased at runtime, requiring no coercions or type-directed reduction. We prove parametricity via a step-indexed logical relation, formalizing the abstraction guarantee provided by parametrized handlers. We also establish type safety and classify the annotations needed for completeness of the type inference algorithm. We demonstrate Cambria's practicality with a working implementation and provide examples including local state, Pólya's urn, and concurrent thread management. The last is a parametrized effect whose abstract thread IDs are shared between concurrent computations, going beyond standard instances. Cambria is the first calculus with user-defined resource-allocating effects that guarantees, via parametricity, that client code cannot depend on how a handler represents its resources.

0.10

Quantisation of Abstract Data Types

cs.PL quant-phcs.SE ·2026-09-03 ·Mingsheng Ying, Zhicheng Zhang, Kean Chen
similarity 0.61
Abstract · 37 pages

In this paper, we introduce a notion of abstract quantum data type within the framework of universal algebra. This notion provides an algebraic foundation for describing data abstraction in quantum programming. We formally define a quantisation of classical data types and show that their equational specifications can be soundly lifted to the quantum setting. Two standard quantisation methods for classical functions, namely the bit oracle and the phase oracle, arise as special cases of this general construction. We illustrate the framework with applications to quantum arrays and quantum error-correcting codes, showing how they can be understood through the lens of data-type quantisation. We further establish conditions under which quantisation preserves structural relationships and constructions of classical data types, including embeddings, isomorphisms, and products.

0.38

Mode Inference for Substructural Adjoint Types

cs.PL ·2026-11-18 ·Sophia Roshal, Frank Pfenning
similarity 0.59
Abstract

Adjoint types [Jang et al. 2024] provide a method of mixing substructural modes (for example, linear, affine, strict, or unrestricted) in a type system while preserving the proof-theoretic and computational properties of each mode. Uses of such a system include performing compiler optimizations or providing safety guarantees on parts of a program whose modes support them, while not restricting the programmer's ability to write other code as they usually do. However, Jang et al.'s algorithmic type system is monomorphic in the modes, requiring the programmer to anticipate a potentially large number of combinations of modes, and possibly copy code to conform to each of them. In this paper we define a mode inference algorithm for programs with adjoint types that produces principal modes, summarizing all possible substructural modes of a function in a simple constraint language. This removes the burden from the programmer to a priori analyze the substructural properties of their code, and, furthermore, allows a single function definition to subsume all its instances at different modes. We show that our system is sound and complete with respect to a mild restriction of Jang et al.'s monomorphic version.

0.33

Unifying Function- and Argument-First Bidirectional Type Systems

cs.PL ·2026-09-02 ·Takuma Yoshioka, Taro Sekiyama, Atsushi Igarashi
publishedtheory similarity 0.59
Abstract · Accepted as a short version at APLAS 2026 (Springer LNCS). This extended version includes substantial new material and results

Bidirectional typing mixes type synthesis and type checking into a single process. Existing bidirectional type systems can be classified into two styles based on whether, given a function application, a bidirectional typing algorithm synthesizes the function's type first and typechecks the argument against the synthesized argument type, or it synthesizes the arguments' types first and typechecks the function against the synthesized arguments' types. We call the former _function-first_ and the latter _argument-first_. Not only do the two styles significantly differ in how the type systems and typing algorithms are formalized, but also they lead to incompatible typeabilities, forcing a language designer to select one style and to give up the other's typeabilities. In this paper, we unify the two styles and develop \lang with a new bidirectional type system for higher-rank polymorphism. Key ideas of the unification are twofold. Each function application is annotated with a bit of information to represent whether function- or argument-first typing is used, to allow a language designer (or even a programmer) to switch between the two styles at their discretion. We reformulate the function- and argument-first type systems by using ideas from colored types and boxy types, which can specify which part of a type should be synthesized or used for checking in a flexible manner. We also develop a typing algorithm based on the worklist approach by Zhao et al. The (declarative) type system of $λ^{BH}$ is shown to be sound and to subsume two representative function- and argument-first systems. Our typing algorithm is shown to be sound with respect to the type system of $λ^{BH}$ and complete with respect to representative function- and argument-first systems. We mechanically prove the metatheorems using the Abella theorem prover.

0.29

Datatypes In, Zippers Out!

cs.PL ·2026-11-17 ·Smayan Agarwal, Aalok Thakkar
theory similarity 0.59
Abstract

A zipper represents a focused position in an algebraic data structure together with the context needed to reconstruct the whole. Datatype derivatives determine one-hole context types, but do not by themselves choose a zipper's concrete representation or specify navigation costs and demands. We present Kamot, a tool that converts regular algebraic datatype declarations in a restricted Haskell fragment into zipper implementations with operational contracts. Navigation, replacement, and reconstruction are proved correct against a reference traversal. Kamot supports mutual recursion and regular containers inside containers. A compositional analysis derives sound bounds on transitions and constructor demands for certified traversal directions. These bounds are affine in trail depth (the number of saved frames) and guarantee termination of each move on productive, potentially infinite inputs. For inhabited families the analysis is complete: when no move certificate is emitted, no bound depending only on trail depth exists, and some productive input makes a move diverge. We prove that the generated code preserves results and the reference order of constructor matches, including finite prefixes of divergent searches. Lean 4 verifies simulation, bounds, and completeness for finite values of single self-recursive datatypes, in both directions. On 19 datatype models and 81 generated families, every generated module passes Haskell type checking, and independent checkers validate certificates, traces, and bounds. In a prefetching workload, starting only searches whose bounds fit a budget answers every local query and avoids discarded source evaluations on long returns, but conservative bounds can lose answers that fuelled search delivers.

0.39

Scenes: A Meta-Logical Algebra for Mutable State

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

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

0.34