world as value

[Adrian Hey]

Thank's to Peter Achten and Pascal Serrarens for taking the time to respond
to my message. I'm a little puzzled by the apparent lack of consensus on this
issue within the Clean team. I have received messages from several people
(not Clean Team people) on this issue (privately, not via clean list) who
are trying to persaude me that the kind of non-determinacy which I would like
to see in a 'viable' (by my standards) general purpose language is neither
desirable nor advantageous. This seems to be Peters view, meanwhile Pascal is
busy introducing non-determinacy into the language (if I understood his
message).

We seem to have got a little bogged down with theoretical arguments about
what is or isn't pure function or a value and models containing infinite
lists of random numbers or whatever. From a pragmatic point of view, the
issue which really worries me is BLOCKING, and achieving what I called
"tolerable behaviour" in earlier posts I.E. behaviour in which activities
are not blocked for 'stupid' reasons (like they just happen to appear lower
down on a 'things to do' list). If they are blocked it should be for sensible
reasons (like dependancy). I'm certain that there are often situations where
deterministic systems will block, but non-deterministic systems won't.
A problem with deterministic environment passing (in my opinion) is that
it introduces apparent dependency where in reality there may be none.

I agree with Peter's point of view that determinism is a highly desirable
property, and that in genuinely independent environments can be identified
then it is possible to achieve some measure of concurrency without
introducing non-determinism. But I can't help suspecting that if we used
this method for 'real world' environments rather than specially defined
Clean run time environments, we would find precious few environments which
were independent. The reality would be something like: this environment is
not independent of the rest of the world, and performing actions A then B
will leave both this environment and the world in a different state than
performing B then A. But, I don't care _exactly_ what state the environment
or the world is left in, just so long as actions A and B are accomplished
at the earliest possible opportunity. Yuk.. non-determinism.

Here's an silly example of what I mean. I have an automated factory controlled
from a Clean Program which is capable of making anything I desire. I desire
a new bicycle and a new helicopter. So I write a Clean program..

mydesire1 world =
 let (world1,factory1)=openthefactory
     factory2 = make "A bicycle"    factory1
     factory3 = make "A helicopter" factory2
 in closethefactory factory3 world1

or I could write..

mydesire2 world =
 let (world1,factory1)=openthefactory
     factory2 = make "A helicopter" factory1
     factory3 = make "A bicycle"    factory2
 in closethefactory factory3 world1

It really doesn't matter which. But these programs could easily result in
the world and the factory being left in a different state, depending on
which item is made first. The important thing is that either way the world
now contains a new bicycle and a new helicopter. Mission accomplished.

But what does matter is blocking. If I chose mydesire1, and for some reason
the first operation was blocked in the Clean program, then I am left without
a new helicopter also.

If I understand what Pascal and Peter have been saying, the solution to this
is to design my factory control interface to open new environments or
channels for each manufacturing activity. I'm not sure this does really
_solve_ the problem, it just means I have to put the non-determinacy
somewhere else that isn't a Clean program. Perhaps Pascals 'non-deterministic'
concurrency would fix this (I believe it would).

                        ------------------------
On Wed 14 Jul, P.R. Serrarens wrote:
> As your questions contain a lot of 'concurrent' words, I will try to clarify
> some things about this.

No, all my words were stricly sequential:-)

> > The problem is that all IO activity after
> > doit will be blocked (unnecessarily) until both writesomedata and
> > dosomethingelse have completed.
> 
> This may not be a real problem, but more a different way of thinking. The
> continuation of the main thread is not contained in <dosomthingelse>.

I don't understand what your saying here. Are you saying that dosomethingelse
may return a world value before it's actually finished, as if it were a
'non-blocking' OS output routine? This is something else I've been wondering
about. What exactly do we (I) mean by 'finished' as far as IO operations are
concerned? You don't need to bother answering that one, I'll figure it out
myself:-)

> > This seems a little inflexible to me. The best I could do would be to dust
> > down my trusty C compiler and hack it. Correct?
> 
> If you like that, fine.

I don't like that, but I would have no choice (at present). But I'm pleased to
see that your work is going to correct that oversight soon.

> First, updating environments in a non-sequential order may result in errors
> which are hard to detect.

Yes, that's why building reliable concurrent systems with traditional 'ad hoc'
methods is so complex and error prone, yet necessary in many real world
applications.

> In some cases it may be fine, but when it this so?

This is a real problem I think. It would be nice if a compiler could figure
this out, but that seems impossible because it has no real knowledge of the
effects of actions on environments, nor wether alternative sequences are
acceptable. It's pretty much down to the programmer to get it right when
invoking non-deterministic concurrency.

                 -----------------------------------

On Wed 14 Jul, Peter Achten wrote:
> No, you can easily add your own environments. An elaborate example is the
> IOSt data structure that plays a central role in the GUI library. Although
> it is an abstract data type for programmers, it is a complete Clean record
> data structure. Of course, when you are building an interface to some new
> OS components, you probably have to do some hacking.

Yes, perhaps I should have said I can't create new IO environment _types_
rather than new instances of IO environments of existing types (like files
and IOSt). The only reason I can create new IOSt's is that you have taken
the trouble to provide the ObjectIO library. I couldn't have done it myself
_entirely_ in Clean (mostly perhaps) :-(

> >My problem with this is: What if we don't care in what order the operations
> >are performed? We still have to pick an order and pass the environment
> >value between operations, thereby making the operations strictly sequential.
>
> If you don't care you shouldn't be bothered to specify an evaluation order.

I don't think the argument is that simple. When I say I don't care (about
the order of operations) I mean I _really_don't_care_, which isn't the
same thing as saying that one fixed deterministic order is a good as any
other. For example, if I have three messages to send via some communications
channel environment. Let's call them A,B & C. I don't care what order they
are sent. Suppose message A is dependent on some value which takes 10 hours to
evaluate. Why should B and C also be blocked for 10 hours? If I had advance
knowledge that A would take 10 hours to compute, then I could solve the
problem by changing the order, say B,C,A. But in general, I would not have
such knowledge. If computation of messages A,B,C could be started as 3
separate threads, then each message could be sent as soon as the corresponding
thread terminated. The trouble is, that's non-deterministic, isn't it?
  
> I don't know how many programs exist 'out there' that require non-determinism
> on a fundamental level,

A significant number I suspect, in fact the I would say the overwhelming
majority of 'system level' programs, like operating systems. Rigidly
deterministic OS's, or applications which run on those OS's, as many early
programs were (and some still are), are a darned nuissance. Why else do we
spend so much time watching hour glasses? Still, they give us a good
excuse to go get a cup of coffee.

> but I do know that many programs exist that can be suitably programmed
> within a functional framework.

Yes, those that won't 'lock up' for prolonged periods, or those intended for
use by caffine junkies :-) 

Regards
-- 
Adrian Hey