Precise pair-sharing analysis of logic programs

Vitaly Lagoon, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

8 Citations (Scopus)

Abstract

The paper presents a novel approach to pair-sharing analysis of logic programs. The pair-sharing domain ASub of Søndergaard is known to be more efficient than the setsharing domain Sharing of Jacobs and Langen and gains accuracy because of linearity tracking. However, it is less accurate because of weaker groundness information, and the fact that it loses track of where new groundness eliminates sharing. In this paper we present a new domain which inherits the advantages of both ASub and Sharing and is uniformly more accurate in terms of pair-sharing than each of the two domains. The proposed domain expresses pair-sharing in terms of existence of traversable paths in relation graphs derived from program constraints. Each edge of a relation graph has an attached groundness formula which defines under what groundness conditions it still causes sharing. This allows the domain to maintain information about when groundness can eliminate sharing. Relation graphs are augmented by separate groundness information (usually Def or Pos). The groundness analysis and groundness formulae can be represented using efficient ROBDD methods.

Original languageEnglish
Title of host publicationProceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02)
PublisherAssociation for Computing Machinery (ACM)
Pages99-108
Number of pages10
ISBN (Print)1581135289, 9781581135282
Publication statusPublished - 1 Jan 2002
EventProceedings of the Fourth ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02) - Pittsburg, PA, United States of America
Duration: 6 Oct 20028 Oct 2002

Publication series

NameProceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02)

Conference

ConferenceProceedings of the Fourth ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02)
Country/TerritoryUnited States of America
CityPittsburg, PA
Period6/10/028/10/02

Keywords

  • Program analysis
  • Sharing

Cite this