For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Transformation of Strictness-Related Analyses Based on Abstract Interpretation
Mizuhito OGAWA Satoshi ONO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1991/02/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Full Text: PDF>>
This paper newly proposes HOMomorphic Transformer (HOMT) in order to formalize relations among strictness-related analyses (SRAs) on first-order functional programs. A HOMT is defined to be a composition of special instances of abstract interpretation, and has enough ability to treat known SRAs including head/tail/total strictness detection on nonflat domains. A set of HOMTs, furthermore, is an algebraic space such that some composition of HOMTs can be reduced to a simpler HOMT. This structure gives a transformational mechanism between various SRAs, and further clarifies the equivalence and the hierarchy among them. First, we show a construction of a HOMT as a composition of Unit-HOMTs (U-HOMTs) which are specified by quadruplet representations. Second, algebraic relations among HOMTs are shown as reduction rules among specific pairs of quadruplet representations. Thus, hierarchy among HOMTs can be clarified by finding some adequate quadruplet representation which bridges a HOMT to the other. Third, various SRAs are formalized as HOMTs in either forward or back-ward manners. They are also shown to be safe under unified discussions. Finally, their equivalence and hierarchy are examined in terms of an algebraic structure of HOMTs.