Dear Russ,
I assume you are talking about the form of the search tree when you
talk about paths. I don't understand what you mean by 'concurrent
paths'.
The propagate-and-search approach (or propagate-and-distribute)
combines making deductions (propagation) and making decisions
(distribution). Making deductions only excludes variable domain values
which can not be part of any solution. Such deductions can never be
'wrong'.
When no further propagation is possible, a decision is made. A decision
is potentially 'wrong' and undone later (although the Oz gurus maintain
that this is no backtracking..). The search tree (as shown, e.g., by
the explorer) only depicts the spaces created by decisions as nodes
(i.e. the propagation process is not visualised).
The decision making process (distribution strategy) is fully
programmable in Oz. An efficient decision making process leaves most of
the work to propagation: to reduce the number of necessary decisions
means to reduce the number of decisions which are potentially wrong ;-)
Obviously, this model is very different from Prolog.
Constraint propagation happens concurrently in a space, constraint
distribution on the other hand is sequential (parallel search engines
are a special issue).
New constraint domains (plus propagators) can be defined for Oz (see
the Constraint Extensions Tutorial). A number of domains are already
predefined by the system (e.g. finite domain integers, finite sets) and
some more are developed by the community (e.g. real intervals (i.e.
floats), graphs).
Best,
Torsten
On 11.10.2005, at 22:41, Russ Abbott wrote:
Thanks, Peter. If I said that concurrent logic programming does
backtracking, it wasn't my intention. Do you remember where I said
that? I'll correct it. At this point my interest is more on the
distinction (that you make also) between logic programming in general
(concurrent or backtracking) and algorithmic programming—and how
Oz seems to provide a nice way to integrate those two paradigms.
Regarding constraint programming, I've just started to learn about
Oz's approach to it. Perhaps the following is an obvious observation
made by a newcomer, but it seems to me that the essence of the Oz
approach to constraint programming is that it groups concurrent paths
together where possible. That is, instead of having a separate path
for each value in a range, it keeps the entire range together in a
single path as long as possible. It's sort of like dynamic refactoring
in which one factors out what is common to many search paths. Of
course it's not put in those terms, but that seems like one way to
think of the difference between pure concurrent search (1 [] 2[] 3 []
... [] k) and Oz's constraint processing (1::k).
Oz has lots of stuff built in to support refactoring of integer ranges
and sets. It seems to me that the next question should be: what other
kinds of choices can be factored out using similar techniques.
-- Russ
On 10/11/05, Peter Van Roy <[EMAIL PROTECTED]> wrote:
Russ Abbott wrote:
> In
>
http://cs.calstatela.edu/~wiki/index.php/Courses/CS_460/Fall_2005/
Concurrent_logic_programming_in_Oz
> <
http://cs.calstatela.edu/%7Ewiki/index.php/Courses/CS_460/Fall_2005/
Concurrent_logic_programming_in_Oz>
> , I attempt to give a brief description of concurrent logic
> programming in Oz. The first (and main) part is explicitly
> procedural. Its procedurality bothered me enough to prompt an
attempt
> to offer a declarative interpretation. This seems somewhat unusual in
> that it offers a declarative version of logic programming in terms of
> a procedural version rather than the other way around.
>
> If anyone has any comments, I'd be very interested.
>
> -- Russ
Dear Russ,
Here is some extra information that can be useful for you when
completing this section.
First of all, 'concurrent logic programming' does not do any
backtracking! It is the kind
of logic programming done by the committed-choice languages (see
section
5.8.1 in
the CTM book, page 394). It is very different from Prolog, which is
based on backtracking.
Prolog-style logic programming is exactly what is given by the Solve
operation of
chapter 9. The Solve operation is a kind of first-class Prolog top
level: it generates
a lazy list of solutions exactly in the order that Prolog generates
them. Section 9.7
of CTM explains how to translate Prolog programs to Oz. (Solve is
defined in
chapter 12, but you don't need to understand computation spaces to
understand
that Solve returns a lazy list of solutions in the order of depth-first
search!)
So there are two styles of logic programming that are currently
popular:
- concurrent logic programming (no backtracking, committed-choice,
concurrent)
- Prolog-style logic programming (global backtracking search,
sequential)
As a final comment, constraint programming works very differently from
these two
styles. It is a kind of third style. It tries to avoid search by
pruning solutions, whereas
the Prolog style does generate and test. The pruning is done in a
concurrent way, by
propagators that each observes the store and tries to do its own
pruning
independently
of the others.
I hope this clarifies some things!
Peter
--
_____________________________________________
Professor, Computer Science
California State University, Los Angeles
o Check out my blog at http://russabbott.blogspot.com/
_______________________________________________________________________
__________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
--
Torsten Anders
Sonic Arts Research Centre
Queen's University Belfast (UK)
www.torsten-anders.de
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
