![]() |
|||
![]()
|
![]() |
![]() |
![]() |
3. PROGRAMMING WITH A CONSTRAINT STORE3.1. PRIMITIVE CONSTRAINTSThe traditional model of a computer store admits only two possible states for a variable: assigned or unassigned. Constraint programming uses a generalization of this model. A so-called constraint store can hold partial information about a variable, expressed as constraints on the variable. In this model, an unassigned variable is an unconstrained variable. An assigned variable is maximally constrained: no further nonredundant constraints can be imposed on the variable, without introducing an inconsistency. Primitive constraints are the constraints that can be held in the constraint store. The simplest constraint store is the ordinary single-assignment store used in functional programming. In our terms, it is a constraint store in which all constraints have the form Variable = Value. The first generalization is the introduction of the logical variable. This allows information of the form Variable = Term to be stored, where Term is any term in first-order logic. For example it is possible to store X = f(Y). The same representation can be used to store partial information about X. Thus, if nothing is known about the argument of f, we can store X = f(_). This is the model used in logic programming, and in particular by Prolog. The storage model used by logic programming has a weakness, however. This is best illustrated by a simple example. The equation X - 3 = Y + 5 is rejected because logic programming does not associate any meaning with - or + in such an equation. The extension of logic programming to store equations involving mathematical functions was an important breakthrough. Equations involving mathematical functions are passed to the constraint store, and checked by a specialized solver. In fact, not only (linear) equations but also inequations can be checked for consistency by standard mathematical techniques. It is necessary, each time a new equation or inequation is encountered, to check it against the complete set of equations encountered so far. Linear equations and inequations are examples of primitive constraints. Thus, we have an example of a constraint store. Further constraint stores can be built for different classes of primitive constraints, by designing constraint solvers specifically for those classes of constraints. We use the term storage model, rather than data model, because the facility to store constraints is independent of the choice of data model -- object-oriented, temporal, etc. On the other hand, the term storage model as used here does not refer to any physical representation of the stored information. Definition: A constraint store is a storage model that admits primitive constraints of a specific class. Each new primitive constraint that is added to the store is automatically checked for consistency with the currently stored constraints. This definition of a constraint store specifies an equivalent operation to writing to a traditional store. However, no equivalent to the read statement is specified. There are two important facilites useful for extracting information from a constraint store. First, it is useful to retrieve all those constraints that involve a given variable, or set of variables. For example, if the constraint store held three constraints X [greater than or equal to] Z, Y [greater than or equal to] X, W [greater than or equal to] Z, the constraints involving X would be Y [greater than or equal to] X and X [greater than or equal to] Z. However, retrieving only constraints explicitly involving a variable may not give a full picture of the entailed constraints on the variable. For example, the store X [greater than or equal to] Y, Y [greater than or equal to] Z entails X [greater than or equal to] Z. The mechanism necessary to return all the constraints and entailed constraints on a given variable or set of variables is termed projection. A very useful property of a class of primitive constraints is the property that the projection of a set of primitive constraints on a given variable, or set of variables, is also expressible as a set of primitive constraints. If the primitive constraints have this property, it is possible, for example, to drop a variable from the constraint store when it is no longer relevant. This is the equivalent to reclaiming the store associated with a variable in a traditional programming language when the variable passes out of scope. Second, it is useful to retrieve particular kinds of entailed constraints from a constraint store. For example, it is very useful to know when a constraint store entails that a particular variable has a fixed value. For example, the constraint store $X [greater than or equal to] Y, Y [greater than or equal to] 3, 3 [greater than or equal to] X, entails that both X and Y have the value 3.
|
![]() |
|
Use of this site is subject certain Terms & Conditions. Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details. |