School of Computing

Lazy Set-Sharing Analysis

Xuan Li, Andy King, and Lunjin Lu

In Philip Wadler and Masimi Hagiya, editors, Eighth International Symposium on Functional and Logic Programming, volume 3945 of Lecture Notes in Computer Science, pages 182-196. Springer-Verlag, April 2006 Also see http://www.springer.de/comp/lncs/index.html.

Abstract

Sharing analysis is widely deployed in the optimisation, specialisation and parallelisation of logic programs. Each abstract unification operation over the classic Jacobs and Langen domain involves the calculation of a closure operation that has exponential worst-case complexity. This paper explores a new tactic for improving performance: laziness. The idea is to compute partial sharing information eagerly and recover full sharing information lazily. The net result is an analysis that runs in a fraction of the time of the classic analysis and yet has comparable precision.

Download publication 319 kbytes (PostScript)

Bibtex Record

@conference{2341,
author = {Xuan Li and Andy King and Lunjin Lu},
title = {Lazy {S}et-{S}haring {A}nalysis},
month = {April},
year = {2006},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {Also see http://www.springer.de/comp/lncs/index.html},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2006/2341},
    publication_type = {conference},
    submission_id = {25690_1138010737},
    booktitle = {Eighth International Symposium on Functional and Logic Programming},
    editor = {Philip Wadler and Masimi Hagiya},
    series = {Lecture Notes in Computer Science},
    publisher = {Springer-Verlag},
    refereed = {yes},
    volume = {3945},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014