[Haskell-cafe] Mutable arrays

Andrew Butterfield Andrew.Butterfield at cs.tcd.ie
Wed Feb 6 15:57:43 EST 2008


Peter Verswyvelen wrote:
> So monads *do* enforce uniqueness... So what is the difference between
> Haskell's monad approach and Clean's uniqueness typing? I always thought
> these were just two different ways to tackle the same problem, and I had the
> feeling Haskell's approach was actually more general.

Yes (1), and no (2).


! Long pedantic post follows


(1)

They are two different ways to tackle the same problem: how to have
I/O in a pure functional language when I/O neccessarily requires the
"world state" to be destructively updated (e.g. we can't copy the entire
filesystem, or the (truly) global internet state).

The solution is based on the following observation: imagine we
a have a large datastructure  (e.g. big tree) and a function that
updates it, then, *in general*, pure functional semantics requires the 
implementation to return a copy of its argument with the update applied, 
leaving the original argumment intact.

However, if in a given program, we know that the old value of the
big structure is never referenced once the function is applied,
then we can *implement* the function application "under the hood"
as a true destructive update, without breaking the pure referential
semantics of the language.

Such a use of a structure in a program is said to "single-threaded".

For example, the program
    f (g (h bigThing))
makes single-threaded use of bigThing, so *in this program*,
we could implement f, g and h using destructive update without altering 
the outcome as predicted by a copy semantics.

However, the program
   (bigThing,h bigThing)
does not have a single-threaded use of bigThing, so h *must* be 
implemented using copying, because we have access to both values.

The upshot of all of this is that a program that restricts itself
to single-threaded use of a (large) structure can use a desctructive
implementation, so if we can ensure that our patterns of I/O access
are single-threaded, then we can:
   - implement I/O as we must, i.e with destructive update
   - yet still maintain the "illusion" that our program is pure (copying).

What's the catch? Well, in general, the question of wether or not
a given structure's use is single-threaded, is undecidable. So what
we have are two (partial) solutions: Clean's uniqueness types, and
Haskell's monads.

Let us assume that the entire I/O state is captured by
a variable world :: World

"Invent-and-Verify": Clean allows you to write a program that
explicity mentions world, and the uses the type-system to check
that accesses to world are single-threaded. Essentially the
destructive functions have type annotations that insist
their World arguments and results are singly-threaded (a.k.a. "unique").

So program
   writefile "a.dat" "Text A" (writefile "b.dat" "Text B" world)
typechecks, but program
   (world,writefile "b.dat" "Text B" world)
doesn't.

Because of undecidability, the type-checker is not totally accurate,
but behaves conservatively, so may report a program as ill-typed,
even if it is actually single-threaded, but will always spot
a program that is truly bad - not single-threaded.

"Correctness-by-Construction": Haskell approaches the problem by hiding
the world inside an abstract data-type called a monad. Haskell programs
do not mention the world explicitly at all. The monad, with its return, 
bind and basic monadic I/O operations is setup so that the hidden world
state is always accessed in a single-threaded fashion,so the underlying
implementation is free to use desctructive update.

So we can write a monadic form of the first program above, as
    do writefile "b.dat" "Text B"
       writefile "a.dat" "Text A"
We cannot begin to express the second (ill-typed) program at all !


(2)

Leaving aside the fact that the monad concept is more general than just
I/O (Maybe monad, List monad, etc..),
we can state categorically that as far as I/O is concerned, that Clean's
uniqueness type approach is more general than Haskell's monads, i.e.:

- any Haskell monad-IO program can be re-written as a correctly typed
   Clean IO program (simply "implement" the IO monad as a state monad
   over a state world :: World).
- not all Clean IO programs can be directly written in monadic style.

The issue has to do with the fact that the IO monad "over-sequences"
IO actions, because the monad encapsulates the entire world in one
lump.

(see slides 37/38 of 
http://research.microsoft.com/~simonpj/papers/haskell-retrospective/HaskellRetrospective.pdf). 


So if we have two functions, one,  f1 :: IO (), reading from file 
"f1.in" and writing to "f1.out", and the other, f2 :: IO ()  reading 
from "f2.in" and writing to "f2.out", we must decide as programmers
what order to use - either do{ f1 ; f2 }   or do { f2; f1 }.
If we generalise to f1 .. fn, we have to sequence these,
which is why the function in Haskell of type [IO a] -> IO [a], is called
"sequence".

In Clean, we not only have explicit access to the world, but
we can partition it. Simplifying somewhat, we could open up
pairs of file-handle (f1.in,f1.out), (f2.in,f2,out) ... (fn.in,fn.out),
which does have to be done sequentially, since each file opening 
modifies the (global) filesystem. However, once this is done,
we could, in principle, execute the fn in any order,
and indeed in such a way that the implementation could choose to
do them in parallel - this potential for (admittedly limited)
deterministic parallel execution of I/O actions is possible with
uniqueness types, but not epxressible in the monadic world as
currently formulated.

(3) Shameless plug : a semantics for I/O that covers both Clean and 
Haskell and which scopes out the "deterministic parallelism" alluded to
above was described in

Malcolm Dowse, Andrew Butterfield: Modelling deterministic concurrent 
I/O. ICFP 2006: 148-159  http://doi.acm.org/10.1145/1159803.1159823





-- 
--------------------------------------------------------------------
Andrew Butterfield     Tel: +353-1-896-2517     Fax: +353-1-677-2204
Foundations and Methods Research Group Director.
Department of Computer Science, Room F.13, O'Reilly Institute,
Trinity College, University of Dublin, Ireland.
                             http://www.cs.tcd.ie/Andrew.Butterfield/
--------------------------------------------------------------------


More information about the Haskell-Cafe mailing list