Today marks the release of version 0.7.0 of Cats STM with several significant bug fixes and improvements to the fairness of retry scheduling.
If you are not familiar with the concept of STM (Software Transactional Memory) then you should definitely read the wonderful original paper Beautiful Concurrency or at least some of the docs for this library :D However, I will endeavour to give a very brief overview here.
The motivating observation is that the traditional tools for doing concurrent programming (mutexes, semaphores, etc) do not compose. Given two functions f: A => B and g: B => C each acquiring mutexes, we cannot reason about the locking behaviour of f andThen g in the presence of concurrency (see sections 2.1 and 2.2 of the paper).
The solution to this is the STM monad. This is compositional by definition (indeed, this practically is the definition of a monad) and exposes combinators such as
def map[A, B](s: STM[A], f: A => B): STM[B]
def orElse[A](attempt: STM[A], fallback: STM[A]): STM[A]
def check(check: => Boolean): STM[Unit]How do we obtain a value of type STM[A] in the first place? These are returned by the operations defined on TVars (transactional vars):
A value of type STM[A] represents a computation that we would like to run atomically and which should return a value of type A. How do we do that? The clue’s in the name!
Why does this return something of type F[A] (assume this is IO[A] for simplicity’s sake) rather than something of type A? The execution of atomically is the point at which we acquire locks and mutate TVars ie perform side effects and hence must be suspended in IO.
Here is a contrived example of what this looks like in practice. We use the check combinator to retry transferring money from Tim to Steve until we have enough money in Tim’s account:
import cats.effect.{ExitCode, IO, IOApp}
import io.github.timwspence.cats.stm.{TVar, STM}
import scala.concurrent.duration._
object Main extends IOApp {
override def run(args: List[String]): IO[ExitCode] =
for {
accountForTim <- TVar.of[Long](100).commit[IO]
accountForSteve <- TVar.of[Long](0).commit[IO]
_ <- printBalances(accountForTim, accountForSteve)
_ <- giveTimMoreMoney(accountForTim).start
_ <- transfer(accountForTim, accountForSteve)
_ <- printBalances(accountForTim, accountForSteve)
} yield ExitCode.Success
private def transfer(accountForTim: TVar[Long], accountForSteve: TVar[Long]): IO[Unit] =
STM.atomically[IO] {
for {
balance <- accountForTim.get
_ <- STM.check(balance > 100)
_ <- accountForTim.modify(_ - 100)
_ <- accountForSteve.modify(_ + 100)
} yield ()
}
private def giveTimMoreMoney(accountForTim: TVar[Long]): IO[Unit] =
for {
_ <- IO.sleep(5000.millis)
_ <- STM.atomically[IO](accountForTim.modify(_ + 1))
} yield ()
private def printBalances(accountForTim: TVar[Long], accountForSteve: TVar[Long]): IO[Unit] =
for {
(amountForTim, amountForSteve) <- STM.atomically[IO](for {
t <- accountForTim.get
s <- accountForSteve.get
} yield (t, s))
_ <- IO(println(s"Tim: $amountForTim"))
_ <- IO(println(s"Steve: $amountForSteve"))
} yield ()
}For a more involved example, see The Santa Claus Problem in the docs.
The importance of laws testing
If you’ve followed cats-stm for a while, you may notice that the Alternative instance for STM has been removed. Upon adding laws testing, I discovered that it does not satisfy the alternative right-absorption and right-distributivity laws (and indeed I believe that STM cannot satisfy these laws in its current formulation). I’ve therefore downgraded it to a MonoidK instance, which can be lawfully implemented.
If you haven’t tried out law-testing before, please do!! It turns out to be immensely valuable! :D If we are unsure that a type conforms lawfully to a typeclass then we cannot safely refactor operations of that typeclass on that type.
Open source at Permutive
I’ve been lucky enough to get to write this library as part of my work for Permutive. Hopefully if you’re a Scala developer you will have already noticed that Permutive is making significant contributions to the open source Scala community through the work of Travis Brown. Hopefully this post has convinced you that we have a wider commitment to open source and community contribution, both in Scala and (watch this space) Haskell. Come join us!