  This paper introduces corpus-guided top-down synthesis as a mechanism for
synthesizing library functions that capture common functionality from a corpus
of programs in a domain specific language (DSL). The algorithm builds
abstractions directly from initial DSL primitives, using syntactic pattern
matching of intermediate abstractions to intelligently prune the search space
and guide the algorithm towards abstractions that maximally capture shared
structures in the corpus. We present an implementation of the approach in a
tool called Stitch and evaluate it against the state-of-the-art deductive
library learning algorithm from DreamCoder. Our evaluation shows that Stitch is
3-4 orders of magnitude faster and uses 2 orders of magnitude less memory while
maintaining comparable or better library quality (as measured by
compressivity). We also demonstrate Stitch's scalability on corpora containing
hundreds of complex programs that are intractable with prior deductive
approaches and show empirically that it is robust to terminating the search
procedure early -- further allowing it to scale to challenging datasets by
means of early stopping.
