Partial evaluation (or program specialization) is a technique that transforms a program into another program, by pre-computing some of its operations. This kind of program transformation typically has been approached from two points of view. The first approach is offline partial evaluation. In offline partial evaluation, a process called binding-time analysis (BTA) is applied to the original program. This process determines, for every statement in the program, which input values will be known during specialization. The second approach is online partial evaluation. Using this approach, specialization is done without any previous analysis.
In this work, a BTA is developed for the logic programming language Mercury (http://www.cs.mu.oz.au/research/mercury/). This BTA is polyvariant (each of the original procedures may occur in several versions of the annotated program), and is based on the type information available in Mercury programs.
The proposed BTA works in two phases. In the first phase, binding times and the relations between them are represented in a symbolic way (without using a particular call pattern); this allows the BTA to perform a large part of the data-flow analysis independent of a particular call pattern. In the second phase, the annotations and the actual binding times are computed, by combining particular call patterns and the result of the first phase.
Thanks to the available mode information, the analysis is driven by a number of constraints between binding time variables. These constraints conveniently represent the dependencies between the values of the control variables associated to a goal and the goal’s input variables.
The approach is well formalized, and covers all the features of the language, including higher-order ones. One important question readers could think about is if this proposal would be applicable to a more established language, such as Prolog. In order to solve this question, the authors provide a complete example, to discuss to what extent the proposed analysis is also applicable in the context of Prolog, and how it could be applied.