Composition in Hierarchical CLP

IJCAI 1995

TL;DR

This paper proposes a new, compositional approach to Hierarchical Constraint Logic Programming (HCLP) that offers a more efficient and tractable semantics than existing methods. By approximating HCLP solutions using bag operations and filter functions, the authors achieve a balance between expressiveness and computational efficiency, making it more practical for real-world applications.

What Problem Does This Paper Address?

Hierarchical Constraint Logic Programming (HCLP) is a powerful extension of Constraint Logic Programming (CLP) that allows for the representation of "hard" (required) and "soft" (optional) constraints with varying levels of preference. While HCLP offers great expressiveness, its existing implementations suffer from poor efficiency and a semantics that is not "compositional." Compositionality is a desirable property where the semantics of a combined system can be understood from the semantics of its individual parts. The lack of compositionality in HCLP means that combining HCLP programs can lead to complex, non-incremental computations, making them computationally expensive and semantically challenging. This paper aims to address this by developing a compositional variant of HCLP that retains much of its expressiveness while improving efficiency and semantic tractability.

Methods

The authors propose a weakening of the HCLP semantics that focuses on approximating solutions rather than achieving exact matches. Their approach uses:

  • Bags (Multisets): Instead of sets, they use bags to represent solutions, allowing for duplicate elements which naturally arise from combining multiple constraint sets.
  • Bag Operations: Standard bag operations like union (&) and a novel "guarded by" operator (/) are used. The guarded-by operator (A / B) keeps elements from bag A only if they are also present in bag B, with the same multiplicity as in A.
  • Filter Functions: These functions are applied to bags of solutions to remove elements that do not meet certain criteria. The paper specifically defines and uses fmax, which keeps only those elements that occur a maximal number of times in a bag.
  • Tuple Representation of Solutions: Solutions for a hierarchy are represented as a tuple (S0, S1, ..., Sn), where Si represents solutions satisfying constraints up to level i. This tuple structure allows for intermediate solutions to be stored and reused, contributing to the compositional nature of their approach.
  • Compose Operation (o): A new composition operation is defined for two-level hierarchies, p o q, which combines the solutions of two hierarchies p and q using bag operations and filter functions. This operation is extended to multi-level hierarchies.

Datasets

Not discussed in the paper. The paper uses illustrative examples and a small case study to demonstrate its approach, rather than formal datasets.

Key Insights and Ideas

  • Compositionality vs. Incrementality: The paper clearly distinguishes between compositionality (a property of formal systems) and incrementality (a property of implementations). They argue that a compositional theory can lead to incremental implementations, but the reverse is not necessarily true.
  • Approximation for Efficiency: By accepting an approximation of HCLP solutions, the authors gain significant computational advantages. This trade-off is crucial for achieving tractability.
  • The "Disorderly" Property of HCLP: Wilson's proof that any comparator respecting hierarchies over a non-trivial domain is "disorderly" is highlighted as a fundamental reason for HCLP's non-compositionality. This means that combining hierarchies can lead to solutions that are not simply derived from the individual solutions.
  • Bags as a Natural Representation: Using bags for solutions naturally handles the multiplicity of solutions arising from combining constraint sets, which is more intuitive than using sets in this context.
  • The fmax Filter: The fmax filter function is presented as a key component that helps approximate the behavior of HCLP's "locally-predicate-better" comparator, offering a way to select preferred solutions within a level.
  • Non-Associativity of Composition: The proposed composition operation is not associative due to the filter functions. This implies that the order of composition matters, and the authors advocate for composing all sub-solutions simultaneously to get the "correct" approximation.

Key Results

The paper demonstrates that their proposed compositional scheme for HCLP can:

  • Approximate HCLP Solutions: In the provided example (Figure 2), their method produces results that are close to standard HCLP solutions, capturing most of the desired valuations.
  • Avoid Re-solving from Scratch: By storing intermediate solutions in tuples and using efficient bag operations and filters, their approach avoids the need to re-solve the entire combined constraint set from scratch, leading to significant efficiency gains.
  • Offer a Tractable Semantics: The use of bag operations and filter functions provides a more mathematically grounded and understandable semantics compared to the original HCLP.

Limitations and Future Work

  • Approximation, Not Exactness: The primary limitation is that the proposed scheme provides an approximation of HCLP solutions, not exact matches. This is a deliberate trade-off for efficiency, but it means it may not be suitable for applications requiring absolute precision.
  • Non-Associativity: The non-associativity of the composition operation means that the order of composition matters, and the authors recommend composing all sub-problems simultaneously, which might require more storage.
  • Future Work:
    • Error Sequences: Extending the scheme to incorporate "error sequences" to handle different comparators more effectively.
  • Constraint Deletion and Dynamic Satisfaction: Investigating constraint deletion and dynamic constraint satisfaction, which are challenging in many formalisms but might be facilitated by their modular tuple representation.
  • Inconsistencies in Unlabeled CLP: Exploring inconsistencies arising from composing standard CLP programs (without hierarchical strength labels) and drawing parallels with their hierarchical system.

Summary updated

BibTeX
@inproceedings{1995composition,
  title = {{Composition in Hierarchical CLP}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure