Implementing channels in haskell -- Tackling the awkward squad

Question

In the paper Tackling the awkward squad, Simon Peyton Jones has provided a "possible implementation" of a Channel.

type Channel a = (MVar (Stream a) , -- Read end
                  MVar (Stream a) ) -- Write end (the hole)

type Stream a = MVar (Item a)

data Item a = MkItem a (Stream a)

Now, he implements a function putChan :: Channel a -> a -> IO () like this

putChan (read, write) val
  = do { new_hole <- newEmptyVar ;
         old_hole <- takeMVar write ;
         putMVar write new_hole ;
         putMVar old_hole (MkItem val new_hole) }

The function above takes a MVar out of write, then puts an empty MVar into it.
Then it writes to the old_hole it extracted from write.

The question is, why does it write to old_hole? It has been taken out from write and its scope is limited to the current block only, then what difference does it make?

Answer 1

The question is, why does it write to old_hole? It has been taken out from write and its scope is limited to the current block only, then what difference does it make?

Not quite. old_hole is "in scope" on the read side. You have to look at newChan for the full picture:

newChan = do { 
    read <- newEmptyMVar ;
    write <- newEmptyMVar ;
    hole <- newEmptyMVar ;
    putMVar read hole ;
    putMVar write hole ;
    return (read,write) }

So right after calling newChan the "old_hole" from putChan is the same MVar as hole in newChan. And as channel operations progress, that old_hole is always somewhere nested in the MVars of read.

I found the design of linked list-style channels truly difficult to wrap my head around at first. The illustration from that paper does a decent job of showing the structure, but the basic idea is readers "peel off" a layer of MVar to reveal a value, while writers are inserting values "at the bottom" of the pile of MVars, mainting a pointer to the bottom-most one.

By the way this is the design used in Control.Concurrent.Chan