{"ID":2834979,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.01036","arxiv_id":"2512.01036","title":"A Word Sampler for Well-Typed Functions","abstract":"We describe an exact sampler for a simply-typed, first-order functional programming language. Given an acyclic finite automaton, $α_{\\varnothing}$, it samples a random function uniformly without replacement from well-typed functions in $\\mathcal{L}(α_{\\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}(α_{\\varnothing})$, while retaining the robust metatheory of formal languages.","short_abstract":"We describe an exact sampler for a simply-typed, first-order functional programming language. Given an acyclic finite automaton, $α_{\\varnothing}$, it samples a random function uniformly without replacement from well-typed functions in $\\mathcal{L}(α_{\\varnothing})$. This is achieved via a fixed-parameter tractable red...","url_abs":"https://arxiv.org/abs/2512.01036","url_pdf":"https://arxiv.org/pdf/2512.01036v1","authors":"[\"Breandan Considine\"]","published":"2025-11-30T19:05:50Z","proceeding":"cs.PL","tasks":"[\"cs.PL\",\"cs.FL\"]","methods":"[]","has_code":false}