world as value

[Fergus Henderson]

On 19-Jun-1999, Adrian Hey <ahey@iee.org> wrote:
> On Thu 17 Jun, Martin Wierich wrote:
> > I am surprised, that some poeple conclude, i/o in functional
> > languages doesn't work soundly.
> 
> I wouldn't say that I think (world as value) i/o in functional languages
> doesn't work soundly. It can work fine, but not as I would want. The big
> problem is that a _purely_ functional language must express system output as
> a (pure) function of system input. This seems to demand that external events
> are responded to in chronological order. I know that most real systems don't
> behave that way, nor should they.
> 
> Real systems can respond to events 'out of order'. This is often called
> non-determinism.

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 would be genuinely interested to know whether Concurrent Haskell
> > made it easy or hard to program your appplications.  GHC and Hugs
> > both implement Concurrent Haskell; GHC's version is a bit more
> > fully-featured.
> 
> I'm not sure I can promise to try it out on a real application. I do my
> work for customers who are highly sceptical of what they perceive as
> experimental languages. I've tried (and failed) to get one them to look
> seriously at Clean (for desktop applications). 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

> On Thu 17 Jun, Fergus Henderson wrote:
> > It helps if the imperative parts also have a declarative semantics,
> > as they do in Clean, Haskell, and Mercury, but this is not essential.
> 
> Could you explain what you mean here?

In Clean, Haskell, and Mercury, the imperative-style parts are written using
syntax that has a very simple mapping to code using only pure functions
(or predicates) which have a relatively simple and clear declarative
(denotational) semantics.
For the imperative-style parts of the program, you can reason about them
using the operational semantics, but because they also have a declarative
semantics, it's possible to reason about them using the declarative semantics
too.

This contrasts to the situation where the imperative-style parts of the
program are written using syntax that does not have a simple declarative
semantics, as would be the case if you wrote the imperative-style parts
of the program in C, for example.

> > In what way would this be an improvement on the "world as value" paradigm?
> 
> It also means that you have pass and return the world baggage all the time
> (although Haskell hides this with a monad). The problem I see with this isn't
> just the notational inconvienience. My main objection (as with the lazy steam
> approach) is that it imposes sequential invokation of actions.

As I said above, there are techniques for modelling nondeterminism in
pure functional languages.  Also there are of course also techniques for
modelling nondeterminism in logic languages -- here you are interested
in the committed choice nondeterminism used by the concurrent logic
languages (Parlog, AKL, etc.), rather than the backtracking approach
used by the more traditional logic languages such as Prolog.
(Mercury supports both kinds.)

Using these techniques, it's quite possible to provide support for concurrency
and nondeterminacy within a pure functional language or a pure logic language.
Simon Peyton-Jones already mentioned `forkIO' in Concurrent Haskell,
but it's also possible to provide an equivalent primitive using the
"world as value" paradigm.  Thomas Conway and I have been doing a bit of
work, off-and-on, on adding support for this kind of thing to Mercury.
(But I don't know when this will be finished; currently we both have other
tasks which have higher priority.)

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

> What I'm thinking about is a system that by default assumes
> that actions can be performed in any order you (I.E. a scheduler of some kind)
> like, subject to satisfying..
> 
>  1 - Dependancy constraints which can be partially infered at compile time,
>      and partly determined at run time.
>  2 - Programmer supplied behavioural constraints. Sometimes these constraints
>      will specify sequential actions, if that's what's needed. 
> 
> In other words, concurrency is the norm, not the exception. Yes, I understand
> that implementation of such a system will be mind bogglingly complex. It would
> also be quite useful I think, but I'm not 100% sure it's possible.

It's certainly possible -- you should look at the concurrent logic languages
for examples of this.  However, it does have a lot of problems.
I don't think it's really a good idea.

> > > 2- Keep the purely functional part of the language as a subset which is
> > > incapable of describing IO. Instead this part of the language describes
> > > 'side effect free' (I'll say more about that later) data transformations.
> > > Functions are never implemented as 'stand alone' bits of code which
> > > perform a reduction. They are just kept within the compiler as
> > > mathematical entities which may be freely manipulated, combined,
> > > transformed etc as usual. Instead, the functions are used to derive
> > > appropriate 'computational actions' from the 'action spec'. So in this
> > > sense, although the language would not be 'purely functional', the 'purely
> > > functional' subset of the language would be, in my opinion, purer than
> > > either Clean or Haskell are at present.
> > 
> > Why would this be any better than they way that Clean, Haskell and Mercury 
> > currently work?
> 
> Well, correct me if I'm wrong (this is always a definite possibity:-), 
> but because Haskell, Clean (and Mercury?) are (functional) programming
> languages, they need operational semantics to determine how expressions
> are evaluated. Lazy/Strict, Lazy pattern matching, Strict Pattern matching etc.
> As far as I'm aware operational semantics are not normally part of the lambda
> calculus or mathematics in general. So if you could do away with it, I would
> say that the functions would be 'purer'.
> 
> In Clean we have strictness and uniqueness annotations in types. In my view,
> these are operational concepts, and have little to do with the properties of
> functions in the abstract sense.

For uniqueness, this is true.  Uniqueness is an operational concept that
doesn't have any meaning in the denotational semantics.

For strictness, it's not so true.  Strictness does have a simple and
well-defined meaning in the denotational semantics (the formal model of
the "abstract sense").  In particular, if you consider the strict application
operator `$!' in Haskell 98, its denotational semantics are defined as
follows:

	f $! x = _|_, if x is _|_
               = f x, otherwise

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