Skip to main content

Three Optimisations for Sharing

Howe, Jacob M., King, Andy (2003) Three Optimisations for Sharing. Theory and Practice of Logic Programming, 3 (2). pp. 243-257. ISSN 1471-0684. (doi:10.1017/S1471068402001497) (KAR id:37579)

Abstract

In order to improve precision and efficiency sharing analysis should track both freeness and linearity. The abstract unification algorithms for these combined domains are suboptimal, hence there is scope for improving precision. This paper proposes three optimisations for tracing sharing in combination with freeness and linearity. A novel connection between equations and sharing abstractions is used to establish correctness of these optimisations even in the presence of rational trees. A method for pruning intermediate sharing abstractions to improve efficiency is also proposed. The optimisations are lightweight and therefore some, if not all, of these optimisations will be of interest to the implementor.

Item Type: Article
DOI/Identification number: 10.1017/S1471068402001497
Uncontrolled keywords: abstract interpretation; sharing analysis; freeness; linearity and rational trees.
Subjects: A General Works
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Andy King
Date Deposited: 12 Dec 2013 19:50 UTC
Last Modified: 16 Nov 2021 10:14 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/37579 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

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