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
A complete transformatio... 暂无评价 48页 免费 Toward a complete transf.....for the verification of PIM- a transformational toolkit for compilers隐藏>> ...
A complete transformatio... 暂无评价 48页 免费 Toward a complete transf.....for the verification of PIM- a transformational toolkit for compilers隐藏>> ...
热门文档