Latent Effects for Reusable Language Components

In a few weeks, we’ll present our work on Latent Effects and Handlers at APLAS 2021. This work addresses some of the limitations of algebraic effects and handlers when modeling advanced control-flow mechanisms that defer execution, by introducing a latent monad. Don’t worry if these terms sound strange and unfamiliar, you will—kind of—know what they mean by the end of this blog post.

Throughout this post, we use an example application with microscopes. This is a real-world use case! In the KU Leuven Nanobiology Lab, the microscopes are operated with a Haskell-based domain-specific language (DSL), where we can put our theory into practice.

A hitchhikers guide to controlling a microscope

Most microscopes that we use in the Nanobiology lab are slightly more advanced than the typical microscope you might have used in highschool. They are entirely computer-controlled and can be operated by the user via an interface. Each microscope is also different, but typical controllable aspects are the position of the stage (the platform where the samples are based on), the focus of the objective lens, the color of the emitted light for fluorescence microscopy, etc.

Fluorescence Microscope	Mouse kidney
Olympus: Anatomy of the Fluorescence Microscope	Nikon MicroscopyU: Mouse Kidney

In our lab, the control software is written using a Domain-Specific Language (DSL). This has some benefits, since the language can focus on correctly operating the microscope, nothing less, nothing more. When operating the microscope, you are not bothered by complex programming features, as they are simply not exposed. You only need to know the domain very well, in this case microscopy. Ideal, isn’t it?

This use case is also a great research opportunity for testing our methods and provides for a nice running example.

Part of the control software is of course very specific to controlling a microscope. For example, the stage loop that updates the position of the platform, or the time lapse function to periodically repeat a program. But, there is also some code that is more generic and that can be reused. Think about logging (IO), connecting to the hardware (IO), keeping track of the stage’s current position (State), catching and handling errors (Exceptions), or abstracting over common (microscopy) techniques (e.g. SIM, FRET,…) (Functions). These features (IO, State, Exceptions, Functions) are usually considered generic, as they can appear in different DSLs as well.

For example, you can imagine that PyRo, Uber’s DSL for modeling traffic, uses State to know the user’s current position. Or Marlowe, a financial DSL for blockchain, uses Functions to abstract over common financial contracts.

As all good programmers are lazy (??), they prefer to reuse these generic features from somewhere on the internet. Then, as all good programmers are smart (??), they combine them in the correct way to get the desired functionality. The only thing to still do then, is to write the domain-specific code, and also plug that into the construction in order to get the Domain-Specific Language.

The microscopy DSL is a perfect example for illustrating this. It also sets the stage for the problem we will solve with our latent monad, because some language features don’t really work in this scheme with the existing solutions.

Datatypes à la Carte

Let’s take a broader look at our DSL. A DSL consists of syntax–tokens–and semantics of those tokens, their meaning.

In the following figure, we have some building blocks on the left (e.g., state, exceptions). Each building block can be thought of as a “mini DSL” with a specific functionality. These blocks only consist of the syntax—some tokens—of the mini DSLs. But there is no meaning yet behind these tokens. On the right, we have the semantics or the meaning of the blocks. The arrows represent the semantic functions that transform the tokens into a meaningful variant.

This is quite abstract, isn’t it? An example: We can have print as tokens in the syntax to mean that we want to print the first argument to stdout. Or, we can use the + token to say that we will have to add two numbers to eachother. Or, in case of the microscope setPosition gives us C code to change the position of the stage. We can execute this C code later.

What is so nice about these building blocks is that, if they are designed in the right way, they can be composed in all different kinds of combinations. Each combination then forms a new language. Also the arrows can be composed into one big arrow, which then forms the overall semantic function for the entire DSL. This is the concept of data types à la carte by Wouter Swierstra.

So in this way all the individual arrows together form a larger arrow pointing to one big semantic representation. However, not all these examples can be lumped together like this. For example, if we want to move our microscope stage and print that it is moving, we have two semantic aspects where the order of execution matters. There is a difference between first moving the stage and printing "The stage stopped moving!" or first printing that it stopped moving … and then starting to move the stage.

These pesky interactions with the real world are called side-effects. They are different from the so-called “pure” functions, where only computations such as + and - are done. They interact with some external resources. For example, changing the position of the stage changes the state of the program, as the current position has altered. Or logging the progress of the program requires the standard output. Since users of our DSL won’t like that everything happens in random order, we need to structure these side-effects.

Eugenio Moggi is the hero of the story here. He came up with monads to structure side-effects. But wait, what’s a monad? A burrito? Or just a monoid in the category of endofunctors? There are plenty (good and bad) blogs about what monads are, but for the purpose of this blog here, it’s enough to know that monads are wrappers (hence the burrito analogy) that return a uniform type instead of the type that it wraps. A well-known monad in Haskell is the wrapper around the effects of input/output: the IO monad.

So, when we have a program that is not pure, but has some effects, we first need to wrap the syntax blocks in monads before we can go to the semantics. That way, we keep things ordered.

But just like a burrito, a bit of wrapping is nice, but too much is a mess. We can wrap each building block separately, that’s okay. But if we want to combine the building blocks, we have to wrap them in multiple monads. For example, if we want a DSL with State and IO, we need to wrap the program in State, and in IO. You can imagine how this scales when adding more features.

Also, it is not so easy anymore to combine building blocks, as we can no longer plug them into eachother with all this wrapping going around. For example, if we have a State & IO monad and we want to add exceptions, we almost have to start over to make a State & IO & Exceptions monad. If it wasn’t clear, this is a lot of work.

Algebraic Effects and Handlers

Luckily, people have thought about this. Algebraic Effects and Handlers make it possible to compose these monads in a smart way so that they become plug-and-play components again.

When using algebraic effects, the side-effects can be combined using simple algebraic operations, such as + and -. (Slightly more complicated, but that’s what it comes down to). What happens is this: instead of using many wrappers and creating chaos, only a single wrapper is used. But this single wrapper contains a “sum” (using the special +) of all the present side-effects. This beautiful construction is called the free monad. Why is it free? Because you get the pluggability for free.

The next figure shows how the free monad has made order in the wilderness of effects. On the left, we still have the building blocks. In the middle we use the free monad with all the effects stacked (added up). And on the right we have our semantic meaning.

But the party isn’t over yet! There’s something else we get for free when using the free monad. This feature is called algebraic effects and handlers, and we haven’t talked about the handlers yet. These appear in the step from translating the monadic representation into the semantics (the right step in the figure). Handlers of algebraic effects ensure that this step is very structured and we love structure!

Every effect can be handled separately. In a sense, every handler peels of a layer of the stack of effects and transforms it into its semantics. A handler only knows about its own effect. For example, the State handler has no clue how to deal with IO. As the IO handler will come later, it can just leave the IO part as is and concentrate on the state part.

And this modularity is free. Great. But it isn’t all puppies and sunshine. Not all building blocks fit the algebraic effects and handlers. Some are too special and complex to be plugged in.

For example, Exceptions can not be handled this way. They mess with the continuations of the program, that’s why. For instance, when the microscpe catches an exception that the stage has gone out of reach, it will continue differently than without this exception as it will first try to move it within the allowed range again. These effects have a certain scope and the free monad cannot take that into account. But there is a way to include exceptions and still keep this nice structure, called Scoped Effects and Handlers. To achieve this, you need a special construction, a variant of the free monad that can deal with the scope of effects and the different possibilities of resuming the program. You don’t have to understand all the details of how these effects work for the purpose of this blogpost.

But still, some stubborn effects don’t fit in Scoped Effects and Handlers as well. Lazy functions, for example, are not algebraic nor scoped. As they are lazy, they want to wait with the execution of the function body until they feel ready. And so, the effects also have to wait.

Our solution: Latent Effects and Handlers

We came up with an even more special construction of a free monad that can deal with deferring effects. In microscopy, this could be a function that only logs to the stdout that the stage has arrived when it has arrived. We dub this construction the latent monad and design handlers accordingly.

This is how it works. Look at the following figure. The only part that changes is the step where we translate the effects into semantics, using the handlers. As you are reading attentively, you have of course already noticed this by looking at the figure.

The new thing is the jute bags with the pebbles. When a handler is doing its part of the job, it not only creates the semantics but also some pebbles. These pebbles represent semantics or a meaning that is not yet added to the overall meaning of the program. They are kept in the bags until the appropriate time.

When the time is appropriate is up to the other handlers. Handlers can consume, add or shuffle pebbles. This way, we can defer effects and add their meaning later to the program.

So, what’s the point of this?

Super nice, all these insane constructions and special monads. Sorry if we blew your mind. But what’s the point of all this?

Thanks to these different kinds of effects and handlers, you can more easily create a DSL. Just surf on the internet and you will find implementations for state, IO, exceptions etc. You can just borrow them to plug into your language. Make sure that you pick an implementation that uses the free monad, though. You get so much fun(ctionality) for free! And if you are adding effectful functions to your DSL, think about this blogpost because it was due to latent effects and handlers that you can pick them from the internet.