Conventional implementations of applicative programming languages perform garbage collection at runtime in a nonoptimal way. Eventually, a request for new storage cannot be satisfied because of space exhaustion, at which moment unused storage must be reclaimed, taking considerable time. To reduce the problem, Mulkers et al. propose optimizations for memory reuse via compile-time analysis. The new method still requires garbage collection, but the number and duration of such interruptions is minimized.

Global flow analysis determines at compile-time the type and scope of data structures that are dynamically created during execution. The proposed live-structure analysis is conducted to derive which structures will be referenced and which ones are dead, an analysis based on abstract interpretation. Section 2 specifies program properties that are of interest to structure liveness. Section 3 discusses the abstract interpretation of logic programs and gives correctness conditions for the primitive abstract operations that guarantee soundness. Section 4 introduces a variant of standard concrete semantics. The main body, section 5, illustrates the primitive operations of unification and procedure entry and exit, and demonstrates that they indeed mimic standard-conforming implementations. Section 6 explains the usefulness of liveness information, which is contrasted with the design alternatives and cost/precision tradeoffs of section 7. Finally, section 8 discusses implementation issues and empirical results obtained by a prototype. Section 9 presents related work.

The writing style, theoretical approach, and numerous long-winded definitions render the paper hard to read. Also, it is not self-contained; to understand the improvements, one must know the literature, particularly Bruynooghe and Janssens. Approaches to liveness analysis are inherently limited, since liveness cannot be derived completely by compile-time analysis. Garbage collection remains necessary, and the paper clarifies why. What is missing is a sense of how much garbage collection is saved with the optimizations described.

Despite these minor shortcomings, the paper is of considerable value for those wishing to offer logic programming languages without the conventional inefficiencies. The authors demonstrate with examples where a compiler can free and reuse space. These examples make it plausible that liveness analysis is effective, and the reader becomes convinced that the resulting object code compares well with imperative languages. The publication makes good use of logic program sources and figures and explains recursive types with back-arcs in their type graphs. Especially valuable are discussions of design alternatives, limitations of the algorithms, and opportunities to trade one design parameter for another. The authors make simplifying assumptions and justify them by explaining why the lost precision is not worth the extra compile-time or complexity. The paper should be required reading for Prolog implementors.