A dynamic approach to characterizing termination of general logic programs

Yi-Dong Shen, Jia-Huai You, Li-Yan Yuan, Samuel S. P. Shen, Qiang Yang

TL;DR

This paper shifts the focus of logic program termination analysis from "static" source code inspection to "dynamic" execution behavior. By introducing generalized SLDNF-trees and the concept of loop goals, the authors provide a necessary and sufficient condition for identifying infinite loops, offering a more precise way to characterize when a program will—or won't—actually stop.

What Problem Does This Paper Address?

In logic programming (like Prolog), recursion is the primary engine of computation. However, this power comes with a major risk: infinite loops. Determining if a program will terminate is a classic "undecidable" problem—there is no magic algorithm that works for every possible program.

Traditionally, researchers have used static analysis. They look at the source code before it runs, trying to find "level mappings" or "norms" (mathematical proofs that some value decreases with every recursive call). While effective, these methods are often too conservative. They might flag a program as potentially non-terminating even if it would run perfectly fine in practice, especially when complex negation is involved. The authors aim to bridge this gap by looking at the dynamic features of the program's execution path (derivation).

Methods

The authors introduce two major theoretical tools:

  1. Generalized SLDNF-trees: Standard SLDNF-trees (the mathematical representation of how a logic program searches for an answer) have a technical flaw: for some programs, a standard tree simply doesn't exist. The authors propose a "generalized" version that mimics how Prolog actually works—specifically, how it "prunes" the search space once a negative subgoal succeeds. This ensures a tree exists for any general logic program.
  2. Loop Goals: This is the heart of their dynamic approach. They define a "loop goal" based on two criteria:
  3. Ancestry: The new goal must be a descendant of a previous goal in the execution chain.
  4. Projection: The new goal must be "larger" than or equal to its ancestor in terms of its symbol structure (using a concept called symbol strings and projections).

By applying Higman’s Lemma—a mathematical theorem about sequences of strings—they prove that if a program runs forever, it must eventually produce a sequence of these loop goals.

Datasets

As a theoretical paper in computer science, this work does not use large-scale empirical datasets or benchmarks. Instead, it uses formal proofs and specific, hand-crafted logic programs (referred to as $P_1$ and $P_2$ in the text) to demonstrate where previous models fail and where their new "generalized" approach succeeds.

Key Insights and Ideas

  • The "Smoking Gun" of Non-termination: The paper identifies that infinite derivations aren't just random; they result from either repeating the same goal or repeating a goal while its arguments grow recursively in size. "Loop goals" capture both behaviors.
  • Prolog-Style Pruning is Key: By incorporating the way Prolog handles negation (stopping a search once a "cut" or success is found), the authors created a more realistic model of execution than previous purely theoretical frameworks.
  • Necessary and Sufficient: Most static analyses only provide a "sufficient" condition (if the proof holds, it terminates). This paper provides an "if and only if" characterization, meaning their definition of loop goals perfectly matches the definition of an infinite execution path.

Key Results

  • Theorem 3.5: The authors successfully proved that a derivation is infinite if and only if it contains an infinite sequence of loop goals.
  • Theorem 4.3: They established a formal characterization of termination: a program terminates for a specific query if and only if its generalized SLDNF-tree contains no infinite paths of loop goals.
  • Practical Application: The authors mention they have already used this theory to develop an algorithm that predicts non-termination. Their experiments showed this approach could identify non-terminating programs that static analysis might miss.

Limitations and Future Work

  • Floundering: The paper explicitly sets aside the issue of "floundering"—a state where a logic program cannot proceed because a negative subgoal contains variables that aren't grounded.
  • Runtime Overhead: Because this is a dynamic approach, identifying loop goals while a program is running could introduce computational overhead. The authors suggest this is best used as a "debugging tool" rather than a constant monitor.
  • Tabling: The authors aim to extend this work to Tabled Logic Programming, a technique that memoizes (saves) previous results to avoid re-computation, which presents its own unique termination challenges.

Summary updated

Abstract

We present a new characterization of termination of general logic programs. Most existing termination analysis approaches rely on some static information about the structure of the source code of a logic program, such as modes/types, norms/level mappings, models/interargument relations, and the like. We propose a dynamic approach that employs some key dynamic features of an infinite (generalized) SLDNF-derivation, such as repetition of selected subgoals and recursive increase in term size. We also introduce a new formulation of SLDNF-trees, called generalized SLDNF-trees. Generalized SLDNF-trees deal with negative subgoals in the same way as Prolog and exist for any general logic programs.
BibTeX
@article{shen2003dynamic,
  author = {Yi-Dong Shen and Jia-Huai You and Li-Yan Yuan and Samuel S. P. Shen and Qiang Yang},
  title = {{A dynamic approach to characterizing termination of general logic programs}},
  journal = {ACM Transactions on Computational Logic},
  year = {2003},
  doi = {10.1145/937555.937556},
}

Loading related content...

Figure