Open Access
- 9 January 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 7 (POPL) , 1182-1213
Abstract
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.Keywords
All Related Versions
Funding Information
- NSF (2141064,1918839)
- DARPA (FA8750-20-C-0542)
- AFOSR (FA9550-19-1-026)
This publication has 31 references indexed in Scilit:
- Network Motifs: Simple Building Blocks of Complex NetworksScience, 2002
- Unification under a mixed prefixJournal of Symbolic Computation, 1992
- The revised report on the syntactic theories of sequential control and stateTheoretical Computer Science, 1992
- A Logic Programming Language with Lambda-Abstraction, Function Variables, and Simple UnificationJournal of Logic and Computation, 1991
- A Deductive Approach to Program SynthesisACM Transactions on Programming Languages and Systems, 1980
- The Power of Dominance Relations in Branch-and-Bound AlgorithmsJournal of the ACM, 1977
- A Transformation System for Developing Recursive ProgramsJournal of the ACM, 1977
- A unification algorithm for typed λ-calculusTheoretical Computer Science, 1975
- Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theoremIndagationes Mathematicae, 1972
- An Automatic Method of Solving Discrete Programming ProblemsEconometrica, 1960