world as value

[Adrian Hey]

Hello,

Here are some thoughts of mine regarding the responses to my post.

On Thu 17 Jun, Martin Wierich wrote:
> Hi everybody,
> 
> Obviously my issue about the world as value paradigm raised interest, thank's
> for that. 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. (I don't like this word. In my view whether of not a system
is deterministic depends on what you're trying to determine about the system.)

I guess the point of view I've been coming round to in recent months is that
ultimately _programming_ is about expressing behaviour. Evaluating
expressions is a necessary part of that, and lambda calculus has a lot to
offer here. But when it comes to formal descriptions of behaviour I think
there may be better/easier techniques.

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

On Thu 17 Jun, Simon Peyton-Jones wrote:
> Do you know about Concurrent Haskell?  It adopts exactly the position
> you describe.  The 'start a new program' thing is called 'forkIO'.

I was aware of something called Concurrent Haskell, but ignorant of any detail
about it. I'll certainly have a look at the paper you referenced sometime soon.
I'm afraid I'm a little out of touch with the Haskell world because I don't
have a machine capable of running ghc or any derivatives. (I have an ancient
486 PC running DOS, a G3 PowerMac and an Acorn RiscPC.) I suppose I could put
Linux on the PC. Or I could use Hans Abergs port of Hugs to MacOS. Would
that work with Concurrent Haskell?

> 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. I have a few doubts of
my own also. Specifically efficiency, dead time during garbage collection and
ensuring the program will run in bounded space. With embedded applications
aborting, crashing, complaining about exhausted heap space, are simply not
options I can consider. 

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

On Thu 17 Jun, Marco Kesseler wrote:
> - if I'm interested in values, I end up with lamda calculus and
>   functional languages.
> - if I'm interested in actions, I end up with process algebra,
>   CSP, and more or less the good old imperative world.

Well yes, more or less, only I wouldn't describe the kind of thing I'm
thinking about as the good old imperative world. It seems to me that we
already have a reasonably good emulation of the imperative world with Clean
*World or Haskell monads. (I think this was one of Fergus Hendersons points.)
I've been wondering if we can't improve on the good old imperative world, as
far as issues like IO, concurrency and behavioural specification are concerned.

Sorry, I know it's impossible for anybody out there to tell what I'm thinking
about unless I spell it out. Perhaps I will soon (after I've mugged up on
Concurrent Haskell:-) It the moment I thinking about lots of different aspects
of the behavioural problem with varying degrees of success, but thinking about
them and publicly advocating them are two different things. Maybe I'll decide
that I can't improve on 'world as value' after all.

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

On Thu 17 Jun, P.R. Serrarens wrote:
> I do not want to say much about your criticism about the world-as-value
> approach of most purely functional language, except that I do like it because
> it clearly shows what is affected by the functions, especially in the
> multi-environment approach as is used by Clean.

I'm not sure what you mean by this. If I understand you correctly, you are
saying that the Clean *World actually consists of independant sub-worlds
(which may also consist of independant sub-worlds etc). So the world may be
broken down into a kind of tree, with primitive sub-worlds at the leaves?
I've never really understood what the semantics of the *World are in this
respect. I've always regarded it as just an abstract data type that forces
sequential IO. Are you saying that sub-worlds on different branches of the
tree can be regarded as independant, and therefore can be manipulated
concurrently? If so, I have a few doubts about this, but I shall refrain
from expressing them until somebody can confirm that I'm not 'barking up the
wrong tree'.

Incidently, how does ObjectIO library fit into this scheme? It seems to be
a hybrid between an event driven system and a world as value system. With
ObjectIO you supply event handlers (state transition functions) which are
magically invoked by a mysterious black box when required. Within each
handler actions use the sequential 'world as value' paradigm. This only makes
sense to me if we impose the constraint that one event handler cannot
interrupt another. I can't recall having seen this stated explicitly (but
maybe its just my memory at fault here). What determines the order in which
event handlers are invoked? Are they in chronological order?
 
> This is actually a rather old idea which was in fashion before monads and
> uniqueness typing became popular. The basis lies in the way Miranda and
> pre-1.3 Haskell did their I/O. The type of a program was:
> 
>    Main :: [ Input ] -> [ Output ]
> 
> And there were basically two programs running: the user programming and the
> outer world, which communicated by lazyy streams.

I don't think this is what I had in mind at all. I was aware that this used to
be the Haskell way of doing things. I am tempted to list all the problems with
this approach that I can think of, but I won't bother because that seems
pointless.
 
> This idea was extended into a multi-program model in the Kent Applicative
> Operating System (KAOS), which used Stoyes sorting office for routing the
> messages between the programs. Each output message was labeled with a
> destination address, which was used by the sorting office to direct the
> message to the correct receiver. The operating system consists then of many
> programs of the type above.

I'd not heard of this before. One problem with the lazy streams approach is
that it imposes an un-natural sequentiality (or should I say sequentialness?),
whereas concurrency seems to be the natural way to describe systems (to me at
least). Was(Is) this also reflected in the sorting office? To put it another
way Was(Is) the network of programs/sorting office 'deterministic'?

The reason I ask is that I don't much like the idea of using external 'helper'
applications, operating systems etc which couldn't be written in my chosen
language. As a pragmatic solution I can accept such things, but ideally I
would like to be able to describe my entire system in the same language using
consistent concepts.

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

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? Do you mean that the order in which
actions (world manipulating functions or whatever) are executed is not
necessarily the order in which they appear in the program? I suspect this
isn't what you mean, but I can't think of an alternative interpretation.
 
> The "world as value" paradigm does more than just forcing imperative actions
> to be executed sequentially.  It also means that there is a clear distinction
> in the type system between imperative actions and actions that do not have
> side effects.  This is where Clean, Haskell, and Mercury do better than ML.

> 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. If concurrency
is what you want then new language constructs are needed and the programmer
has to _use_ them. 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. The biggest
problem I can see is being absolutely certain that illegal action sequences
don't slip through the net, so to speak. One of the ideas I've been toying
with to enforce sequential action where it's needed has close resemblence to
continuation passing, which I suspect will prove just as awkward as world as
value. So the jury's still out on that one.

As far as the type system is concerned, I agree that actions must be
distinguishable from functions, but you don't need a world argument/result to
do that. e.g. You could have a print string function:
   printString :: String -> Action ()
This is really the same as the Haskell IO monad. printString is a function,
(printString "Hello") is an action.

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

Now if you view computation as an action, couldn't you specify different
semantics for different expressions if you want? From a latency point of view,
laziness may not be a good evaluation strategy.
For pragmatic reasons, I might want to say things like..
  Evaluate this expression now.
  Evaluate this expression only if you need it.
  Evaluate this expression when you've got nothing better to do.
  Evaluate this expression if you're running low on heap space.
  Un-Evaluate this expression if you're running low on heap space.
  Purge this expression of exceptions, and deal with them this way if found.
or some combination of the above.

Of course this isn't the whole story, there's still the reduction order to
consider, but it's this sort of thing that's going through my mind. So you
don't get rid of operational semantics, you just move them to the
non-functional (I.E. operational) part of the language.

Regards
-- 
Adrian Hey