world as value

[Fergus Henderson]

On 21-Jun-1999, Adrian Hey <ahey@iee.org> wrote:
> 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.

Yes.  This kind of non-determinism arises whenever you need to cross an
abstraction boundary.  For example, within a functional programming setting
the operation of getting the current time is non-deterministic in this sense.

> Now, I haven't read either of the papers you mention. Are they on the web?

I don't think so.

> I don't know exactly what the authors were trying to achieve.

They were trying to find ways to express operations such as getting the
current time in a purely functional setting in a way that didn't violate
desirable properties of pure functional languages such as referential
transparency.

> is this of any use from an implementational point of view (rather than
> a research point of view)?

Well, it's useful if you want to add operations such as
"get the current time" to a purely declarative language like Haskell
or Clean.

> 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?

Only in the sense of apparent non-determinism due to crossing abstraction
boundaries.

(Of course modern hardware includes non-deterministic components
(e.g. my CD writer seems to be decidedly non-determinstic!),
and a program expressed as a pure function can access such devices
and therefore behave non-deterministically.  Perhaps you would argue
that this is only apparent nondeterminism, and that if we could just
know reset the state of the system more accurately then the nondeterminism
would vanish.  At this point we would then most likely digress into arguments
about quantum mechanics...)

> 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 ????)

I think the answer is yes, even if you're a Haskell or Clean user.
Why do you think otherwise?

> > > 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
> 
> Why Haskell, as distinct from Concurrent Haskell?

Oh, just for the same kinds of reasons that many people say they are
programming in the internationally standardized language C++ but then
go on to actually program in some dialect such as MSVC++ ;-)

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3        |     -- the last words of T. S. Garp.