Composition in Hierarchical CLP

1 Introduction

The HCLP (Hierarchical Constraint Logic Programm­ ing) scheme [Borning et al., 1989; Wilson and Borning, 1993] greatly extends the expressibility of the general CLP scheme [Jaffar and Lassez, 1987]. There is also related work by Satoh [1990]. A semantics has been de­ fined for HCLP [Wilson and Borning, 1989] and some instances of it have been implemented [Menezes et al., 1993] . However, the semantics is not as natural as one might hope, and the implementations are inherently less efficient than those of CLP. We believe that these two is­ sues may be related, and suggest that an equally expres­ sive scheme which gives similar but not identical answers may go some way to overcoming both of them.

Therefore we propose a weakening of the semantics of HCLP, in which the results of composing solutions to individual hierarchies approximate the solutions that would be obtained from combining the programs and starting from scratch. Our semantics are adequate for some of the standard examples in the literature. They are definitely not sufficient to solve some of the other examples exactly, but our approximations are very rea­ sonable.

2 Incrementality and compositionality

An important difference between logic programming lan­ guages and, say, theorem provers, is that the former are more efficient; expressibility and completeness are traded-off against efficiency. Standard HCLP is beauti­ fully expressive, but the efficiency of its implementations may be poor, and its semantics lacks certain desirable properties. Our proposal in this paper involves trading­ off completeness to gain efficiency and more tractable semantics. In constraint logic programming, efficiency is discussed with reference to 'incrementality', and seman­ tics can be discussed with reference to compositionality, which is what we will do in the rest of this section.

Compositionality is a desirable property for a system to have because it shows that the semantics of the system can be modelled by a mathematical system with formal properties, and because it suggests that implementations will be efficient. This is because compositionality implies decompositionality, i.e. we can solve a complex problem by splitting it into simpler parts, solving them, and then composing the results into a complete solution.

Whereas compositionality is a property of formal sys­ tems, incrementality is a (desirable) property of Con­ straint Logic Programming implementations. There is no precise definition, but what it means is that the work required to add an extra constraint to the solution of a large set of constraints and check its satisfiability is proportional to the complexity of the addition, and not related to the size of the initial set. If a system is not incremental, then adding one more constraint to the so­ lution of, say, 20 constraints, involves as much work as solving the system of 21 constraints from scratch.

In fact, even in an 'incremental' system the amount of work required to deal with an additional constraint will probably depend on more than just the constraint itself: the number of variables in the original set may be relevant, as well as other factors .

We wish to suggest that compositionality is weaker than incrementality: a theory which has compositional semantics may have a non-incremental implementa­ tion, but a truly incremental implementation of a non­ compositional formalism is not possible. What is more important than the distinction between incrementality and compositionality is the distinction between having both these properties and having neither, which is re­ lated to the distinction between 'sufficiently efficient' and 'unusably inefficient'. Both logic programming and con­ straint logic programming are in principle sufficiently ef­ ficient, and they have compositional theories (see next section), and so compositionality is assumed to hold in general, almost without being mentioned. Therefore, the focus in previous CLP work has tended to be on in­ crementality alone, rather than on its relationship with compositionality.

2.1 Query composition in logic programming and CLP

Consider the two programs in Figure 1. They may be logic programs or constraint logic programs. The sub­ scripts 1,2,3 are not part of the predicate names; they indicate that the query?- p(X) will have up to three so­ lutions {P1, P2, P3 }, one from ·each of the three clauses ofp. The composed query?- p(X) &: q(X) will have up to six solutions, arising from®, the composition, in some sense, of the elements of the cartesian product of the two sets of solutions. We could treat each of the {P; ® Qj} combinations independently, and make a distinction be­ tween this multiplicity and multiple solutions all arising from one branch, but we will just consider the collection of solutions as a whole, ignoring how they arose.

In standard logic programming, the composition of the solutions to two or more queries is the most general uni­ fier (m.g.u.) of those solutions. Calculating the m.g.u. of two solutions takes time related to the size of the solu­ tions, and not related to the size of the original programs. Similarly, in constraint logic programming, solving the conjunction of two output sets of constraints will depend on the size of the output, not on the size or complexity of the input constraints.

Hierarchical CLP is not compositional, and so in­ cremental implementations have to make assumptions which may then need to be retracted [Menezes et al., 1993]. But before we can demonstrate this non­ compositionality, it is necessary to provide an overview ofHCLP.

3 Hierarchical Constraint Logic Programming

A good introduction to HCLP can be found in Molly Wilson's PhD thesis [1993, chapter 4] or in the early ref­ erence [Borning et al., 1989]; here is a brief overview. Just as Logic Programming can be extended to CLP, so CLP can be extended to a Hierarchical CLP scheme in­ cluding both 'hard' and 'soft' constraints. The HCLP scheme is parameterised not only by the constraint do­ main 1J but also by the comparator C, which is used to compare and select from the different ways of satisfying the soft constraints.

where t is a list of terms, p, q1, ... , qm are atoms and l1c1, ... , lncn are labelled constraints. A program is a bag (multiset) of rules, and a query is a bag of atoms. The strengths of the different constraints are indicated by a non-negative integer label. Constraints labelled with a zero are required (hard), while constraints la­ belled j for some j > 0 are optional (soft), and are preferred over those labelled k, where k > j. (A pro­ gram can include a list of symbolic names, such as re­ quired, strongly-preferred, etc., for the strength labels, which will be mapped to the natural numbers by the in­ terpreter. If the strength label on a constraint is omitted, it is assumed to be required.)

Goals are executed as in CLP, except that initially non-required constraints are accumulated but otherwise ignored 1 . If a goal is successful but with a non-unique an­ swer, the accumulated hierarchy of optional constraints is then solved, which refines the valuations in the solu­ tion. The method used to solve the non-required con­ straints will vary from domain to domain, and for differ­ ent comparators within a given domain.

The constraint store (]' (a set) is partitioned into the set of required constraints So and the set of optional ones S;. The solution set for the whole hierarchy is a subset of the solution set of So, such that no other solution could be 'better'' i.e. for all levels up to k' sk is completely sat­ isfied, and for level sk+l this solution is better' in terms of some comparator, than all others. Backtracking and incomparable hierarchies give rise to multiple possible solution sets, each a subset of the solution to So. (So­ lutions in standard HCLP are generally described using sets, not bags.)

Certain comparators can be used with any domain. For example, a 'predicate' comparator prefers one solu­ tion to another if it satisfies more constraints at some level (and an equal number of constraints at all previous levels). However if the domain has a metric (such as the real numbers) it is possible to ask how far from the pre­ ferred answer a solution is, in which case one might prefer fewer constraints to be exactly satisfied if the distance of the answer from a given point can be minimised 2 . Weights can be used within a particular level of the hi­ erarchy in order to influence the solution, but a heavily weighted constraint in a given level is completely domi­ nated by the lightest constraint in any higher level. Wil­ son calls this property 'respecting the hierarchy' [1993].

1 Menezes et al. use an alternative strategy [1993].

3.1 The disorderly property of HCLP

Wilson discusses a very simple but powerful example in her PhD thesis [1993], which shows the non-monotonic, hence non-compositional, nature of any variant ofHCLP which respects the hierarchy.

Wilson defines the 'orderly' property as follows: Let P and Q be constraint hierarchies, and let S{P} (C) be the set of solutions to the hierarchy P when comparator Cis used. Then Cis orderly if S{PuQ} (C) ~ Sp'} (C) . A comparator which is not orderly is disorderly.

Prop. 1 Any comparator which respects hierarchies over a non-trivial domain V is disorderly.

Proof ([Wilson, 1993]): Let P = {weak X = a} and Q = {strong X = b} for two distinct elements of V, a and b. (The existence of distinct elements is what makes V non-trivial.) S{P} (C) will be the valuation which maps X to a, and if C respects the hierarchy then S{PuQ} (C) will be the valuation which maps X to b. So S{PuQ} (C) Cf:. Sp'} (C), so C is disorderly. D

We can easily adapt this proof to demonstrate non­ compositionality. Consider S{ Q} (C): it will consist of the valuation mapping X to b. The solution to the composition (conjunction) of the constraints will be S{PuQ} (C), i.e. a mapping from X to b. This is not related to, or derivable from, the union, intersec­ tion, or any other potentially incremental composition of S{P}(C) and S{Q}(C). In this paper we define an ap­ proximation to HCLP which is incremental; our work is based on bags, and so the next section provides an overview of bag theory.

4 Bags and guards

Bags, sometimes called multisets, are like sets except that duplicate elements are allowed i.e. (a, a5 # (a5 (we use(, 5 to denote bags) . In this section, we define various properties of bags, treating as basic the notion of number of occurrences of an element in a bag [Gries and Schnei­ der, 1994]. A brief overview of some of the properties of bags can be found in Knuth [1969] .

2 For a complete understanding of comparators it is neces­ sary to consider 'error sequences' [Wilson and Borning, 1993], but they are quite complicated and are only used briefly in this paper, so we omit them here for reasons of space.

The intuition is that an element which occurs a times in a bag A, and b times in B, occurs a+ b times in the additive-union A 1±1 B, max(a,b) times in AU B, which is the equivalent of set-theoretic union, and min(a,b) times in the intersection AnB. We will not use AUB in this pa­ per, and so we feel free to refer to A 1±1 B as union, rather than the more clumsy 'addition' or 'additive-union'.

Let e#B denote the natural number n of occurrences of the element e in the bag B . Examples: a# (a, a 5 = 2. b# (a, a 5 = 0. A shorthand is to label elements with a superscript indicating the number of occurrences. Ex­ ample: (a, a 5 = ( a 2 5. Of course a#( ak 5 = k. Note that bag intersection is a 'lifted' version of set intersection. In other words, if A and B are both bags with no duplicate elements ('set-like' bags), then so is An B.

4.1 Guards

The above is all standard bag theory. Later in the paper we need an alternative to intersection, with certain other properties, and so we now define a new infix binary op­ erator IJ ('guarded by'). If A and B are both bags, the intuition is that A IJ B contains only those elements of A which are also in B, with the same multiplicity as in A.

We claim that our variant of HCLP, to be defined below using guards, has a strong mathematical basis. In order to defend this view, we now state some properties of §. The proofs are straightforward, using the definitions of the symbols involved, and can be found in our technical report [Jampel and Hunt, 1995] .

Prop. 2 (Idempotence) A(JA =A.

It is clear that IJ is not commutative, i.e. A(JB # B(JA, but it is associative:

Prop. 5 (Associativity) A(J(B(JC) = (A(JB)(JC.

Prop. 6 (Union Distributivity)

(A 1±1 B) IJC = (AIJC) 1±1 (B (JC).

Prop. 7 (Intersection Distributivity)

4.2 Filter functions

To complete the mathematical tools we use later in this paper, we define a class of filters, functions from bags to bags, which remove some of the elements from the input bag. It is necessary to introduce them here because we will use them in the next section to define rules for hi­ erarchy composition; particular examples are discussed later, but in general filter functions will be denoted by f. Note that the guard operator IJ is concerned with the relationship between different strength levels in a hi­ erarchy, whereas filter functions select solutions within a given level. (Similarly, in standard HCLP the com­ parators compare solutions within a given level.) More details can be found in Section 6, where we examine one particular filter at length.

5 Two-level hierarchy composition

We now come to the main interest of the paper. In this section we define an operation o which combines bags and sets in a certain way to form new bags. Our in­ terpretation of these rules is that o approximates the solutions to a composition of hierarchies.

Let P and Q be two programs, and p and q be queries with respect to each of those programs. We will also use capital letters to refer to the entire hierarchy (i.e. program, query, and solutions). Let So(p) be the set of valuations which are solutions to the required constraints in the hierarchy, and let sl (p) be the set of valuations satisfying both the required and the (one level of) op­ tional constraints. Note that S1 (p) ~ So (p). Similarly S'1 ( q) ~ So ( q). Define the solution set for the query p as a tuple containing the solution sets for each level of the hierarchy: S(p) = (So(p),SI(P)).

Note that the solutions to a single (branch of a) query are assumed to form a set (or, rather, a set-like bag). The multiplicities will arise when the solutions to sepa­ rate queries are composed using bag union. (Treating so­ lutions to a single query as bags would give more weight to duplicated solutions from one hierarchy, rather than treating equally all the hierarchies to be composed.)

Later we will use 'p&q' to refer to a standard HCLP query, solved by starting from scratch, and compare it to p o q, which has solutions defined as follows:

Definition (ComposeOl):

The reason for guarding the two S1 's with So (p o q) is to remove solutions for p which are inconsistent with q's required constraints and vice versa, although remember that at this stage we should not really be discussing hi­ erarchies and solutions, because we are still merely ma­ nipulating bags. (In fact, as S1 (p) ~ So(p), it is enough just to guard S1 (p) with So ( q) and vice versa, as can be shown using absorption and distributivity properties, but this does not generalise neatly to compositions of

more than two hierarchies.)

Note that we type-coerce sets to be set-like bags when­ ever we wish to do bag operations on them. Note also that in the definition of sl (p 0 q), we have not included an application of set. We consider it to be the very last action that should be performed on the bags of solutions, perhaps just treated as an aspect of pretty-printing.

Example: Let p and q have the following solution sets: So(P) = {a,b,c} and So(q) = {b,c,d}. Then S0 (poq) = {b,c}. Let S1(p) = {b,c} and S1(q) = {b,d}. Then

Filtering must be left as late as possible within a given level. Specifically, if we are composing more than two hi­ erarchies, the union and guard must be completed before any filtering is done; therefore the general definitions are as follows:

Definition (Multi-Compose):

Although o is commutative (i.e. p o q = q o p), it is not associative, because of the filter functions, i.e. po(qor) f. (p o q) o r f. p o q o r. Only p o q o r is 'correct' for our purposes, which implies the following: if we have calculated the composition po q but suspect that we may later need to compose with another hierarchy, we cannot discard the solutions top and q, but must store them to be able to calculate po qo r subsequently. Thus we trade space against time compared to standard HCLP.

If there are no constraints at the required level, the solution set is the entire domain (the cartesian product of the domains of all the variables) i.e. So = U. It can be seen that guarding any bag with this universal set using IJ will not have any effect: VA · A/JU = A. If there are no constraints at one of the optional levels, the solutions for that level will just be the same as for the next higher level i.e. Sn+l(P) = Sn(p) . Therefore the rules we have defined here will work for hierarchies with arbitrarily many or few constraints at any given level.

In HCLP, the key difference between required and non­ required constraints is that the former can cause failure to occur. In other words, the required constraints may have an empty solution set, but no weaker constraints can cause a failure if stronger constraints have been sat­ isfied. In our composition rules, in A IJ B, A represents the solutions for a weaker level than B, and yet the def­ inition of IJ allows the possibility of A/JB being empty even if B is not (in the case that A n B = (5). Thus our rules appear to allow failure to arise from optional constraints. In fact, as we define the solution S to be the tuple (So, S1, ... , Sn) and not just its final element Sn, it is not a problem if one of the elements of S is empty:

the solution that is offered to the user is no longer the final element of the tuple, but the final non-empty ele­ ment . Thus this aspect of HCLP is not present in our logic, but is left until the interpretation.

6 The filter fmax

The rules defined in the previous section are parame­ terised by filter functions. We now define one particular filter function fmax, which is the most interesting when compared to HCLP's 'locally-predicate-better' compara­ tor [Wilson and Borning, 1993]. fmax removes those el­ ements of a bag which do not occur a maximal number of times. In other words, if some elements occur once in a given bag, and some elements occur twice, fmax defines the bag containing only those elements occurring twice.

Definition:

Examples:

6.1 fmax is incremental

Consider some hierarchy (program, query, and solutions) formed from twenty constraints. Consider the amount of work needed to augment it with a hierarchy resulting from one extra constraint: the two So levels must be intersected, the sl levels must be unioned, filtered, then guarded by the combined So. Calculating an intersection requires work bounded by the size of the smaller of the two sets or bags, as does set-union. Creating a bag-union could take constant time, or at worst time related to the size of the smaller of the two bags. Filtering and guarding will, admittedly, take time bounded by the size of the union of the two bags. But all these operations (intersection, union, filtering , etc.) are computationally very cheap compared to constraint solving. They may be considered unit time operations when measured on the scale of constraint solving. Therefore, when compared to the cost of composing the two programs and queries and starting from scratch, it is reasonable to say that our scheme is incremental.

7 Example and comparison with HCLP

The Multi-Compose definitions from Section 5 can be unfolded as follows :

Definition (Compose012):

We will now use these rules in an extended example, which includes a comparison between our solutions and those of standard HCLP.

Consider the example in Figure 2; part of it (P) is taken from Wilson's thesis [1993, Section 2.2] . The first point to note is that the sub-example of com­ posing P and Q provides motivation for the choice of fmax over simpler filter functions : if we used frd then So(poq) = S1(poq) = ((0 <X< 20)) and S2(poq) = ((X = 4), (X = 7), (X = 14)), i.e. there is not enough discrimination to capture, or even approximate, the be­ haviour of standard HCLP. (Note that we have been using {0 < X < 10} as short-hand for the uncountably in­ finite set-like bag {(X= 0), (X= 1), (X= 2), ... , (X= 0.1), (X = 0.01), ... }, but it is obvious within this no­ tation that the bag union of, say, {0 < X < 10} and {5 < X < 15} has 0 < X ::; 5 and 10 ::; X < 15 with multiplicity 1, and 5 < X < 10 with multiplicity 2.)

Secondly, if we initially apply Compose012 top and q and then apply it again top o q and r, S2((p o q) or) will be the same as S2 (p o q or) (with different muliplicities at the S1 level). But if instead we compose p with q or, then S2(P o (q or)) =((X= 4), (X= 16)5, which differs from s2 ( (p 0 q) 0 r) and is a worse approximation to the result given by standard HCLP. This non-associativity gives rise to multiple possible composition orders and hence solutions, which is why we define the only correct answer to be the one based on composing all three sub­ solutions simultaneously.

Thirdly, and most importantly, if we apply Com­ pose012 all at once, we get an answer which differs from the standard HCLP solution, because it omits the valu­ ation which maps X to 8. Any system which calculates exactly the same answers as HCLP will be vulnerable to Wilson's proof of non-compositionality (discussed ear­ lier in Section 3.1), so the question is whether Com­ pose012 gives a reasonable approximation. We believe that it does; in this example, the only valuation omitted is one which was not present in the original sub-solution containing the constraint which gave rise to it. In R, the X = 8 possibility for X div 8 was dominated by the strong constraint X > 15. In standard HCLP, this domination is weakened by other strong constraints from completely separate hierarchies. In other words, the only solution not calculated by Compose012 is one which we probably do not want anyway!

8 Conclusions and Further Work

We have seen that by storing the intermediate solutions to a hierarchy in a tuple (So, S1, ... , Sn), we can find an approximate solution to its composition with other hier­ archies. We use simple filtering functions and bag oper­ ations, with clear mathematical characterisations, which avoids the need to invoke the constraint solver and start from scratch calculating a solution to the combination of the constraints. The non-associativity of filter functions means that the method is not truly compositional, but it does avoid the need to invoke the constraint solver. In general, constraint satisfaction is of exponential com­ plexity, compared to which filtering and set operations are very cheap indeed. Therefore we feel justified in call­ ing this scheme 'incremental'.

Thus we have developed a variant of Hierarchical CLP in which the solution to a composed problem is defined in terms of the solutions to its sub-problems. The op­ erations involved are simple to understand and efficient and closely approximate the answers we would obtain from standard HCLP, while avoiding its computational expense and complex semantics.

In the future we wish to extend this scheme to take account of error sequences, and hence bring different comparators within the scope of our filtering scheme. We would like to investigate constraint deletion and dy­ namic constraint satisfaction, which are difficult in most formalisms but should be made easier by the modular nature of our tuple representation of solutions.

More generally, we are investigating inconsistencies arising from the composition of CLP programs i.e. pro­ grams without hierarchical strength labels. We wish to explore the parallels between composition of these unla­ belled systems and composition of the labelled systems discussed in this paper.

Acknowledgements

Thanks to Rob Scott, David Gilbert, Steven Eker and Bernie Cohen for helpful discussions on CLP and HCLP.