Exploiting goal independence in the analysis of logic programs

✍ Scribed by Michael Codish; Maurice Bruynooghe; Maria García De La Banda; Manuel Hermenegildo

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 880 KB
• Volume: 32
• Category: Article
• ISSN: 0743-1066
• DOI: 10.1016/s0743-1066(96)00143-4

✦ Synopsis

This paper illustrates the use of a top-down framework to obtain goal independent analyses of logic programs, a task which is usually associated with the bottom-up approach. While it is well known that the bottom-up approach can be used, through the magic set transformation, for goal dependent analysis, it is less known that the top-down approach can be used for goal independent analysis. The paper describes two ways of doing the latter. We show how the results of a goal independent analysis can be used to speed up subsequent goal dependent analyses. However this speed-up may result in a loss of precision. The influence of domain characteristics on this precision is discussed and an experimental evaluation using a generic top-down analyzer is described. Our results provide intuition regarding the cases where a two phase analysis might be worthwhile. © Elsevier Science Inc., 1997 <1

1. Introduction

The framework of abstract interpretation [12] provides the basis for a semantic approach to data-flow analysis. A program analysis is viewed as a nonstandard semantics defined over a domain of data descriptions where the syntactic constructs in the program are given corresponding nonstandard interpretations. For a