3.4 New Primitives

This section gives you an idea of the new Oz primitives needed to express search engines and finite domain scripts.

The new primitives come in two orthogonal groups. The first group provides the ability to create and distribute spaces and to explore search trees. This ability is essential for the implementation of search engines based on the propagate and distribute paradigm. As was mentioned before, this paradigm is general and applies also to constraints other than finite domain constraints.

The second group of primitives provides the ability to create finite domain propagators and to tell domain constraints to the constraint store. It also provides the ability to access the domain of a variable in the current constraint store, an expressivity needed for programming distribution strategies.

first-class spaces

Oz provides spaces as first-class citizens that can be created, distributed, and killed, among other things. A first-class space is almost like Oz's unique top-level space, where regular computation takes place. Like the top-level space, first-class spaces have a constraint store, a procedure store, and a cell store and can host any number of threads. One important difference between the top-level and first-class spaces is the treatment of failure, which is considered an error at the top level and a regular event in first-class spaces (this space has no solution).

attributes of global objects cannot be assigned

The parent of a first-class space is the space that created it. The constraint and the procedure store of a first-class space inherit all constraints and procedures in the respective stores of the parent space. However, a first-class space has no write access to the cell store of its parent space. Consequently, it is impossible to assign in a first-class space attributes of objects that belong to an ancestor space. On the other hand, a first-class space can create its own objects and apply them freely.

The details of first-class spaces need only concern programmers who want to implement new search engines. For finite domain problems, the necessary search engines are already available as predefined functionality (e.g., SearchOne and SearchAll).

All functionality related to finite domain constraints is provided through the procedures of the module FD. We have already seen FD.distinct (creates a propagator) and FD.distribute (creates a distributor) in the script for the Send More Money Puzzle (see Section 3.2).

infix notations

For some of the procedures of the module FD, Oz provides special infix notations governed by the following operators:

   ::    :::    =:    \=:    <:    >:    =<:    >=:

You have already seen examples of the use of :::, \=:, and =: in the script Money. An equivalent version of Money not using these notational conveniences appears in Figure 3.4

proc {Money Root}
   S E N D M O R Y
in 
   Root = sol(s:S e:E n:N d:D m:M o:O r:R y:Y)
   {FD.dom 0#9 Root}
   {FD.distinct Root}
   {FD.sum [S] '\\=:' 0}
   {FD.sum [M] '\\=:' 0}
   {FD.sumC
    [1000  100   10  1  1000  100  10  1  ~10000  ~1000  ~100  ~10  ~1]
    [   S    E    N  D     M    O   R  E       M      O     N    E   Y]
    '=:' 
    0}
   {FD.distribute ff Root}
end