Example CLP languages:

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

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

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

Syntax: variables begin with a capital letter.

Anonymous variable: _ (underscore)

Examples:

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:

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

dual declarative and procedural reading of Prolog program

To run clpr on orcas:

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:

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

To reload a changed file: `reconsult(myfile).`

- 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

benefits of CLP scheme (pointed out in paper)

- static constraints vs dynamic constraints
- constraints can affect future program execution

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

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.

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

- equality solver
- inequality solver
- nonlinear handler

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

Nonlinear handler: delay nonlinear constraints until they become linear