CPI class OZ_Propagator

The emulator requires a uniform way to refer to all instances of propagators. This is realised by providing the class OZ_Propagator, which is the class all propagators have to be inherited from. Therefore, the emulator can refer to any propagator by a pointer of type (OZ_Propagator *) The class OZ_Propagator is in terms of C++ a so-called abstract base class, i. e. no object of such a class can be created (since for at least one member function intentionally no implementation is provided, indicated by an appended =0. Instead, it defines the minimal functionality required of all classes inherited from it. The following code depicts a fragment of the definition of the class OZ_Propagator defined by the CPI (in the file mozart_cpi.hh). It shows all member functions which have to be defined in a derived class.

class OZ_Propagator {
public:
  OZ_Propagator(void);
  virtual OZ_Term getParameters(void) const             = 0;
  virtual size_t sizeOf(void)                           = 0;
  virtual void gCollect(void)                           = 0;
  virtual void sClone(void)                             = 0;
  virtual OZ_Return propagate(void)                     = 0;
  virtual OZ_PropagatorProfile * getProfile(void) const = 0;
}

getProfile()

For each propagator class, one instance of class OZ_PropagatorProfile is allocated. This class is intended to give the Oz Profiler access to some information about this class, for instance a count of the number of invocations of propagators belonging to this class. This function must return a pointer to this instance, but otherwise the programmer needs not to be concerned about it. Note that for the profile function to be shared for all instances, it has to be declared static.

getParameters()

The arguments of a propagator are returned by getParameters() as a list represented as an Oz heap data structure. This is denoted by the return type OZ_Term.

sizeOf()

Memory management of Oz requires to know the size of a propagator. The member function sizeOf() implements this functionality. Its return type is defined in the standard header <stddef.h>.

gCollect() and sClone()

Further, on garbage collection and space cloning references into heap which are held in the state of the propagator (or somehow reachable by a propagator) have to be updated, since items stored on the heap are occasionally moved to a new location. The member functions gcollect() and sClone are provided for that purpose. The definition of these functions is identical for most propagators. For an example where the difference of both functions matters see Section 1.7.2.

propagate()

The most important member function is propagate(). It is responsible for the actual constraint propagation and is called by the emulator when the propagator's execution state is switched to running. The returned value of type OZ_Return indicates the runtime system the outcome of the propagation performed by propagate().

CPI class OZ_FDIntVar

A propagator needs direct access to the variables it is imposed on. The interface class OZ_FDIntVar provides member functions to access variables in the constraint store. The constructor dereferences a variable in the store and stores the dereferenced information in the state of the newly created object. The operators * and -> are overloaded to provide direct access to the finite domain of a variable in the store or to invoke member functions of the class OZ_FiniteDomain (see below).

CPI class OZ_FiniteDomain

The finite domain of a variable is represented by an instance of the class OZ_FiniteDomain, modifying their value is immediately visible in the constraint store. Calling the constructor with the value fd_empty creates an empty finite domain, as used for the auxiliary variables here. The operator += adds a value to a domain. The operator &= intersects two domains, modifies the domain on the left hand side and returns the size of the intersected domain. The member function getMinElem() returns the smallest value of the domain and getNextLargerElem(i) returns the smallest value of the domain larger than i (both return -1 when they reach their respective end of the domain). Testing whether a value is contained in a domain or not can be done by the member function isIn().

The implementation

The implementation of the constraint proceeds as follows. First the variables in the store are retrieved and stored in the local C/C++ variables x, y and z. The corresponding auxiliary domains are held in the variables x_aux, y_aux and z_aux, which are initialised to empty domains. Two nested for-loops enumerate all possible pairs of values of the domains of and . Each loop starts from the smallest value of the domain and proceeds until -1 is returned, indicating that there is no larger value. If there is a value in the domain of satisfying the relation , these values are added to the appropriate auxiliary domains. After completing the nested loops, the domains of the variables are constrained by intersecting them with the auxiliary domains.

FailOnEmpty()

The macro FailOnEmpty() branches to the label failure if its argument results in the value 0. Thereby, constraining the domain of a variable to an empty domain causes the execution to branch to label failure and eventually to return OZ_FAILED to the emulator. The return value of the member function leave() of class OZ_FDIntVar is used to decide whether the propagator returns OZ_SLEEP or OZ_ENTAILED. The return value OZ_ENTAILED indicates entailment and is returned if all variable's domains are singletons. Otherwise, OZ_SLEEP is returned and the propagator is resumed when at least one of its variables is constrained again.

The header function

Before a propagator can be created and introduced to the emulator, its variables must be sufficiently constrained, e.g. the variables must be constrained to finite domains. In case, only a subset of variables is sufficiently constrained, the computation will suspend and resume again when more constraints become available. This is checked by the header function, which is called by the runtime system, when an appropriately connected Oz abstraction is applied. For our example, this function is called fd_add.

Determining when to resume a propagator

Further, when a propagator is imposed on a variable, it has to be determined which changes to the domain resume the propagator again. The alternatives are to resume a propagator if the variable's domain becomes a singleton, the bounds are narrowed or some value is removed from the domain.

Using OZ_EXPECT

The macro OZ_EXPECT ensures that incompatible constraints on the propagator's parameters lead to failure and insufficient constraints cause the execution to be suspended until more constraints become known. An object of class OZ_Expect collects in its state all variables the propagator is to be imposed on. Such an object is at the first argument position of OZ_EXPECT. The second argument of OZ_EXPECT determines which argument of fd_add shall be checked. The member function expectIntVar() of class OZ_Expect expects a variable to be already constrained to a finite domain. If a variable is sufficiently constrained, it is stored in the state of the object pe. The second argument of expectIntVar is used to determine what kind of domain pruning causes a propagator to be resumed. Its default value is fd_prop_any, i. e. a propagator is resumed on any pruning of the domain. For further details see Section 1.4.

Creation of a propagator

Finally, the actual propagator is created by calling its constructor via the application of the new operator. The reference to the newly created propagator is passed as argument to impose(), a member function of OZ_Expect, which executes the propagate() method and introduces the propagator to the emulator.

Connecting Propagators and Oz Code

Propagators are connected with Mozart Oz 3 as native functors according to Section 15.3 of ``Application Programming''. To enable that one has to define a function oz_init_module.

 
OZ_BI_proto(fd_add);
 
OZ_C_proc_interface *oz_init_module(void)
{
  static OZ_C_proc_interface i_table[] = {
    {"add", 3, 0, fd_add},
    {0,0,0,0}
  };
 
  AddProp::profile      = "addition/3";
 
  printf("addition propagator loaded\n");
  return i_table;
}
 

The line AddProp::profile = "addition/3"; assigns explicitly the name "addition/3" to the propagator. The default name is "<anonymous propagator>".

Troubleshooting