# 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:

• CHIP
• Prolog III
• CLP (sigma*)
• CLP(R) -- domain is reals plus trees
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

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 ML and 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"

### Rules

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).`

## Examples

/**********************************************/ /* 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:

• ordinary prolog examples (no use of constraints on the reals):
• append
• flight - simple airline database
• map
• member
• nrev
• sublist
• examples illustrating use of constraints:
• fact: factorial
• fib: fibonacci
• gcd: greatest common divisor
• length: length of a list
• points: point arithmetic (illustrates constraint abstraction)
• permute (includes inefficient sort)
• smm: cryptarithmetic
• air: chemical engineering
• resistors: simple resistor circuits
• laplace: heat transfer problem
• mortgage: interest computation
• amplif, rlc: circuit analysis

## 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)

• static constraints vs dynamic constraints
• constraints can affect future program execution
some efficiency issues:
• comparable to Prolog for pure logic programs
• good average behavior of constraint satisfier
-> use several constraint satisfaction algorithms, appropriately linked
• incremental constraint satisfier

points to notice from online demos:
• parametric variables
A=2*B+1, 4*C=A+3, B=D-8.

• power of paradigm -- nice examples include heat transfer application, resistors analysis program

• standard Prolog search order loop(X) :- loop(X). test1(A) :- A=4, loop(A), A=3. test2(A) :- A=4, A=3, loop(A). test1 goes into an infinite depth-first search, but test2 fails.

• delayed constraints & "maybe" answer X*X = 4. not as smart as one might like (but making it smarter would probably slow it down a lot!) X*X = 4, X>0. /* gives a 'maybe' answer */ X*X = 4, X=2. /* gives a 'yes' answer with X=2 */ 4=abs(W).

• unification vs equality constraints X = point(3,4). A = f( X , 0.5 , g(Z) ), B = f( sin(Y) , Y , WW ), A=B. In the above example, `point` and `g` are uninterpreted function symbols; `sin` is interpreted.

## 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

solver modules:
• equality solver
• inequality solver
• nonlinear handler
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:

• unconstrainted variables and slack variables
• symbolic entries denoting infinitesimal values
• negative or positive coefficients for basic unconstrained variables
detection of implicit equalities (could scrap equality solver and just do it all with Simplex ...)

Nonlinear handler: delay nonlinear constraints until they become linear