CSE 341 - Constraints and Constraint Logic Programming

A constraint represents some relation that we want to be satisfied. For example, we can have a constraint that A=2*B, that a milling machine can process at most 5 parts per hour, that a line in a picture remain horizontal, that a resistor in an electrical circuit simulation obey Ohm's Law, or that one column in a web page table be at least twice as wide as another. Constraints have been used in a variety of languages and systems, for example for planning and scheduling, user interface toolkits, and simulation.

We can augment the basic idea with such concepts as optimization (for example, to maximize or minimize some expression subject to a set of constraints), or with preferential as well as required constraints.

Constraints are declarative: ideally, they let the user express what is wanted rather than how to do it. They can often be used in multiple ways. For example, given an Ohm's Law constraint V=I*R, if we know V and I we can find R; but if we know I and R we can find V. Constraints also allow partial information to be expressed and combined: one constraint might specify that X is non-negative, another that X is less than 10.

Unfortunately, it is often easier to express constraints than it is to solve them, so that for practical systems we need to limit the class of constraints that can be expressed, give information on how to solve them, or both.

Constraints can be embedded in a fundamental way in a programming language. In 341 we will look at the Constraint Logic Programming (CLP) language framework. CLP(D) is a language framework, parameterized by the domain of the constraints. We'll be using CLP(R), constraint logic programming for the reals. CLP is basically a superset of the logic programming language Prolog, so we'll be learning about logic programming at the same time.

Example CLP languages:

CLP(R) -- domain is reals plus trees
CHIP
Prolog III
CLP (sigma*)

Benefits of Learning about Constraints and CLP Languages

Logic and constraint programming is another major language family, which we haven't seen in the other languages in 341.
CLP has a nice theoretical basis -- we will use this as a vehicle to (briefly) discuss operational semantics.
Declarative languages have some major benefits in terms of ease of analysis and optimization, which may well be important in the future. So far, the major success story for declarative languages is probably SQL -- but we may see more in the future.

Key concepts in CLP(R)

Data

Data is either real numbers (approximated by floating point numbers), or trees ("elements in the Herbrand universe"). Also called "terms".

Trees are constructed from atoms (written as a symbol beginning with a lower case letter) and "uninterpreted functors" (function symbols). Examples:

x fred point(3,4) [a,b,c,d] /* a list with four elements */ line(point(3,4),point(10,20))

Logic variables

There is no assignment statement; rather, the value of a variable is refined as the computation progresses and constraints are accumulated on the value of a variable. Important: we can have variables embedded in trees (terms).

Scope rules are simple: variables locally scoped within a fact, rule, or query.

Syntax: variables begin with a capital letter.
Anonymous variable: _ (underscore)

Constraints

For trees, the only kind of constraint is equality. These equality constraints are solved by unification (two-way pattern matching), as we used in type checking in Haskell.

Examples:

a=a succeeds a=b fails a=X succeeds with X=a X=Y succeeds with X=Y (or Y=X) point(X,X)=point(10,Y) succeeds with X=Y=10 [X,Y] = [1,2] succeeds with X=1, Y=2 [X|Xs] = [1,2,3,4,5] succeeds with X=1, Xs=[2,3,4,5] [X|Xs] = [1] succeeds with X=1, Xs=[] [X|Xs] = [] fails

For lists, the vertical bar divides the elements at the front of the list from the rest of the list.

For real numbers, the relational operators are +, <=, <, >= and >. The function symbols are + - * / sin cos pow max min abs.

Examples:

X=1+4*5 succeeds with X=21 2*X+Y=7, X+Y=5 succeeds with X=2, Y=3 X<=10, X<=5, X>=2 succeeds with 2<=X<=5 pow(sin(X),2) + pow(cos(X),2) = 1 says "maybe" X*X + 3*X + 5 = 9 says "maybe"

CLP(R) Programs

Given an initial goal, a CLP interpreter rewrites any user-defined constraints in the goal using their definitions. This may yield more user defined constraints, which are then rewritten. We continue until there are only primitive constraints, which are solved by the system.

However, if the constraint store contains an unsatisfiable set of constraints, we can stop rewriting immediately.

We may have multiple rules for a given user-defined constraint. We search through the possible rules using a depth-first search, backtracking if one of the choices fails.

Toward a More Formal Model

Here's a slightly more formal discussion. (We'll formalize this in a separate set of notes.)

A CLP(R) program consists of a collection of rules. Each rule has the form

P :- L₁, ... L_m P is a user-defined constraint, and L₁, ... L_m are either primitive constraints or other user-defined constraints. (The L_i are called "literals".) This rule says that P holds if L₁, ... L_m hold.

Dual reading of CLP(R) rules

declarative: L₁ and ... L_m => P
procedural: to satisfy P, satisfy L₁ and ... L_m.

A goal is a sequence of primitive and user-defined constraints.

Execution model (still an informal description):

Suppose the user presents a goal G, where G = L₁, ... L_m. We process the literals in order (left-to-right). If L_i is a primitive constraint, we add it to the "constraint store". If the constraint solver can determine that the constraints in the store are unsatisfiable, we either backtrack and try another choice, or signal a failure if there aren't any more choices. (More about choices and backtracking shortly.)

Otherwise L_i must be a user-defined constraint. We look for a rule matching that constraint, set up constraints between the arguments of L_i and those of the head of the rule, and replace L_i with the body of the rule. (This is a bit like calling a procedure, and passing the arguments by setting up equality constraints between the actual and formal parameters.) When we do this replacement, we get fresh variables for those in the rule -- there isn't a problem if we happened to have a variable with the same name in the goal and the rule.

There may be several possible rules that are applicable to process L_i. If there are, pick the first one (but remember that there was a choice, in case we need to try another one later).

Continue on in this way until all of the user-defined constraints have been rewritten as primitive constraints. If the primitive constraints are not known to be unsatisfiable, return an answer. The answer is the set of constraints in the store with respect to the variables in the original goal. In some cases this answer will be specific values for each variable in the goal, but in other cases it will be some more general constraints on the variables.

At any point along the way, if the system decides the constraints in the constraint store are unsatisfiable, backtrack and try another choice of rule. (This is done using a depth-first search.) If there are no more possible rules to try, the result is failure.

The user can also reject an answer; in that case, backtrack and try another choice of rule for a user-defined constraint (again, using a depth-first search).

Examples

For various CLP(R) examples, see the file lecture.clpr. There are other examples as well in ~borning/clpr/* on attu