We study the problem of an efficient and precise sharing analysis of (constraint) logic programs. After recognizing that neither plain Sharing nor its non-redundant (but equivalent) abstraction scale well to real programs, we consider the domain proposed by C. Fecht. This domain consists of a combination of Pos with a quite weak abstraction of Sharing. While verifying that this domain is truly remarkable, in terms of both precision and efficiency, we have revealed significant precision losses for several real programs. This loss concerns groundness, pair-sharing, linearity, but not freeness. (Indeed, we have proved that a wide family of abstractions of Sharing do not incur precision loss on freeness.) We define a simple domain for sharing analysis that supports the implementation of several widening techniques. In particular, with this domain it is straightforward to turn Fecht's idea into a proper widening. More precise widenings are also considered. However, in spite of thorough experimentation we found that the first widening we propose is hard to improve on, provided Pos is included in the domain. We show that when Pos is not included, a widening based on cliques of sharing pairs is preferred.

Widening Sharing / ZAFFANELLA E.; BAGNARA R.; HILL P. M.. - 1702 of LNCS(1999), pp. 414-431. ((Intervento presentato al convegno International Conference on Principles and Practice of Declarative Programming tenutosi a Paris, France nel September 29 - October 1, 1999.

Widening Sharing

ZAFFANELLA, Enea;BAGNARA, Roberto;
1999

Abstract

We study the problem of an efficient and precise sharing analysis of (constraint) logic programs. After recognizing that neither plain Sharing nor its non-redundant (but equivalent) abstraction scale well to real programs, we consider the domain proposed by C. Fecht. This domain consists of a combination of Pos with a quite weak abstraction of Sharing. While verifying that this domain is truly remarkable, in terms of both precision and efficiency, we have revealed significant precision losses for several real programs. This loss concerns groundness, pair-sharing, linearity, but not freeness. (Indeed, we have proved that a wide family of abstractions of Sharing do not incur precision loss on freeness.) We define a simple domain for sharing analysis that supports the implementation of several widening techniques. In particular, with this domain it is straightforward to turn Fecht's idea into a proper widening. More precise widenings are also considered. However, in spite of thorough experimentation we found that the first widening we propose is hard to improve on, provided Pos is included in the domain. We show that when Pos is not included, a widening based on cliques of sharing pairs is preferred.
9783540665403
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11381/2310477
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 11
social impact