In this paper we study the connection between the structure of relational abstract domains for program analysis and compositionality of the underlying semantics. Both can be systematically designed as solution of the ...
详细信息
ISBN:
(纸本)9781581134551
In this paper we study the connection between the structure of relational abstract domains for program analysis and compositionality of the underlying semantics. Both can be systematically designed as solution of the same abstract domain equation involving the same domain refinement: the reduced power operation. We prove that most well-known compositional semantics of imperative programs, such as the standard denotational and weakest precondition semantics can be systematically derived as solutions of simple abstract domain equations. This provides an equational presentation of both semantics and abstract domains for program analysis in a unique formal setting. Moreover both finite and transfinite compositional semantics share the same structure, and this allows us to provide consistent models for program manipulation.
We treat a program as an object of manipulation, determine items of program constancy, and simplify the program based on the constancy. Some motivation for program manipulation is presented, along with two examples of...
详细信息
ISBN:
(纸本)9781450374774
We treat a program as an object of manipulation, determine items of program constancy, and simplify the program based on the constancy. Some motivation for program manipulation is presented, along with two examples of “higher level optimization” written in an Algol-like language. A collection of program transformations and a model of the compilation process in terms of source-to-source transformations are presented. Finally a description of the application of these ideas to an existing programming language is given.
A method for combining decision procedures for several theories into a single decision procedure for their combination is described, and a simplifier based on this method is discussed. The simplifier finds a normal fo...
详细信息
A system of rules for transforming programs is described, with the programs in the form of recursion equations. An initially very simple, lucid, and hopefully correct program is transformed into a more efficient one b...
详细信息
An algorithm for prettyprinting is given. For an input stream of length n and an output device with linewidth m, the algorithm requires time O(n) and space O(m). The algorithm is described in terms of two parallel pro...
详细信息
暂无评论