Constraint Logic Programming

CLP(D) is a language framework, parameterized by the domain of the constraints. We'll be looking at CLP(R), constraint logic programming for the reals.

Example CLP languages:

There is also an analogous framework HCLP(D), which allows both required and preferential constraints. It is again parameterized by the domain of the constraints. (See Molly Wilson's PhD dissertation.)

Key concepts in CLP


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)


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 ML and Haskell.


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.


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"


A CLP(R) program consists of a collection of rules. P :- Q1, ... Qn, C1, ... Cm This says that P holds if Q1, ... Qn, C1, ... Cm hold, for subgoals Q1, ... Qn and constraints C1, ... Cm.

Execution model: depth-first search; backtracking when needed.

dual declarative and procedural reading of Prolog program

To run clpr on orcas:
/cse/courses/misc_lang/axp/clpr/bin/clpr (or put /cse/courses/misc_lang/axp/clpr/bin/ in your search path)

For example programs see ~borning/clpr/myprogs/* and ~borning/clpr/progs/* )

You can load a file using the file name as a command line argument:

clpr resistors

Once you are in clpr, you can load a file using consult(myfile).

To reload a changed file: reconsult(myfile).


/**********************************************/ /* centigrade-fahrenheit converter* cf(C,F) :- F = 1.8*C + 32. /**********************************************/ /* length relation */ length([],0). length([H|T],N) :- N > 0, length(T,N-1). /**********************************************/ /* list of numbers between Start and Stop */ range(Start,Stop,[]) :- Start > Stop. range(Start,Stop,[Start|More]) :- Start <= Stop, range(Start+1,Stop,More). /**********************************************/ /* sorting */ quicksort([],[]). quicksort([X|Xs],Sorted) :- partition(X,Xs,Smalls,Bigs), quicksort(Smalls,SortedSmalls), quicksort(Bigs,SortedBigs), append(SortedSmalls,[X|SortedBigs],Sorted). partition(Pivot,[],[],[]). partition(Pivot,[X|Xs],[X|Ys],Zs) :- X <= Pivot, partition(Pivot,Xs,Ys,Zs). partition(Pivot,[X|Xs],Ys,[X|Zs]) :- X > Pivot, partition(Pivot,Xs,Ys,Zs). /* auxiliary function - list append */ append([],X,X). append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs). Some sample programs on orcas:

The CLP(R) system

an instance of the CLP scheme: explores efficient implementation; used for a variety of applications

benefits of CLP scheme (pointed out in paper)

some efficiency issues:
points to notice from online demos:

The CLP(R) interpreter

Constraint Logic Abstract Machine (CLAM) -- derived from Warren Abstract Machine (WAM)

The Engine

The engine is a structure sharing Prolog interpreter (see Figure 2, page 360)

Distinguish between constraints that can be handled in the engine (e.g. nonsolver variable = number) and those that must be passed to the interface. Constraints that can be handled in the engine are shown in figure 3, page 361.

The Interface

Simplify input constraint by evaluating arithmetic expressions. If constraint is ground, test it

If there is one non-solver variable, set up a binding. Otherwise put constraint into a canonical form and invoke solver.


solver modules: Equality Solver: variant of Gaussian elimination.

Represent nonparametric variables in terms of parametric variables and constants. Central data structure: a tableau (2d array). Each row represents some nonparametric variable as a linear combination of parametric variables.

Equality solver is invoked by the interface with a new equality, from the inequality solver with an implicit equality, or with a delayed constraint from the nonlinear handler. Inequality Solver: adapted from first phase of two-phase Simplex algorithm

augmentations of basic Simplex algorithm:

detection of implicit equalities (could scrap equality solver and just do it all with Simplex ...)

Nonlinear handler: delay nonlinear constraints until they become linear