© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Three Optimisations for Sharing
Jacob Howe and Andy King
Technical Report 11-01, University of Kent, Computing Laboratory, University of Kent at Canterbury, August 2001 Accepted to appear in Theory and Practice of Logic Programming subject minor corrections.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 lightweight optimisations for tracing sharing in combination with freeness and linearity, and proves their correctness. Correctness is established in the presence of rational trees in terms of a novel abstraction operator. A method for pruning intermediate sharing abstractions is also proposed. The cost of these optimisations ranges from zero to linear (even before the efficiency gains that follow from improved precision), therefore some, if not all, of these optimisations will be of interest to an implementor.
Download publication
372 kbytes
(PostScript)
Bibtex Record
@techreport{1309,
author = {Jacob Howe and Andy King},
title = {{Three Optimisations for Sharing}},
month = {August},
year = {2001},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {Accepted to appear in Theory and Practice of Logic Programming subject minor corrections.},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2001/1309},
publication_type = {techreport},
submission_id = {10736_1007542963},
number = {11-01},
address = {University of Kent at Canterbury},
institution = {University of Kent, Computing Laboratory},
}