An Algebraic Approach to Sharing Analysis of Logic Programs

Michael Codish, Vitaly Lagoon and Francesco Bueno   

The Journal of Logic Programming; 41 (2): 110-149, 2000


This paper describes an algebraic approach to the sharing analysis of logic programs based on an abstract domain of set logic programs. Set logic programs are logic programs in which the terms are sets of variables and unification is based on an associative, commutative, and idempotent equality theory. All of the basic operations required for sharing analyses, as well as their formal justification, are based on simple algebraic properties of set substitutions and set-based atoms. An ordering on set-based syntactic objects, similar to ``less general' on concrete syntactic objects, is shown to reflect the notion of ``less sharing' information. The (abstract) unification of a pair of set-based terms corresponds to finding their most general ACI1 unifier with respect to this ordering. The unification of a set of equations between set-based terms is defined exactly as in the concrete case, by solving the equations one by one and repeatedly applying their solutions to the remaining equations. We demonstrate that all of the operations in a sharing analysis have natural definitions which are both correct and optimal.

Available:    bibtex entry   compressed postscript

Related sites:   The conference version   PDF from the publisher   PDF from Scirus - scientific search engine

Michael Codish
The Department of Computer Science
Ben-Gurion University of the Negev
PoB 653, Beer-Sheva, 84105, Israel

© copyright notice