LIVE-STRUCTURE DATA-FLOW ANALYSIS FOR PROLOG

For the class of applicative programming languages, efficient methods for reclaiming the memory occupied by released data structures constit ute an important aspect of current implementations. The present articl e addresses the problem of memory reuse for logic programs through pro gram analysis rather than by run-time garbage collection. The aim is t o derive run-time properties that can be used at compile time to speci alize the target code for a program according to a given set of querie s and to automatically introduce destructive assignments in a safe and transparent way so that fewer garbage cells are created. The dataflow analysis is constructed as an application of abstract interpretation for logic programs. An abstract domain for describing structure-sharin g and liveness properties is developed as are primitive operations tha t guarantee a sound and terminating global analysis. We explain our mo tivation for the design of the abstract domain, make explicit the unde rlying implementation assumptions, and discuss the precision of the re sults obtained by a prototype analyzer.