[Haskell-cafe] SimonPJ and Tim Harris explain STM - video

Cale Gibbard cgibbard at gmail.com
Thu Nov 23 15:44:07 EST 2006


On 23/11/06, Jason Dagit <dagit at eecs.oregonstate.edu> wrote:
> A comment on that video said:
>
> ----- BEGIN QUOTE ----
> It seems to me that  STM creates  new problems with composability.
> You create two classes of code: atomic methods and non atomic methods.
>
> Nonatomic methods can easily call atomic ones – the compiler could
> even automatically inject the atomic block if the programmer forgot.
>
> Atomic methods and blocks cannot be allowed to call nonatomic code.
> The nonatomic code could do I/O or other irrevocable things that would
> be duplicated when the block had to retry.
> ---- END QUOTE ----
>
> I imagine an example like this (some pseudo code for a side effect
> happy OO language):
>
> class Foo {
>   protected int counter; // assume this gets initialized to 0
>   public doSomething() {
>     atomic{
>       counter++;
>       Console.Write("called doSomething execution# " + counter);
>       // something which could cause the transaction to restart
>     }
>   }
>   public doOtherThing() {
>     atomic{
>       doSomething();
>       // something which could cause the transaction to restart
>     }
>   }
> }
>
> Now imagine doSomething gets restarted, then we see the console output
> once each time and counter gets incremented.  So one solution would be
> to move the side effects (counter++ and the console write) to happen
> before the atomic block.  This works for doSomething, but now what if
> we called doOtherThing instead?  We're back to having the extra
> side-effects from the failed attempts at doSomething, right?  We just
> lost composability of doSomething?  I'm assuming counter is only meant
> to be incremented once per successful run of doSomething and we only
> want to see the output to the log file once per successful run, but it
> needs to come before the log output inside doSomething so that the log
> makes sense.
>
> I realize STM is not a silver bullet, but it does seem like
> side-effects do not play nicely with STM.  What is the proposed
> solution to this?  Am I just missing something simple?  Is the
> solution to make it so that Console.Write can be rolled back too?
>
> Thanks,
> Jason

The solution is to simply not allow side effecting computations in
transactions. They talk a little about it in the video, but perhaps
that's not clear. The only side effects an atomic STM transaction may
have are changes to shared memory.

Another example in pseudocode:

atomic
   x <- launchMissiles
   if (x < 5) then retry

This is obviously catastrophic. If launchMissiles has the side effect
of launching a salvo of missiles, and then the retry occurs, it's
unlikely that rolling back the transaction is going to be able to put
them back on the launchpad. Worse yet, if some variable read in
launchMissiles changes, the transaction would retry, possibly causing
a second salvo of missiles to be launched.

So you simply disallow this. The content of a transaction may only
include reads and writes to shared memory, along with pure
computations. This is especially easy in Haskell, because one simply
uses a new monad STM, with no way to lift IO actions into that monad,
but atomically :: (STM a -> IO a) goes in the other direction, turning
a transaction into IO. In other languages, you'd want to add some
static typechecking to ensure that this constraint was enforced.

 - Cale


More information about the Haskell-Cafe mailing list