A Word Sampler for Well-Typed Functions
Breandan Considine · 2025
Read A Word Sampler for Well-Typed Functions by Breandan Considine (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-2512-01036.txt.
Introduction
Breandan Considine describes an exact sampler for small programs in a 2025 paper. The setting is a simply-typed, first-order functional programming language, where every function has a declared type. Sampling a random well-typed function sounds simple, but most random programs fail the type check.
Given a finite automaton that describes allowed shapes, the sampler draws a function uniformly, without replacement, from all well-typed functions the automaton accepts. Uniform sampling matters for testing compilers and program analyzers, since biased samples hide bugs. An exact sampler gives fair coverage of the program space, letting tools be tested against rare cases too.
Catalog record
| CREATOR | Breandan Considine |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 17 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-01036
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Word Sampler for Well-Typed Functions Breandan Considine Abstract . We describe an exact sampler for a simply-typed, first-order functional programming language. Given an acyclic finite automaton, α ∅ \alpha_{\varnothing} , it samples a random function uniformly without replacement from well-typed functions in ℒ ( α ∅ ) \mathcal{L}(\alpha_{\varnothing}) . This is achieved via a fixed-parameter tractable reduction from a syntax-directed type system to a context-free grammar, preserving type soundness and completeness w.r.t. ℒ ( α ∅ ) \mathcal{L}(\alpha_{\varnothing}) , while retaining the robust metatheory of formal languages. 1. Introduction Consider a simply-typed language with the following terms: \hskip-2.84544pt\begin{array}[]{ccl}\texttt{FUN}&::=&\texttt{\lx@texthl@color{fun}}\;\;\texttt{\lx@texthl@color{f0}}\;\;\texttt{\lx@texthl@color{(}}\;\;\texttt{PRM}\;\;\texttt{\lx@texthl@color{)}}\;\;\texttt{\lx@texthl@color{:}}\;\;\mathbb{T}\;\;\texttt{\lx@texthl@color{=}}\;\;\texttt{EXP}\\ \texttt{PRM}&::=&\texttt{PID}\;\;\texttt{\lx@texthl@color{:}}\;\;\mathbb{T}\;\mid\;\texttt{PRM}\;\;\texttt{\lx@texthl@color{,}}\;\;\texttt{PID}\;\;\texttt{\lx@texthl@color{:}}\;\;\mathbb{T}\\ \texttt{EXP}&::=&\ulcorner\mathbb{N}\lrcorner\;\mid\;\ulcorner\mathbb{B}\lrcorner\;\mid\;\texttt{PID}\;\mid\;\texttt{INV}\;\mid\;\texttt{IFE}\;\mid\;\texttt{OPX}\\ \texttt{OPX}&::=&\texttt{\lx@texthl@color{(}}\;\;\texttt{EXP}\;\;\texttt{OPR}\;\;\texttt{EXP}\;\;\texttt{\lx@texthl@color{)}}\\ \texttt{IFE}&::=&\texttt{\lx@texthl@color{if}}\;\;\texttt{EXP}\;\;\texttt{\lx@texthl@color{\lx@text@lbrace}}\;\;\texttt{EXP}\;\;\texttt{\lx@texthl@color{\lx@text@rbrace}}\;\;\texttt{\lx@texthl@color{else}}\;\;\texttt{\lx@texthl@color{\lx@text@lbrace}}\;\;\texttt{EXP}\;\;\texttt{\lx@texthl@color{\lx@text@rbrace}}\\ \texttt{INV}&::=&\texttt{FID}\;\;\texttt{\lx@texthl@color{(}}\;\;\texttt{ARG}\;\;\texttt{\lx@texthl@color{)}}\\ \texttt{ARG}&::=&\texttt{EXP}\;\mid\;\texttt{ARG}\;\;\texttt{\lx@texthl@color{,}}\;\;\texttt{EXP}\\ \texttt{OPR}&::=&\texttt{\lx@texthl@color{+}}\;\mid\;\texttt{\lx@texthl@color{*}}\;\mid\;\texttt{\lx@texthl@color{<}}\;\mid\;\texttt{\lx@texthl@color{==}}\\ \texttt{PID}&::=&\texttt{\lx@texthl@color{p1}}\;\mid\;\ldots\;\mid\;\texttt{\lx@texthl@color{pk}}\\ \texttt{FID}&::=&\texttt{\lx@texthl@color{f0}}\;\mid\;\texttt{\lx@texthl@color{f1}}\;\mid\;\ldots\;\mid\;\texttt{\lx@texthl@color{fn}}\\ \ulcorner\mathbb{B}\lrcorner&::=&\texttt{\lx@texthl@color{true}}\;\mid\;\texttt{\lx@texthl@color{false}}\\ \ulcorner\mathbb{N}\lrcorner&::=&\texttt{\lx@texthl@color{1}}\;\mid\;\texttt{\lx@texthl@color{2}}\;\mid\;\texttt{\lx@texthl@color{3}}\;\mid\;\ldots\end{array} At the type level, we will assume an ambient global context, \Gamma , consisting of invokable named functions, and a finite type universe with two primitive types, \mathbb{B} and \mathbb{N} . \begin{array}[]{rcl}\Gamma&::=&\varnothing\texttt{ }\mid\texttt{ }\Gamma,\texttt{\lx@texthl@color{f\_}}:(\tau_{1},\ldots,\tau_{k})\rightarrow\tau\\ \mathbb{T}&::=&\hskip 1.1097pt\mathbb{B}\texttt{ }\mid\texttt{ }\mathbb{N}\texttt{ }\mid\texttt{ }\tau^{(3)}\texttt{ }\mid\texttt{ }\ldots\texttt{ }\mid\texttt{ }\tau^{(d)}\end{array} Let us define a fragment of the typing judgements for IFE , INV , and OPX , which are mostly conventional. \Gamma\vdash e_{c}:\mathbb{B} \Gamma\vdash e_{\top}:\tau \Gamma\vdash e_{\bot}:\tau IFE \Gamma\vdash\texttt{\lx@texthl@color{if}}\;\;e_{c}\;\;\texttt{\lx@texthl@color{\lx@text@lbrace}}\;\;e_{\top}\;\;\texttt{\lx@texthl@color{\lx@text@rbrace}}\;\;\texttt{\lx@texthl@color{else}}\;\;\texttt{\lx@texthl@color{\lx@text@lbrace}}\;\;e_{\bot}\;\;\texttt{\lx@texthl@color{\lx@text@rbrace}}:\tau \Gamma\vdash\texttt{\lx@texthl@color{f\_}}:(\tau_{1},\ldots,\tau_{m})\rightarrow\tau \Gamma\vdash e_{i}:\tau_{i}\>\>\forall i\in[1,m] INV \Gamma\vdash\texttt{\lx@texthl@color{f\_}}\;\;\texttt{\lx@texthl@color{(}}\;\;e_{1}\;\;\texttt{\lx@texthl@color{,}}\;\;\ldots\;\;\texttt{\lx@texthl@color{,}}\;\;e_{m}\;\;\texttt{\lx@texthl@color{)}}:\tau \delta_{\texttt{OPR}}(\odot,\tau,\tau^{\prime})=\hat{\tau} \Gamma\vdash e_{1}:\tau \Gamma\vdash e_{2}:\tau^{\prime} OPX \Gamma\vdash\texttt{\lx@texthl@color{(}}\;\;e_{1}\odot e_{2}\;\;\texttt{\lx@texthl@color{)}}:\hat{\tau} where \delta_{\texttt{OPR}}:\Sigma_{\texttt{OPR}}\times\mathbb{T}\times\mathbb{T}\rightharpoonup\mathbb{T} is defined as follows: \delta_{\texttt{OPR}}(\odot,\tau,\tau^{\prime})=\begin{cases}\mathbb{B}&\text{ if }\odot\in\{\texttt{\lx@texthl@color{<}}\},\tau,\tau^{\prime}:\mathbb{N}\\ \mathbb{N}&\text{ if }\odot\in\{\texttt{\lx@texthl@color{+}},\texttt{\lx@texthl@color{*}}\},\tau,\tau^{\prime}:\mathbb{N}\\ \mathbb{B}&\text{ if }\odot\in\{\texttt{\lx@texthl@color{==}}\},\tau=\tau^{\prime}\>\>\forall\tau,\tau^{\prime}:\mathbb{T}\end{cases} We will encode the type checker as a context-free grammar. 2. Notation Recall that a context-free grammar (CFG) is a quadruple, \langle\Sigma,V,P,S\rangle , consisting of terminals (\Sigma) , nonterminals (V) , productions \big(P\subset V\times(V\cup\Sigma)^{*}\big), and a start symbol (S) . Also, a finite automaton (FA) is a quintuple \langle Q,\Sigma,\delta,q_{\alpha},F\rangle , with states (Q) , an alphabet (\Sigma) , transitions (\delta\subseteq Q\times\Sigma\times Q) , an initial state (q_{\alpha}) , and accepting states (F\subseteq Q) . These devices generate words in languages, denoted \mathcal{L}(\cdot)\subseteq\Sigma^{*} , that are context-free and regular, respectively. A few notational rules for CFG compilation will be helpful: . \Sigma \texttt{\lx@texthl@color{.}}\in\Sigma (\sigma_{0}\rightarrow\sigma_{1..n})\in P P_{V} \bigcup_{i=0}^{n}\{\sigma_{i}\}\setminus\Sigma\in V (\sigma_{0}\rightarrow\sigma_{1..n})\in P P_{\Sigma} \bigcup_{i=1}^{n}\{\sigma_{i}\}\setminus V\in\Sigma The notation \mathop{\largecomma}\limits(\cdot) is a macro for a comma-separated list. 1 1 1 i.e., \mathop{\largecomma}\limits_{i=1}^{m}(x_{i})\;:=\;x_{1}\;\;\texttt{\lx@texthl@color{,}}\;\;\ldots\;\;x_{m}\text{ if }m>1\text{ else }x_{1}\text{ if }m=1\text{ else }\varepsilon . 3. Method We want to permit functions of up to arity- k , so the start symbol, S_{\Gamma} , will need to express each of these possibilities: \langle\vec{\tau},\dot{\tau}\rangle\in\mathbb{T}^{0..k}\times\mathbb{T} \vec{\tau}_{0..|\vec{\tau}|}\in\vec{\tau} \texttt{FUN}_{\varphi} \Big(S_{\Gamma}\rightarrow\texttt{\lx@texthl@color{fun}}\;\;\texttt{\lx@texthl@color{f0}}\;\;\texttt{\lx@texthl@color{(}}\mathop{\largecomma}\limits_{i=1}^{|\vec{\tau}|}\big(p_{i}\;\;\texttt{\lx@texthl@color{:}}\;\;\vec{\tau}_{i}\big)\>\texttt{\lx@texthl@color{)}}\;\;\texttt{\lx@texthl@color{:}}\;\;\dot{\tau}\;\;\texttt{\lx@texthl@color{=}}\;\;\texttt{EXP}[\dot{\tau},\vec{\tau}\rightarrow\dot{\tau}]\Big)\in P_{\Gamma} We will decorate EXP nonterminals with a pair, EXP [\cdot,\cdot] , of (1) the expression’s local return type (\tau) , and (2) available parameters (\vec{\tau}) and expected return type (\dot{\tau}) for \texttt{\lx@texthl@color{f0}}:\vec{\tau}\rightarrow\dot{\tau} : \texttt{EXP}[\tau,\vec{\tau}\rightarrow\dot{\tau}]\in V_{\Gamma} \Gamma\vdash\texttt{\lx@texthl@color{f\_}}:(\tau_{1},\ldots,\tau_{m})\rightarrow\tau \texttt{INV}_{\varphi} \big(\texttt{EXP}[\tau,\vec{\tau}\rightarrow\dot{\tau}]\;\rightarrow\;\texttt{\lx@texthl@color{f\_}}\;\;\texttt{\lx@texthl@color{(}}\mathop{\largecomma}\limits_{i=1}^{m}\texttt{EXP}[\tau_{i},\vec{\tau}\rightarrow\dot{\tau}]\>\texttt{\lx@texthl@color{)}}\big)\in P_{\Gamma} \texttt{EXP}[\tau,\vec{\tau}\rightarrow\dot{\tau}]\in V_{\Gamma} \tau=\dot{\tau} \vec{\tau}_{0..|\vec{\tau}|}\in\vec{\tau} \texttt{REC}_{\varphi} \big(\texttt{EXP}[\tau,\vec{\tau}\rightarrow\dot{\tau}]\;\rightarrow\;\texttt{\lx@texthl@color{f0}}\;\;\texttt{\lx@texthl@color{(}}\mathop{\largecomma}\limits_{i=1}^{|\vec{\tau}|}\texttt{EXP}[\vec{\tau}_{i},\vec{\tau}\rightarrow\dot{\tau}]\>\texttt{\lx@texthl@color{)}}\big)\in P_{\Gamma} \texttt{EXP}[\tau,\vec{\tau}\rightarrow\dot{\tau}]\in V_{\Gamma} \tau=\tau^{\prime} \tau,\tau^{\prime}\in\mathbb{T} \texttt{IFE}_{\varphi} \left(\begin{array}[]{l}\texttt{EXP}[\tau,\vec{\tau}\rightarrow\dot{\tau}]\;\rightarrow\;\texttt{\lx@texthl@color{if}}\;\;\texttt{EXP}[\mathbb{B},\vec{\tau}\rightarrow\dot{\tau}]\;\;\texttt{\lx@texthl@color{\lx@text@lbrace}}\;\;\texttt{EXP}[\tau,\vec{\tau}\rightarrow\dot{\tau}]\;\;\texttt{\lx@texthl@color{\lx@text@rbrace}}\\[4.26773pt] \phantom{\texttt{EXP}[\tau,\vec{\tau}\rightarrow\dot{\tau}]\;\rightarrow\;}\;\texttt{\lx@texthl@color{else}}\;\;\texttt{\lx@texthl@color{\lx@text@lbrace}}\;\;\texttt{EXP}[\tau^{\prime},\vec{\tau}\rightarrow\dot{\tau}]\;\;\texttt{\lx@texthl@color{\lx@text@rbrace}}\end{array}\right)\in P_{\Gamma} \texttt{EXP}[\hat{\tau},\vec{\tau}\rightarrow\dot{\tau}]\in V_{\Gamma} \delta_{\texttt{OPR}}(\odot,\tau,\tau^{\prime})=\hat{\tau} \odot\in\{\texttt{\lx@texthl@color{==}},\texttt{\lx@texthl@color{<}},\texttt{\lx@texthl@color{+}},\texttt{\lx@texthl@color{*}}\} \texttt{OPX}_{\varphi} \big(\texttt{EXP}[\hat{\tau},\vec{\tau}\rightarrow\dot{\tau}]\;\rightarrow\;\texttt{\lx@texthl@color{(}}\;\;\texttt{EXP}[\tau,\vec{\tau}\rightarrow\dot{\tau}]\;\odot\;\texttt{EXP}[\tau^{\prime},\vec{\tau}\rightarrow\dot{\tau}]\;\;\texttt{\lx@texthl@color{)}}\big)\in P_{\Gamma} \texttt{EXP}[\tau,\vec{\tau}\rightarrow\dot{\tau}]\in V_{\Gamma}\;\;\;\;\exists\vec{\tau}_{i}=\tau \texttt{PID}_{\varphi} \big(\texttt{EXP}[\tau,\vec{\tau}\rightarrow\dot{\tau}]\rightarrow\texttt{\lx@texthl@color{pi}}\big)\in P_{\Gamma} \texttt{EXP}[\tau,\vec{\tau}\rightarrow\dot{\tau}]\in V_{\Gamma}\>\>\>\tau\in\{\mathbb{B},\mathbb{N}\}\>\>\>\texttt{\lx@texthl@color{\_}}:\tau \texttt{LIT}_{\varphi} (\texttt{EXP}[\tau,\vec{\tau}\rightarrow\dot{\tau}]\rightarrow\texttt{\lx@texthl@color{\_}})\in P_{\Gamma} The resulting grammar, G_{\Gamma}:=\langle\Sigma,V_{\Gamma},P_{\Gamma},S_{\Gamma}\rangle , will be put into Chomsky Normal Form (CNF), G_{\Gamma}^{\prime} , pruning productions containing unreachable or unproductive nonterminals and refactoring each production to either (w\rightarrow xz):V\times V^{2} or (w\rightarrow t):V\times\Sigma . During normalization, arbitrary CFGs may undergo a quadratic blowup in space ( 6 ) , however, as this grammar does not use \varepsilon or contain unary production chains, we can approximate the enlargement as being linear in |G_{\Gamma}| . 3.1. Space complexity Let us attempt to estimate |G_{\Gamma}^{\prime}| in terms of the contribution from each constructor. Following the convention of Lange and Leiß ( 6 ) , we define |G|=\sum_{w\in V}\sum_{w\rightarrow\sigma}|w\sigma| . We will also use |\cdot|^{\prime} to denote binarized production size, which depends on the specific binarization technique, but is bounded by: \displaystyle|w\rightarrow\sigma|^{\prime}:P\rightarrow\mathbb{N}\begin{cases}=|w\sigma|&\text{ if }|w\sigma|\leq 3\\ \leq 3|w\sigma|-1&\text{ otherwise.}\end{cases} The leading term clearly depends on \texttt{FUN}_{\varphi} , which generates function signatures up to arity- k , with d=|\mathbb{T}| types. If one considers permuted orderings of the input type signature, \vec{\tau} , as identical, its cost improves to d\sum_{i=0}^{k}{d+i-1\choose i-1} , however we will adhere to the naïve interpretation, which takes an arithmetico-geometric form, \sum_{p=1}^{k}pd^{p+1} , whose Lange-Leiß size is primarily determined by three factors: \displaystyle|\texttt{FUN}_{\varphi}|^{\prime} \displaystyle=\big|S_{\Gamma}\rightarrow\texttt{\lx@texthl@color{fun}}\ \texttt{\lx@texthl@color{f0}}\ \texttt{\lx@texthl@color{(}}\mathop{\largecomma}\limits_{i=1}^{|\vec{\tau}|}p_{i}\ \texttt{\lx@texthl@color{:}}\ \vec{\tau}_{i}\>\texttt{\lx@texthl@color{)}}\ \texttt{\lx@texthl@color{:}}\ \tau\ \texttt{\lx@texthl@color{=}}\ \texttt{EXP}[\tau,\vec{\tau}\rightarrow\tau]\big|^{\prime}\leq\boxed{12|\vec{\tau}|+23} \displaystyle|\texttt{REC}_{\varphi}|^{\prime} \displaystyle=\big|\texttt{EXP}[\tau,\vec{\tau}\rightarrow\tau]\rightarrow\texttt{\lx@texthl@color{f0}}\ \texttt{\lx@texthl@color{(}}\mathop{\largecomma}\limits_{i=1}^{|\vec{\tau}|}\texttt{EXP}[\vec{\tau}_{i},\vec{\tau}\rightarrow\tau]\>\texttt{\lx@texthl@color{)}}\big|^{\prime}\leq\boxed{6|\vec{\tau}|+8} \displaystyle|\texttt{PID}_{\varphi}|^{\prime} \displaystyle=|\vec{\tau}|\cdot\big|\texttt{EXP}[\vec{\tau}_{i},\vec{\tau}\rightarrow\tau]\rightarrow\texttt{\lx@texthl@color{pi}}\big|^{\prime}=\boxed{2|\vec{\tau}|} Letting p=|\vec{\tau}| and assembling these factors, we have, \displaystyle|G_{\Gamma}^{\prime}|\simeq \displaystyle\sum_{p=0}^{k}d^{p+1}\big(\underbrace{(12p+23)}_{|\texttt{FUN}_{\varphi}|^{\prime}}+\underbrace{(6p+8)}_{|\texttt{REC}_{\varphi}|^{\prime}}\big)+\sum_{p=1}^{k}d^{p+1}\underbrace{(2p)}_{\mathclap{|\texttt{PID}_{\varphi}|^{\prime}}} \displaystyle\simeq \displaystyle\sum_{p=1}^{k}(20p+31)d^{p+1}\simeq\frac{20kd^{k+2}}{(d-1)^{2}}+\mathcal{O}\left(\frac{d^{k+2}}{d-1}\right)+\ldots and lower-degree terms. While our analysis omits \texttt{INV}_{\varphi} , et al., their contributions are less sensitive to the parameter k . 3.2. Sampling The context-free languages have the pleasant property of being closed under intersection with regular languages ( 1 ) , with an explicit construction given by Salomaa ( 9 ) . In brief, for every production \text{W}\rightarrow\text{X Z} in the CNF grammar and state triple p,q,r:Q in the automaton one creates synthetic (1) binary productions p\text{W}r\rightarrow p\text{X}q\>\>\>q\text{Z}r , (2) unit productions p\text{W}q\rightarrow a for every \text{W}\rightarrow a and p,q such that \delta(p,a)=q , and (3) start productions \text{S}\rightarrow q_{\alpha}\text{S}q_{\omega} for every final state q_{\omega} . Once constructed, a variety of methods for enumerating and sampling CFGs can be applied (e.g., ( 4 ; 3 ; 7 ) ). We use Considine’s ( 4 ) , which supports sampling words in language intersections parameterized by an acyclic FA, in which case the intersection will be representable as an acyclic FA, \alpha_{\cap} . This representation can be derminimized to produce an acyclic deterministic FA and then decoded left-to-right using an autoregressive model, or, if uniformity over \ell_{\cap} is desired, by constructing a bijection, b:\mathbb{Z}_{|\ell_{\cap}|}\leftrightarrow\ell_{\cap} , and then drawing samples from a pseudorandom source (e.g., a linear feedback shift register). The latter method has the virtue of perfect parallelizability, although we evaluate this method serially. 4. Evaluation We evaluate the sampler for small arity, k\in[1,3] , with fixed |\Gamma|=18,|\mathbb{T}|=7 (see Appendix A ). This generates tractable CNF grammars, |G_{\Gamma}^{\prime}|\in[1.9\times 10^{4},9.9\times 10^{5}] , from which we then sample words on an Apple M4 with 16 GB of memory. First, we sample words from a slice, \sigma\leftsquigarrow\mathcal{L}(G_{\Gamma}^{\prime})\cap\Sigma^{n} , and measure total time to first sample ( \mu TTFS). Next, using our dataset of random functions obtained during slice sampling, we will replace (\texttt{\lx@texthl@color{:}}\>\tau\>\texttt{\lx@texthl@color{=}}) with a hole (\texttt{\lx@texthl@color{:}}\>\Sigma\>\texttt{\lx@texthl@color{=}}) and resample \sigma^{\prime}\leftsquigarrow\mathcal{L}(G_{\Gamma}^{\prime})\cap(\ldots\>\texttt{\lx@texthl@color{:}}\>\Sigma\>\texttt{\lx@texthl@color{=}}\>\ldots) , which we call type inference. 20 30 40 50 10^{1} 10^{2} 10^{3} 10^{4} |\sigma|=n \mu TTFS (ms) Slice sampling delay k=1 k=2 k=3 20 30 40 50 10^{2} 10^{3} 10^{4} |\sigma|=n \mu TTFS (ms) Type inference delay k=1 k=2 k=3 Figure 1. Slice sampling and type inference delay (log-scaled) vs. sequence length |\sigma|=n for arities k\in[1,3] . Once the first sample is obtained, we observe bounded delay of 1786\pm 817 ns (\mu\pm\sigma) , or an average throughput of \sim 5.6\times 10^{5} samples per second. Enumeration delay does not appear strongly correlated with either arity or word length. 5. Related work Prior work demonstrates how to embed a deterministic CFL into a type-system ( 8 ) , but the reverse direction remains largely unexplored. Existing work on constrained decoding (e.g., Willard et al. ( 10 ) ) shows that syntactic soundness is feasible to guarantee, but the sample space is often ill-defined or an overapproximation to the space of semantically valid candidates. Frank et al. ( 5 ) introduce a type-theoretic method for sampling well-typed terms, but their method does not guarantee statistical uniformity or syntactic completeness. Finally, Bendkowski ( 2 ) uses techniques from enumerative combinatorics to sample closed \lambda -terms of the simply-typed variety, which is most closely related to