Explanation Based Program Transformation

TL;DR

This paper introduces a novel technique for automatically transforming logic programs to eliminate redundant computations, inspired by explanation-based learning. By analyzing an example execution, the method identifies repeated sub-computations and uses this information to guide a fold-unfold transformation, leading to more efficient programs.

What Problem Does This Paper Address?

Many logic programs suffer from inefficiencies due to repeatedly computing the same sub-results. While techniques like lemma generation and tabulation exist, they often don't yield optimal performance. The classic fold-unfold transformation technique can address this, but it typically requires a human "Eureka step" to invent new procedures. This paper tackles the challenge of automating this process, specifically for programs where inefficiencies arise from identical subcomputations.

Methods

The core of the proposed method is an example-driven fold-unfold transformation. Here's how it works:

  1. Example Execution Analysis: The system takes an example input and executes the logic program to generate a proof tree.
  2. Identifying Redundancy: The proof tree is analyzed to find identical sub-computations that appear multiple times.
  3. Unfolding: The clause responsible for the redundant sub-computation is "unfolded" to expose the repeated calls more directly.
  4. Factoring: Identical sub-computations are identified and consolidated. This involves replacing repeated calls with a single call and ensuring the shared variables are correctly handled.
  5. Folding: The factored sub-computations are then "folded" into a new, more efficient predicate. This process is guided by the structure observed in the example's proof tree.

This approach is presented as an extension of explanation-based learning, where the example's proof structure actively controls the transformation process, enabling automation.

Datasets

Not discussed in the paper. The paper uses illustrative examples like Fibonacci numbers and the exponential function series expansion to demonstrate the technique.

Key Insights and Ideas

  • Example as a Guide: The key insight is that an example execution's proof tree can provide the necessary information to automate the fold-unfold transformation, eliminating the need for manual intervention or "Eureka" moments.
  • Bridging EBL and Program Transformation: The paper highlights a strong connection between explanation-based learning (EBL) and program transformation, suggesting that EBL's focus on learning from examples can be leveraged to guide program optimization.
  • Automation Potential: The method is designed to be automatable, which is a significant advantage over traditional fold-unfold techniques.
  • Handling Similar Subcomputations: The authors suggest that extensions to handle similar, not just identical, subcomputations might be feasible, opening up broader applications.
  • Restructuring for Efficiency: The paper emphasizes that restructuring the prooftree (e.g., by introducing new predicates) is crucial for obtaining truly operational and efficient predicates.

Key Results

The paper demonstrates the effectiveness of the technique through detailed examples:

  • Fibonacci Numbers: The method successfully transforms a naive Fibonacci program into a more efficient one by introducing a new predicate (fibi) that avoids redundant calculations.
  • Exponential Function Series: A similar transformation is shown for the exponential function series expansion, again eliminating redundant calls to power and fact.
  • Complex Fibonacci Variant: A more complex example involving a variant of Fibonacci computation also shows successful transformation, illustrating the technique's robustness.

The paper argues that the transformed programs are equivalent to the original ones but offer improved efficiency by eliminating repeated subcomputations.

Limitations and Future Work

  • Identical Subcomputations: The current method primarily addresses inefficiencies arising from identical subcomputations. The authors acknowledge that extending this to similar subcomputations (e.g., in the Towers of Hanoi problem where peg names differ) is an area for future work.
  • Automation of Generalization: While the core fold-unfold is automated, the paper hints that more complex reasoning capabilities might be needed for certain simplifications or generalizations, which are typical in program transformation systems.
  • Completeness: The paper touches upon the challenge of maintaining program completeness after transformations, suggesting that techniques from program transformation literature could be applied to prove equivalence and potentially remove inefficient original rules.
  • Broader Applicability: The authors believe the method could be extended to other types of programs and inefficiencies.

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{1989explanation,
  title = {{Explanation Based Program Transformation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
}

Loading related content...

Figure