Constraint Processing in cc(FD)

Pascal Van Hentenryck^{1}, Vijay Saraswat^{2}, Yves Deville^{3}

Abstract

Constraint logic programming languages such as CHIP [26,5] have demonstrated the practicality of declarative languages supporting consistency techniques and nondeterminism. Nevertheless they suffer from the black-box effect: the programmer must work with a monolithic, unmodifiable, inextensible constraint-solver.

This problem can be overcome within the logically and computationally richer concurrent constraint (cc) programming paradigm [17]. We show that some basic constraint-operations currently hardwired into constraint-solvers can be abstracted and made available as combinators in the programming language. This allows complex constraint-solvers to be decomposed into logically clean and efficiently implementable cc programs over a much simpler constraint system. In particular, we show that the CHIP constraint-solver can be simply programmed in cc(FD), a cc language with an extremely simple built-in constraint solver for finite domains.

1 Introduction

The purpose of our research is to design programming languages that support the solution of various combinatorial search problems arising in areas like combinatorial optimization, artificial intelligence, natural language processing, and hardware design. Our goal is to extract some of the fundamental techniques used in those areas and to support them inside programming languages in order to speed development time, allow rapid prototyping, and ease modifiability.

One aspect of our work has focused on the support of consistency techniques, a paradigm emerging from Artificial Intelligence, inside constraint logic programming. Consistency techniques have been used in a number of systems (e.g. [12,6,14,15] in order to reduce the search space by removing combinations of values that cannot appear together in a solution. Constraint Logic Programming (CLP) is a new class of declarative languages which generalizes Logic Programming by replacing unification with constraint solving [10]. Such languages are attractive for solving combinatorial search problems since their nondeterminism makes them adequate for stating various search procedures and their relational form makes it easy to state constraints. The support of consistency techniques in conjunction with nondeterminism is particularly appealing (as noted by Mackworth in [14]) as it frees the programmer from implementing both tree-search and constraint propagation.

The feasibility and practicality of a declarative language supporting both consistency techniques and nondeterminism was demonstrated in the CHIP system [26,5]. Solutions for a large variety of combinatorial problems — test-generation [22,29], car-sequencing [3], microcode labelling [4], scheduling and cutting stock [26] — were developed quickly, and were comparable in efficiency (within a constant factor) to specialized algorithms using the same approach. CHIP supported consistency techniques mainly by providing a number of primitive constraints, such as equations, inequalities, and disequations involving variables ranging over finite subsets of natural numbers.

Though successful, CHIP has a number of limitations, the most important being its lack of extensibility. The programmer has to recast non-primitive constraints in terms of existing constraints, is unable to define new primitive constraints and is unable to cope adequately with disjunctions of constraints or the definition of incomplete constraint solvers. As a result, non-primitive constraints are often recast in terms of more basic variables (e.g. Boolean variables) and/or are used to make choices. Both alternatives decrease pruning, increase the search space, and entail a substantial loss in efficiency compared to procedural languages. The problem is not specific to CHIP but present in all CLP languages which are all based on a black-box constraint solver that the programmer cannot extend or modify.

1Brown University, Box 1910, Providence, RI 02912, Email: pvh@cs.brown.edu

2Xerox Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, CA 94304, Email: saraswat@parc.xerox.com

3Université Catholique de Louvain, Pl. Ste Barbe, 2 B-1348 Louvain-La-Neuve, Belgium, Email: yde@info.ucl.ac.be

The glass-box approach. We propose to remove the above limitation by taking a different approach. Our thesis is that consistency techniques can be supported in a much more fundamental way by providing general-purpose, efficiently implementable, declarative operations in the programming language that capture essential algorithmic techniques embedded in the implementation of such systems. To support this thesis, we introduce four new constraint language ideas: (1) indexical constraints, related to a restricted use of universal quantification, (2) cardinality operators with indexical bounds, related to the threshold operator of propositional logic [28], (3) constructive disjunction, related to intuitionistic disjunction, and (4) extended Asks, related to intuitionistic implication. We instantiate these ideas in the programming language cc(FD), incorporating a very simple constraint system over finite systems, FD. Through these combinators, we show that cc(FD) supports the basic reasoning principles implemented in systems such as ALICE [12], REF-ARF [6], CHIP in a very simple and flexible way. Further, we briefly discuss a prototype implementation of cc(FD) that supports our contention that the language can be implemented extremely efficiently.

The main advantages of our approach are generality, extensibility, efficiency and semantic simplicity. The constructs introduced are general-purpose: they are definable on very general notions of constraint

systems [19], including rational arithmetic, Booleans and first-order terms.

They are powerful enough that the underlying constraint-solver can be extremely simple (e.g., it may provide only unary constraints). The additional functionality provided by more powerful constraint-solvers can be obtained by means of user-level programs. This significantly reduces the black-box effect. The programmer can define his own constraints (to the extent of the reasoning principles supported) without sacrificing the declarative reading of the programs.

Since the embedded constraint-solver is extremely simple, it can be very efficiently implemented. The combinators themselves are sufficiently “low-level” as not to introduce overhead (in time or space) compared to procedural implementation of the reasoning principles supported.

Finally, the abstract semantics of these combinators can be presented in a very simple way, within the concurrent constraint (cc) programming [17,18,19]. In this framework, computation progresses through the interaction of agents that communicate with each other via a shared store that is itself a constraint. The basic operations are Tell (add a constraint to the store) and Ask (check that a constraint is entailed by the store). [17,18,19] also discuss several other combinators such as parallel composition, hiding, and backtracking. Logically, the Ask operation corresponds to a primitive form of intuitionistic implication, parallel composition to conjunction, hiding to existential quantification and backtracking to disjunction in a very precise way [13]. Denotationally, agents can be thought of as closure operators over the underlying constraint system^{4}. The four new combinators we introduce in this paper can readily be integrated into the framework as new operations on closure operators.

Rest of this paper. In summary, cc(FD) offers a new alternative to the traditional CLP model for constraint programming by systematically exploiting the cc framework. It proposes to design constraint languages by abstracting the computational principles behind a class of applications and by supporting them at the language level via constraint operations. The combinators are based on procedural interpretations of logical connectives; hence the approach combines the advantages of referential transparency, flexibility, and computational efficiency. This idea would bring similar advantages for other solvers (e.g. first-order terms, rationals) and application areas exploiting constraint technology (e.g. natural language processing, artificial intelligence). Although languages of this type would be more basic, it is natural to imagine that constraint solvers would be built in a modular, incremental, and hierarchical manner recovering the ease of programming of existing CLP languages while adding flexibility and efficiency.

The rest of this paper is devoted to an overview of the constraint processing facilities of cc(FD). First we present the FD constraint system underlying cc(FD)— this is used in several examples throughout the paper.

4A closure operator over a lattice is a monotone, idempotent and extensive operator.

Next, we introduce the four combinators and discuss their operational and denotational semantics. Finally we consider the design of the cc language, which is an instantiation of the cc language with these combinators, over the FD constraint system. In particular, we sketch the implementation of the CHIP constraint-solver in

cc(FD).

To ease reading, only informal presentation are given in the text. The precise operational and denotational semantics of the new constructs will be given in the full version of the paper.

Note for the reviewer 1.1 This technical abstract assumes some familiarity with the notions of constraint systems, concurrent constraint programming languages and closure operators. For more information on these, the reviewer may consult [19]. Appendix A briefly summarizes the notions of closure operators. [15] is a good source for information on local consistency techniques (e.g., arc-consistency).

2 The FD constraint system

We briefly present the very simple constraint system underlying cc(FD). (In reality, the constraint system in cc(FD) also provides Herbrand trees, but for the purposes of this paper we concentrate on novel aspects.)

There are three kinds of syntactic objects, (t) arithmetic terms, (r) ranges, and (c) constraints. Their syntax is given by the grammar in Table 1. Ranges denote a finite union of intervals on the number-line — the given operations are interpreted in the obvious way. The entailment relation on constraints is induced in the obvious way from the interpretation: a valuation θ satisfies a constraint X in r exactly when θ(X) lies in the range denoted by r. Thus the constraint

X in t_{1} .. t_{2}

is inconsistent if t_{2} < t_{1} — this is the only way inconsistency can arise in this system. Note that the constraint system is closed under negation: the constraint ¬X in r is just X in − r.

Incremental algorithms for checking consistency of constraints, and for entailment are completely straightforward and very efficiently implementable.

The following proposition is easy to establish.

Proposition 2.1 Any finite conjunction of constraints in this system in one variable can be represented by a single constraint of one of the following kinds:

\begin{matrix}X in (m_{1} .. n_{1} : …: m_{k} .. n_{k}) \\ X in (m_{1} .. n_{1} : …: m_{k} ..) \end{matrix}

where either (k = 1, m_{1} = 1, n_{1} = 0) or (k ≥ 1, m_{i} ≤ n_{i} < m_{i+1}).

Such a constraint is said to be in normal form. A set of constraints {X_{i} in s_{i} | i ∈ I}, for some index-set I, is in normal form if all the variables are distinct and each constraint is in normal form.

The construction in the following theorem is the completion by ideals used in the definition of information systems [21].

Theorem 2.2 For any finite set of variables V, let FD_{V} be the family of all entailment-closed sets of constraints generated from a set of constraints with free variables in V.

1. F D_{V} is a complete distributive lattice, with glbs given by intersection, and lubs by closure of the union.

2. The finite elements of FD_{V} are exactly those generated from a finite set of constraints.^{5}

3. FD_{V} is not finitary: that is, there exists a finite constraint which has infinitely many finite elements below it.

5u is a finite element of a lattice L iff for every directed subset S of L with lub above u, there is a finite subset of S with lub above u.

In the following, n ranges over natural numbers.

t ::= X | n | t + t | t − t | t ∗ t | t mod t | t ÷ t
r ::= [t_{1}] .. [t_{2}] (from t_{1}, default 0, to t_{2}, default infinity)
| t  (shorthand for t .. t)
| r_{1} : r_{2} (union)
| r_{1} & r_{2} (intersection)
| − r  (complementation)
| r + t  (pointwise addition)
| r mod t (pointwise mod)
c ::= X in r

Each constraint is associated with an implicit ask restriction [17] — a constraint X in r can be added to the store only when r is ground. Some handy abbreviations:

X in {n_{1}, …, n_{k}} =^{△} X in n_{1} : …: n_{k}
X ≤ t  =^{△} X in .. t
X < t  =^{△} X in .. (t − 1)
X ≥ t  =^{△} X in t ..
X > t  =^{△} X in (t + 1) ..
X ≠ t  =^{△} X in .. (t − 1) : (t + 1) ..
X = t  =^{△} X in t

Table 1: The constraint system FD

4. The glb of two finite elements of FD_{V} is itself finite.

In particular, the glb of two normal-form sets of constraints {X_{i} in r_{i} | i ∈ I} and {Y_{j} in s_{j} | j ∈ J} is just the set of constraints generated by Z in r_{i} : s_{j} where X_{i} = Y_{j}.

Note that the choice of the constraints represent one more step towards simplicity in the constraint-solver and hence reduces the black-box effect of usual CLP languages. In previous work [27], primitive constraints were limited to at most two variables. Such constraints can be solved completely with arc-consistency. In this paper, we can achieve the same effect while assuming that the implementation supports just unary constraints, using indexical constraints.

3 The Extended cc language framework

The basic Ask-and-Tell cc languages provide several combinators: Tell, Ask, Parallel composition, Hiding and Backtracking. These are provided in cc(FD) as well. The discussion of these combinators is omitted because they are standard — some information about Ask, Tell and Parallel composition can be obtained from the operational semantics in Table 3.

Indexical Constraints. Suppose we would like to write a program on top of the FD constraint system to implement reasoning with variation intervals for the constraint X ≥ Y + c, for X, Y variables and c a constant. That is, we would like this program to have the following effect:

1. whenever it is true that Y ≥ e (for e a constant), the program should impose the constraint X ≥ e + c.

2. whenever it is true that e ≥ X, the program should impose the constraint (e − c ≥ Y).

In other words, we would like the program to behave as if it were the infinite conjunction of rules of the form

(Y ≥ α) → (X ≥ α + c)

Basic Ask-and-Tell language.

Programs P::= H::A | P ∧ P | ∀X P
Agents A::= B  (Tell)
| B → A  (Ask)
| A, A  (Conjunction)
| A; A  (Disjunction)
| ∃XA  (Local variables)
| H  (Procedure Call)
Basic constraints B::= c | B, B
Procedure Call H::= p(X_{1}, …, X_{n})

The Extended language. The language allows Basic agents to be defined using cardinality, constructive disjunction, and indexical constraints. It allows users to specify new primitive constraints (the atomic formulas D), provided tell, ask, declarations are provided. It adds to the grammar for the basic Ask-and-Tell language the productions:

Basic agents B::= #(l, [B, …, B]) | #([c, …, c], u) (Cardinality)
| ∇ (B, …, B)  (Constructive Disjunction)
| ic  (Indexical constraints)
| D  (User-defined constraints)
Programs P ::= tell D :: B | ask D :: B

Basic agents are required to be monotone in their indexical arguments in the Tell part, and anti-monotone in their Ask part. The definitions for user-defined constraints are required to be recursion-free.

Table 2: Abstract Syntax for cc(FD)

for all values of α.

For this purpose we introduce the notion of indexical terms and indexical constraints. An indexical term is syntactically an ordinary term (e.g., max(X)), but semantically it denotes a mapping from constraints to terms. As an example, for X a variable, we may define max(X) to be the indexical term which in store s denotes n, where n is the least upper bound on X given s. Thus, in store s = {X in 1 : 3 : 4 .. 20}, the value max(X)_{s} of the indexical term max(X) would be 20. The indexical terms min(X) (returns the greatest lower bound on X) and dom(X) (returns the domain of X) can similarly be defined in FD.

We allow indexical terms to be used within constraints just as ordinary terms. A constraint containing an indexical sub-term is called an indexical constraint. It denotes a mapping from constraints to constraints obtained in the obvious way: given an indexical constraint d and input constraint s, the mapping returns the constraint obtained from d by replacing each indexical sub-term t by t_{s}. For example, in the store s = {X in 3 .., Z in 2}, the indexical constraint (Y in min(X) ..) denotes the constraint (Y in 3 ..).

Example 3.1 (greatereqc/3) The constraint greatereqc/3 may now be programmed as follows:

greatereqc(X, Y, C) :: (X in (min(Y) + C) ..), (Y in .. (max(X) − C)).

In any store s, both constraints may fire, producing information about X and Y respectively, exactly as desired.

Logically, a constraint (X in (min(Y) + c) ..) can be thought of as the constraint: ∀k.(Y ≥ k) ⇒ X ≥ k + c. However, only very restricted kinds of universal quantifications can be obtained by using min/1, max/1, dom/1 indexical terms.

Example 3.2 (mod/4) As another example, consider the constraint mod(X,Y,C,Base) which holds iff X = (Y + C) mod Base assuming that X,Y are variables ranging over {0..Base-1} and C is a integer in {0..Base-1} and Base is a positive number. We can get this effect with:

Configurations are pairs of the form ⟨Γ, s⟩ where s is a set of constraints, and Γ is a multiset of agents. (The empty multiset is denoted ().) Below, we define a binary relation ⟶, the transition relation which specifies how configurations evolve. Note that only fair execution sequences (e.s.) are considered legal. (A fair e.s. is not unfair; an unfair e.s. is one in which some given transition is enabled at every configuration in the sequence, and never taken.)

Basic Ask-and-Tell language. We omit the rules for existential quantification, backtracking and procedure calls, since they are standard. (See for example, [11].) Below, ⊢ is the entailment relation of the underlying constraint system.

(Tell) ⟨(Γ, c), s⟩ ⟶ ⟨Γ, s ∪ {c}⟩
(Ask) ⟨(Γ, d → A), s⟩ ⟶ ⟨(Γ, A), s⟩  s ⊢ d
(Parallel Composition) ⟨(Γ, (A_{1}, A_{2})), s⟩ ⟶ ⟨(Γ, A_{1}, A_{2}), s⟩

Indexical Constraints.

⟨(Γ, ic), s⟩ ⟶ ⟨(Γ, ic), s ∪ {ic_{s}}⟩

Cardinality. To simplify presentation we assume that the collection of agents of a cardinality constraint is a multiset of the form [(B_{1}, d_{1}), …, (B_{n}, d_{n})], where the d_{i} are (possibly empty) sets of constraints. (The d_{i} denote local stores for each basic agent.)

\frac{⟨B, d ∪ s⟩ ⟶ ⟨B′, d′⟩}{⟨(Γ, #(l, [(B, d) | σ])), s⟩ ⟶ ⟨(Γ, #(l, [(B′, d′) | σ])), s⟩}

⟨(Γ, #(l, [(B, false) | σ])), s⟩ ⟶ ⟨(Γ, #(l, σ)), s⟩

⟨(Γ, #(l, [((), d) | σ])), s⟩ ⟶ ⟨(Γ, #(l − 1, σ)), s⟩  if s ⊢ d

⟨(Γ, #(l, [(B_{1}, d_{1}), …, (B_{l}, d_{l})])), s⟩ ⟶ ⟨(Γ, B_{1}, …, B_{l}), s ∪ d_{1} ∪ … ∪ d_{l}⟩

⟨(Γ, #(l, σ)), s⟩ ⟶ ⟨(), false⟩  if |σ| < l

The rules for upper-cardinality agents are similar, and omitted.

Constructive Disjunction. To simplify presentation we assume that the argument of a disjunctive agent is an unordered collection of agents of the form (B, d), where d is a possibly empty set of constraints.

\frac{⟨B, d ∪ s⟩ ⟶ ⟨B′, d′⟩}{⟨(Γ, ∇ ((B, d), E)), s⟩ ⟶ ⟨(Γ, ∇ ((B′, d′), E)), s⟩} ; ⟨(Γ, ∇ ((B_{1}, d_{1}), …, (B_{n}, d_{n}))), s⟩ ⟶ ⟨(Γ, ∇ ((B_{1}, d_{1}), …, (B_{n}, d_{n}))), s ∪ glb(d_{1}, …, d_{n})⟩

Extended Asks. To simplify presentation, we assume that the ask part is an agent of the form (B, d), where d is a possibly empty set of constraints.

\frac{⟨B, d ∪ s⟩ ⟶ ⟨B′, d′⟩}{⟨(Γ, (B, d) → A), s⟩ ⟶ ⟨(Γ, (B′, d′) → A), s⟩} ; ⟨(Γ, ((), d) → A), s⟩ ⟶ ⟨(Γ, d → A), s⟩

Table 3: Transition system for Extended cc language

it ::= X | n | it + it | it − it | it × it | it mod t | it ÷ it | min(X) | max(X)
ir ::= [it_{1}]..[it_{2}] | it | ir_{1} : ir_{2} | ir_{1}&ir_{2} | − ir | ir + t | ir mod t | dom(X)
ic ::= X in ir

The indexical terms min(X), max(X), and dom(X) are considered ground, for purposes of the implicit Ask restriction. Also, constraints satisfy the condition that terms min(X) must occur “negatively” in the range, and terms max(X) must occur “positively” in the range.

Table 4: Indexical constraints in cc(FD)

mod(X, Y, C, Base) :: X in (dom(Y) + C) modBase, Y in (dom(X) − C) modBase.

The first expression makes sure that, whenever a value is removed from the domain of Y, the corresponding value is removed from the domain of X. Similarly for the second.

For indexical constraints to generate closure operators, (and hence to be well-defined) they must denote monotone functions: that is, as the information content of the store increases, the strength of the constraint yielded by the indexical constraint should increase.^{6} This is true, for example, for (Y in min(X) ..). It is not true for (Y in .. min(X)). Therefore, additional syntactic restrictions have to be placed on occurrences of indexical terms to ensure that the overall constraints built using them are monotone. These conditions are easy to state: intuitively all (positive) occurrences of terms max(X) should be in the “upper” portions of range-restrictions, and all (positive) occurrences of terms min(X) should be in “lower” portions of rangerestrictions.

Use. Indexical arithmetic constraints provide more effective algorithms for arc-consistency. The new algorithms are O(ed) (where e is the number of constraints and d the size of the domains), improving on the traditional quadratic algorithms. More important, the space requirement is O(e) — each constraint takes constant space. An example of an application which can benefit from this extension is the microcode labeling problem [26].

Implementation. It should be clear that for the FD constraint system, the implementation of indexical terms and constraints is totally straightforward. The implementation already maintains max, min and dom information for each variable: we are now simply providing a mechanism for the user to access this information in a “safe” way.

Cardinality. The cardinality combinator [28] is a generalization of the threshold operators for propositional calculus and provides a general form of disjunction. Related to the Andorra model of computation [30], it allows arc-consistency of any finite domain constraint to be implemented within the complexity bounds of the optimal algorithm of [16]. Moreover, it provides a general way of implementing the DMA/DMT options as well as the conditional summation of ALICE [12].

There are two cardinality combinators, the lower and the upper, of the form #(it, [B_{1}, …, B_{n}]) and #([c_{1}, … c_{n}], it) respectively, where it is an indexical term. Intuitively, the constraint #(l, [B_{1}, …, B_{n}]) holds in store s iff at least l_{s} of the given agents are true, and the constraint #([c_{1}, …, c_{n}], u) holds iff at most u_{s} of the given constraints are true. Note that for this to be well-defined it must be the case that l_{s} increases as s becomes stronger (e.g. l = min(X)), and u_{s} decreases as s becomes stronger (e.g. u = max(X)). In the following, we will consider the expression c ⇒ d as shorthand for #(1, [¬c, d]), and the expression c ⟺ d as shorthand for (c ⇒ d), (d ⇒ c).

The agent #(l, [c_{1}, …, c_{n}]) is executed by spawning n Ask agents, one for each argument and maintaining a counter each for the number of entailed constraints (a), and the number of constraints whose negation is not yet entailed (t). If in any store a ≥ l, the agent may terminate without adding any new information to the store. On the other hand, if l = t, then the agent may terminate, adding those constraints c ∈ [c_{1}, …, c_{n}] such that neither c nor its negation is entailed by the store. If l > t, the agent may terminate, causing the store to become inconsistent. The evaluation rules for #([c_{1}, …, c_{n}], u) are similar — note just that if u = a, the agent may terminate, adding the negations of all the constraints in [c_{1}, …, c_{n}] not entailed by the store. The set of equational laws underlying this procedural description are given in Table 5.

6Every monotone function f generates a closure operator f̂ = λs.fix(λa.s ∧ (fa))) by augmentation and iteration to quiescence.

Use.

Example 3.3 (Arc-consistency.) We show how to enforce directional arc-consistency on a binary constraint p(X,Y). First, the domains of X and Y must be reduced respectively to the projections of the constraint on the first and second arguments, say D_{1}, D_{2}. Next, for each value v in D_{1}, we generate the constraint

Y ≠ w1, …, Y ≠ wp ⇒ X ≠ v

where w_{1},…,w_{p} are all values w such that p(v,w). Thus, as soon as Y is constrained to be different from all values in {w_{1},…,w_{p}}, X is constrained to be different from v. Conversely, if X is equated to v, then Y will be required to take on one of the given values.

[28] showed that, on simple examples, cardinality can bring an exponential improvement over traditional approaches. Most CHIP applications can be solved more naturally using cardinality removing the need for ad-hoc built-in constraints. For these applications, the overhead may be as low as 6% (e.g. car-sequencing [3]) while not exceeding 30%. A new interesting application is the allocation of jobs to pipeline processors to minimize total delay. A cc(FD) program was developed for the task and is comparable (sometimes faster) in efficiency to a specific branch and bound algorithm. Cardinality was used to implement conditional summation (e.g. the summation of the computation times of all jobs assigned to the same processor must not exceed it capacity in a cycle time) as well as the constraint for the transmission time which is: if either job is run on the master processor (processor 1), then transmission time is 0; and if the two jobs are run on adjacent machines (neither of which is the master processor) then transmission time is 1; otherwise transmission time is 2. This can be expressed directly in cc(FD):

#(1, [P1 ≠ 1, P2 ≠ 1, T12 = 0])

#(1, [P1 = 1, P2 = 1, #([X in dom(Y) + 1, Y in dom(X) + 1], 0), T12 = 1]) #(1, [P1 = 1, P2 = 1, #([min(P1) > max(P2) + 1, min(P2) > max(P2) + 1], 0), T12 = 2])

where P1, P2 are the processors associated with jobs 1 and 2 and T12 is the transmission time between them.

Constructive Disjunction. The basic idea behind constructive disjunction is to add to the store constraints entailed by all possible alternatives, i.e. the conjunctions made up from the store and one of the disjunctions. By factoring common information from the disjuncts constructive disjunction produces more pruning than cardinality, albeit at a greater cost. Constructive disjunction can be used for many constraints involving (explicitly or implicitly) disjunctions.

Example 3.4 (max/3) A typical example is the max/3 constraint, especially useful in scheduling problems [26]. The constraint max(X,Y,Z) holds iff Z is the maximum of X and Y. It can be expressed, using cardinality, in the following way:

max(X, Y, Z) :: Z in min(X) .. & min(Y) .., #(1, [Z in dom(X), Z in dom(Y)]).

The first two constraints ensure that Z is always not smaller than X and Y, while the last constraint ensures that Z is equal to one of them. The constraint however does not achieve as much pruning as we would like. For instance, if X,Y,Z range over {5..10}, {7..11}, and {1..20} respectively, the above program would reduce the domain of Z to to {7..20} instead of the expected {7..11}, because cardinality handles the two equations locally and concludes that neither is entailed.

Constructive disjunction adds to the store the constraints common to the disjuncts, e.g. Z in {5..11} in the above example. Syntactically, a constructive disjunction is of the form ∇ (B_{1}, …, B_{n}) and can be read declaratively as a disjunction. Operationally it performs constraint generalization, i.e. it computes the greatest lower bound (glb) in the constraint lattice of the constraints B_{1}(s), …, B_{n}(s) (where we are thinking of each B_{i} as a closure operator). If a glb algorithm is not available for the constraint system, any approximation (i.e. any set of constraints which is implied by all constraints in the glb) would do as well.

Example 3.5 (max/3 contd.) The max/3 constraint can be expressed as

max(X, Y, Z) :: Z in min(X) .. & min(Y) .., ∇ (Z in dom(X), Z in dom(Y)).

This program achieves the expected pruning since information from both equations can be combined during propagation.

Use. Constructive disjunction is mainly motivated by disjunctive scheduling applications although it may be used in many other applications (e.g. biology). In the general problem, tasks have to be scheduled on different machines in presence of precedence and other constraints. For simplicity, we assume that the machine on which a task has to be executed has already been determined. At this point, the key problem is to find an ordering of the tasks on a machine so as to minimize an objective function (e.g. the makespan or the total delay). To obtain reasonable efficiency, it becomes necessary to exploit the disjunctions to prune the search space. Consider n tasks in such a disjunction and assume that their starting dates, end dates and durations are denoted by S_{1}, E_{i}, D_{i} respectively. A typical pruning rule [2] is as follows:

If the starting date of task i plus the summation of all durations is greater than the maximum of all end dates but the one of task i, then task i cannot be scheduled first.

This rule can be implemented using implication and constructive disjunction as

Max in min(E1) .. & … & min(En), ∇ (Max in dom(E1), …, Max in dom(En)), Max in .. (min(Si) + D1 + … + Dn − 1) → Pi in 0 : 2 ..).

where P_{1} represents the position of task i in the disjunction.

The branch & bound algorithm of [2] was implemented using the above constraint and additional ones in the same spirit. The resulting program is short, yet it provides reasonable efficiency (between 5-10 time slower). As constraint programming languages are still rather recent and cc(FD) is a prototype, the result is encouraging.

Implementation. In our current implementation constraint generalization is done pairwise and changes are propagated only when the result has been modified and a subsequent operation may change the result. Successive glbs are maintained in a persistent data structure (somewhat similar to a RETE network [7]) to avoid restarting the whole computation from scratch when the store is updated. Similar implementations are possible for other domains (e.g. first-order terms).

Extended Asks. To obtain a flexible, extensible, and efficient system, it is desirable to ask non-primitive constraints as well as primitive constraints. In general, a non-primitive constraint will be a closure operator. Asking whether a primitive constraint c holds is just checking to see if the store has enough information to entail c. Semantically, the closure operator corresponding to c → f (for c a constraint, and f a closure operator) is just the operator whose fixed-point set is {s | s ⊬ c}∪f [18] (see the Appendix for the connection between closure operators and their fixed-point sets). What should it mean to Ask a closure operator?

One natural answer is as follows: say that a store s solves a closure operator f if f terminates when run in s, without producing any more information. In such a case, f cannot produce any more information in s, or in any strengthening of s. More abstractly, we can say that s solves f (and write s ⊢ f) if s is a stable fixed-point of f, that is, every t ≥ s is a fixed-point of f (notationally: ↑ s ⊆ f). Now it becomes easy to define an extended ask operator: given a closure operators f and g, f → g is the closure operator whose fixed-point set is given by

{s | s ⊬ f} ∪ g

It is easy to see that this set is closed under glbs and hence is the fixed-point set of a closure operator.

The operational semantics of Extended Asks is given in more detail in Table 3. The correspondence between the operational and denotational semantics is not difficult to establish. We note that this operation satisfies a number of nice properties, summarized in Table 5. Note, however, that the operation is antimonotone in its first argument — hence we cannot allow the class of agents that appear in this position (namely, Basic Agents) to be closed under recursion.

We also note in passing that (monotone) indexical constraints can be answered quite efficiently in cc(FD). We illustrate with an example. A constraint s solves the indexical constraint X in ..max(Y) iff s ⊢ (X in .. min(Y)_{s}. Thus, all that needs to be done is to evaluate a constraint in the current store — if the check succeeds, then the Ask succeeds, no more work needs to be done.

Non-primitive Constraints. cc(FD) also provides a simple facility for defining Basic Agents. For each new non-primitive constraint, two actions need to be defined, tell and ask, via declarations of the form:

tell D :: Bt. ask D :: Ba.

The first is used in situations where the user-defined constraint needs to imposed, and the second in situations where it is to be asked. If the user supplies only the tell action Bt for a user-defined constraint D, the system will take the ask action to be Bt as well. However, the tell action is usually an incomplete approximation to the intended interpretation of D, and it may be possible for the user to supply a better approximation for Ask. For this reason, we allow the user to specify the two actions separately. It is the user’s responsibility to ensure that these two definitions are logically related to each other in the expected way.

Example 3.6 (greatereqc(X,Y,C)) This example illustrates the advantage of allowing the user to define the four basic actions differently. A typical definition for this constraint in cc(FD) would be:

tell greatereqc(X, Y, C) :: X in (min(Y) + C ..), Y in (.. max(X) − C). ask greatereqc(X, Y, C) :: X in (max(Y) + C ..).

Denotational semantics. Above, we have discussed the denotational semantics of extended asks explicitly. The semantics of the other constructs (indexical constraints, cardinality and constructive disjunction) is straightforward: all of them can be seen as defining closure operators in the obvious way. Indeed the constructive disjunction operation is just the glb operation in the lattice of closure operators over the constraint system. (This is how they were first discovered; only later was their computational significance understood.)

Cardinality. In the following, σ′ is a permutation of σ.

#(l, σ, u) = #(l, σ), #(σ, u)

#(l, σ) = #(l, σ′)  #(σ, u) = #(σ′, u)
c, #(l, [d | σ]) = #(l, [e | σ])  c, #([d | σ], u) = #([e | σ], u)  (c, d) ⟺ (c, e)
#(l, σ) = false  (|σ| < l) #(σ, u) = false  (u < 0)
#(l, σ) = true  (l ≤ 0) #(σ, u) = true  (|σ| ≤ u)
#(l, [false | σ]) = #(l, σ)  #([false | σ], u) = #(σ, u)
#(l, [true | σ]) = #(l − 1, σ)  #([true | σ], u) = #(σ, u − 1)
#(l, [c_{1}, …, c_{l}]) = (c_{1}, …, c_{l})  #([c_{1}, …, c_{n}], 0) = (¬c_{1}), …, (¬c_{n})

Constructive Disjunction.

c_{1} ∇ c_{2} = c_{1}  (if c_{2} → c_{1})
c, (d ∇ B) = c, (e ∇ B)  (if c → (d ↔ e))
c ∇ d = glb(c, d), (c ∇ d)

                                B ∇ false = B

B_{1} ∇ B_{2} = B_{2} ∇ B_{1}
B_{1} ∇ (B_{2} ∇ B_{3}) = (B_{1} ∇ B_{2}) ∇ B_{3}

Extended Asks. Definition 3.1 s ⊢ B =^{△}↑ s ⊆ B Proposition 3.1 s ⊢ (B_{1}, B_{2}) iff s ⊢ B_{1} and s ⊢ B_{2}.

Definition 3.2 B_{1} → B_{2} =^{△} {s | s ⊬ B_{1}} ∪ B_{2}

Proposition 3.2 s ⊢ B_{1} → B_{2} if B_{1}(s) ⊢ B_{2}. The converse may not hold; there are simple counter-examples. The following laws are satisfied by Extended Asks: (I is the identity closure operator)

A → A = I

I → A = A
B_{1} → B_{2} = (B_{1} → (B_{1}, B_{2})
B_{1} → (B_{2} → B_{3}) = (B_{1}, B_{2}) → B_{3}
B_{1} → (B_{2}, B_{3}) = (B_{1} → B_{2}), (B_{1} → B_{3})

Table 5: Simplification rules for basic combinators.

4 The language cc(FD)

cc(FD) is simply an instantiation of the above language framework, over the FD constraint system. In many ways it can be thought of as a “rational reconstruction” of CHIP. Below we discuss how the constraint-solver of CHIP can be programmed in cc(FD) in very straightforward ways.

Arithmetic Constraints. CHIP supports the use of numerical constraints over finite domains using reasoning over variation intervals. These constraints are constructed from natural numbers, domain variables, the operators +, ∗, −, and the relations ≤, ≥, <, >, =. It is easy to see that any such constraint can be expressed in terms of constraints having more than three variables. Hence it is sufficient to show how to simulate three-variable CHIP constraints in cc(FD). For this we use indexical constraints. For instance, the constraint X × Y ≥ Z is modelled as:

gtemult(X, Y, Z) ::

Z in (.. max(X) × max(Y)),

X in (1 ..) → Y in (min(Z)/max(X)..), Y in (1 ..) → X in (min(Z)/max(Y)..).

Similarly for other constraints.

Disequations are only handled in cc(FD) exactly in the same way as in CHIP: suspend until exactly one variable is left in the constraint. Minimum and Maximum constraints can be defined directly as discussed earlier.

Symbolic Constraints. A number of symbolic constraints were available in CHIP and were instrumental in solving many practical problems. For example, CHIP provides the constraint element(I,L,V) which holds iff element I of list L is equal to V. The constraint is used with I and V being domain variables and L being a list of integers. In CHIP, the user may specify that the system reason with this constraint using either arc-consistency or reasoning about variation intervals. Both these reasoning techniques can be expressed as user-programs in cc(FD) as follows. To enforce arc-consistency on element(I,L,V), generate the constraint V = e ⇔ I in i1 : …: ip for all values e with occurrences i1, …, ip in L. To enforce reasoning with variation intervals, generate the constraint V ≥ e ⇔ I ∉ {i_{1}, …, i_{p}} for each value e in L, where i1, …, ip are all positions in L with values smaller than e. If desired, similar constraints can be generated for V ≤ e — and indeed that is the basic point of cc(FD): the programmer can put in his own heuristics in a declarative way.

The most difficult constraint is circuit which enforces a circuit among a set of n variables wrt their indices. The easiest way to implement the constraint is to spawn a recursive predicate for each variable. Those constraints make sure that all variables at a distance < n-2 on the path starting from a variable are different from the index of that variable. The recursive predicate makes use of Ask to control the termination and find the successor (instead of guessing it). It is also possible to express the circuit constraint using only cardinality and universal quantification by creating variables for the successors of a variable.

Demons and Declarations. CHIP also has demon declarations and an if then else construct, which are easily expressed using Asks. It also has two declaration mechanisms to define non-primitive constraints using forward checking and lookahead. These two mechanisms are obsolete since arc-consistency can be enforced in an optimal manner using cardinality. In addition, Ask can delay a constraint until it is sufficiently instantiated thus obtaining the effect of forward checking.

Discussion. cc(FD) generalizes the finite domain part of CHIP in many ways. First, it provides, at the language level, all the principles that were previously buried inside the implementation. Typical examples are arithmetic reasoning and consistency techniques. Second, it proposes general ways of dealing with some issues such as disjunctions. Cardinality and constructive disjunction are particularly helpful in that respect. Third, it allows more efficient implementation techniques by taking advantage of the property of the constraints. This is one of the basic features of universal and existential quantification. Last, it allows non-primitive constraints to be handled in exactly the same way as primitive constraints.

5 Conclusion

This paper aimed at presenting an overview of the constraint processing facilities of cc(FD). cc(FD) is best viewed as a systematic reconstruction and extension of the finite domain part of CHIP and supports both consistency techniques and nondeterminism in a declarative language. The main novelty in cc(FD) is to support consistency techniques at the language level through a number of combinators and constraint operations. This is to be contrasted with existing constraint logic programming languages where all constraint techniques are buried inside the constraint solver with the consequence that the user has no way to extend and modify the constraint solver and to define his own non-primitive constraints.

The main advantages which result from the design of cc(FD) are (1) the additional flexibility and extensibility which enables the user to define his own constraints (2) the clean semantic foundation in terms of an extremely simple constraint solver.

Another contribution of this research is the identification of a number of general-purpose constraint operations and combinators which will be valuable for other constraint systems as well.

Current research on this topic is devoted to a robust implementation of the language as well as the study of the combinators for other constraint systems, e.g. linear rational arithmetics.

Acknowledgements. We thank John Lamping, Johan deKleer, Danny Bobrow and Francesca Rossi for useful discussions.

References

[1] A. Borning. The Programming Language Aspects of ThingLab, a Constraint-Oriented Simulation Laboratory. ACM Transaction on Programming Languages and Systems, 3(4):353–387, 1981.

[2] J. Carlier. Ordonnacement a contraintes disjunctives. RAIRO , 12:333–351, 1978.

[3] M. Dincbas, H. Simonis, and P. Van Hentenryck. Solving the Car Sequencing Problem in Constraint Logic Programming. In European Conference on Artificial Intelligence (ECAI-88), Munich, W. Germany, August 1988.

[4] M. Dincbas, H. Simonis, and P. Van Hentenryck. Solving Large Combinatorial Problems in Logic Programming. Journal of Logic Programming, 8(1-2):75–93, 1990.

[5] M. Dincbas, P. Van Hentenryck, H. Simonis, A. Aggoun, T. Graf, and F. Berthier. The Constraint Logic Programming Language CHIP. In Proceedings of the International Conference on Fifth Generation Computer Systems, Tokyo, Japan, December 1988.

[6] R.E. Fikes. A Heuristic Program for Solving Problems Stated as Non-deterministic Procedures. PhD thesis, Comput. Sci. Dept., Carnegie-Mellon Univ. Pittsburgh, PA, 1968.

[7] C.L. Forgy. Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem. Artificial Intelligence, 19:17–37, 1982.

[8] G.Gierz, K.H.Hoffman, K.Keimel, J.D.Lawson, M.Mislove, and D.S.Scott, editors. A compendium of continuous lattices. Springer-Verlag Berlin Heidelberg New York, 1980.

[9] T. Graf, P. Van Hentenryck, C. Pradelles, and L. Zimmer. Simulation of Hybrid Circuits in Constraint Logic Programming. Computers and Mathematics with Applications, 20(9/10):45–56, 1990.

[10] J. Jaffar and J-L. Lassez. Constraint Logic Programming. In POPL-87, Munich, FRG, January 1987.

[11] R. Jagadeesan, V. Shanbhogue, and V. Saraswat. Angelic non-determinism in concurrent constraint programming. Technical report, System Sciences Laboratory, Xerox PARC, January 1991.

[12] J-L. Lauriere. A Language and a Program for Stating and Solving Combinatorial Problems. Artificial Intelligence, 10(1):29–127, 1978.

[13] Patrick Lincoln and Vijay Saraswat. Proofs as Concurrent Processes: A Logical Interpretation for Concurrent Constraint Programming. Technical report, Systems Sciences Laboratory, Xerox PARC, November 1991.

[14] Alan. K. Mackworth. Consistency in Networks of Relations. AI Journal, 8(1):99–118, 1977.

[15] Alan. K. Mackworth. Constraint Satisfaction. Handbook of AI, 205–211, 1988.

[16] R. Mohr and T.C. Henderson. Arc and Path Consistency Revisited. Artificial Intelligence, 28:225–233, 1986.

[17] V.A. Saraswat. Concurrent Constraint Programming Languages. PhD thesis, Carnegie-Mellon University, 1989.

[18] V.A. Saraswat and M. Rinard. Concurrent Constraint Programming. In Proceedings of Seventeenth ACM Symposium on Principles of Programming Languages, San Francisco, CA, January 1990.

[19] V.A. Saraswat, M. Rinard, and P. Panangaden. Semantic Foundations of Concurrent Constraint Programming. In Proceedings of Ninth ACM Symposium on Principles of Programming Languages, Orlando, FL, January 1991.

[20] Dana S. Scott. Data types as lattices. SIAM, 5(3):522–587, 1976.

[21] Dana S. Scott. Domains for denotational semantics. In Proceedings of ICALP, 1982.

[22] H. Simonis. Test Generation using the Constraint Logic Programming Language CHIP. In Sixth International Conference on Logic Programming, Lisbon, Portugal, June 1989.

[23] H. Simonis and M. Dincbas. Using an Extended Prolog for Digital Circuit Design. In IEEE International Workshop on AI Applications to CAD Systems for Electronics, pages 165–188, Munich, RFA, October 1987.

[24] H. Simonis and M. Dincbas. Using Logic Programming for Fault Diagnosis in Digital Circuits. In German Workshop on Artificial Intelligence (GWAI-87), pages 139–148, Geseke, RFA, Septembre 1987.

[25] A. Tarski. Logics, semantics and meta-mathematics. Oxford University Press, 1956. Translated by J.H. Woodger.

[26] P. Van Hentenryck. Constraint Satisfaction in Logic Programming. Logic Programming Series, The MIT Press, Cambridge, MA, 1989.

[27] P. Van Hentenryck and Y. Deville. Operational Semantics of Constraint Logic Programming over Finite Domains. In Third International Symposium on Programming Language Implementation and Logic Programming (PLILP-91), Passau (Germany), August 1991.

[28] P. Van Hentenryck and Y. Deville. The Cardinality Operator: A new Logical Connective and its Application to Constraint Logic Programming. In Eighth International Conference on Logic Programming (ICLP-91), Paris (France), June 1991.

[29] P. Van Hentenryck, H. Simonis, and M. Dincbas. Constraint Satisfaction Using Constraint Logic Programming. Technical Report (Forthcoming), Brown University, November 1991.

[30] D.H.D. Warren. The Andorra Principle. Presented at the 1987 GigaLips workshop, U. of Bristol.

A Closure operators

An operator over a partial order that is extensive, idempotent and monotone is called a closure operator (or, more classicaly, a consequence operator, [25]). Closure operators are extensively studied in [8]; continuous closure operators have been used in [20] to characterize data-types.

We list here some basic properties. Every closure operator can be uniquely represented by its range (which is the same as its set of fixed points); the function can be recovered by mapping each input to the least element in the range above it. (In the following, we shall often confuse a closure operator with its range, writing x ∈ f to mean f(x) = x.) In fact, a subset of |D| is the range of a closure operator iff it is closed under glbs of arbitrary subsets. (Thus, the range of every closure operator is non-empty, since it must contain ⊤_{|D|} = glb∅.)

Also, it can be shown that a closure operator is continuous iff its range is closed under the lubs of directed subsets. The extensional partial order on closure operators (f ≤ g iff for all x, f(x) ≤ g(x)) translates into reverse-inclusion on the set of fixed points: f ≤ g iff f ⊇ g. The identity operator I (with range |D|) is the bottom element; the operator which maps every element to ⊤ (and hence has range {⊤}) is the top element. In fact it is easy to see that the set of closure operators over |D| ordered by ⊇ is a complete lattice, with meets and joins given by: P ⊓Q = {c⊓d | c, d ∈ P ∪Q} and P ⊔Q = P ∩Q. As we shall see, joins correspond to parallel composition.

In the presence of angelic non-determinism (disjunction), it becomes necessary to take the denotation of a program to be a linear closure operator over P_{I}(|D|), the indeterminate power-domain of |D| [11]. (Roughly, this power-domain has as elements upwards-closed subsets of |D|, ordered by reverse set inclusion. A function is linear if it satisfies the property that f(S) = ∪_{s∈S}f({s}).) Such closure operators can also be characterized by the set of their fixed-points, which need not be closed under glbs.