next up previous contents
Next: Search Up: Complex Constraints Previous: The chr (Constraint Handling

Explicit Data Driven Control

The propia and chr libraries are implemented using a set of underlying facilities in ECLiPSe which support data-driven computation. The main feature supporting data-driven computation is the suspension. This is illustrated below.

[eclipse 1]:    lib(fd).
*       fd loaded

[eclipse 2]:    suspend(writeln("Wake up!"),1,X->inst),
                writeln("Do this first"), 
                X=1.
*       Do this first
*       Wake up!
*       X = 1
*       yes.

[eclipse 3]:    suspend(writeln("Wake up!"),1,X->inst),
                current_suspension(S),
                suspension_to_goal(S,Goal,M),
                kill_suspension(S),
                call(Goal,M).
*       Wake up!
*       ...
*       yes.

[eclipse 4]:    X::1..10,
                suspend(writeln("Wake up!"),1,X->min),
                X#>3,
*       Wake up!
*       X = X{[4..10]}
*       yes.
Handling Suspensions  

A suspension is a goal that waits to be executed until a certain event occurs. Each suspension is associated with a set of variables, and as soon as a relevant event occurs to any one of the variables in the set, the suspension ``wakes up'' and the goal is activated. One such event is instantiation: all the suspensions on a variable wake up when the variable is instantiated.

In figure gif the first query loads the fd library, which will be used in the last example. It is preferable to load all the libraries that may be needed at the start of the session.

Query 2 suspends a goal writeln(``Wake up!'') on one variable X. The goal will be executed as soon as X becomes instantiated ( tex2html_wrap_inline1694 ). When woken the goal will be scheduled with a certain priority. The priority is given as the second argument of suspend. In this case the priority is 1, which is the highest priority. The remainder of query 2 performs another write statement and then instantiates X. The output from ECLiPSe shows that the suspended goal is not executed, until X is instantiated, after the system has already output Do this first.

Query 3 shows various facilities for explicitly handling a suspension. The current suspensions can be accessed. (It is also possible to access the just the suspensions on a particular variable.) A suspension can be converted to a goal.gif A suspension can be ``killed'', so it is no longer accessible or wakeable. The suspension has no connection to the goal, however, which can still be executed.

To save space the output of variable values is omitted here.

Finally query illustrates another kind of event that can wake up a suspended goal. In this case the goal is suspended until the lower bound of the finite domain associated with X is tightened ( tex2html_wrap_inline1708 ).

There are other events which can wake suspended goals associated with other constraint handlers, but the most general event is that the variable becomes more constrained in any way (expressed as tex2html_wrap_inline1710 ). Goals suspended in this way will wake when any new constraint on X is added (an fd constraint, a ria constraint, or an eplex constraint.

Finally it is also possible to retrieve goals suspended on a given variable, or those associated with a given event on a given variable.

Based on this simple idea it is possible to define a constraint behaviour explicitly. As a simple example let us make a constraint that two variable differ by more than some input number N. We will call the constraint ndiff(N,X,Y), where N is the difference, and X and Y the two variables. Its behaviour will be to tighten the finite domains of the variables.

:- lib(fd).
:- suspend.

ndiff(N,X,Y) :-
    mindomain(X,XMin),
    maxdomain(Y,YMax),
    YMax<XMin+N, !,
    X#>=Y+N.

ndiff(N,X,Y) :-
    mindomain(Y,YMin),
    maxdomain(X,XMax),
    XMax<YMin+N, !,
    Y#>=X+N.
    
ndiff(N,X,Y) :-
    suspend(ndiff(N,X,Y),3,[X,Y] -> any).
Using Suspensions to Implement Constraints  
In figure gif we implement a behaviour for our ndiff constraint. Since we use underlying fd constraints, we load the fd library.gif

The first clause for ndiff checks if the lower bound for X is so close to the upper bound for Y, that X cannot be less than Y (if it was, then to satisfy the ndiff constraint we would need to have Y>=X+N). In this case it imposes the constraint that tex2html_wrap_inline1732 .

The second clause does the symmetrical test on the lower bound of Y and the upper bound of X.

If neither of these conditions are satisfied, then ndiff doesn't do anything. It just suspends itself until the finite domains of X or Y are tightened ([X,Y] -> any).

This very same mechanism of suspended goals is used to implement all the built-in constraints of ECLiPSe. For example the constraint tex2html_wrap_inline1744 is implemented using a goal which is suspended on two events: a change in the maximum of the domain of X, and a change in the minimum of the domain of Y. Typically all the finite domain built-in constraints are suspended on events which occur to the finite domains of their variables.

Before concluding this subsection, we should observe that the different constraint libraries of ECLiPSe are supported by a very flexible facility. The information about each kind of constraint on a variable is held in a data structure which is attached to the variable called an attribute. When the fd library is loaded, each variable in ECLiPSe has a finite domain attribute. If the variable has no finite domain, this attribute contains nothing, and the behaviour of the variable is just as if it had no attribute. On the other hand if the variable does have a finite domain, then the attribute stores the finite domain, as well as pointers to all the suspended goals which are waiting for an event to occur to the finite domain.

Naturally ria constraints and eplex constraints are stored in other attributes, and they have their own suspended goals attached to them.

Any ECLiPSe user can define and implement a completely new constraint handling library in three steps.

  1. A new attribute storing information about the new class of constraints, must be defined.
  2. Events specific to this class of constraints must be specified.
  3. New constraint behaviours must be implemented in terms of goals which suspend themselves on these events.
The ECLiPSe extensions manual [Be97] gives an example of defining such a new constraint library.


next up previous contents
Next: Search Up: Complex Constraints Previous: The chr (Constraint Handling

Joachim Schimpf
Wed Sep 3 18:07:19 BST 1997