Syntax-Guided Synthesis with Quantitative Syntactic Objectives
Syntax-Guided Synthesis with Quantitative Syntactic Objectives
复制标题
具有定量句法目标的句法引导综合
DOI：
10.1007/978-3-319-96145-3_21
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Hu, Q. and
中科院分区：
文献类型：
--
作者：
Hu, Q. and
自动程序合成有望通过自动化繁琐且容易出错的任务来提高程序员和计算设备的最终用户的生产力。尽管程序综合在实践中取得了成功，但我们仍然没有系统的框架来综合根据某些度量标准的“好”程序-例如，产生合理大小或具有良好运行时间的程序，并了解何时合成可以产生这样的好程序。在本文中，我们proposeQSyGuS，一个统一的框架，用于描述语法指导的合成问题的定量目标的合成programmes. QSyGuS建立在加权（树）文法，一个干净的和基础的形式主义，提供灵活的支持不同的定量目标，有用的封闭属性，和实际的决策程序。然后，我们提出了一个算法solvingQSyGuS。我们的算法利用封闭属性的加权文法生成的中间问题，可以使用非quantitativeSyGuSsolvers解决。最后，我们实现了我们的算法在一个工具中，SISSI，并评估它的26个定量扩展existingSyGuSbenchmarks. SISCAN合成最佳解决方案，在15/26基准的时间可比那些需要找到一个任意的解决方案。
Automatic program synthesis promises to increase the productivity of programmers and end-users of computing devices by automating tedious and error-prone tasks. Despite the practical successes of program synthesis, we still do not have systematic frameworks to synthesize programs that are “good” according to certain metrics—e.g., produce programs of reasonable sizes or with good runtime—and to understand when synthesis can result in such good programs. In this paper, we proposeQSyGuS, a unifying framework for describing syntax-guided synthesis problems with quantitative objectives over the syntax of the synthesized programs.QSyGuSbuilds on weighted (tree) grammars, a clean and foundational formalism that provides flexible support for different quantitative objectives, useful closure properties, and practical decision procedures. We then present an algorithm for solvingQSyGuS. Our algorithm leverages closure properties of weighted grammars to generate intermediate problems that can be solved using non-quantitativeSyGuSsolvers. Finally, we implement our algorithm in a tool,QuaSi, and evaluate it on 26 quantitative extensions of existingSyGuSbenchmarks.QuaSican synthesize optimal solutions in 15/26 benchmarks with times comparable to those needed to find an arbitrary solution.
登录
查看更多内容
使用符号转换器自动程序反演
DOI：
10.1145/3062341.3062345
发表时间：
2017
期刊：
Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Qinheping Hu;Loris D'antoni
通讯作者：
Loris D'antoni
SyGuS-Comp15 的结果和分析
影响因子：
1.6
作者：
R. Alur;D. Fisman;Rishabh Singh;Armando Solar
通讯作者：
Armando Solar
DOI：
--
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
Manos Koukoutos;Mukund Raghothaman;Etienne Kneuss;Viktor Kunčak
通讯作者：
Viktor Kunčak
影响因子：
22.7
作者：
Eric Schkufza;Rahul Sharma;A. Aiken
通讯作者：
A. Aiken
加权树自动机和加权逻辑
影响因子：
1.1
作者：
M. Droste;H. Vogler
通讯作者：
H. Vogler