Reproduce “A Word Sampler for Well-Typed Functions” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Breandan Considine
An exact sampler is developed for a simply-typed, first-order functional programming language, capable of generating well-typed functions uniformly and without replacement. This method achieves a throughput of approximately 5.6 × 10^5 samples per second after initial setup and supports type inference for function signatures.
Key insights
- Type systems can be effectively encoded as decorated Context-Free Grammars, allowing the leveraging of robust formal language theory for rigorous program generation.
- The problem of generating well-typed and syntactically constrained programs can be framed as sampling from the intersection of a context-free language (derived from the type system) and a regular language (from arbitrary syntactic constraints).
- Exact and uniform sampling of programs, a strong statistical guarantee often missing in other generators, is achievable for functional languages of small arity, opening avenues for unbiased program analysis and testing.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.