POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

We explore a new approach to \textit{library learning}, the task of extracting a reusable library of functions by finding common structure in a corpus of programs. We build on two related approaches to this problem: Stitch, which frames library learning as a top-down program synthesis problem, and Babble, which approaches it via an anti-unification procedure over e-graphs. Both of these techniques have shortcomings: Stitch’s top-down search cannot leverage equivalence relations, and Babble’s anti-unification algorithm is inherently quadratic in the size of the corpus. In this work, we introduce E-Stitch, which extends Stitch’s corpus-guided top-down search to operate over a corpus in an \textit{e-graph}. This combines the efficiency of the top-down approach with the expressivity afforded by equivalence relations. We provide an evaluation of our approach on the benchmarks from Babble, and are able to outperform it in both speed and compression. We additionally demonstrate that E-Stitch scales to domains with substantially more complex sets of rewrites, finding abstractions inaccessible to Stitch.