CS223, 6/2/2010
Lecture 22

Computing with computations
===========================

We have seen four cases of a phenomenon that is typically
associated with functional programming.  This phenomenon
is the composition of delayed or potential computations
before they are actually performed.  The four cases are:

1. thunks and lazy evaluation.
   lazy data structures like lists and streams involve
   working with potentially infinite computations in
   a latent form

2. IO actions
   We compose these, building potentially complex and
   dynamically unfolding actions. The the actual performance
   of the action is delayed to the very end of the computation
   (and is only implicit in the program)

3. continuation passing style
   we construct and transform continuations, which represent
   "the rest of the computation"

4. First-class events in Concurrent ML.  We construct concurrency
   abstractions by composing events (e.g. choice) in advance of
   the "occurrence" of the events (caused by sync).




Concurrent Haskell
==================

Primities for concurrency are found in module Control.Concurrent:

1. Threads and forking

type ThreadId      -- primitive

forkIO :: IO () -> IO ThreadId

  the "work" to be performed by a thread is packaged as an IO ()
  action (in contrast to a unit -> unit thunk for CML). Like spawn
  in CML, returns a unique ThreadId when performed.

yield :: IO ()

  allows a thread to explicitly yield control (for cooperatively
  scheduled concurrency)

killThread :: ThreadId -> IO ()

  kills the thread designated by ThreadId arg

Plus some more esoteric operations.

Note: threads reading (e.g.) the same pure list value require
low-level synchonization because of forcing of thunks and the
side-effect of memoization.

Example: parent and child threads
----------------------------------------------
file : conc1.hs
----------------------------------------------
import Control.Concurrent

loop :: Char -> Int -> IO ()
loop ch 0 = return ()
loop ch n = putChar ch >> loop ch (n-1)

foo :: Int -> IO ()
foo n = forkIO (loop 'a' n) >>= (\ _ -> loop 'z' n)
----------------------------------------------


2. Communication/Synchronization

(1) MVars: 

type MVar a      -- primitive

  Like a single element buffered channel. It has two states:
  empty, or full (containing one value of type a). Communication
  via MVals is "asynchronous".

newEmptyMVar :: IO (MVar a)
newMvar :: a -> IO (MVar a)

  Create new MVar either empty or filled with an initial value

takeMVar :: MVar a -> IO a

  blocks until MVar contains a value, then returns that value,
  leaving MVar empty

  single wakeup: if multiple threads are blocked trying to write
  into the MVar, takeMVar will only enable one of them to run
  

putMVar :: MVar a -> a -> IO ()

  puts a value into an MVar, if empty. If MVar is full, blocks
  (i.e. waits) until it becomes empty

  single wakeup: if multiple threads are blocked trying to read
  from the MVar, putMVar will only enable one of them to run

  
isEmptyMVar :: MVar a -> IO Bool

  checks whether the MVar is empty; does not block

Example: producer and consumer
--------------------------------------------------------------
file: prodcon.hs
--------------------------------------------------------------
import Control.Concurrent
import Control.Concurrent.MVar

buf :: IO (MVar Int)
buf = newEmptyMVar

producer :: MVar Int -> Int -> IO ()
producer buf 0 = return ()
producer buf n = putMVar buf n >> producer buf (n-1)

consumer :: MVar Int -> IO ()
consumer buf = takeMVar buf >>= (\c -> print c) >> consumer buf

run n = do buf <- newEmptyMVar
           forkIO (producer buf n)
           consumer buf
--------------------------------------------------------------


(2) Channels

type Chan a    -- primitive

  buffered FIFO channels

newChan :: IO (Chan a)

  create a new empty channel

writeChan :: Chan a -> a -> IO ()

  add a value to the end of the channel queue (enqueue)

readChan :: Chan a -> IO a

  read the first value from the channel queue (dequeue)

unGetChan :: Chan a -> a -> IO ()

  put an item back onto the front of the channel queue
  (e.g. undo a readChan)

isEmptyChan :: Chan a -> IO Bool

  check if channels queue is empty

getChanContents :: Chan a -> IO [a]

  return a lazy list representing the contents of the Chan
  (i.e. the list of all elements that are in the channel
  queue now or will be written to the channel in the future

These channels differ from CML channels, which are
synchonous (not buffered). In CML, the sender and receiver
on a channel have to "rendezvous".


==========================================================
There is a lot more to concurrency in Haskell:

* Data parallel Haskell

* Haskell Orc (Launchbury & Elliot)