Live-structure Analysis for Logic Programming Languages with Declarations

Live-structure analysis addresses the problem of memory reuse for logic programs through program analysis rather than by runtime garbage collection. The present paper focuses on pure logic programs with declarations of modes, types, and determinism. The analysis is based on previous work for pure Prolog but introduces important innovations. First, the liveness analysis is extended to consider not only forward liveness but also backward liveness (i.e., during backtracking by the program). This allows us to identify the calls with exclusive access to some parts of the data-structures. Second, the efficiency of the analysis is reached not only by exploiting the information provided by the declarations, but also by splitting the analysis in a goal-independent and a goal-dependent phase (as proposed by Codish et al.)