Top-Down Synthesis for Library Learning
Top-Down Synthesis for Library Learning
复制标题
DOI：
10.1145/3571234
复制
发表时间：
2022-11
影响因子：
--
通讯作者：
Matthew Bowers;Theo X. Olausson;Catherine Wong;Gabriel Grand;J. Tenenbaum;Kevin Ellis;Armando Solar-Lezama
中科院分区：
文献类型：
--
作者：
Matthew Bowers;Theo X. Olausson;Catherine Wong;Gabriel Grand;J. Tenenbaum;Kevin Ellis;Armando Solar-Lezama
本文介绍了语料库引导的自上而下的合成，作为合成库函数的机制，从域特定语言中捕获程序的共同功能（DSL），该算法直接从初始的DSL原始词中构建抽象。中间抽象以智能修剪搜索空间并指导算法介绍了在语料库中最大程度地捕获共享结构的抽象。 Dreamcoder的算法表明，针迹更快地使用了3-4个数量级，并且使用2个数量级，同时保持可比较或更好的库质量（通过压缩来衡量）。通过先前的演绎方法棘手的程序，并迫切地表明，尽早终止搜索程序是坚固的 - 允许其扩展以通过早期停止来挑战数据集。
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.