[email protected] (Jorge M. Pelizzoni) writes:
> In Prolog there is a way to "name" choice points so as to allow cutting
> at once all choice points occurring after a referred choice point. I
> wonder if this is possible in Mozart (i) without having to write a brand
> new search engine or (ii) at all (I mean, using "Choose" and "Commit"
> somehow and not creating a whole new "artificial" framework).
Your question suggests that you may have deeply misunderstood the
support for search in Oz. The notion of "cut" is only meaningful when
you have chronological backtracking. Search in Oz is not based on
backtracking, but on copying. Furthermore, there is no implicit and
fixed depth-first search strategy: instead, search is entirely
programmed in Oz itself, and the strategy is up to you. In fact,
there are 2 aspects:
1. the distribution strategy: this is specified in your search
predicate and defines the shape of the search tree
2. the exploration strategy: this is specified by the search engine
and determines the order in which you visit the nodes of this
search tree.
The notion of "cut" just doesn't make much sense in this context. At
most, maybe, you can write a search engine that has the ability to not
explore certain parts of the tree (i.e. "cutting" them out).
But really, the problem is that (apparently) you are trying to do
logic programming. Oz is not a logic programming language: it is a
constraint programming language. Logic programming is entirely
predicated on non-determinism, i.e. on making choices. This is why it
often suffers from combinatorial explosion. The whole point of
constraint programming is to avoid non-determinism as much as possible
through deterministic inferences (aka constraint propagation). Making
a choice should only be done as a last resort when constraint
propagation has pruned available options as much as it could.
You need to reformulate your approach to take advantage of
_concurrent_ constraints instead of using the LP approach of making a
sequence of non-deterministic choices. You should want to avoid
having to make these choices at all. Sometimes, instead of:
choice A=1[]A=2 end ...
choice B=2[]B=3[]B=4 end
a formulation like this may help:
thread or A=1 ... [] A=2 ... end end
thread or B=2 ... [] B=3 ... [] B=4 ... end end
first you don't have to choose A and B in this order; second, it might
very well happen that other constraints determine B, which then in
turn might determine A. That's the sort of situation that you want to
encourage: where constraints do the work for you, and you don't have
to make choices.
To come back to this specific question:
> % somehow I know now that A's current choice is fated to failure,
> % so it's no use trying other values for B while A stays the
> % way it is. Thus:
> {CutAllTill Id}
How do _you_ know that A's current choice is doomed? You are
certainly applying some sort of decision procedure. Well, then
encapsulate it as a constraint: let's call it C(A). This constraint
must fail when your decision procedure says that A's current value
cannot lead to a solution. Then you post it as follows:
choice A=1[]A=2 end
...
C(A)
choice B=2[]B=3[]B=4 end
...
However, you will gain most by removing these explicit choices and
going with constraints all the way.
Cheers,
--
Dr. Denys Duchier
�quipe Calligramme
LORIA, Nancy, FRANCE
-
Please send submissions to [email protected]
and administriva mail to [email protected].
The Mozart Oz web site is at http://www.mozart-oz.org/.
Please send bug reports to [email protected].