Substructural Parametricity

C. B. Aberlé, Chris Martens, Frank Pfenning · 2025

Read Substructural Parametricity by C. B. Aberlé, Chris Martens, Frank Pfenning (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-03153.txt.

Introduction

Some type systems ration how programs use data: each value once, or in a fixed order. Aberle, Chris Martens, and Frank Pfenning ask what such rationing guarantees in this 2025 paper. They use the lens of parametricity, the idea that a program must behave uniformly across types. They build a family of logical relations, each tuned by an algebraic dial.

Set the dial to a plain monoid and the relations speak for ordered types; make it commutative and they speak for linear ones. From the main theorem, exact censuses fall out. The ordered type of list append admits exactly one function, as does reversal. The linear identity on lists admits only shuffles of its input. The capstone shows the ordered fold type is inhabited by the fold function alone. Guarantees like these are gold for language designers.

Catalog record

CREATORC. B. Aberlé, Chris Martens, Frank Pfenning
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-03153

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Substructural Parametricity C. B. Aberlé, Chris Martens, Frank Pfenning Abstract Ordered, linear, and other substructural type systems allow us to expose deep properties of programs at the syntactic level of types. In this paper, we develop a family of unary logical relations that allow us to prove consequences of parametricity for a range of substructural type systems. A key idea is to parameterize the relation by an algebra, which we exemplify with a monoid and commutative monoid to interpret ordered and linear type systems, respectively. We prove the fundamental theorem of logical relations and apply it to deduce extensional properties of inhabitants of certain types. Examples include demonstrating that the ordered types for list append and reversal are inhabited by exactly one function, as are types of some tree traversals. Similarly, the linear type of the identity function on lists is inhabited only by permutations of the input. Our most advanced example shows that the ordered type of the list fold function is inhabited only by the fold function. Carnegie Mellon [email protected] Northeastern [email protected] Carnegie Mellon [email protected] We would like to thank Karl Crary for an early instantiation of the underlying idea. ccs Theory of computation Type structures keywords Substructural type systems, logical relations, ordered logic † † runningauthor: C. B. Aberlé and Chris Martens and Frank Pfenning † † copyright: C. B. Aberlé, Chris Martens, and Frank Pfenning 1 Introduction Substructural type systems and parametric polymorphism are two mechanisms for capturing precise behavioral properties of programs at the type level, enabling powerful static reasoning. The goal of this paper is to give a theoretical account of these mechanisms in combination. Substructural type systems have been investigated since the advent of linear logic, starting with the seminal paper by Girard and Lafont [ 11 ] . Among other applications, with substructural type systems one can avoid garbage collection, update memory in place [ 20 , 21 ] , make message-passing [ 9 , 7 ] or shared memory concurrency [ 10 , 28 ] safe, model quantum computation [ 8 ] , or reason efficiently about imperative programs [ 19 ] . Substructural type systems have thus been incorporated into languages that seek to offer such guarantees, such as Rust, Koka, Haskell, Oxidized OCaml, and ProtoQuipper. Parametricity, originally introduced for System F [ 35 ] , enables the idea that programs whose types involve universal quantification over type parameters have certain strong semantic properties. This idea supports powerful program reasoning principles such as representation independence across abstraction boundaries [ 23 ] and “theorems for free” that can be derived about all inhabitants of certain types, for example that every inhabitant of \forall{\alpha}.\;\alpha\to\alpha is equivalent to the identity function [ 38 ] . The theory of substructural logics and type systems is now relatively well understood, including several ways to integrate substructural and structural type systems [ 6 , 31 , 12 ] . It is therefore somewhat surprising that we do not yet know much about how parametricity and its applications interact with them. The main foray into substructural parametricity is a paper by Zhao et al. [ 39 ] that accounts for a polymorphic dual-intuitionistic linear logic. They point out that logical relations on closed terms are problematic because substitution obscures linearity. Their solution was to construct a logical relation on open terms, necessitating the introduction of “semantic typing” judgments that mirror the syntactic type system, which complicates their definition and application. In this paper, we follow an approach using constructive resource semantics in the style of Reed et al. [ 32 , 34 , 33 ] to construct logical relations on closed terms . We start with an ordered type system [ 30 , 29 , 17 ] , which may be considered the least permissive among substructural type systems and therefore admits a pleasantly minimal definition. However, the construction is generic with respect to certain properties of the resource algebra, which allows us to extend it also to linear and unrestricted types. Consequences of our development include that certain polymorphic types are only inhabited by the polymorphic append and reverse functions on lists. Similarly, certain types are only inhabited by functions that swap or maintain the order of pairs. The most advanced application shows that the ordered type of fold over lists is inhabited only by the fold function. We conjecture that the three substructural modes we investigate—ordered, linear, and unrestricted—can also be combined in an adjoint framework [ 6 , 12 ] but leave this to future work. Similarly, we simplify our presentation by defining only a unary logical relation since it is sufficient to demonstrate proof-of-concept, but nothing stands in the way of a more general definition (for example, to support representation independence results). 2 A Minimalist Fragment We start with a small fragment of the Full Lambek Calculus [ 18 , 22 ] , extended with parametric polymorphism [ 36 ] . This fragment is sufficient to illustrate the main ideas behind our constructions. For the sake of simplicity we choose a Curry-style formulation of typing, concentrating on properties of untyped terms rather than intrinsically typed terms. This allows the same terms to inhabit ordered, linear, and unrestricted types and thereby focus on semantic rather than syntactic issues. \begin{array}[]{llcll}\mbox{Types}&A,B&::=&\alpha\mid A\bullet B\mid A\rightarrowtail B\mid A\twoheadrightarrow B\mid\forall\alpha.\,A\\ \mbox{Expressions}&e&::=&x\\ &&\mid&(e_{1},e_{2})\mid\mathbf{match}\;e\;((x,y)\Rightarrow e^{\prime})&(A\bullet B)\\ &&\mid&\lambda x.\ e\mid e_{1}\,e_{2}&(A\rightarrowtail B,A\twoheadrightarrow B)\end{array} In this fragment, we have A\bullet B (read “ A fuse B ”) which, logically, is a noncommutative conjunction. We have two forms of implication: A\rightarrowtail B (read: “ A under B ”, originally written as A\mathbin{\backslash}B ) which is true if from the hypothesis A placed at the left end of the antecedents we can deduce B , and A\twoheadrightarrow B (read: “ B over A ”, originally written as B\mathbin{/}A ) which is true if from the hypothesis A placed at the right and of the antecedents we can prove B . Lambek’s original notation was suitable for the sequent calculus and its applications in linguistics, but is less readable for natural deduction and functional programming. Our basic typing judgment has the form \Delta\mid\Omega\vdash e:A where \Delta consists of hypotheses \alpha\;\mathsf{type} , and \Omega is an ordered context (x_{1}:A_{1})\ldots(x_{n}:A_{n}) . We make the standard presuppositions that \Delta\vdash A\;\mathsf{type} and \Delta\vdash A_{i}\;\mathsf{type} for every x_{i}:A_{i} in \Omega , and that both type variables and term variables are pairwise distinct. The rules are show in Figure 1 . \begin{array}[]{c}\Delta\mid x:A\vdash x:A\\[10.00002pt] \Delta\mid\Omega\vdash\lambda x.\,e:A\twoheadrightarrow B\Delta\mid\Omega\,(x:A)\vdash e:B\hskip 30.00005pt\Delta\mid\Omega\,\Omega_{A}\vdash e_{1}\,e_{2}:B\lx@proof@logical@and\Delta\mid\Omega\vdash e_{1}:A\twoheadrightarrow B\Delta\mid\Omega_{A}\vdash e_{2}:A\\[10.00002pt] \Delta\mid\Omega\vdash\lambda x.\,e:A\rightarrowtail B\Delta\mid(x:A)\,\Omega\vdash e:B\hskip 20.00003pt\Delta\mid\Omega_{A}\,\Omega\vdash e_{1}\,e_{2}:B\lx@proof@logical@and\Delta\mid\Omega\vdash e_{1}:A\rightarrowtail B\Delta\mid\Omega_{A}\vdash e_{2}:A\\[10.00002pt] \Delta\mid\Omega_{A}\,\Omega_{B}\vdash(e_{1},e_{2}):A\bullet B\lx@proof@logical@and\Delta\mid\Omega_{A}\vdash e_{1}:A\Delta\mid\Omega_{B}\vdash e_{2}:B\hskip 10.00002pt\Delta\mid\Omega_{L}\,\Omega\,\Omega_{R}\vdash\mathbf{match}\;e\;((x,y)\Rightarrow e^{\prime}):C\lx@proof@logical@and\Delta\mid\Omega\vdash e:A\bullet B\Delta\mid\Omega_{L}\,(x:A)\,(y:B)\,\Omega_{R}\vdash e^{\prime}:C\\[10.00002pt] \Delta\mid\Omega\vdash e:\forall\alpha.\,A\Delta,\alpha\,\mathsf{type}\mid\Omega\vdash e:A\hskip 30.00005pt\Delta\mid\Omega\vdash e:A(B)\lx@proof@logical@and\Delta\mid\Omega\vdash e:\forall\alpha.A(\alpha)\Delta\vdash B\;\mathsf{type}\end{array} Figure 1: Ordered Natural Deduction Here are a few example judgments that hold or fail. We elide the context \Delta= (\alpha\,\mathsf{type},\beta\,\mathsf{type},\gamma\,\mathsf{type}) . \begin{array}[]{lcll}&\vdash&\lambda x.\,x:\alpha\rightarrowtail\alpha\\ &\vdash&\lambda x.\,x:\alpha\twoheadrightarrow\alpha\\ &\not\vdash&\lambda x.\,\lambda y.\,x:\alpha\twoheadrightarrow(\beta\twoheadrightarrow\alpha)&(\mbox{no weakening})\\ &\not\vdash&\lambda x.\,(x,x):\alpha\twoheadrightarrow(\alpha\bullet\alpha)&(\mbox{no contraction})\\ &\vdash&\lambda x.\,\lambda y.\,(x,y):\alpha\twoheadrightarrow(\beta\twoheadrightarrow(\alpha\bullet\beta))\\ &\not\vdash&\lambda x.\,\lambda y.\,(x,y):\alpha\rightarrowtail(\beta\rightarrowtail(\alpha\bullet\beta))&(\mbox{no exchange})\\[4.30554pt] f:\beta\twoheadrightarrow(\alpha\rightarrowtail\gamma)&\vdash&\lambda x.\,\lambda y.\,(f\,y)\,x:\alpha\rightarrowtail(\beta\twoheadrightarrow\gamma)&(\mbox{``associativity''})\\ g:\alpha\rightarrowtail(\beta\twoheadrightarrow\gamma)&\vdash&\lambda y.\,\lambda x.\,(g\,x)\,y:\beta\twoheadrightarrow(\alpha\rightarrowtail\gamma)\\[4.30554pt] g:(\alpha\bullet\beta)\twoheadrightarrow\gamma&\vdash&\lambda x.\,\lambda y.\,g\,(x,y):\alpha\twoheadrightarrow(\beta\twoheadrightarrow\gamma)&(\mbox{currying})\\ f:\alpha\twoheadrightarrow(\beta\twoheadrightarrow\gamma)&\vdash&\lambda p.\,\mathbf{match}\;p\;((x,y)\Rightarrow f\,x\,y):(\alpha\bullet\beta)\twoheadrightarrow\gamma&(\mbox{uncurrying})\end{array} The strictures of the typing judgment imply that certain types may be uninhabited, or may be inhabited by terms that are extensionally equivalent to a small number of possibilities. To count the number of linear functions, translate (A\twoheadrightarrow B)^{\mathchoice{\mathsf{L}}{\mathsf{L}}{\scriptscriptstyle\mathsf{L}}{\scriptscriptstyle\mathsf{L}}}=(A\rightarrowtail B)^{\mathchoice{\mathsf{L}}{\mathsf{L}}{\scriptscriptstyle\mathsf{L}}{\scriptscriptstyle\mathsf{L}}}=A^{\mathchoice{\mathsf{L}}{\mathsf{L}}{\scriptscriptstyle\mathsf{L}}{\scriptscriptstyle\mathsf{L}}}\multimap B^{\mathchoice{\mathsf{L}}{\mathsf{L}}{\scriptscriptstyle\mathsf{L}}{\scriptscriptstyle\mathsf{L}}} and

Read the complete text