PROLEARN: Towards a Prolog Interpreter that Learns

Armand Prieditis, Jack MostowAAAI 1987

Introduction

Traditional programming language interpreters are static entities; they execute code identically regardless of repetition or task frequency. In logic programming environments like Prolog, the primary performance bottleneck is the search process. When an interpreter processes a query, it must navigate complex trees of subroutines and facts, often encountering numerous dead ends.

Presented at AAAI-87, PROLEARN is an experimental Prolog interpreter designed to mitigate this bottleneck by "learning" from its own execution traces. By integrating Explanation-Based Generalization (EBG) with partial evaluation, the system dynamically creates specialized, high-performance versions of subroutines, effectively optimizing itself for specific task domains.

Methodology

PROLEARN transforms execution experience into performance gains through two primary techniques:

  1. Explanation-Based Generalization (EBG): Upon successful execution of a subroutine, PROLEARN treats the resulting "proof" or execution trace as a template. It generalizes this trace by replacing specific constants with variables while preserving the underlying logical structure. This results in a "special case" rule that is logically sound but significantly faster to execute, as it bypasses redundant intermediate steps.
  2. Partial Evaluation (PE): Rules generated via EBG can be verbose. PROLEARN applies partial evaluation to "clean up" these rules—pre-calculating arithmetic (e.g., simplifying 12 is X * 4 to X = 3), eliminating tautologies, and streamlining variable bindings.

These learned rules are automatically prepended to the database, ensuring the interpreter attempts the optimized shortcuts before reverting to standard, computationally expensive versions.

Experimental Evaluation

The authors evaluated PROLEARN using four benchmark Prolog programs:

  • safe_to_stack: A logic puzzle involving physical properties like volume and density.
  • Towers of Hanoi (move): A classic recursive mathematical puzzle.
  • member: A standard utility for list membership.
  • equiv: A program testing the equivalence of boolean expressions.

Results and Discussion

The quantitative results demonstrate significant algorithmic improvements, particularly for programs with complex search spaces.

Table 1: Performance speedup factors and branching characteristics for various Prolog queries under PROLEARN.

As shown in Table 1, the most dramatic improvement occurred in the Towers of Hanoi (move) query, where the combination of EBG and partial evaluation yielded a 94x speedup. This was achieved by eliminating costly recursive calls and pre-calculating moves. The safe_to_stack problem similarly saw a 23x speedup.

The Utility Problem and Branching Factors

A key insight from the study is that learning is not universally beneficial. In the member example, PROLEARN generated a new rule for every list position encountered. Over time, the overhead of checking these numerous learned rules caused the interpreter to perform slower than the original unoptimized code—a phenomenon known as the "Utility Problem."

Furthermore, the data suggests that speedups are most significant in programs with a high "average branching factor." In deterministic programs (branching factor of 1), the overhead of the learning mechanism often outweighs the execution benefits.

The Meta-Interpreter Penalty

Despite these algorithmic gains, a major implementation hurdle remains. PROLEARN was implemented as a meta-interpreter (a Prolog program interpreting other Prolog programs), making it inherently slower than native Prolog. Even with a 94x algorithmic speedup, the overall system remained significantly slower than standard, non-adaptive Prolog engines. This indicates that for such techniques to be practical, they must be integrated directly into the low-level execution engine.

Conclusion and Future Work

While PROLEARN demonstrates the potential for adaptive logic programming, it faces several limitations. It currently cannot handle control flow symbols like cut or side effects (I/O), which complicate the guarantee of logical equivalence in generalized rules.

Future research should focus on "selective learning"—developing filters to predict the "learning worth" of a rule based on its execution cost and expected future utility. Additionally, refined rule placement strategies are needed to prevent learned rules from inadvertently masking intended program behaviors.

Summary updated

BibTeX
@inproceedings{prieditis1987prolearn,
  author = {Armand Prieditis and Jack Mostow},
  title = {{PROLEARN: Towards a Prolog Interpreter that Learns}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure