Software Transactional Memory - Composability Exam

Question

One of the major advantages of software transactional memory that always gets mentioned is composability and modularity. Different fragments can be combined to produce larger components. In lock-based programs, this is often not the case.

I am looking for a simple example illustrating this with actual code. I'd prefer an example in Clojure, but Haskell is fine too. Bonus points if the example also exhibits some lock-based code which can't be composed easily.

Answer 1

A translation of Ptival's example to Clojure:

;; (def example-account (ref {:amount 100}))

(defn- transact [account f amount]
  (dosync (alter account update-in [:amount] f amount)))

(defn debit [account amount] (transact account - amount))
(defn credit [account amount] (transact account + amount))
(defn transfer [account-1 account-2 amount]
  (dosync
    (debit account-1 amount)
    (credit account-2 amount)))

So debit and credit are fine to call on their own, and like the Haskell version, the transactions nest, so the whole transfer operation is atomic, retries will happen on commit collisions, you could add validators for consistency, etc.

And of course, semantics are such that they will never deadlock.

Answer 2

An example where locks don't compose in Java:

class Account{
  float balance;
  synchronized void deposit(float amt){
    balance += amt;
  }
  synchronized void withdraw(float amt){
    if(balance < amt)
      throw new OutOfMoneyError();
    balance -= amt;
  }
  synchronized void transfer(Account other, float amt){
    other.withdraw(amt);
    this.deposit(amt);
  }
}

So, deposit is okay, withdraw is okay, but transfer is not okay: if A begins a transfer to B when B begins a transfer to A, we can have a deadlock situation.

Now in Haskell STM:

withdraw :: TVar Int -> Int -> STM ()
withdraw acc n = do bal <- readTVar acc
                    if bal < n then retry
                    writeTVar acc (bal-n)

deposit :: TVar Int -> Int -> STM ()
deposit acc n = do bal <- readTVar acc
                   writeTVar acc (bal+n)

transfer :: TVar Int -> TVar Int -> Int -> STM ()
transfer from to n = do withdraw from n
                        deposit to n

Since there is no explicit lock, withdraw and deposit compose naturally in transfer. The semantics still ensure that if withdraw fails, the whole transfer fails. It also ensures that the withdraw and the deposit will be done atomically, since the type system ensures that you cannot call transfer outside of an atomically.

atomically :: STM a -> IO a

This example comes from this: http://cseweb.ucsd.edu/classes/wi11/cse230/static/lec-stm-2x2.pdf Adapted from this paper you might want to read: http://research.microsoft.com/pubs/74063/beautiful.pdf

Answer 3

And to make trprcolin's example even more idiomatic i would suggest changing parameter order in transact function, and make definitions of debit and credit more compact.

(defn- transact [f account amount]
    ....  )

(def debit  (partial transact -))
(def credit (partial transact +))

Answer 4

Here's a Clojure example:

Suppose you have a vector of bank accounts (in real life the vector may be somewhat longer....):

(def accounts 
 [(ref 0) 
  (ref 10) 
  (ref 20) 
  (ref 30)])

(map deref accounts)
=> (0 10 20 30)

And a "transfer" function that safely transfers an amount between two accounts in a single transaction:

(defn transfer [src-account dest-account amount]
  (dosync
    (alter dest-account + amount)
    (alter src-account - amount)))

Which works as follows:

(transfer (accounts 1) (accounts 0) 5)

(map deref accounts)
=> (5 5 20 30)

You can then easily compose the transfer function to create a higher level transaction, for example transferring from multiple accounts:

(defn transfer-from-all [src-accounts dest-account amount]
  (dosync
    (doseq [src src-accounts] 
      (transfer src dest-account amount))))

(transfer-from-all 
  [(accounts 0) (accounts 1) (accounts 2)] 
  (accounts 3) 
  5)

(map deref accounts)
=> (0 0 15 45)

Note that all of the multiple transfers happened in a single, combined transaction, i.e. it was possible to "compose" the smaller transactions.

To do this with locks would get complicated very quickly: assuming the accounts needed to be individually locked then you'd need to do something like establishing a protocol on lock acquisition order in order to avoid deadlocks. As Jon rightly points out you can do this in some cases by sorting all the locks in the system, but in most complex systems this isn't feasible. It's very easy to make a hard-to-detect mistake. STM saves you from all this pain.