Explanation Based Program Transformation

Maurice Bruynooghe, Luc De Raedt, Danny De Schreye

Abstract: Fold-unfold is a well known program transformation technique. Its major drawback is that folding requires an Eureka step to invent new procedures. In the context of logic programming, we present a technique where the folding is driven by an example. The transformation is aimed at programs suffering from inefficiencies due to the repetition of identical subcomputations. The execution of an example is analysed to locate repeated subcomputations. Then the structure of the example is used to control a fold-unfold-transformation of the program. The transformation can be automated. The method can be regarded as an extension of explanation based learning.

Introduction

In the world of logic programming (like Prolog), it is easy to write "elegant" code that is computationally disastrous. A classic example is the naive Fibonacci sequence: to calculate $fib(n)$, the program recursively calculates $fib(n-1)$ and $fib(n-2)$. This leads to a massive explosion of redundant work, as the same values are recalculated thousands of times.

Computer scientists have long used fold-unfold transformation to fix this. By "unfolding" definitions and then "folding" them back into new, more efficient recursive structures, redundancy can be eliminated. However, the "folding" step usually requires a "Eureka" step—a human programmer must intuitively "invent" a new helper predicate that captures the optimized state. This paper introduces Explanation Based Program Transformation (EBPT) to bridge this gap by automating the invention of these predicates.

Methodology

EBPT draws inspiration from Explanation Based Learning (EBL) in AI, but instead of learning new rules, it restructures existing ones. The process follows these steps:

  1. Trace an Example: Run the inefficient program with a specific input (e.g., fib(5)).
  2. Analyze the Proof Tree: Look at the "explanation" (the proof tree) of how the result was reached to identify subgoals that appear multiple times.
  3. Unfold and Factor: Use the structure of the example to "unfold" the program until the redundant subgoals appear side-by-side in a single goal statement, then "factor" them by merging identical calls.
  4. Fold into New Predicates: Automatically define a new, more efficient recursive predicate based on the shared variables and repeating structure.
  5. Generalize: The transformation derived from the specific example is then generalized for any input $n$.
Figure 1: Proof tree for the query fib(5,F) showing redundant subcomputations.

Key Results and Evaluation

The method was evaluated using classic algorithmic benchmarks known for redundancy, including Fibonacci numbers, exponential series expansion ($e^x$), and complex Fibonacci variants. The core "aha" moment is that a specific execution trace contains all the information needed to find the optimal general structure; the example serves as a "map" to guide the transformation.

Figure 3: Proof tree for a complex Fibonacci variant f(20,F).

The authors successfully demonstrated that their system can:

  • Automatically derive linear-time algorithms from exponential-time specifications. For Fibonacci, the system produces a version that passes the result of the previous step forward, mimicking an iterative loop.
  • Handle complex numerical methods where subcomputations involve complex terms rather than simple numbers.
  • Maintain Program Equivalence: The new, transformed set of rules is proven to be logically equivalent to the original, ensuring correctness.

Limitations and Future Work

Currently, the method requires subcomputations to be identical in the example trace to trigger an optimization. The authors note that many problems (like the Towers of Hanoi) have similar but not identical subcomputations. Extending the method to handle "similarity" via generalization is a suggested next step. Additionally, while the transformation is automated, choosing which example to use and which part of the tree to focus on still involves some heuristics. Implementing a fully general system that handles all edge cases of logic programming remains a significant engineering challenge.

Summary updated

Abstract

Fold-unfold is a well known program transformation technique. Its major drawback is that folding requires an Eureka step to invent new procedures. In the context of logic programming, we present a technique where the folding is driven by an example. The transformation is aimed at programs suffering from inefficiencies due to the repetition of identical subcomputations. The execution of an example is analysed to locate repeated subcomputations. Then the structure of the example is used to control a fold-unfold-transformation of the program. The transformation can be automated. The method can be regarded as an extension of explanation based learning.
BibTeX
@inproceedings{bruynooghe1989explanation,
  author = {Maurice Bruynooghe and Luc De Raedt and Danny De Schreye},
  title = {{Explanation Based Program Transformation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
}
Figure