Systematic abstraction of abstract machines
Systematic abstraction of abstract machines
复制标题
抽象机的系统抽象
DOI：
10.1017/s0956796812000238
复制
发表时间：
2011
影响因子：
1.1
通讯作者：
M. Might
中科院分区：
文献类型：
--
作者：
David Van Horn;M. Might
摘要我们描述了一种抽象解释的衍生方法，当应用于良好的抽象机器上，可以将新颖和透明的静态分析用于高阶和势在必行的编程语言，以演示我们的主张并支持我们的主张，我们会改变Felleisen的Cek Machine。和Friedman（第14个ACM Sigact-SigplanSymp。Prin。Prin。Langs，1987年，第314-325页） Krivine的机器（高阶Symb。Comput。2007，pp。199–207）和Clements and Felleisen的堆栈检查CM机器（ACMTrans。Program。Lang。Syst。Syst。Syst。Vol26，2004，pp。 1029–1052）对自己的分析进行了抽象的解释。参数。对于所有这些机器，我们发现一系列众所周知的混凝土机器，以及商店分配的连续性技术，可以通过分配来使机器抽象成静态分析。调整性能和精度并实质上扩大了该框架可以代表的分析空间的功能。现实的语言特征，包括尾巴呼叫，条件，突变，例外，一流的连续性，甚至是垃圾收集，以弥补格式和实施之间的差距，我们将数学的翻译作为运行的Haskell代码我们的方法。
Abstract We describe a derivational approach to abstract interpretation that yields novel and transparently sound static analyses when applied to well-established abstract machines for higher-order and imperative programming languages. To demonstrate the technique and support our claim, we transform the CEK machine of Felleisen and Friedman (Proc. of the 14th ACM SIGACT-SIGPLAN Symp. Prin. Program. Langs, 1987, pp. 314–325), a lazy variant of Krivine's machine (Higher-Order Symb. Comput. Vol 20, 2007, pp. 199–207), and the stack-inspecting CM machine of Clements and Felleisen (ACM Trans. Program. Lang. Syst. Vol 26, 2004, pp. 1029–1052) into abstract interpretations of themselves. The resulting analyses bound temporal ordering of program events; predict return-flow and stack-inspection behavior; and approximate the flow and evaluation of by-need parameters. For all of these machines, we find that a series of well-known concrete machine refactorings, plus a technique of store-allocated continuations, leads to machines that abstract into static analyses simply by bounding their stores. These machines are parameterized by allocation functions that tune performance and precision and substantially expand the space of analyses that this framework can represent. We demonstrate that the technique scales up uniformly to allow static analysis of realistic language features, including tail calls, conditionals, mutation, exceptions, first-class continuations, and even garbage collection. In order to close the gap between formalism and implementation, we provide translations of the mathematics as running Haskell code for the initial development of our method.
解释其工作的函数式程序
DOI：
10.1145/2364527.2364579
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Perera R
通讯作者：
Perera R