Concurrency in Haskell: Fast, Simple, Correct

This why I haven't fully embraced Rust yet. Whenever I ask about safely mutating shared state (see sibling comment), I'm met with silence, or some comment like: Rust guarantees that you aren't mutating shared state.

I'm surprised you say this. The core type system guarantees is that there is no aliasing while mutating, and no mutation while it is aliased. You get single writer multiple reader for free without overhead.

If you want multiple writers, you can always use the Arc container and use the built-in lock.

>> or some comment like: Rust guarantees that you aren't mutating shared state.

> The core type system guarantees that there is no [sharing] while mutating, and no mutation while [sharing]

Not sure what you are pointing out, so let me spell out what I said earlier.

1. You get single-writer multiple reader for free from the type system, without any runtime overhead.

2. For the same reason, the type system does not allow multiple writers. If you want multiple writers, then you are forced to use locks. Once you use locks, the runtime guarantees safety for this case.

Either way, you get 100% safety.

You're not adding any new information. I already understand you completely.

> 1. You get single-writer multiple reader for free from the type system, without any runtime overhead.

Take the example from the article which is accepted by the Haskell type system:

   writeTBCQueue :: TBCQueue a -> a -> STM ()
   writeTBCQueue q v = do
     stillOpen <- readTVar q.open
     when stillOpen $ writeTBQueue q.queue v

Rust would reject this because of multiple writers.

Also, thinking about it more, I'm now very skeptical of Rust even providing 'single-writer multiple-reader'. Is it in fact single-reader-writer xor multiple-reader? In other words, how does it handle a goblin constantly moving money between accounts while a gnome is constantly trying to count the total amount?

  goblinBankerThread = forever $ do
    seed <- randomSeed
    atomically $ do
        (acctA, acctB) <- chooseTwoRandomAccounts seed
        if (amount acctA) > (amount acctB)
            then moveAmount $5 acctA acctB
            else moveAmount $5 acctB acctA

  gnomeAccountantThread = forever $
    atomically $ do
      accounts <- readAllAccounts
      assert someConstantAmount allAccounts

Yes, Rust is 100% safe because it would reject this code, so it would never run. Not running code also has guaranteed no-overhead!

2. For the same reason, the type system does not allow multiple writers. If you want multiple writers, then you are forced to use locks

* Locks are problematic, which is why I chose STM over locks in the first place.

* Locks are in all the languages. Does your comment about 100% safety really apply to all languages ?

Your first point is not comparing the same thing. STM is wonderful, but as you no doubt know, it is meant for many TVars to be read/modified. This necessarily has overhead (transactional logs), performs poorly under contention and also is subject to livelock, and has no fairness.

In your goblin example, I believe the gnomeAccountantThread would have to constantly retry, because the writer (if successful) would have produced a new version of two accounts, which would trip up the reader, forcing it to start again. In general, Haskell's STM is built for short-lived transactions; for longer running transactions or those that touch a lot of objects, you'd need something like multi-versioned objects seen in databases or epochs to get a consistent snapshot. Neither Rust nor Haskell is suited to this example out of the box.

For your second question, you assume axiomatically that locks are problematic. They aren't in Rust (except, see later about deadlocks). Unlike any other language with in-place mutation, Rust will force you to use a mutex in order to share something for read-write (in a multiple writer scenario), otherwise it won't compile. You have to use lock() in order to get access to the underlying object, and once you have that object, the type system makes sure only the owner can mutate it. In C/C++/Java/Go, you don't get this guarantee at all ... it is possible to mistakenly use the object without using a mutex. So, there is not guarantee of safety in the other languages. There is a 100% guarantee in Rust.

---

That said, the problematic part about locks (whether it is mutexes or MVars in Haskell) is deadlocks, which is solved by having a deterministic lock order. In your Haskell example, if acctA and acctB were MVars, you'd do

    let (first, second) = if acctA < acctB then (acctA, acctB) else (acctB, acctA)
       withMVar first  $ \_ ->
         withMVar second $ \_ -> do
            ...