[Haskell-cafe] Adaptive transactions

Ryan Ingram ryani.spam at gmail.com
Tue Jul 7 17:34:18 EDT 2009


It seems to me that the Adaptive framework[1][2] is well-suited to STM
transactions.  Consider this snippet:

> expensive_transaction :: STM Int  -- does a bunch of work
>
> example :: TVar Int -> STM Int
> example t = (+) <$> readTVar t <*> expensive_transaction

If the TVar passed to example is rapidly changing (perhaps it
represents the current time), then this transaction will starve; it
never gets a chance to complete, even if the values used by
expensive_transaction aren't changing at all, we still re-evaluate the
entire action each time we "retry" this transaction.

But STM has a wonderful property: what we need to commit a transaction
is just the result value and a transaction log; both of these depend
only on the values of TVars read by that transaction.

So, if "expensive_transaction" doesn't refer to the TVar "t", then
even if "t" is rapidly changing, the transaction log generated by
"expensive_transaction" must not change, and we can just re-generate
the part of the transaction log for "readTVar t" and recompute the
(+).

This gets even better when considering big processes that are blocked
by an explicit "retry"; if some change in input is just going to cause
the transaction to retry again (and go back to sleep), we'd like that
to happen as quickly as possible.

Has anyone looked down this path?  It seems quite promising to me.

  -- ryan

[1] http://hackage.haskell.org/package/Adaptive
[2] Acar et al, Adaptive Functional Programming, POPL 2002
     http://citeseer.ist.psu.edu/old/752721.html


More information about the Haskell-Cafe mailing list