Constraints

Constraints

Post by Mauro Di N » Sun, 02 Oct 2005 22:40:47


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

Post by Neng-Fa Zh » Mon, 03 Oct 2005 11:32:35

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

Cheers,
Neng-Fa

 
 
 

Constraints

Post by Mauro Di N » Mon, 03 Oct 2005 21:43:57

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.
Thanks in advance,
M
 
 
 

Constraints

Post by Torbjn Lag » Mon, 03 Oct 2005 21:53:40

Check out this excellent book:

http://www.yqcomputer.com/

Cheers,
Torbjn
 
 
 

Constraints

Post by A.L. » Mon, 03 Oct 2005 22:30:13

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
to adjust your browser settings...."

A.L>
 
 
 

Constraints

Post by A.L. » Mon, 03 Oct 2005 22:42:22

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

Post by arv83 » Mon, 03 Oct 2005 23:06:13

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

Post by Mauro Di N » Mon, 03 Oct 2005 23:41:31

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.
(One could read about this in almost any Prolog introductory book)
2) Prolog could use a sort of "asynchronous" variable-freezing.
This has the known advantages regarding both source-readability and
execution speed.
Can this be called CLP?
(This could be implemented in a few sourcecode lines)
3) "Real" CLP implements algorythms to prune the search.
(I think there is very much "theory" behind this)

Isn't it?
M