Efficient Bottom-Up Synthesis for Programs with Local Variables
Efficient Bottom-Up Synthesis for Programs with Local Variables
复制标题
具有局部变量的程序的高效自下而上综合
DOI：
10.1145/3632894
复制
发表时间：
2024
影响因子：
--
通讯作者：
Wang, Xinyu
中科院分区：
文献类型：
--
作者：
Li, Xiang;Zhou, Xiangyu;Dong, Rui;Zhang, Yihong;Wang, Xinyu
我们提出了一种新的综合算法，可以有效地搜索具有局部变量的程序（例如，由 lambda 引入的变量）。现有的自下而上的综合算法无法评估具有自由局部变量的程序，因此无法有效地减少此类程序的搜索空间（例如，使用标准的观察等价减少技术），从而使得综合速度变慢。我们的算法可以减少带有局部变量的程序空间。被称为提升解释的关键思想是提升程序解释过程，从一次评估一个程序到同时评估语法中的所有程序。提升解释提供了一种系统地枚举局部变量的所有绑定上下文的机制，从而使我们能够评估和减少具有局部变量的程序空间。我们的想法在网络自动化领域得到体现。由此产生的工具 Arborist 可以比 WebRobot 和 Helena 等最先进的技术更有效地自动化更广泛的挑战性任务。
We propose a new synthesis algorithm that can efficiently search programs with local variables (e.g., those introduced by lambdas). Prior bottom-up synthesis algorithms are not able to evaluate programs with free local variables, and therefore cannot effectively reduce the search space of such programs (e.g., using standard observational equivalence reduction techniques), making synthesis slow. Our algorithm can reduce the space of programs with local variables. The key idea, dubbed lifted interpretation, is to lift up the program interpretation process, from evaluating one program at a time to simultaneously evaluating all programs from a grammar. Lifted interpretation provides a mechanism to systematically enumerate all binding contexts for local variables, thereby enabling us to evaluate and reduce the space of programs with local variables. Our ideas are instantiated in the domain of web automation. The resulting tool, Arborist, can automate a significantly broader range of challenging tasks more efficiently than state-of-the-art techniques including WebRobot and Helena.
登录
查看更多内容
DOI：
10.1145/3453483.3454047
发表时间：
2021-04
期刊：
Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Qiaochu Chen;Aaron Lamoreaux;Xinyu Wang;Greg Durrett;O. Bastani;Işıl Dillig
通讯作者：
Qiaochu Chen;Aaron Lamoreaux;Xinyu Wang;Greg Durrett;O. Bastani;Işıl Dillig
使用天使执行的递归函数程序的自下而上综合
DOI：
--
发表时间：
2021
期刊：
Proc. ACM Program. Lang.
影响因子：
--
作者：
Anders Miltner;A. Nunez;Ana Brendel;Swarat Chaudhuri;Işıl Dillig
通讯作者：
Işıl Dillig
浏览器记录和重放作为最终用户 Web 自动化工具的构建块
DOI：
10.1145/2740908.2742849
发表时间：
2015
期刊：
Proceedings of the 24th International Conference on World Wide Web
影响因子：
--
作者：
Sarah E. Chasins;Shaon Barman;Rastislav Bodík;Sumit Gulwani
通讯作者：
Sumit Gulwani
影响因子：
--
作者：
Xinyu Wang;Işıl Dillig;Rishabh Singh
通讯作者：
Xinyu Wang;Işıl Dillig;Rishabh Singh
使用有限树自动机合成数据完成脚本
影响因子：
--
作者：
Xinyu Wang;Işıl Dillig;Rishabh Singh
通讯作者：
Rishabh Singh