Name
Abstract | ||
|---|---|---|
We investigate Jacobs and Langen's Sharing domain, introduced for the analysis of variable sharing in logic programs, and show that it is isomorphic to Marriott and Søndergaard's Pos domain, introduced for the analysis of groundness dependencies. Our key idea is to view the sets of variables in a Sharing domain element as the models of a corresponding Boolean function. This leads to a recasting of sharing analysis in terms of the property of “not being affected by the binding of a single variable.” Such an “unaffectedness dependency” analysis has close connections with groundness dependency analysis using positive Boolean functions. This new view improves our understanding of sharing analysis, and leads to an elegant expression of its combination with groundness dependency analysis based on the reduced product of Sharing and Pos. It also opens up new avenues for the efficient implementation of sharing analysis, for example using reduced order binary decision diagrams, as well as efficient implementation of the reduced product, using domain factorizations. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1145/330249.330252 | ACM Trans. Program. Lang. Syst. |
Keywords | Field | DocType |
dataflow analysis,sharing analysis,domain factorization,abstract interpretation,boolean functions,domain element,variable sharing,unaffectedness dependency,program analysis,groundness dependency analysis,groundness analysis,global analysis,efficient implementation,reduced product,groundness dependency,reduced order binary decision,pos domain,logic program,languages,dependence analysis,boolean function | Boolean function,Programming language,Computer science,Abstract interpretation,Binary decision diagram,Theoretical computer science,Isomorphism,Reduced product,Invariant (mathematics),Logic programming,Program analysis | Journal |
Volume | Issue | ISSN |
21 | 5 | 0164-0925 |
Citations | PageRank | References |
29 | 0.94 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Codish | 1 | 1048 | 53.99 |
| Harald Søndergaard | 2 | 858 | 79.52 |
| Peter J. Stuckey | 3 | 4368 | 457.58 |