Abstract interpretation in weak powerdomains
Robert Muller, Yuli Zhou · 1992
We introduce a class of semantic domains, weak powerdomains, that are intended to serve as value spaces for abstract interpretations in which safety is a concern. We apply them to the analysis of PCF programs. In the classical abstract interpretation approach, abstract domains are constructed explicitly and the abstract semantics is then related to the concrete semantics. In the approach presented here, abstract domains are derived directly from concrete domains. The conditions for deriving the domains are intended to be as general as possible while still guaranteeing that the derived domain has sufficient structure so that it can be used as a basis for computing correct information about the concrete semantics. We prove three main theorems, the last of which ensures the correctness of abstract interpretation of PCF programs given safe interpretations of the constants. This generalizes earlier results obtained for the special case of strictness analysis.