文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > A complete transformational toolkit for compilers
侵权投诉

A complete transformational toolkit for compilers

and their applications. SMC is sponsored by the Netherlands Organization for Scientific Research (NWO). CWI is a member of

A Complete Transformational Toolkit for Compilers

1

Introduction

In an earlier paper[18], one of the present authors presented a preliminary account of an equational logic called PIM. PIM is intended to function as a“transformational toolkit” to be used by compilers and analysis tools for imperative languages. In a nutshell, PIM consists of the untyped lambda calculus extended with an algebraic rewriting system that characterizes the behavior of lazy stores[9] and generalized conditionals. Together, these constructs are suf cient to model the principal dynamic semantic elements of most Algol-class languages. Translation of programs in most such languages to PIM is straightforward; programs can then be formally manipulated by reasoning about their PIM analogues. Moreover, the graph representations of various PIM normal forms can be manipulated in a manner similar to intermediate representations commonly used in optimizing compilers. As with other intermediate representations, the PIM form of the program can serve as a more suitable starting point for subsequent analysis than the program text itself. Unlike other such representations, however, P IM has a strong formal foundation and permits a number of different semantics-preserving manipulations to be carried out in the same framework. A major question left open in[18] was whether there existed a complete equational axiomatization of PIM’s semantics. In this paper, we answer this question in the af rmative for PIM’s core algebraic component, PIMt, under the assumption of certain reasonable restrictions on term formation. Formally, we show that there exists an ! -complete equational axiomatization of PIM’s nal algebra semantics. Obtaining a positive answer to the completeness question is, we believe, quite important, since it means that we can be assured that our transformational toolkit has an adequate supply of tools. In[18], it was shown that many aspects of the construction and manipulation of compiler intermediate representations could be expressed by partially evaluating PIM graphs using rewriting rules formed from oriented instances of PIM equations. Until now, however, we could not be certain that all the equations required to manipulate arbitrary programs were present (with or without restrictions on term formation). Obtaining a complete equational axiomatization for PIM is also an important prerequisite to designing a decision procedure. We are aware of only a few prior completeness results for logics for imperative languages: Mason and Talcott[32] show that their logic for reasoning about equivalence in a Lisp-like (rather than Algol-class) language is complete; however, unlike PIM, their logic is a sequent calculus, rather than an equational system. Hoare et al.[

24] present a partial completeness result for an equational logic; however, their result does not hold for the cases where addresses or stores are unknowns, i.e., can be represented by variables. For program transformations commonly required in optimizing compilers, it is extremely important that these latter cases be addressed. Although the merits of equational reasoning for programs have been widely touted[2, 26, 35, 24, 27], results characterizing the power of formal systems required for such reasoning appear to be few and far between. Similarly, while partial evaluation has often been advocated as a means for optimizing programs[14, 15, 10, 7, 38], it is unusual to nd a precise characterization of the transformational capabilities that a particular partial evaluator implements. In the sequel, we systematically derive the complete PIM logic as the culmination of a sequence of increasingly powerful equational systems starting from a straightforward“interpreter” for P IM’s term language. While this approach to developing a logic is not new, it appears to be undertaken only

2

上一页第4页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email