## Constraints

### Constraints

Hi all!

Could someone suggest me a good lecture about how "constraints" in logic
programming are implemented?

P.S.: How much the approach is really different from the following...

brutal_example :-
(X = 1; X = 4; X = 7), % domain of X
(Y = 3; Y = 4; X = 5), % domain of Y
A is X+Y,
B is X*Y,
A < B. % this has 4 solutions on backtracking.

?

Thank you.
M

### Constraints

brutal_example :-
X :: [1,4,7], % domain of X
Y :: [3,4,5], % domain of Y
X+Y #< X*Y.

Cheers,
Neng-Fa

### Constraints

Yes, but I am interested in how the step from "generate-and-test" (LP) to
"constraint-and-generate" (CLP) is achieved.
I searched on google and I found some interesting material. But I am
wondering where to find a low-lovel (i.e. a real prolog implementation
"theory", not a user manual) introduction to CLP.
M

### Constraints

Check out this excellent book:

http://www.yqcomputer.com/

Cheers,
Torbjn

### Constraints

On Sun, 02 Oct 2005 12:53:40 GMT, Torbjn Lager < XXXX@XXXXX.COM >

"...The page you are looking for is currently unavailable. The Web
site might be experiencing technical difficulties, or you may need

A.L>

### Constraints

On Sat, 1 Oct 2005 15:40:47 +0200, "Mauro Di Nuzzo"

See the thread " I now realize WHY my 'consistency check' was
pointless: CLP"

A.L.

### Constraints

Essentially the low level WAM machine is extended with 3 or 4 extra
data types to the standard Prologs (var,int,float,atom,struct,list). In
IF/Prolog ( http://www.yqcomputer.com/ ) these extra var
types include:

finite domain - a bit map representation of numbers (A..B)
enumeration - a outer bounds checked value X is between A and B
rationals - an infinite arithmetric representation of real numbers

All of these types are variables which can be freely mixed with the
standard var type. They are initialised as constraint variables using
an in/2 predicate.

Constraint predicates are added and unification is extended for
propagation. The most important aspect of speeding the execution of CLP
as against Prolog search is through propagating data values as soon as
possible. For example if A ?= B + C then as soon as any two of A,B or C
are known the value for the other can be calculated and checked against
the domain. If it is not in the domain then the search backtracks. In
Prolog (A =:= B + C) the value would first be assigned to A,B and C
before the =:=/2 fails causing new NAIVE value generation for A,B and
C.

The key difference is that A,B and C are variables until a value can be
determined. In Prolog the ;/2 generates alternatives in turn for A,B
and C.

Prolog offers other advatages over other constraint systems through the
constraint meta call predicate freeze/2. This enables you to program
code that is executed each time a value is determined for a constraint
variable. This is very useful for solving general problems where
general checks are required.

Constraint programming is also about global constraints which provide
propagation between constraint variables using efficient internal
algorithms.

A simple example of a global constraint is:

cardinality(1,2,[A ?> B,A ?> C,B ? > C])

here the global constraint adds a rule that at least one of the
relations must hold and at most 2 of the relations must hold. This can
further propagate values for other variables leading to efficient
pruning of the search.

There is of course much more to constraint programming than just this
small taster, take a look at http://www.yqcomputer.com/
see some of the interesting projects we have worked on using constraint
logic programming.

### Constraints

Very interesting. Thank you.

So, I learned the following (I hope I am right):
1) Prolog unify variables and test goals, backtracking on failure.
So alternatives are tested along the SLD tree.