Skip to main content

Quotienting Share for Dependency Analysis: 8th European Symposium on Programming, ESOP’99 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS’99 Amsterdam, The Netherlands, March 22–28, 1999 Proceedings

King, Andy and Smaus, Jan-Georg and Hill, Pat (1999) Quotienting Share for Dependency Analysis: 8th European Symposium on Programming, ESOP’99 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS’99 Amsterdam, The Netherlands, March 22–28, 1999 Proceedings. In: Swierstra, Doaitse, ed. Programming Languages and Systems. Lecture Notes in Computer Science, 1576 . Springer, pp. 59-73. ISBN 978-3-540-65699-9. (doi:10.1007/3-540-49099-X_5) (KAR id:37618)

Abstract

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 modeled 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.

Item Type: Book section
DOI/Identification number: 10.1007/3-540-49099-X_5
Subjects: A General Works
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Andy King
Date Deposited: 13 Dec 2013 14:44 UTC
Last Modified: 16 Nov 2021 10:14 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/37618 (The current URI for this page, for reference purposes)

University of Kent Author Information

King, Andy.

Creator's ORCID: https://orcid.org/0000-0001-5806-4822
CReDIT Contributor Roles:

Smaus, Jan-Georg.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.