9.1 A Naive Distribution Strategy

The distributor we program in this section implements a naive distribution strategy: choose the first not yet determined variable from a list and try the smallest possible value first. The distributor is shown in Figure 9.1.

proc {NaiveDistributor Is}
      Fs={Filter Is fun {$ I} {FD.reflect.size I}>end}
      case Fs
      of nil then skip 
      [] F|Fr then M={FD.reflect.min F} in 
         choice F=M   {NaiveDistributor Fr}
         []     F\=:M {NaiveDistributor Fs}

Figure 9.1: A distributor for a naive distribution strategy.


To maximize the information available for distribution we wait until the computation space becomes stable. A thread that executes {Space.waitStable} blocks until its hosting computation space S becomes stable. When S becomes stable, execution proceeds with the next statement.

Thus, the variable Fs in Figure 9.1 denotes the list of undetermined variables after S has become stable. To detect undetermined variables we use the procedure FD.reflect.size that returns the current size of a variable's domain. If the domain size is one, the variable is determined and consequently not included in the list Fs.

Then the least possible value for the first undetermined variable F is computed by

M={FD.reflect.min I}

binary choice-statements

We now have to distribute. To this aim Oz provides a binary choice-statement. If a thread reaches the statement

choice S1 

the thread is blocked until its hosting computation space becomes stable.

If the space has become stable, the computation in the blocked thread is resumed and it is distributed. Distribution yields two spaces, one obtained by replacing the choice-statement by the statement S1, one obtained by replacing the choice-statement by the statement S2. All search engines in this tutorial will explore the space first which hosts S1.

In Figure 9.1, we distribute with the constraint that the selected variable is determined to the current least possible value. The distribution is done if no undetermined variables are left.

Christian Schulte and Gert Smolka
Version 1.4.0 (20080702)