C++ Software Transactional Memory library

Working library for Software Transactional Memory that is built using several FP techniques and modern C++17.

• STM is monadic and combinatorial.
• It is very robust due to purely functional design.
• It is built on top of the custom Free monad.
• It operates by custom ADTs.
• It is usable despite it's experimental.

Additional materials

• Tutorial: Software Transactional Memory in C++
• Dining Philosophers Problem solved (variant 1)
• Dining Philosophers Problem solved (variant 2)
• More samples
• stm-free | Implementation in Haskell
• cpp_parsec_free | Implementation of Haskell's Parsec in C++ using the same Free Monad approach
• Functional Approach To Software Transactional Memory in C++ (Talk, Rus) | Slides (Eng) | My talk about this approach at C++ Russia 2018, Saint-Petersburg
• Functional Programming in C++ and Concurrent Calculations (Talk, Rus) | Slides (Eng) | My talk about this approach at LambdaNsk meetup, Novosibirsk, 2019

Requirements

• GCC 7.2

Troubleshooting

• Pass tvars to closures by copy.
• Make retry satisfiable.

Examples

The simplest possible usage is int counter increment from different threads.

Transaction:

stm::STML<int> incrementCounter(const stm::TVar<int>& tCounter) {
    stm::STML<stm::Unit> modified =
            stm::modifyTVar<int>(tCounter, [](int i) { return i + 1; });

    return stm::bind<stm::Unit, int>(modified,
                     [&](const stm::Unit&){ return stm::readTVar<int>(tCounter); });
}

Evaluation:

Context ctx;

stm::TVar<int> tCounter = stm::newTVarIO(ctx, 0);
int counter = stm::atomically(ctx, incrementCounter(tCounter));
std::cout << "Counter: " << counter << std::endl;

The Dining Philosopher Problem can be solved with STM elegantly. Here are the transactions for taking of forks:

stm::STML<stm::Unit> takeFork(const TFork& tFork) {
    return stm::withTVar<Fork, stm::Unit>(tFork, [=](const Fork& fork) {
       if (fork.state == ForkState::Free) {
           return stm::writeTVar<Fork>(tFork, Fork { fork.name, ForkState::Taken });
       }
       else {
           return stm::retry<stm::Unit>();
       }
    });
}

stm::STML<stm::Unit> takeForks(const TForkPair& forks) {
    stm::STML<stm::Unit> lm = takeFork(forks.left);
    stm::STML<stm::Unit> rm = takeFork(forks.right);
    return stm::sequence(lm, rm);
}

Notice the retry combinator that marks some state illegal and makes the transaction to restart on case if fork was already taken.

To get more information, read the tutorial.