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