Abilities for the monadically inclined

Control flow

The actual superpower of monads is the embedding of control flow. In other words, we can abstract control flow (and various patterns) as datatypes and use functions over values.

Control flow is the order of execution — the path a program takes, based on instructions like conditions, loops, and function calls. For instance, do X, then do Y, and depending on some condition do S or Z (using if/then/else):

graph TD;
    X[doing X]-->Y;
    Y[doing Y]-->C{condition};
    C-->|true|S[doing S];
    C-->|false|Z[doing Z];
    S-->done;
    Z-->done;

In traditional programming languages, the set of control flow patterns is fixed. Expanding it requires additional features, such as try/catch, while and for loops, async and await, and so on.

Sometimes, we can represent complex patterns using simpler building blocks; for example, we can represent loops using conditionals (aka if/then/else):

fun loop(counter: Int, iterations: Int) =
  if counter >= max_iterations
    // Do something
  else
    // Do something else
    loop(counter + 1, iterations)

Writing loops from scratch quickly becomes cumbersome. So, usually, we'll get built-in loops.

Another example is checking if the value exists (checking for null, nil, whatever). It can be implemented using a simple check:

String result = "";
if (album != null) {
  result = album.getLast().toString();
} else {
  result = "missing";
}

It also doesn't scale well:

String result = "";
if (artist != null
    && artist.getDiscography() != null
    && artist.getDiscography().getAlbums() != null
    && artist.getDiscography().getAlbums().getLast() != null) {
  result = artist.getDiscography().getAlbums().getLast().toString();
} else {
  result = "missing";
}

That's why languages like Kotlin and Rust provide operators or special syntax to safely chain and deal with nullable values:

artist?.discography?.albums?.last?.toString() ?: "missing"

artist?.discography?.albums?.last.map(|album| album.to_string())

Which are pretty much monads in disguise. We represent optionality as datatypes and use functions over values. And it's not just optionality. We can model various concepts (such as exceptions, iterating, sync / async, parsing, finalizing or closing resources, dependency injection, and cancellation) with monads and monad-like things:

• doSomething.handleErrorWith(doSomethingElse)
• listOfItems.traverse(item => persistToDB(item))
• (fetchFromOneService, fetchFromAnotherDataBase).parMapN(doSomethingWithResult)

The largest recent “monadization” we can observe in strict and mainstream languages is around asynchronous programming: Reactive Streams in Java, Futures in Scala, Promises in JavaScript and many other places.

Eventually, languages catch up and acquire some sort of async/await syntax or lightweight threads, which replace monads (and monad-like things). But it takes time. For example, Java finally obtained virtual threads (see Project Loom), but we have been doing asynchronous programming in Java thanks to “monads” for more than 10 years already!

This is the real superpower of monads. This is why we use monads! They allow us, developers, to have more control over the flow of the program.

Monads vs. Direct Style

Direct style is simple, yes, but only when it's possible. Each feature (or control-flow mechanism) needs to be supported by the language and usually comes with its own syntax.

Another trade-off is effects tracking: the effects are not typed and it's not as painful to mix different effects.

On the one hand, it's still easier to teach; on the other hand, it comes with annoying properties such as a lack of referential transparency and some presence of function coloring (depends on the particular implementation).

The latter can be frustrating with monads as well. Have you ever had to replace a bunch of maps with traverse when you introduce one additional monad (e.g., adding a log) in a deeply nested function?

def one(str: String): String

def two(y: String): Option[String] =
  y.some.map(one(_))

def three(x: Option[String]): Option[String] =
  x.flatMap(two(_))

// if String becomes IO[String]
def one(str: String): IO[String]

// map becomes traverse
def two(y: String): IO[Option[String]] =
  y.some.traverse(one(_))

// flatMap becomes flatTraverse
def three(x: Option[String]): IO[Option[String]] =
  x.flatTraverse(two(_))

So, can we do better?

The worst of both worlds? Mixed styles

Naturally, we want to have our cake and eat it too, so we wind up with a mix both — the cons of both! We are stuck in this world because we want the power of monads to embed user-defined effects and control flows, but at the same time, we never handled the hate of monads.

Some effects are controlled by evaluation (direct style), and some — by explicit combinators (monadic style). As a result, we lose both the immediacy of the former and the systematic clarity of the latter.

However, we don't have to stay here.

Control flow and the call stack

In a nutshell, direct-style algebraic effects is “just” a nice interface over delimited continuations.

Control flow happens by affecting the call stack. As a reminder: exceptions, loops, async, finalizing or closing resources, dependency injection, cancellation — all of these require some technique to jump through the function call stack. So, instead of manipulating the call stack “directly” via custom features, we can use monads or some other instrument.

• Direct style / Custom features: The compiler does that.
• Monads: We can manipulate the data structures that reify the call stack.
• Delimited continuations: We can use user-level primitives to affect the call stack, but it's quite mind-breaking. Nobody wants that.
• Direct-style algebraic effects: We can use delimited continuations via a better interface (types + syntax).

The pros of direct-style algebraic effects

What do we have now?

Right up front, we get the ability to embed user-defined effects — a massive improvement over traditional direct style; plus the ability to write code in direct style — a considerable improvement in expressing control flow.

We haven't demonstrated this, but writing custom effects is more accessible than monads. You have to trust us on that. Writing custom monads is an upper-intermediate or expert-only endeavor (especially when you have to deal with stack-safety in a strict language).

At the same time, there's a limited amount of syntax. The language designers must make a few choices: around effect handlers, suspending and forcing execution. We saw two variations in the case of Unison. Still, there is no need to make a new syntax for every feature.

Which leads us to teaching. Teaching people how to use effects is trivial (essentially, they need to grasp suspending and forcing computations).

Remember how easy it was to add the Store ability to existing abilities? We keep typed effects and peacefully mix them! And on top of all that, no more function coloring at all. There is no map/`traverse` distinction and so on.

The elephant in the pure room

Nothing comes for free. This might sound dramatic for people coming from monadic worlds, but the first thing we lose with direct-style algebraic effects is referential transparency.

Imagine we have a program that initializes two mutable refs with "empty", writes "full" into the first one, and then reads values from the both refs:

refExample1 : '{IO} Text

refExample1 : '{IO} Text
refExample1 = do
  use IO ref
  use Text ++
  use mutable.Ref read
  x = ref "empty"
  y = ref "empty"
  mutable.Ref.write x "full"
  read x ++ "|" ++ read y

When we run refExample, we get:

"full|empty"

If we decide to dry the code and naively extract the initialization into emptyRef:

refExample2 : '{IO} Text

refExample2 : '{IO} Text
refExample2 = do
  use Text ++
  use mutable.Ref read
  emptyRef = IO.ref "empty"
  x = emptyRef
  y = emptyRef
  mutable.Ref.write x "full"
  read x ++ "|" ++ read y

We get a different program because, when we run refExample2, we get:

"full|full"

Both x and y were updated because they are the same ref. What we wanted to do is to suspend the initialization and then force it twice (first time for x and second for y):

refExample3 : '{IO} Text

refExample3 : '{IO} Text
refExample3 = do
  use Text ++
  use mutable.Ref read
  emptyRef = do IO.ref "empty"
  x = emptyRef()
  y = emptyRef()
  mutable.Ref.write x "full"
  read x ++ "|" ++ read y

Which would give us:

"full|empty"

As you can see, refactoring the code with abilities might require more brain activity than with monads. Even though it's a hurdle for people with a “monadic” background, it's not the end of the world. We gave up something important, but we also gained a ton.

Other limitations and unknowns

The drawbacks don't stop there. Direct-style algebraic effects is a novel concept (even comparatively to monads) — there are still some open questions and some unknowns. We need some time to explore their limitations.

For example, static control flow (applicative-style code) is a niche use case (e.g., applicative parsers, applicative-style build tools) can't be expressed with abilities. Because there is no way not to evaluate effects or undo an effect.

Are there more cases like this? We don't know yet. However…