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