Скачать или смотреть [LAFI'26] A Word Sampler for Well-Typed Functions

A Word Sampler for Well-Typed Functions (Video, LAFI 2026)
Breandan Considine
(unaffiliated)

Abstract: We describe an exact sampler for a simply-typed, first-order functional programming language. Given an acyclic finite automaton, α∅, it samples a random function uniformly without replacement from well-typed functions in L(α∅). 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. L(α∅), while retaining the robust metatheory of formal languages.


Presentation at the LAFI 2026 workshop, Jan 11, 2026, https://popl26.sigplan.org/home/lafi-...
Sponsored by ACM SIGPLAN.