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

brutal_example :-

X :: [1,4,7], % domain of X

Y :: [3,4,5], % domain of Y

X+Y #< X*Y.

Cheers,

Neng-Fa

X :: [1,4,7], % domain of X

Y :: [3,4,5], % domain of Y

X+Y #< X*Y.

Cheers,

Neng-Fa

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

"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

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>

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

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.

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

pointless: CLP"

A.L.

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.

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.

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

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

1. fmincon constraints: why do inequality constraints fail but bound constraints succeed?

2. Constraint matches constraint named Constraint1 already in collect

3. Data Constraints AND Application Constraints

4. Converting a minimum constraint into an equality constraint?

5. tcltest::test -constraints <constraint with ::>

7. Find out which row/constraint triggers the constraint exception

8. Database constraints and dataset constraints

10. Data Constraints Vs Application Constraints

11. [ANN] constraint 2.0 -- Ensure that objects always satisfy a set of constraints

12. fmincon constraints: why do inequality constraints fail but bound

13. signal constraint: spectral constraint

14. Re-using a simple type definition; with enumeration constraint and without enumeration constraint

15. CFP: Constraints Journal: Special Issue on Local Search in Constraint Satisfaction

8 post • Page:**1** of **1**