Hi Ben,
please disregard my previous reply, I was not planning on sending it,
as it will probably only add to the confusion. Sorry, it escaped
anyway.
But this is what I meant to say:
On 19 Nov 2003, at 21:08, Ben Moseley wrote:
> Hi,
>
> A question has occurred to me whilst reading the Concepts Techniques
> and Models book...
>
> On p22 it gives the following as an example of observable
> nondeterminism in Oz:
>
> declare
> C={NewCell 0}
> thread
> C:=1
> end
> thread
> C:=2
> end
>
> There is observable nondeterminism because we can't tell in advance
> what the content of C will be.
Yes, well actually because your program _ends_ in a state that is
unpredictable. The "observable" part of "observable nondeterminism"
refers to what is in the store when the program ends. Better: when the
program "partially ends", which means that no runnable thread is left
that could influence the variable store. This is important if you
really want to understand the definition of observable nondeterminism.
It means that, without extra input from outside (binding a variable),
the remaining threads either block (waiting for a variable to become
determined), or only do things that are obviously irrelevant to the
store (like endlessly looping and skipping). So while the program is
in a running state, you should not look into the store, as if you did,
you would see that variables become defined in an undetermined order,
even in the declarative subset. Using only the declarative subset, you
would also see however, that the information in the store is only
growing, never "changing". That is an alternative definition for
non-observable nondeterminism, coming from constraint programming.
Sometimes the information in the store might grow too much eventually,
as inconsistent unifications would add information that is
contradictory, and then the store would grow to a "failed" state.
>
> But isn't there observable nondeterminism in the declarative
> concurrent subset of Oz by exactly the same argument:
>
> declare C
> thread
> C=1
> end
> thread
> C=2
> end
> ... with this example you cannot tell in advance which value C will be
> bound to. Certainly the other binding attempt will fail, but isn't
> this observable nondeterminism nonetheless?
Your program ends here in a predictable state: inconsistent store: "too
much information added!"
There is some form of nondeterminism here too, we all agree, and it is
introduced by the nondeterministic execution order of threads and thus
unavoidable. If you can make the thread-execution-order observable, in
the sense that the outcome of your program is determined by it, you
have observable nondeterminism. You could show C on a screen or put it
in a file before the program terminates with an inconsistent state. But
therefor you would need non-deterministic operations (read on in the
book to find out about them).
It doesn't matter whether after the first binding of C, there is a lot
of time before the second binding causes failure. All that time, you
cannot make the difference observable in this sense. Man, I've tried to
do this so hard, I think it's only fair you should try it too :-)
Succes,
Fred.
-----------------
Fred Spiessens
Researcher Software Security
Université catholique de Louvain
Louvain-la-Neuve
Belgium
fsp@info.ucl.ac.be
http:www.info.ucl.ac.be/people/fsp/fred.html
-
Please send submissions to users@mozart-oz.org
and administriva mail to users-request@mozart-oz.org.
The Mozart Oz web site is at http://www.mozart-oz.org/.
Please send bug reports to bugs@mozart-oz.org.