Thread by @graninas

Programming in C++ is like being a patient in a mental hospital. 🧠👩‍🦽

Functional Programming in C++ is when those patients organize a secret mental hospital within the mental hospital and start pretending they are doctors.

🏗️Advanced FP I did in C++ ⬇️ Thread 🧵

You might have heard of the wonderful book "Functional Programming in C++" by @ivan_cukic (by @ManningBooks). I highly recommend it. This book will show you many nice FP tricks and tips.

It highlights most of what we call FP, but I went much further in exploring this area.

I've implemented a custom monadic Software Transactional Memory in C++ with my own approach based on Free monads.

The idea of interpretable Free monadic eDSLs helped me to implement this concurrency model in a really simple way compared to the mature STM libraries.

In the pictures, a classic concurrency problem known as "Dining Philosophers" is solved in both Haskell and C++ with custom STMs I made.

This is a transactional model of the task. There are philosophers, and there are forks to eat spaghetti. Forks are a shared resource here.

My custom STM eDSL should have 3 methods to deal with transactional variables and the retry combinator as it's in the native Haskell's STM:

data TVar a
type STM a

newTVar :: a -> STM (TVar a)
readTVar :: TVar a -> STM a
writeTVar :: TVar a -> a -> STM ()
retry :: STM a

With these methods made monadic, my STM would be minimal although completely viable and highly convenient.

I made this easily in Haskell. A custom interpretable STMF language and STML Free monad over it, and also, a simple interpreter to make it actually work. And it worked.

In C++, there are no ADTs and no Free monads.

I needed all this, so I first implemented ADTs and then implemented the Free monad itself.

Here I should have done:

- interpretable ADT for eDSL
- recursive interpretable Free type (also an ADT)
- monadic facilities for eDSL + Free

Algebraic Data Types

C++ doesn't have ADTs as we know them in functional languages.

Structures may be considered a product type if used as immutable values.

std::tuple is also a product type although very inconvenient compared to tuples in normal languages.

Sum types in C++ are sick.

Dynamic sum types aka OO hierarchy could work, but it's not the same as static sum types from the FP PoV.

We have to use std::variant, a very clumsy tool that requires a lot of ceremonies.

Here, Human and Animal are different types in C++, and Species is also a separate type.

In Haskell, there are no Human and Animal types. They are value constructors (aka object constructors in C++) of the Species type.

In both examples, we can construct a list of those values.

The differences become significant when it comes to pattern matching.

In functional languages, pattern matching over ADTs is essential.

In C++ (old versions), there is no pattern matching. There is std::visit (Visitor design pattern) that does a similar thing. But it's crazy.

This is where things are getting out of control. Implementing all those STM methods in C++ meant I needed 4 structures for my custom STMF ADT:

NewTVar
ReadTVar
WriteTVar
Retry

And, what a pity, I couldn't just have

struct NewTVar {}

for deep reasons.

All these types should be parametrized as it is for their Haskell counterparts. As you can see, Haskell STMF ADT is this:

data STMF next where
NewTVar :: a -> (TVar a -> next) -> STMF next

where 'next' is a type parameter of a user type not known upfront.

This method is also "hiddenly" parametrized by the type variable 'a'.

This makes my STMF type to be an existential ADT.

Existential ADTs are an advanced feature of Haskell. They are not commonly spread and are very sophisticated by nature.

In C++, there is no such thing at all.

This means I should do a lot of tricky non-trivial template metaprogramming alloyed with tricky non-trivial functional programming made through the tricky non-trivial C++ mechanisms.

In fact, I made this STM library for my talk at @cpp_russia , and when I first submitted the talk, I had nothing except the idea.

I had a strong belief that I can implement STM with Free monads despite the mature STMs are complicated on their own.

I was brave - and I did it.

Unfortunately, the code listings are extremely long. For example, these are the methods of my STMF algebra, and even so, I dropped a lot of constructors and destructors to make it shorter.

All these structures are expected to be used as stack-located immutable values.

Notice the std::any type. This type helps to work with unknown user types uniformly.

This is actually another trick I needed in both Haskell and C++ STMs. It's the so-called Typed-Untyped design pattern that I invented. It has many other uses in my Free monadic methodology.

Now it's time to actually have the STMF ADT.

Don't be misled by its simple look. This is actually an existential ADT because it only exposes the Ret type variable and hides the Any type variable inside the structures.

The next step was to implement a generic Free type in C++.

This straightforward Free ADT has two constructors: Pure and Free. And it's generically recursive.

I failed: I couldn't make it statically generic. So I made my Free type highly entangled with the STMF language.

But this is a basic Free type. Being a monad, it is slow: it has the O(N^2) complexity in monadic binding.

So I implemented another Free type for my STMs. This one is known as a Church-encoded Free monad, and it's faster.

So my STM library supports 2 engines now.

Church-encoded Free type is much more tricky. It represents one big complicated continuation (function) that has the ability to join (bind) two separate actions of my STMF eDSL.

In a basic Free type, this binding works by keeping the usual values of STMF, not functions.

My monads however would not work without many important functions for doing the stuff behind the scene. All monads are so: there is some functionality a developer doesn't see, but this functionality defines the behavior of the monad.

First, the STMF eDSL should be a Functor. Not a functor in C++ meaning, but rather a Functor in FP meaning.

And this is where I have to have a visitor instead of pattern matching. This visitor visits every action of STMF and does some needed conversions of it with a function.

The Functor instance for STMF (the StmfFunctorVisitor) is rather long and complicated.

Today, 5 years later, I don't really remember how it works. I only remember that I was shocked when it started working.

You know, it's C++. Undefined Behavior all the way (cc @Nekrolm).

The same is true for the 'bind' function - the essence of every monad. For the Free monad, my monadic binding should traverse a monadic STML scenario (transaction) and join it with another STML monadic scenario (transaction) thus having the final monadic STM scenario.

The 'bind' function is also a visitor implemented differently for the regular Free monad and for its Church-encoded version.

Don't ask. I have no idea how it works.

I don't think I'm able to repeat this journey again. And I'm not sure what money could even motivate me to try.

But once these facilities are done, we actually have everything we need to start writing STM scenarios which are monadically combinable transactions.

The library provides tons of monadic functions that allow one to write various behavioral models.

C++ doesn't support the do-notation.

Do-notation in Haskell and for-comprehension in Scala make working with all monads so easy and convenient that I strictly believe this feature should be introduced for all programming languages.

I personally tried to implement a generic do-notation with C++ macros, but couldn't make it work. I've seen some other attempts for C++ as well, all are very unsatisfactory.

For Rust, you can see this attempt by @politrons:

https://twitter.com/politrons/status/1660556275489333249

The final piece of the story of how my custom STM works should be about interpreters. As long as STMF, STML and Free are interpretable declarative eDSLs / ADTs, there should be some way to interpret/run them against a real environment and do the actual work.

Oh, this is another mind-blowing piece of code.

I invented a way to store transactional variables (TVars) of a custom user-defined type (hint: with the Typed-Untyped pattern and Typed Avatar design patterns).

Also, I made it transactional and thread-safe with certain tricks.

Today, after years of this endeavor, I believe this was a true enlightenment that allowed me to implement this library. My path wasn't free of local deadends of course, and sometimes I had a feeling that I'm in deep trouble. After all, I submitted a talk and was afraid to fail.

I especially remember when I first hit the need for existential types in C++. It was a cold shower to realize because I had no idea how to even approach the task.

Fortunately, the C++ language was insane enough for this to be possible, so I managed to overcome this obstacle.

I made STM in C++ for giving a talk.

But my meta-goal was to strengthen the methodology I call Functional Declarative Design.

Today I can say: functional C++ was a really interesting mental hospital to me. I appreciate it a lot but will never visit it again.