world as value

[Adrian Hey]

On Sun 20 Jun, Fergus Henderson wrote:
> It is quite possible to model non-determinism in a purely functional
> framework.
> See for example the following references.
> 
>      *  F. Warren Burton, ``Nondeterminism with Referential
>         Transparency in Functional Programming Languages,'' in Computer
>         Journal, 31(3), 1988, pp. 243-7.
> 
>      *  John Hughes, John O'Donnell, ``Expressing and Reasoning About
>         Non-deterministic Functional Programs,'' in Proc. of the 1989
>         Glasgow Workshop on Functional Prog., pp. 308-28.

I think the best way for me to respond to this is to briefly explain my gripe
about the use of the word deterministic (or non-deterministic). To cut a long
story short, a physisist takes one of these supposedly non-deterministic
systems and repeats the same stimulus-response experiment many times, each
time ensuring the system has been initialised to some defined state at the
start. Each time the observed response is identical. So the physicist turns
to the computer scientist and asks "What makes you suspect that this system is
non-deterministic? I can't find any evidence to suggest that."   

Of course the resolution of this paradox is simple. The physicist and computer
scientist aren't working with the same system. The physicist is working with
a physically tangilble bit of finite state machinery. The computer scientist
is working with an incomplete abstract mathematical model of a machine. The
apparent non-determinacy arises because the physicist considers sequences of
stimulation events which occur at different times with respect to timer
events (such as a CPU clock) as different, so isn't too surprised if the
finite state machine outputs different responses. If the computer scientists
model doesn't take proper account timer events, then sequences of (non-timer)
stimulation will be regarded as the same if they occur in the same order.
But despite this, the finite state machine doesn't always output the same
response sequence, so the computer scientist concludes that it is 
non-deterministic.

So it seems to me that what we really mean by a program/system being
non-deterministic is that we can't predict the response of any finite state
machine which implements the program, given only the program itself and the
sequence of stimulation events explicitly accounted for by the program.
We need more information about the the finite state machine which implements
the program, and any other events which influence its response (in particular,
timer events).  

Now, I haven't read either of the papers you mention. Are they on the web? If
not then they probably won't get read by me:-) So I don't know exactly what
the authors were trying to achieve. It's not clear to me what is meant by
'model' in this context. Do you mean 'described and implemented' or just
'simulated'? If it's the latter, the fact that (apparent) non-determinism can
be simulated (deterministicly) doesn't really surprise me, but is this of any
use from an implementational point of view (rather than a research point of
view)?

I must admit I'm a bit baffled by this. Have these researchers really managed
to elicit non-determinstic behaviour from a program expressed as a pure
function?

The issue which really concerns me is not whether non-deterministic systems
be simulated. Nor is it wether or not non-deterministic systems be implemented.
The issue which concerns me is:

 'Can systems with tolerable behaviour be described, reasoned about and
  implemented within the same language?'.

I suppose the answer is yes (people must have been working on this problem
for years), but not (yet) if you're a Haskell or Clean user. (And not ever
if they remain purely functional ????)

Non-determinism is often the price paid to achieve tolerable behaviour,
it is not usually the goal. If all internal computation could be performed
instantaneously, then I don't think non-determinism would really be an issue.
Similarly, there are situations where internal computation can be performed
sufficiently quickly to allow the system exhibit tolerable and deterministic
behaviour. This situation can usually be dealt with quite easily using the
simple single threaded, sequential world as value paradigm we've been talking
about. (But even here, concurrency might simplify life, even if it wasn't
strictly necessary.)

> > It's probably safe to assume
> > that Concurrent Haskell would get the same response.
> 
> You might have more luck if you just suggest that they try Haskell

I very much doubt it. For embedded work, they're pretty well committed to
ADA (and I have to admit, I think they're right here). The trouble is, because
ADA is the languge they know, it tends to get used for everything else.

Why Haskell, as distinct from Concurrent Haskell? Do you have something
against Concurrent Haskell :-) Now that I've read the Concurrent Haskell paper
I have to say that it looks like a pretty good system, and if I was a Haskell
user I'd seriously consider using it (for desktop/workstation applications).  
 
> > If concurrency
> > is what you want then new language constructs are needed and the programmer
> > has to _use_ them.
> 
> Yes, or at least new standard library constructs, of the kind that could
> not be implemented in terms of other standard library constructs.
> 
>
> Note that in Concurrent Haskell `forkIO' is a library function, not a
> new language construct as such, and the same is true in our design for
> concurrency extensions to Mercury.
> 
> I'm sorry for being pedantic ;-)

Don't worry, I'm a pedant myself. Yes, I know that I can write concurrent
applications in assembler or C, despite the fact that neither language
provides any 'support' for concurrency, so I shouldn't be surprised if the
same is true for Haskell or Clean. If you don't mind relying on foriegn
'black box' library functions or hardware this is fine. However, this approach
does mean it's hard to get the compiler to tell you anything useful about
your program, or spot hazards/errors.

If some kind of 'action calculus' was built into the language, all sorts of
useful analysis might be possible, like warning me my program could end up
deadlocked or warning me that some protocol would be violated. The trouble is,
I have no idea which action calculus one should chose, there seem to be so
many :-)

Oh dear, another long winded message. Excuse me please!
-- 
Adrian Hey