Constraint Logic Programming
CLP(D) is a language framework
syntax much like Prolog
Prolog rules:
P :- Q1, ... Qn
CLP rules
P :- Q1, ... Qn, C1, ... Cm
where constraints Ci are over some domain D
Example CLP languages:
- CHIP
- Prolog III
- CLP (sigma*)
- CLP(R) -- domain is reals (plus ordinary Herbrand Universe)
In contrast to Prolog, the function symbols for constraints over the domain
D are interpreted
Examples:
cf(C,F) :-
F = 1.8*C + 32.
?- 2*A+B=7, 3*A+B=9.
A=2, B=3
?- X*X*X + X = 10.
("maybe" answer)
To run clpr on lynx/grizzly/wolf:
put this in your .login
setenv CLPRLIB ~borning/clpr/lib
then execute:
~borning/bin/clpr
For example programs see ~borning/clpr/myprogs/* and ~borning/clpr/progs/* )
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
unification vs equality -- there are actually two domains: the Herbrand
universe and D (in this case the real numbers)
unification is solving equations over the Herbrand universe
For a given Prolog program, the Herbrand universe contains all values that
can possibly be produced by the program
example:
p(f(X)) :- q(X).
q(a).
q(b).
Herbrand Universe:
a, b, f(a), f(b), f(f(a)), f(f(b)), ...
Other example -- peano arithmetic in Prolog
/* addition */
plus(X,0,X).
plus(X,s(Y),s(Z)) :- plus(X,Y,Z).
Herbrand universe is 0, s(0), s(s(0)), ...
In contrast, CLP programs are not restricted to the Herbrand Universe
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
[online demo happens here]
points to notice from demo:
- 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
Hierarchical Constraint Logic Programming
HCLP is a generalization of the CLP scheme that allows both required and
preferential constraints
Like CLP, it is parameterized by D, the domain of the constraints.
See
UW papers on HCLP for more information.