Concise Read-Only Specifications for Better Synthesis of Programs with Pointers
Concise Read-Only Specifications for Better Synthesis of Programs with Pointers
复制标题
DOI：
10.1007/978-3-030-44914-8_6
复制
发表时间：
2020-04-18
期刊：
影响因子：
--
通讯作者：
Sergey I
中科院分区：
文献类型：
--
作者：
Costea A;Zhu A;Polikarpova N;Sergey I
在计划合成中，简洁和强大的规格之间存在一个众所周知的权衡：如果规范太冗长，那么编写可能比程序更难编写； . In this work we explore the use of annotations for restricting memory access permissions in program synthesis, and show that they can make specifications much stronger while remaining surprisingly concise. Specifically, we enhance合成分离逻辑（SSL），是合成堆堆操作程序的框架，并具有仅读取的逻辑机制。
我们观察到，这种极简主义和保守的SSL扩展通过几种方式使合成受益，使其更具表现力（通过适度的注释开销来实现更强的正确性保证），（b）有效（它产生更简洁，更易于 - 更易于 - 读取程序），（c）有效（更快的合成）和（d）稳健（综合效率较少受搜索启发式的影响）。对于只读的借用，我们通过描述了我们对借贷感知的合成实施的定量评估来证实（a） - （d），以针对各种堆积的管理程序进行一系列标准基准规范。
In program synthesis there is a well-known trade-off between concise and strong specifications: if a specification is too verbose, it might be harder to write than the program; if it is too weak, the synthesised program might not match the user’s intent. In this work we explore the use of annotations for restricting memory access permissions in program synthesis, and show that they can make specifications much stronger while remaining surprisingly concise. Specifically, we enhance Synthetic Separation Logic (SSL), a framework for synthesis of heap-manipulating programs, with the logical mechanism of read-only borrows. We observe that this minimalistic and conservative SSL extension benefits the synthesis in several ways, making it more (a) expressive (stronger correctness guarantees are achieved with a modest annotation overhead), (b) effective (it produces more concise and easier-to-read programs), (c) efficient (faster synthesis), and (d) robust (synthesis efficiency is less affected by the choice of the search heuristic). We explain the intuition and provide formal treatment for read-only borrows. We substantiate the claims (a)–(d) by describing our quantitative evaluation of the borrowing-aware synthesis implementation on a series of standard benchmark specifications for various heap-manipulating programs.
登录
查看更多内容
影响因子：
1.8
作者：
Jung, Ralf;Jourdan, Jacques-Henri;Dreyer, Derek
通讯作者：
Dreyer, Derek
影响因子：
--
作者：
Leino, K. Rustan M.;Milicevic, Aleksandar
通讯作者：
Milicevic, Aleksandar
影响因子：
1.3
作者：
Balabonski, Thibaut;Pottier, Francois;Protzenko, Jonathan
通讯作者：
Protzenko, Jonathan
影响因子：
1.3
作者：
Garcia, Ronald;Tanter, Eric;Aldrich, Jonathan
通讯作者：
Aldrich, Jonathan
影响因子：
--
作者：
Bornat, R;Calcagno, C;Parkinson, M
通讯作者：
Parkinson, M