Comments on Kornfeld's Equality for Prolog: E-Unification as a Mechanism for Augmenting the Prolog Search Strategy

Edward W. Elcock, P. HoddinottAAAI 1986

Abstract

This paper provides a formal critique of William Kornfeld’s "Equality for Prolog," a system designed to improve Prolog’s search strategy using "extended unification" (e-unification). While the idea of using equality theories to delay evaluation is intuitively appealing, formal modeling demonstrates that Kornfeld’s specific implementation is mathematically unsound, incomplete, and computationally inefficient.

Introduction

Standard Prolog struggles when a predicate is called with uninstantiated variables representing an "infeasibly large" or infinite number of values. For instance, querying greater_than(X, 5) before X is bound often leads to failure or infinite loops as the system attempts to enumerate all possible integers.

In 1983, William Kornfeld proposed modifying the unification algorithm to invoke a user-defined "equality theory" upon failure. This "e-unification" allows the system to treat uninstantiated variables as "partially specified objects," delaying evaluation until more information is available. This study formalizes this mechanism to evaluate its logical consistency.

Formalizing E-Unification

The analysis utilizes the General Procedure framework to separate logic programs into logical clauses and an associated theory of equality. A key component of Kornfeld's approach is the $\Omega$-term, a 2-ary functor used to "wrap" a variable with its constraints (e.g., $\Omega(X, greater\_than(X, 5))$).

To evaluate this, the authors translated the original Lisp-based implementation into standard Prolog axioms. They identified a critical requirement for "function substitutivity"—axioms that allow equality to propagate through complex terms like lists or rational numbers.

Axiomatization of equality for lists and rational numbers.

Logical and Computational Challenges

The formalization reveals several significant issues:

The Surrogate Chain Problem

Kornfeld’s method creates "surrogates" for variables. During execution, these can form long, nested chains of $\Omega$-terms, leading to massive redundancy where the same constraint is repeatedly checked, severely impacting performance.

Unsoundness and Incompleteness

The most critical finding is that the mechanism is logically flawed. The authors provide counter-examples where goals that should fail actually succeed, representing a state of unsoundness. Furthermore, program success can depend on goal ordering, violating the declarative nature of logic programming (incompleteness).

Axioms for the greater-than predicate (gr) using Omega-terms.

As shown in Figure 3, the gr predicate is defined through a series of axioms that handle various instantiation states. The authors demonstrated that a query like gr(X, Y), eq(X, Y)—asserting that X is both greater than and equal to Y—could succeed under specific conditions, which is a logical contradiction.

Conclusion

While using an equality theory to augment Prolog's search strategy is a provocative concept, the specific implementation via $\Omega$-terms is problematic. The authors suggest that "direct methods," where the interpreter itself manages variable constraints (as seen in systems like Absys or Prolog II), are likely superior to forcing this behavior through the unification layer. Future research may determine if a more robust axiomatization can overcome these logical hurdles.

Summary updated

BibTeX
@inproceedings{elcock1986comments,
  author = {Edward W. Elcock and P. Hoddinott},
  title = {{Comments on Kornfeld's Equality for Prolog: E-Unification as a Mechanism for Augmenting the Prolog Search Strategy}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}

Loading related content...

Figure