- Up - | Next >> |
The distributor we program in this section implements a rather naive strategy. It has a single argument which is a list of finite domain variables. From this list the distributor will select the leftmost undetermined variable and distributes with the constraint
where
is the least possible value for
. The distributor is shown in Figure 9.1.
proc {NaiveDistributor Is}
choice skip end
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 have to wait on stability of a computation space. For this purpose Oz provides a so-called choice-statement. If a thread reaches the statement choice
S end
the thread is blocked until its hosting computation space becomes stable. Then the computation in the blocked thread is resumed and the statement S is executed.
Thus, the variable Fs
in Figure 9.1 denotes the list of undetermined variables after the space has become stable. To detect undetermined variables we use the procedure FD.reflect.size
which reflects the current size of a variable's domain. If the domain size is one, the variable is determined.
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
S1S2
[]
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.
- Up - | Next >> |