Russ Abbott wrote:
It had been my tentative plan to introduce search through standard
Prolog backtracking and then to show how FD-style search was a lot more
efficient. That's one reason I wanted to do CTM chapter 9 and then CTM
chapter 12--to solve a problem using basic Prolog-style backtracking and
then to solve the same problem using FD.
But I now suspect that I can't do that. I don't see how I can express
standard Prolog-style backtrack search in Oz. Am I wrong?
Yes, and IMO backtracking is simpler in Oz than in Prolog.
A "logic" program must be written as a one-argument procedure, and use
explicit nondeterminism with "choice". Procedures and recursion are
allowed, but don't use threads in this style. The execution of such a
program must be delegated to a search engine.
A thread executing "choice" blocks until which alternative to choose is
told by the search engine. Backtracking means to reconstitute the state
of the program at the last "choice" it ran.
You can easily visualize search with the Explorer. Each internal node
in the tree corresponds to a state of the program blocked at a "choice".
The leaves are the final states of the program (success or failure).
Clicking on a node shows the state of the root variable.
The FD extends this simple model with concurrency, domain propagation,
and use "distributors" instead of "choice". A distributor waits until
propagation reaches a fixpoint, and dynamically decides which
nondeterministic choice to make.
Cheers,
raph
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
