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).
The order in which the computations in these new threads (spaces) proceeds is one of the pieces of information that is abstracted away by SearchAll.
Abstracting thing away or hiding them under a level of abstraction is not magic. Nothing is magic. We are dealing with computers, after all. The idea that a computation may be magic has been suggested on this at least list twice recently.
The way in which multiple computations proceed is hidden in much the same way that the mechanism that creates a thread (space) and gives it its own copy of its parent's variables is hidden. In both cases, these things just happen. They are part of the SearchAll abstraction. They are not visible to the user, and the user should not be (cannot be?) concerned with it. But they are not magic.
On 10/8/05, David Hopwood <[EMAIL PROTECTED]> wrote:
Russ Abbott wrote:
> On 10/8/05, David Hopwood < [EMAIL PROTECTED]> wrote:
>>Russ Abbott wrote:
>>
>>>A piece of the code is
>>>
>>>N1 = 10*{Digit} + {Digit}
>>>N2 = 10*{Digit} + {Digit}
>>>X = N1 * N2
>>>
>>>where {Digit} generates all of the digits using choice. (This is from
>>>CTM chapter 9.) I said that the way to think about what's going on is that
>>>these two lines generate 10,000 threads, some of which get killed off later
>>>when X is found not to be a 4-digit palindrome. The ones that succeed produce
>>>results that are gathered together by SearchAll.
>>>(In Prolog one would talk about backtracking. I gather that in Oz one
>>>imagines them all running at once. Is that reasonable?)
>>
>>Not really. When used in a search, this potentially creates up to 10000
>>*spaces*, but a space is not the same thing as a thread. How a search
>>engine uses threads is specific to each search engine.
>
> Recently we discussed (very briefly) how much one had to know about spaces
> to understand how to use Oz as a logic programming system.
I don't think that spaces are complicated. In fact I think it's a misjudgement
to attempt to teach Oz-style (committed choice) constraint programming without
explaining spaces relatively early.
> If one says
> 10,000 spaces instead of 10,000 threads, how does one explain (to someone
> who just wants to use it, not someone who wants to implement it or
> understand the implementation) what a space is, and how does one explain
> what happens after those 10,000 spaces are created? In other words, to
> explain Oz's abstract computational model, how does one explain what a space
> is and what part it plays in an Oz computation.
A space represents one branch of a search -- i.e. a subcomputation that is
dependent on some set of assumptions about the problem variables. Each space
can have local bindings for constraint variables that are different from the
bindings in other spaces.
Spaces are definitely not threads. A thread does not have thread-specific
variable bindings.
> Another way of putting it is: what words go with Figure 9.2 on p 628 of
> CTM? The StrangeTwoDigit example on that page is explained in terms of
> depth-first-search. But do we really want to talk about Oz's computation
> model at that level?
There's nothing complicated here. Depth-first search is an implementation of
search. If you don't care what the order is, you can use a search engine that
implements any order. Anyone who is being taught constraint programming should
consider this straightforward.
> Of course, the order in which the results are presented
> is determined by something. (It is running on a deterministic
> single-processor computer after all.) But when one is just starting, we
> probably don't want to talk about that issue.
And leave it as "magic"? It's not much effort to just say that it is the
implementation of the search engine that determines how search is performed
and what result orderings are possible. Anyway, you weren't suggesting to
not talk about it; you were suggesting to think as if the alternatives were
explored in parallel. But they aren't (in general). Don't teach things that
you will later need to unteach.
> The point is that SearchAll
> gives us all the results (in some order, which shouldn't matter to us--at
> least not now).
It's still a bad idea to explain spaces as if they were threads. If Oz did
not also provide threads as an independent concept, this wouldn't matter as
much, but since they are separate concepts, it does matter.
--
David Hopwood <[EMAIL PROTECTED]>
_________________________________________________________________________________
mozart-users mailing list [email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
_________________________________________________________________________________ mozart-users mailing list [email protected] http://www.mozart-oz.org/mailman/listinfo/mozart-users
