# Searching Entangled Program Spaces

arXiv: https://arxiv.org/abs/2206.07828 · HTML: https://mlsanity.com/paper/2206.07828/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2022.

## Built on by (most cited first, 1 of 1)

- [Efficient Bottom-Up Synthesis for Programs with Local Variables](https://mlsanity.com/paper/2311.03705/) (2023)

## Abstract (arXiv)

Many problem domains, including program synthesis and rewrite-based optimization, require searching astronomically large spaces of programs. Existing approaches often rely on building specialized data structures -- version-space algebras, finite tree automata, or e-graphs -- to compactly represent these programs. To find a compact representation, existing data structures exploit independence of subterms; they blow up when the choices of subterms are entangled. We introduce equality-constrained tree automata (ECTAs), a generalization of the three aforementioned data structures that can efficiently represent large spaces of programs with entangled subterms. We present efficient algorithms for extracting programs from ECTAs, implemented in a performant Haskell library, textttecta. Using textttecta we construct textscHectare, a type-driven program synthesizer for Haskell. textscHectare significantly outperforms a state-of-the-art synthesizer Hoogle+ -- providing an average speedup of 8x -- despite its implementation being an order of magnitude smaller.