Russ Abbott wrote:
You're absolutely right. I certainly didn't mean Oz threads.
The idea is that a choice splits a thread (understood not as an Oz
thread but in the generic sense as a thread of control that includes its
own copy of its parent's variables, which in Oz is called a space) into
multiple such threads (spaces).
Here is an definition of choice and spaces.
A choice is a nondeterministic branch. I means that the program has two
(or more) possible outcomes. A computation space is a box that contains
a running program. The API of the box allows to
- tell whether the encapsulated program has succeeded, failed, or is
facing a choice;
- clone the box (and its computation);
- commit a given alternative when the computation is facing a choice;
- merge the computation in the box with the main program, and give
access to its root variable.
Computation spaces allow to "manipulate" (possibly nondeterministic)
computations. We can use them to explore all possible outcomes of a
nondeterministic program: SearchAll is nothing else than that.
I strongly encourage you to use the Explorer to visualize the search
tree resulting from the search process.
The exploration of program outcomes can be done in a concurrent or
sequential way. The concurrent way implies that all outcomes of the
program must be in memory, therefore we rarely use it. The sequential
way is traditionaly done with a depth-first strategy. Coming back to a
node after having explored its subtrees is called "backtracking".
Here is a naive implementation of SearchAll (for binary choices only).
I am pretty sure your students can understand it. That should be enough
to give them a quite precise intuition of search in Oz.
fun {SearchAll P}
%% return the root variables of all succeeded spaces
{Map {ExploreAll {Space.new S}} Space.merge}
end
%% return all succeeded spaces "generated" from space S
fun {ExploreAll S}
case {Space.ask S}
of succeeded then [S]
[] failed then nil
[] alternatives(2) then C={Space.clone S} Ls Rs in
{Space.commit S 1} Ls={ExploreAll S}
%% we now backtrack and explore the second alternative
{Space.commit C 2} Rs={ExploreAll S}
{Append Ls Rs}
end
end
Cheers,
raph
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
