After working last year I was about ready to give up on threading. It is just too difficult to avoid deadlocks, and race conditions. I had basically resigned myself to using only message passing as a model for threading. Everything else seems just too damn hard. But now I excited by this software transaction memory implementation in Haskell.
The key idea is that a block of code, including nested calls, can be enclosed by an atomic block, with the guarantee that it runs atomically with respect to every other atomic block. Transactional memory can be implemented using optimistic synchronisation. Instead of taking locks, an atomic block runs without locking, accumulating a thread-local transaction log that records every memory read and write it makes. When the block completes, it first validates its log, to check that it has seen a consistent view of memory, and then commits its changes to memory. If validation fails, because memory read by the method was altered by another thread during the block’s execution, then the block is re-executed from scratch.
Transactional memory eliminates, by construction, many of the low-level diffculties that plague lock-based programming. There are no lock-induced deadlocks (because there are no locks); there is no priority inversion; and there is no painful tension between granularity and concurrency.
The main difficultly seems that your atomic block can only execute memory transactions. If your atomic block does I/O, then it cannot be rolled back. How is one going to distinguish between blocks of code that do I/O and those that do not? Hmm…
This is where Haskell comes to the rescue. It is already the case that all I/O must be tainted with the IO monad marker. So in Haskell you do know which blocks of code are safe for an atomic block and which are not.
Our starting point is this: a purely-declarative language is a perfect setting for transactional memory, for two reasons. First, the type system explicitly separates computations which may have side-effects from effect-free ones. As we shall see, it is easy to refine it so that transactions can perform memory effects but not irrevocable input/output effects. Second, reads from and writes to mutable cells are explicit, and relatively rare: most computation takes place in the purely functional world. These functional computations perform many, many memory operations—allocation, update of thunks, stack operations, and so on—but none of these need to be tracked by the STM, because they are pure, and never need to be rolled back. Only the relatively-rare explicit operations need be logged, so a software implementation is entirely appropriate.
This programming style doesn’t eliminate deadlocks, and doesn’t directly address race conditions. But it does eliminate locking. I hope that the ability to say, “make this block of code atomic” is simple enough to understand that it makes threaded programming sane.
I am confident that a purely functional, statically typed language like Haskell will be the general programming language of the future. All it needs is more libraries, and more intelligent abstractions designed by smart computer scientists.