Top-Down Synthesis for Library Learning
Proposes Stitch, a top-down corpus-guided synthesis algorithm, achieving 3-4 orders faster and 20x less memory than prior methods.
Key Findings
Methodology
This paper introduces a corpus-guided top-down synthesis framework that combines syntax-based pattern matching with branch-and-bound search. Implemented in Rust, Stitch leverages partial abstraction matching, upper-bound utility estimation, and parallel processing to efficiently discover abstractions that compress program corpora. The core process involves defining abstraction syntax, matching subtrees across the corpus, estimating maximum utility via overapproximations, and iteratively expanding partial abstractions until optimal compression is achieved. This approach avoids exponential search spaces typical of deductive methods, enabling scalable library learning.
Key Results
- On Wong et al. 2022’s complex program datasets, Stitch learns high-quality libraries within seconds to minutes for hundreds of programs with average lengths of 76-189 symbols, outperforming Ellis et al. 2021’s deductive approach by 3-4 orders of magnitude in speed and 20x in memory savings, while maintaining comparable or better compression quality.
- The method demonstrates robustness under resource constraints via early stopping, with experimental results confirming scalability to large corpora, and ablation studies highlighting the importance of matching and pruning strategies.
- The learned libraries significantly reduce program size, enabling more efficient code reuse and potential integration into industrial software pipelines.
Significance
This work addresses fundamental scalability issues in program library learning, providing a highly efficient, scalable alternative to traditional deductive approaches. By leveraging syntax-guided search and pruning, Stitch enables practical application to large-scale codebases, facilitating automatic code compression, reuse, and refactoring. Its ability to scale and operate under resource constraints opens new avenues for automated software engineering, including intelligent code synthesis and optimization tools that can adapt to diverse programming domains.
Technical Contribution
The paper introduces a novel branch-and-bound top-down search algorithm guided by syntax matching, which directly synthesizes abstractions without exhaustive rewriting. Key innovations include the use of match location upper bounds for pruning, parallelized implementation, and integration with a flexible utility function focused on compression. Unlike prior deductive methods relying on rewrite rules and semantic evaluation, Stitch performs efficient, syntax-based abstraction discovery, providing theoretical guarantees of optimality and significant performance gains.
Novelty
This is the first application of corpus-guided top-down search for library learning, combining syntax-based pattern matching with branch-and-bound pruning to achieve scalability. The approach diverges from existing deductive and bottom-up methods, offering a new paradigm for abstraction synthesis that is both fast and scalable, addressing the core limitations of prior work.
Limitations
- Dependence on the quality and representativeness of the input corpus; noisy or unrepresentative data may impair abstraction quality.
- While scalable, extremely large or highly complex program sets still pose challenges, requiring further optimization of matching and pruning heuristics.
- Current focus on compression may limit generalization to other abstraction objectives like robustness or generalization beyond the training corpus.
Future Work
Future directions include integrating deep learning models for improved pattern matching, extending the framework to multi-layer abstractions, and applying the method across multiple programming languages and domains. Further research will explore combining this syntax-guided approach with semantic analysis for richer abstractions and broader applicability.
AI Executive Summary
Program library learning has long been a bottleneck in automatic program synthesis, especially when dealing with large, complex datasets. Traditional deductive approaches like DreamCoder, while effective, face exponential growth in search space, limiting their scalability. This paper introduces Stitch, a novel algorithm that leverages a corpus-guided, top-down search strategy to efficiently discover shared abstractions across program corpora.
Stitch’s core innovation lies in combining syntax-based pattern matching with a branch-and-bound search framework. By estimating upper bounds on utility gains based on match locations, the algorithm prunes large portions of the search space, dramatically reducing computational costs. Implemented in Rust with parallel processing, Stitch can learn high-quality libraries within seconds to minutes for hundreds of programs, significantly outperforming prior methods in speed and memory usage.
Experimental results on datasets from Wong et al. 2022 demonstrate that Stitch maintains or exceeds the compression quality of state-of-the-art algorithms while being 3-4 orders faster and 20 times more memory efficient. Its robustness under resource constraints and early stopping further enhance its practical applicability, making it suitable for industrial-scale codebases. The approach’s scalability and efficiency open new avenues for automated code optimization, reuse, and refactoring.
This work fundamentally shifts the landscape of program abstraction learning, providing a scalable, syntax-guided alternative to traditional deductive methods. Future work aims to incorporate deep learning for pattern recognition, extend to multi-layer abstractions, and adapt across diverse programming languages. Overall, Stitch represents a significant step toward practical, scalable automatic program synthesis and library construction.
Deep Analysis
Background
程序合成和库学习经历了从符号推理到深度学习的演变，代表性工作如DreamCoder、Ellis等2021提出的推导式抽象学习，解决了程序重用和压缩问题。然而，这些方法在处理大规模复杂程序时面临计算瓶颈，限制了其实际应用。近年来，基于语法匹配和搜索剪枝的启发式算法逐渐崛起，试图突破规模限制，但仍存在效率不足的问题。随着程序规模和复杂度的增加，传统方法难以满足工业级需求，亟需更高效的算法。
Core Problem
核心问题在于如何在保证抽象质量的同时，显著降低搜索空间和计算成本。现有推导方法依赖重写规则，导致指数级的空间爆炸，难以扩展到数百甚至上千个程序的库学习。如何利用语料的结构信息引导搜索，减少不必要的探索，是提升算法实用性的关键。
Innovation
本研究的创新点在于：1）提出基于语料引导的自顶向下搜索（CTS）框架，利用语法匹配限制搜索空间；2）引入分支界限策略，通过上界估算提前剪枝；3）在Rust中实现高效并行算法，显著提升速度和内存效率。与传统推导方法不同，Stitch直接在抽象空间进行搜索，避免了重写空间的指数级爆炸。
Methodology
- �� 定义抽象语法和partial abstraction（含空洞）；
- �� 利用语法匹配找到潜在匹配位置，估算最大压缩潜力；
- �� 采用分支界限策略，利用上界剪枝无效分支；
- �� 逐步扩展partial abstraction，直至满足压缩目标；
- �� 利用多线程优化匹配和搜索过程，确保高效执行。
Experiments
采用Wong等2022的中等复杂度程序集，比较Stitch与Ellis等2021的推导算法，指标包括压缩比、运行时间和内存消耗。通过不同资源限制和早停策略，验证算法的扩展性和鲁棒性。还进行了消融实验，分析匹配、剪枝等关键技术的贡献。
Results
实验显示，Stitch在学习复杂程序库时，速度提升3-4个数量级，内存减少20倍，且库的压缩性与最优方法相当。在处理数百个程序时，平均运行时间为几秒到几分钟，远超传统方法。早停机制保证了在资源有限时仍能获得较优结果，验证了算法的实用价值。
Applications
该算法适用于自动代码生成、程序优化和软件重构等场景，尤其在大规模代码库的抽象和压缩方面表现出巨大潜力。可为工业软件开发提供高效的库构建工具，减少手工编码成本。未来还可结合深度学习模型，提升匹配和剪枝的智能化水平。
Limitations & Outlook
当前方法依赖于预定义DSL和语料的代表性，若语料偏差或噪声较多，可能影响抽象质量。面对极端复杂或高度重用的程序集，搜索空间仍然庞大，需进一步优化匹配和剪枝策略。此外，算法主要优化压缩目标，泛化能力和多任务学习仍待探索。
Plain Language Accessible to non-experts
想象你在整理一个厨房的食谱库。每个菜谱都用一些基本的步骤写成，比如“切菜”、“炒菜”、“调味”。有经验的人会发现一些常用的步骤组合，比如“炒菜后加入调味料”，他们会把这些常用的步骤总结成一个“炒调料”的小工具。这样，以后做菜就可以直接用这个工具，省时省力。
现在，假设你有很多菜谱，想找出这些共同的步骤，把它们变成工具箱。传统的方法就像逐个检查每个菜谱，试图重写它们，找到共同点，但这个过程非常慢，尤其菜谱多、步骤复杂时。
这篇研究提出一种聪明的办法：用一种“搜索引擎”在菜谱中快速找到共同的步骤，然后把它们抽象出来，形成工具箱。这个搜索引擎会根据已有的菜谱，自动猜测哪些步骤可以合成一个工具，然后验证这个猜测是否能压缩所有菜谱的长度。它像是在厨房里不断试验，把常用的步骤总结成一个“万能调料包”，让所有菜谱都能用上，变得更简洁、更高效。这种方法比以前的方式快得多，也能处理更复杂的菜谱，未来还可以用在软件代码的自动优化上。
ELI14 Explained like you're 14
想象你在学校的厨房里帮老师整理食谱。每个菜谱都写着一些步骤，比如“切菜”、“炒菜”、“加调料”。有经验的厨师会发现很多菜都用到类似的步骤，然后把这些步骤总结成一个“工具包”，以后做菜就可以直接用这个工具包，省时又方便。
可是，如果你要整理上百个菜谱，逐个分析每个步骤，找出共同点，就会变得非常慢。这时候，你需要一种聪明的方法：用一个“搜索助手”帮你快速找到这些共同的步骤，然后把它们变成工具包。这个助手会根据你已有的菜谱，猜测哪些步骤可以合成一个工具，然后验证这个猜测是否能让所有菜谱变得更简洁。
就像在厨房里用魔法一样，这个方法可以在很短的时间内，把复杂的菜谱变得简单明了。它不仅节省时间，还能处理非常复杂的菜谱，甚至可以用在软件代码的优化上。未来，这种智能搜索工具会让我们的工作变得更轻松，也让软件变得更聪明、更高效！
Glossary
库学习 (Library Learning)
自动从程序语料中抽象出共享结构，形成函数库，用于压缩和重用代码。技术上通过匹配子树和搜索策略实现。
论文中提出的核心技术，用于自动构建程序库以提升程序压缩效率。
语料引导 (Corpus-guided)
利用已有程序集中的结构信息引导抽象合成的搜索过程，限制搜索空间以提升效率。
算法的核心思想，确保搜索方向与程序集的共享结构一致。
分支界限 (Branch-and-bound)
一种优化搜索策略，通过估算上界提前剪枝，避免遍历无用分支。
Stitch算法中用于高效剪枝，确保搜索的最优性和速度。
抽象语法树 (Abstract Syntax Tree, AST)
程序的结构化表示，描述程序的语法结构，用于匹配和重写。
算法中用来匹配子树和定义抽象。
压缩性 (Compressivity)
用抽象重写程序后，程序长度的缩减比例，衡量库的压缩能力。
评估库学习效果的重要指标。
Open Questions Unanswered questions from this research
- 1 如何进一步提升匹配和剪枝策略的精度，以应对极端复杂或噪声较多的程序集。
- 2 将算法扩展到多语言、多领域的程序库构建，提升泛用性和适应性。
- 3 结合深度学习模型，自动学习更复杂的抽象结构，突破现有规则限制。
Applications
Immediate Applications
自动代码压缩与优化
可用于自动化整理大型代码库，提升代码重用率，减少冗余，提高软件维护效率。
程序自动生成与重构
辅助开发者快速生成高层次抽象，简化复杂程序结构，支持自动重构和迁移。
Long-term Vision
智能软件工程平台
未来可集成到IDE或软件开发平台，实现自动抽象、压缩和优化，推动自动化软件开发。
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.