Program synthesis with algebraic library specifications
Program synthesis with algebraic library specifications
复制标题
使用代数库规范进行程序综合
DOI：
10.1145/3360558
复制
发表时间：
2019
影响因子：
--
通讯作者：
Solar-Lezama, Armando
中科院分区：
文献类型：
--
作者：
Mariano, Benjamin;Reese, Josh;Xu, Siyuan;Nguyen, ThanhVu;Qiu, Xiaokang;Foster, Jeffrey S.;Solar-Lezama, Armando
程序合成中的一个关键挑战是合成使用库的程序，大多数现实世界的软件都是这样做的。目前的技术水平是用模拟库实现来建模库，这些实现以更简单的方式执行相同的功能。然而，模拟可能仍然很大且复杂，并且必须包括许多实现细节，这两者都可能限制合成性能。为了解决这个问题，我们引入了JLibSketch，这是一个Java程序合成工具，它允许用代数规范来描述库行为，代数规范是方法调用序列的重写规则，例如，加密后接着解密（使用相同的密钥）是身份。JLibSketch通过将JLibSketch问题编译为Sketch程序合成工具的问题来实现重写规则。更具体地说，在编译之后，库调用由抽象数据类型（ADT）表示，重写规则操纵这些ADT。我们形式化的编译，并证明它的声音和完整的重写规则是有序的和不可统一的。我们通过使用JLibSketch来合成九个使用来自三个领域的库的程序来评估JLibSketch：数据结构，密码学和文件系统。我们发现，代数规格，平均而言，大约一半的大小模拟。我们还发现，代数规范的表现优于模拟的九个程序中的七个，有时显着，并执行同样好的最后两个程序。因此，我们相信JLibSketch向使用库的程序的合成迈出了重要的一步。
A key challenge in program synthesis is synthesizing programs that use libraries, which most real-world software does. The current state of the art is to model libraries with mock library implementations that perform the same function in a simpler way. However, mocks may still be large and complex, and must include many implementation details, both of which could limit synthesis performance. To address this problem, we introduce JLibSketch, a Java program synthesis tool that allows library behavior to be described with algebraic specifications, which are rewrite rules for sequences of method calls, e.g., encryption followed by decryption (with the same key) is the identity. JLibSketch implements rewrite rules by compiling JLibSketch problems into problems for the Sketch program synthesis tool. More specifically, after compilation, library calls are represented by abstract data types (ADTs), and rewrite rules manipulate those ADTs. We formalize compilation and prove it sound and complete if the rewrite rules are ordered and non-unifiable. We evaluated JLibSketch by using it to synthesize nine programs that use libraries from three domains: data structures, cryptography, and file systems. We found that algebraic specifications are, on average, about half the size of mocks. We also found that algebraic specifications perform better than mocks on seven of the nine programs, sometimes significantly so, and perform equally well on the last two programs. Thus, we believe that JLibSketch takes an important step toward synthesis of programs that use libraries.
登录
查看更多内容
SMT 中递归函数的模型查找
DOI：
10.1007/978-3-319-40229-1_10
发表时间：
2016
期刊：
The Journal of infectious diseases
影响因子：
--
作者：
Andrew Reynolds;J. Blanchette;Simon Cruanes;C. Tinelli
通讯作者：
C. Tinelli
通用代数中的简单应用题††本文报告的工作得到了美国海军研究办公室的部分支持。
DOI：
--
发表时间：
1970
期刊：
影响因子：
--
作者：
D. Knuth;P. Bendix
通讯作者：
P. Bendix
并行程序综合的自适应具体化
DOI：
10.1007/978-3-319-21668-3_22
发表时间：
2015
期刊：
Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Jinseong Jeon;Xiaokang Qiu;Armando Solar;J. Foster
通讯作者：
J. Foster
使用有限树自动机合成数据完成脚本
影响因子：
--
作者：
Xinyu Wang;Işıl Dillig;Rishabh Singh
通讯作者：
Rishabh Singh
具有等价约简的程序综合
DOI：
--
发表时间：
2019
期刊：
and Abstract Interpretation
影响因子：
--
作者：
Smith, Calvin;Albarghouthi, Aws
通讯作者：
Albarghouthi, Aws