world as value

[Adrian Hey]

Hello,

I've been wondering wether or not I dare utter this heresy in public for some
time. Now seems an appropriate moment, so here goes..

   "Who said that languages have to be purely functional anyway."

I guess nobody will admit to this, but there seems to be a general consensus
in the Clean and Haskell communities that this is the way to go. The more I
think about this the more I believe that the expression 'purely functional
programming language' is self contradictory. I have nothing against the idea
of a language which allows pure functions to be defined, (in fact this is why
I like functional programming languages), but the use of the word 'programming'
implies an imperative to me. Unfortunately such things are outlawed from
languages which are claimed to be 'purely functional' so the 'world as value'
paradigm was invented to dress up side effect causing actions as functions.

It is my humble opinion that, at the end of the day, all the 'world as value'
paradigm achieves is to enforce imperative, side effect causing and prone
actions (sorry, perhaps some people would rather I call them functions) to be
executed sequentially. Sure this works, but it's a little simplistic I think.
I should emphasise that I'm not griping about Clean in particular here,
Haskellians have the same problem with their IO monad. So does ML, in fact I
think ML is even worse because it allows IO in ordinary functions.

(Excuse me for talking about myself a little.) My bread and butter is
electronics design and 'real time' embedded systems programming. (Please don't
ask me to define 'real time', in return I promise not to use the that other
wretched buzzword 'deterministic':-) Anyway, this software requires lots of
complicated interaction with hardware devices, interrupt handlers etc. I find
it hard to imagine how the 'world as value' paradigm can be extended to
provide an adequate description of the behavioural requirements and
complexities of such programs. Of course, that fact that I can't imagine how
this can be done doesn't mean that it can't be done, but even if such a thing
is possible, would it be the easiest way?

That said, I might observe that if we disregard the occasional context switch,
then execution within any single thread is sequential. So in this respect
the 'world as value' paradigm leaves us no worse off than a C hacker, but it
leaves us no better off either. I think it would be really useful if a
language provided some means of directly specifying the behavioural
requirements of a program.

So here's my idea...

1- Forget about the 'world as value' paradigm completely. Instead invent a
different (non functional?) way of nailing down program behaviour it terms of
actions that must be executed in response to events external to the program.
I must confess that I have very little idea how best to do this, or how to
go about proving that (from a behavioural point of view) a program satisfied
some kind of formal specification. The only thing I feel reasonably sure about
is that this approach requires big programs to be decomposable to smaller
sub-programs which interact my generating events which are seen by other
sub-programs. Some means of starting new sub-programs dynamically would be
useful (essential?) too. I think I'll call this the 'action spec' for want
of a better word. (Does this remind you of Erlang??)

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.

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

A note about side effects and 'computational actions'. We often appear to
assume that referential transparency and freedom from side effects are the
same thing. This can't be true. Referential transparency guarantees that the
value of any expression doesn't change or depend on when the expression is
evaluated, but the mere fact that evaluating any expression will consume
memory and CPU time means that the act of evaluating an expression may have
behavioural consequences, so cannot be regarded as 'side effect free'.
In other words, even internal computation is a subtle form of IO. That's why
I used the expression 'computational action'. The trouble is, I can't see how
the appropriate 'computational actions' can be derived from the definitions of
functions alone. I think we also need a behavioural context, which is why I
think we also need the 'action spec' or something similar.

Sorry if all this sounds a little vague. I admit that it is. I've been
thinking about this for some time, but I don't have much idea about how to
go about implementing such a system yet. Recently I came across a paper by
Robin Milner about 'Calculi for Interaction'...

   ftp://ftp.cl.cam.ac.uk/users/rm135/ac9.ps

My guts tell me that this is highly relevant to this issue. Unfortunately,
it's one of those papers which are full of strange hieroglyphics and
unfamiliar buzzwords, so I didn't understand most of it. Perhaps other people
out there can make sense of it. One thing I did find here was a brief
formalisation of Petri Nets as an 'action calculus'. Since Petri Nets are
graphical, they're probably a little easier for most people to understand.
There also seems to be an ISO Petri Net standard in preparation here..

   http://www.daimi.aau.dk/PetriNets/

What interests me about Petri Nets is that although graphical, they appear to
be more than just another b*ll sh*t methodology. Apparently, you can conduct
formal proofs with Petri Nets. (But I don't know exactly what you can or
can't prove, and the above website seems have little explanatory material.)
Perhaps I'll buy a book about them.

So how about using Petri Nets or some other action calculus as the basis for
a future Clean IO system? If I'm not mistaken, this would enable the IO and
concurrency issues to be rolled up in one consistent formalism.

Would anybody who knows more about them than me care to comment?

Regards
-- 
Adrian Hey