Transformation of Strictness-Related Analyses Based on Abstract Interpretation

Mizuhito OGAWA  Satoshi ONO  

IEICE TRANSACTIONS on Information and Systems   Vol.E74-D   No.2   pp.406-416
Publication Date: 1991/02/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Bio-Cybernetics

Full Text: PDF>>
Buy this Article

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.