Quotienting Share for Dependency Analysis

Publication TypeConference Paper
Year of Publication1999
AuthorsKing A, Smaus J-G, Hill PM
EditorS. Swierstra D
Conference NameProceedings of the European Symposium on Programming
ISBN Number3-540-65699-5
Keywordsabstract interpretation, groundness analysis, logic programming, mode analysis, quotient, sharing analysis, software verification, static analysis

Def, the domain of definite Boolean functions, expresses (sure) dependencies between the program variables of, say, a constraint program. Share, on the other hand, captures the (possible) variable sharing between the variables of a logic program. The connection between these domains has been explored in the domain comparison and decomposition literature. We develop this link further and show how the meet (as well as the join) of Def can be modelled with efficient (quadratic) operations on Share. Further, we show how by compressing and widening Share and by rescheduling meet operations, we can construct a dependency analysis that is surprisingly fast and precise, and comes with time and space-performance guarantees. Unlike some other approaches, our analysis can be coded straightforwardly in Prolog.

We are a passionate team of experts. Do not hesitate to let us have your feedback:
You may be surprised to discover just how much your suggestions matter to us.