Title: On the design of a correct freeness analysis for logic programs
Authors: Codish, Michael ×
Dams, Denis
File, Gilberto
Bruynooghe, Maurice #
Issue Date: Sep-1996
Publisher: Elsevier science inc
Series Title: Journal of logic programming vol:28 issue:3 pages:181-206
Abstract: Several proposals for computing freeness information for logic programs have been put forward in the recent literature. The availability of such information has proven useful in a variety of applications, including parallelization of Prolog programs, optimizations in Prolog compilers, as well as for improving the precision of other analyses. While these proposals have illustrated the importance of such analyses, they lack formal justification. Moreover, several have been found incorrect. This paper introduces a novel domain of abstract equation, systems describing possible sharing and definite freeness of terms in a system of equations. A simple and intuitive abstract unification algorithm is presented, providing the core of a correct and precise sharing and freeness analysis for logic programs. Our contribution is not only a correct algorithm, but perhaps primarily, the application of a systematic approach in which it is derived by mimicking each step in a suitable concrete unification algorithm. Consequently, the abstract algorithm is intuitive-as it resembles the concrete algorithm. It is amenable to formal justification-as the proof of correctness is reduced to showing that each step in the concrete algorithm is mimicked by a corresponding step in the abstract algorithm. Finally, it is precis as each step mimics only those situations which can arise in the concrete algorithm.
ISSN: 0743-1066
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science