Data flow refinement type inference
Data flow refinement type inference
复制标题
数据流细化类型推断
DOI：
10.1145/3434300
复制
发表时间：
2021
影响因子：
--
通讯作者：
Wies, Thomas
中科院分区：
文献类型：
--
作者：
Pavlinovic, Zvonimir;Su, Yusen;Wies, Thomas
精化类型支持功能程序的轻量级验证。用于静态推断精化类型的算法通常通过归约为从类型派生中提取的受约束Horn子句的求解系统来工作。液体类型推理就是一个例子，它使用谓词抽象来解决所提取的约束。然而，简化到约束求解本身已经意味着程序语义的抽象，这影响了整个静态分析的精度。为了更好地理解这个问题，我们从抽象解释的角度对类型推理问题进行了整体研究。我们提出了一个新的精化类型系统，它是参数的，它选择类型精化的抽象域以及它跟踪上下文敏感控制流信息的程度。然后，我们导出了相应的参数推理算法，作为对函数式程序的一种新的数据流语义的抽象解释。我们进一步证明了该类型系统相对于所构造的抽象语义是健全和完备的。我们的理论发展揭示了精化型推理算法固有的关键抽象步骤。这些抽象步骤的精度和效率之间的权衡由类型系统的参数控制。现有的精化类型系统及其相应的推理算法，如液体类型，通过具体的参数实例化来捕获。我们已经在一个原型工具中实现了我们的框架，并针对一系列新的参数实例化对其进行了评估(例如，使用八角形和多面体来表示类型细化)。与其他现有工具相比，该工具更具优势。我们的评估表明，我们的方法可以用来系统地构造新的精化型推理算法，这些算法既健壮又精确。
Refinement types enable lightweight verification of functional programs. Algorithms for statically inferring refinement types typically work by reduction to solving systems of constrained Horn clauses extracted from typing derivations. An example is Liquid type inference, which solves the extracted constraints using predicate abstraction. However, the reduction to constraint solving in itself already signifies an abstraction of the program semantics that affects the precision of the overall static analysis. To better understand this issue, we study the type inference problem in its entirety through the lens of abstract interpretation. We propose a new refinement type system that is parametric with the choice of the abstract domain of type refinements as well as the degree to which it tracks context-sensitive control flow information. We then derive an accompanying parametric inference algorithm as an abstract interpretation of a novel data flow semantics of functional programs. We further show that the type system is sound and complete with respect to the constructed abstract semantics. Our theoretical development reveals the key abstraction steps inherent in refinement type inference algorithms. The trade-off between precision and efficiency of these abstraction steps is controlled by the parameters of the type system. Existing refinement type systems and their respective inference algorithms, such as Liquid types, are captured by concrete parameter instantiations. We have implemented our framework in a prototype tool and evaluated it for a range of new parameter instantiations (e.g., using octagons and polyhedra for expressing type refinements). The tool compares favorably against other existing tools. Our evaluation indicates that our approach can be used to systematically construct new refinement type inference algorithms that are both robust and precise.
登录
查看更多内容
TypeScript 的细化类型
DOI：
10.1145/2908080.2908110
发表时间：
2016
期刊：
Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Panagiotis Vekris;B. Cosman;Ranjit Jhala
通讯作者：
Ranjit Jhala
Ruby 的细化类型
DOI：
--
发表时间：
2018
期刊：
and Abstract Interpretation - VMCAI'18
影响因子：
--
作者：
Kazerounian, Milod;Vazou, Niki;Bourgerie, Austin;Foster, Jeff;Torlak, Emina
通讯作者：
Torlak, Emina
作为抽象解释的字符串分析
DOI：
10.1007/978-3-642-18275-4_21
发表时间：
2011
期刊：
World's Poultry Science Journal
影响因子：
--
作者：
Se;K. Choe
通讯作者：
K. Choe
DOI：
10.1007/3-540-47813-2_16
发表时间：
2002
期刊：
World's Poultry Science Journal
影响因子：
--
作者：
R. Gori;G. Levi
通讯作者：
G. Levi
单项式和从句谓词抽象的复杂性和算法
DOI：
10.1007/978-3-642-02959-2_18
发表时间：
2009
期刊：
Cardiovascular revascularization medicine : including molecular interventions
影响因子：
--
作者：
Shuvendu K. Lahiri;S. Qadeer
通讯作者：
S. Qadeer