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

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 which 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.

Introduction

In logic programming, 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. Traditionally, researchers have relied on static analysis, inspecting source code for "level mappings" or "norms" to prove that some value decreases with every recursive call. While effective, these methods are often too conservative, flagging programs as non-terminating even if they would run correctly in practice, particularly when complex negation is involved.

This work shifts the focus from static inspection to dynamic execution behavior. By introducing generalized SLDNF-trees and the concept of loop goals, we provide a necessary and sufficient condition for identifying infinite loops, offering a more precise characterization of program termination.

Theoretical Framework: Generalized SLDNF-Trees

Standard SLDNF-trees—the mathematical representation of how a logic program searches for an answer—possess a technical flaw: for certain programs, a standard tree simply does not exist. We propose "generalized" SLDNF-trees that mimic Prolog's actual execution model, specifically how it handles negation and "prunes" the search space once a negative subgoal succeeds. This ensures a tree exists for any general logic program.

Generalized SLDNF-trees illustrating the handling of negative subgoals and pruning through sub-computations.

Characterizing Non-Termination via Loop Goals

The heart of this dynamic approach is the loop goal. A loop goal is defined by two primary criteria:

  1. Ancestry: The new goal must be a descendant of a previous goal in the execution chain.
  2. Projection: The new goal must be "larger" than or equal to its ancestor in terms of its symbol structure.

Infinite derivations are not random; they result from either repeating the same goal or repeating a goal while its arguments grow recursively in size. By applying Higman’s Lemma—a mathematical theorem regarding sequences of strings—we prove that if a program runs forever, it must eventually produce an infinite sequence of these loop goals.

An infinite derivation path showing the recursive increase in term size (e.g., a to f(a) to f(f(a))) and the repetition of subgoals.

Key Results and Insights

Our research establishes two foundational theorems:

  • Theorem 3.5: A derivation is infinite if and only if it contains an infinite sequence of loop goals.
  • Theorem 4.3: A program terminates for a specific query if and only if its generalized SLDNF-tree contains no infinite paths of loop goals.

Unlike most static analyses that only provide a "sufficient" condition (if the proof holds, it terminates), this provides an "if and only if" characterization. This dynamic definition of loop goals perfectly matches the definition of an infinite execution path. Practically, this theory has been used to develop algorithms that identify non-terminating programs that static analysis might overlook.

Limitations and Future Work

While powerful, this dynamic approach has limitations. It does not currently address "floundering"—where a program stalls because a negative subgoal contains ungrounded variables. Additionally, identifying loop goals during runtime introduces computational overhead, making it currently best suited as a debugging tool. Future work will extend these concepts to Tabled Logic Programming, which uses memoization to avoid re-computation and presents 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 which 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},
}
Figure