Value constraints in the CLP scheme

This paper addresses the question of how to incorporate constraint propagation into logic programming. A likely candidate is the CLP scheme, which allows one to exploit algorithmic opportunities while staying within logic programming semantics. CLP($cal R$) is an example: it combines logic programming with the algorithms for solving linear equalities and inequalities. In this paper we describe two contrasting constraint store management strategies within the CLP scheme. One leads to CLP($cal R$), while the other, which we call value constraints, supports consistency methods such as arc consistency and interval constraints. In value constraints, the infer step of the CLP scheme is the application of a consistency operator acting on the active constraints. We show how the continued application of the infer step can be optimized and that such optimization is equivalent to the Waltz algorithm for constraint propagation. Using the Lassez-Maher fixpoint theory of chaotic iterations, we show that the Waltz algorithm does not necessarily converge to a fixpoint, but that it does so in the finitary case.