[Haskell-cafe] Can you do everything without shared-memory concurrency?

[Timothy Goddard]

On Tue, 09 Sep 2008 07:33:24 Bruce Eckel wrote:
> I know that both Haskell and Erlang only allow separated memory spaces
> with message passing between processes, and they seem to be able to
> solve a large range of problems -- but are there problems that they
> cannot solve? I recently listened to an interview with Simon
> Peyton-Jones where he seemed to suggest that this newsgroup might be a
> helpful place to answer such questions. Thanks for any insights -- it
> would be especially useful if I can point to some kind of proof one
> way or another.

In Haskell it is  simply irrelevant whether parts of the structures being 
passed between threads are shared or not because the structures are 
immutable. We keep our code side-effect free and as a result it is incredibly 
easy to make parallel. This is so solid that we can also add implicit 
threading to the code with simple annotations such as 'par' and 'seq'.

Having said this, it is possible to generate structures which are mutable and 
only accessible in the IO monad. As a general rule, IO code using shared 
memory has the same threading issues as in any other language while pure code 
is guaranteed safe. Haskell is capable of working with both models, but 
mutable data structures are deliberately restricted in their use and are rare 
in practice.

A great deal of parallelism can be added to pure code without any risk. I 
can't assist with mathematical proofs, but can't think of any reason why 
shared, manipulable memory would be absolutely necessary. In the worst case, 
all operations on the data structure can be converted to messages to a 
central thread which manages that structure and serialises access. Any 
procedure call can become an asynchronous pair of request, response messages. 

I am not a mathematician, I can't prove it, but I can't think of circumstances 
where I would need to put mutable references in a data structure except where 
the language and compiler can't handle immutable structures efficiently.

Tim