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}
   {Space.waitStable}
   local 
      Fs={Filter Is fun {$ I} {FD.reflect.size I}>1 end}
   in 
      case Fs
      of nil then skip 
      [] F|Fr then M={FD.reflect.min F} in 
         choice F=M   {NaiveDistributor Fr}
         []     F\=:M {NaiveDistributor Fs}
         end 
      end 
   end 
end

Figure 9.1: A distributor for a naive distribution strategy.

choice-statements

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 [] S2 end

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.