© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Abstract matching can improve on abstract unification
Andy King and Mark Longley
Technical Report 4-95*, University of Kent, Computing Laboratory, University of Kent, Canterbury, UK, March 1995.Abstract
Analyses for sharing and freeness are important in the optimisation and parallelisation of logic programs. By using suitable abstract analogs for concrete operations like renaming, restriction, unification and extension sharing and freeness analysis can be constructed from a standard fixed-point framework. Extension is required in the clause exit mechanisms and is typically formulated in terms of restriction and matching. Matching also arises as goal-head unification in normalised programs in which the (formal) arguments of each clause head are distinct variables. Abstract matching, however, is rarely given special attention and is usually implemented by abstract unification. This paper remedies this, contributing a series of useful, practical and formally-justified abstract matching algorithms for the popular domains Share, Share x Free and Share x Free x Lin The matching algorithms are both useful and important because they can outperform their corresponding unification algorithms in both speed and precision.
Download publication
91 kbytes
Bibtex Record
@techreport{64,
author = {Andy King and Mark Longley},
title = {Abstract Matching Can Improve on Abstract Unification},
month = {March},
year = {1995},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1995/64},
address = {University of Kent, Canterbury, UK},
hensa_abstractfilename = {pub/misc/ukc.reports/comp.sci/abstracts/4-95},
hensa_ftpaddress = {unix.hensa.ac.uk},
hensa_reportfilename = {pub/misc/ukc.reports/comp.sci/reports/4-95.ps.Z},
institution = {University of Kent, Computing Laboratory},
number = {4-95*},
}