Li, Xuan, King, Andy, Lu, Lunjin (2006) Correctness of Closure Collapsing (appendix to conference submission). Lecture Notes in Computer Science, 4079/2. Report number: 10.1007/11799573_13. University of Kent, School of Computing, University of Kent, Canterbury, CT2 7NF ISBN 978-3-540-36635-5. (doi:10.1007/11799573_13) (KAR id:14487)
Postscript
Language: English |
|
Download this file (Postscript/369kB) |
Preview |
Request a format suitable for use with assistive technology e.g. a screenreader | |
Official URL: http://dx.doi.org/10.1007/11799573_13 |
Abstract
A description in the Jacobs and Langen domain is a set of sharing groups where each sharing group is a set of program variables. The presence of a sharing group in a description indicates that all the variables in the group can be bound to terms that contain a common variable. The expressiveness of the domain, alas, is compromised by its intractability. Not only are descriptions potentially exponential in size, but abstract unification is formulated in terms of an operation, called closure under union, that is also exponential. This paper shows how abstract unification can be reformulated so that closures can be collapsed in two senses. Firstly, one closure operation can be folded into another so as to reduce the total number of closures that need to be computed. Secondly, the remaining closures can be applied to smaller descriptions. Therefore, although the operation remains exponential, the overhead of closure calculation is reduced. Experimental evaluation suggests that the cost of analysis can be substantially reduced by collapsing closures.
Item Type: | Research report (external) |
---|---|
DOI/Identification number: | 10.1007/11799573_13 |
Uncontrolled keywords: | Sharing analysis, abstract interpretation, closures |
Subjects: | Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming, |
Divisions: | Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing |
Depositing User: | Andy King |
Date Deposited: | 24 Nov 2008 18:04 UTC |
Last Modified: | 05 Nov 2024 09:48 UTC |
Resource URI: | https://kar.kent.ac.uk/id/eprint/14487 (The current URI for this page, for reference purposes) |
- Link to SensusAccess
- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV
- Depositors only (login required):