Please use this identifier to cite or link to this item:
doi:10.22028/D291-25805
Title: | Efficient and precise sharing domains for logic programs |
Author(s): | Fecht, Christian |
Language: | English |
Year of Publication: | 1996 |
SWD key words: | Technische Informatik Application sharing |
DDC notations: | 004 Computer science, internet |
Publikation type: | Report |
Abstract: | Sharing information between logical variables is crucial for a lot of analyses of logic programs, e.g., freeness analysis, detection of And-parallelism, and occur-check. Therefore, the development of accurate sharing domains has attracted a lot of research. The sharing domain bf JL of Jacobs/Langen, which represents substitutions by powersets of variables, is considered one of the most precise sharing domains. However, it is too inefficient in practice; lots of programs cannot be analyzed in reasonable time. Improvements of bf JL, by adding auxiliary information like linearity, suffer from the same inefficiency, too. To improve upon this situation, we systematically derived a new sharing domain mathorddownarrowbf JL from bf JL which represents variables by downward closed powersets of variables. We combined mathorddownarrowbf JL with the groundness domain bf POS. Both bf JL and the new domain mathorddownarrowbf JL+bf POS have been implemented with the help of the Prolog analyzer generator GENA. In order to study the impact of linearity, we also implemented the abstract domains bf JL+bf LIN and mathorddownarrowbf JL+bf POS+bf LIN. The new domains are much more efficient as their counterparts bf JL and bf JL+bf LIN, respectively. Even more important, they can analyze even largest real-world programs in reasonable time. Surprisingly, the new sharing domains seem to have the same precision than bf JL and bf JL+bf LIN in practice. |
Link to this record: | urn:nbn:de:bsz:291-scidok-3581 hdl:20.500.11880/25861 http://dx.doi.org/10.22028/D291-25805 |
Series name: | Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes |
Series volume: | 1996/04 |
Date of registration: | 23-Jun-2005 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
fb14-96-04.pdf | 197,92 kB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.