Nondeterministic Lisp as a Substrate for Constraint Logic Programming

Jeffrey Mark Siskind, David A. McAllester

Abstract

This paper presents SCREAMER, an extension to Common Lisp that integrates nondeterministic programming with a robust constraint-solving engine. By layering a constraint layer over a nondeterministic substrate, SCREAMER bridges the gap between symbolic Lisp programming and declarative Constraint Logic Programming (CLP). The system employs hybrid constraint propagation—combining binding, Boolean, generalized forward checking, bounds propagation, and unification—interleaved with backtracking search. This architecture enables the resolution of complex nonlinear and discrete problems within a general-purpose programming environment, offering greater flexibility and interoperability than traditional Prolog-based CLP systems.

Introduction

In the early 1990s, Constraint Logic Programming (CLP) emerged as a powerful paradigm for solving combinatorial and numeric problems. However, most CLP implementations, such as CLP(ℝ) and CHIP, were built atop Prolog. This dependency limited their utility for developers who required the extensive libraries, object-oriented features (like CLOS), and general-purpose flexibility of Common Lisp. Furthermore, existing systems were often specialized for specific domains, such as linear equations or discrete sets.

SCREAMER addresses these limitations by providing a unified substrate for Boolean, numeric, and symbolic constraints within Common Lisp. It demonstrates that a nondeterministic Lisp can serve as a superior foundation for constraint programming, allowing for seamless integration with existing software ecosystems.

The SCREAMER Architecture

SCREAMER is designed as a two-layer system:

  1. The Nondeterministic Substrate: Common Lisp is augmented with primitives for nondeterministic choice and backtracking. This allows functions to explore multiple search paths, with "local side effects" automatically undone upon failure.
  2. The Constraint Layer: Built upon the substrate, this layer provides "lifted" versions of standard Lisp primitives. These operators can handle variables representing unknown values, propagating constraints as information becomes available.
Table of lifted primitives in SCREAMER, showing the 'v' suffix convention for constraint-aware functions.

As shown in the figure above, SCREAMER introduces a naming convention where constraint-aware counterparts to standard functions are suffixed with v (e.g., +v, <v, andv). This distinction allows programmers to mix standard Lisp logic with constraint-based reasoning clearly and effectively.

Hybrid Constraint Propagation

The core efficiency of SCREAMER's solver stems from its use of Hybrid Constraint Propagation. The system interleaves five distinct inference methods to prune the search space before resorting to backtracking:

  • Binding Propagation: Propagates known values through functional dependencies (e.g., if $z = x + y$, knowing $x$ and $y$ determines $z$).
  • Boolean Constraint Propagation (BCP): Performs unit resolution for logical constraints.
  • Generalized Forward Checking (GFC): Prunes impossible values from discrete domains, essential for problems like N-Queens.
  • Bounds Propagation: Utilizes interval arithmetic to maintain upper and lower bounds on numeric variables, enabling the handling of nonlinear equations.
  • Unification: Employs standard logic programming unification for symbolic S-expressions.

When these local, "fast but incomplete" propagation methods reach a fixpoint without finding a solution, SCREAMER falls back on nondeterministic search to explore the remaining possibilities.

Evaluation and Benchmarks

The authors evaluated SCREAMER using classic computational benchmarks rather than external datasets, focusing on the system's ability to handle diverse problem types:

  • Discrete Constraints: The N-Queens problem was used to demonstrate the effectiveness of GFC and backtracking.
  • Nonlinear Systems: SCREAMER successfully solved complex systems of nonlinear equations (e.g., $4x^2y + 7yz^2 + 6x^2z^2 = 1356.14$). Such problems are typically beyond the capabilities of simplex-based solvers used in systems like CLP(ℝ), showcasing the power of combining bounds propagation with search.

Discussion and Key Insights

A central argument of the paper is that Lisp is a more extensible and practical substrate for constraint programming than Prolog. Because SCREAMER is "just Lisp," it can easily interoperate with the Common Lisp Object System (CLOS) and graphical toolkits like CLIM. This makes it a viable tool for real-world engineering applications.

Furthermore, the design philosophy acknowledges that local propagation is often incomplete. By seamlessly interleaving propagation with search, SCREAMER ensures robustness; it can solve problems that might cause purely propagation-based solvers to stall.

Conclusion

SCREAMER represents a significant step in unifying symbolic, numeric, and Boolean constraint solving within a high-level, general-purpose programming language. By providing a nondeterministic substrate for Lisp, the authors created a portable and versatile tool that leverages the strengths of both declarative constraint satisfaction and procedural symbolic processing. Future work suggests the potential for "automatic lifting," where standard code could be automatically transformed into optimized constraint-based implementations.

Summary updated

Abstract

We have implemented a comprehensive constraint-based programming language as an extension to COMMON LISP. This constraint package provides a unified framework for solving both numeric and non-numeric systems of constraints using a combination of local propagation techniques including binding propagation, Boolean constraint propagation, generalized forward checking, propagation of bounds, and unification. The backtracking facility of the nondeterministic dialect of COMMON LISP used to implement this constraint package acts as a general fallback constraint solving method mitigating the incompleteness of local propagation.
BibTeX
@inproceedings{siskind1993nondeterministic,
  author = {Jeffrey Mark Siskind and David A. McAllester},
  title = {{Nondeterministic Lisp as a Substrate for Constraint Logic Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure