Compositional soundness proofs of abstract interpreters
Compositional soundness proofs of abstract interpreters
复制标题
抽象解释器的组合健全性证明
DOI：
10.1145/3236767
复制
发表时间：
2018
影响因子：
--
通讯作者：
S. Erdweg
中科院分区：
文献类型：
--
作者：
S. Keidel;C. Bach Poulsen;S. Erdweg
抽象解释是一种开发静态分析的技术。然而，对于有趣的分析来说，证明抽象的口译员的声音是具有挑战性的，因为它具有高度的复杂性和证明的努力。为了减少复杂性和工作量，我们提出了一个抽象解释器的框架，使他们的可靠性证明是组成的。我们方法的关键是在单个共享解释器中捕获具体解释器和抽象解释器之间的相似性，该解释器通过基于箭头的接口进行参数化。在我们的框架中，可靠性证明被归结为在该接口的具体和抽象实例上证明可重用的可靠性引理；整个解释器的可靠性源于一般定理。为了进一步减少证明工作量，我们探索了可靠性和参数之间的关系。参数化不仅为如何设计共享解释器的无泄漏接口提供了有用的指导，而且还为我们提供了共享纯函数的可靠性作为自由定理。我们在Haskell中实现了我们的框架，并为PCF开发了AK-CFA分析，为策略开发了树形分析。与传统的可靠证明相比，我们能够以可管理的复杂性和工作量来证明这两种分析的成分都是合理的。
Abstract interpretation is a technique for developing static analyses. Yet, proving abstract interpreters sound is challenging for interesting analyses, because of the highproof complexityandproof effort. To reduce complexity and effort, we propose a framework for abstract interpreters that makes their soundness proof compositional. Key to our approach is to capture the similarities between concrete and abstract interpreters in a single shared interpreter, parameterized over an arrow-based interface. In our framework, a soundness proof is reduced to proving reusable soundness lemmas over the concrete and abstract instances of this interface; the soundness of the overall interpreters follows from a generic theorem.To further reduce proof effort, we explore the relationship between soundness and parametricity. Parametricity not only provides us with useful guidelines for how to design non-leaky interfaces for shared interpreters, but also provides us soundness of shared pure functions asfree theorems. We implemented our framework in Haskell and developed ak-CFA analysis for PCF and a tree-shape analysis for Stratego. We were able to prove both analyses sound compositionally with manageable complexity and effort, compared to a conventional soundness proof.
登录
查看更多内容
具有嵌套具体语法的高阶转换
DOI：
10.1145/1988783.1988787
发表时间：
2011
期刊：
--
影响因子：
--
作者：
Economopoulos R
通讯作者：
Economopoulos R
DOI：
10.13016/m2j96097d
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
David Darais
通讯作者：
David Darais
一元抽象解释器
DOI：
10.1145/2491956.2491979
发表时间：
2013
期刊：
Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Ilya Sergey;Dominique Devriese;M. Might;Jan Midtgaard;David Darais;D. Clarke;Frank Piessens
通讯作者：
Frank Piessens
DOI：
10.1145/3141517.3141855
发表时间：
2017
期刊：
Proceedings of the 2nd ACM SIGPLAN International Workshop on Meta-Programming Techniques and Reflection
影响因子：
--
作者：
S. Keidel;S. Erdweg
通讯作者：
S. Erdweg
Conf.Researchr.Org：用于管理大型会议网站的特定领域内容管理系统
DOI：
10.1145/2814189.2817270
发表时间：
2015
期刊：
Companion Proceedings of the 2015 ACM SIGPLAN International Conference on Systems, Programming, Languages and Applications: Software for Humanity
影响因子：
--
作者：
E. V. Chastelet;E. Visser;C. Anslow
通讯作者：
C. Anslow