# Pearls of Algebraic Effects and Handlers

In the previous post, I presented a simple cooperative multithreaded scheduler written using algebraic effects and their handlers. Algebraic effects are of course useful for expressing other forms of effectful computations. In this post, I will present a series of simple examples to illustrate the utility of algebraic effects and handlers in OCaml. Some of the examples presented here were borrowed from the excellent paper on Eff programming language1. All of the examples presented below are available here.

## State

We can use algebraic effects to model stateful computation, with the ability to retrieve (`get`) and update (`put`) the current state:

The function `run` runs a stateful computation with the given initial state. Here is the implementation of the module `State` which provides the desired behaviour:

The key idea here is that the handler converts the stateful computation to functions that accept the state. For example, observe that if the function `f` returns a `unit` value (line 13), we return a function which accepts a state `s` and returns `unit`. The handler for effect `Get` (line 15) passes the current state `s` to the continuation `k`. The expression `continue k s` returns a function that accepts the current state and returns `unit`. Since fetching the current state does not modify it, we apply this function to `s`, the original state. Since `Put` modifies the state (line 14), the function returned by `continue k ()` is applied to the new state `s'`. We evaluate the computation by applying it to the initial state `init` (line 16).

Observe that the implementation of the handler for the stateful computation is similar to the implementation of State monad in Haskell. Except that in Haskell, you would have the stateful computation `f` have the type `State t ()`, which says that `f` is a stateful computation where `t` is the type of state and `()` the type of return value. Since multicore OCaml does not have a effect system, `f` simply has type `unit -> unit` as opposed to being explicitly tagged with the effects being performed. While the OCaml type of `f` under specifies the behaviour of `f`, it does allow you to combine various kinds of effects directly, without the need for monad transformer gymnastics2. For example, the following code snippet combines an int and string typed state computations, each with its own handler:

which prints:

## References

We can expand upon our state example, to model ML style references:

The idea is to represent the state as a list of universal typed values, references as a record with inject and project functions to and from universal type values, assign as appending a new value to the head of the state list, and dereference as linear search through the list for a matching assignment. The universal type implementation is due to Alan Frisch.

## Transactions

We may handle lookup and update to implement transactions that discards the updates to references in case an exception occurs:

Updating a reference builds up a rollback function that negates the effect of the update. In case of an exception, the rollback function is evaluated before re-raising the exception. For example, in the following code snippet:

the updates to reference `r` by transaction `T1` are discarded on exception and the program prints the following:

## From Iterators to Generators

An iterator is a fold-function of type `('a -> unit) -> unit`, that iterates a client function over all the elements of a data structure. A generator is a function of type `unit -> 'a option` that returns `Some v` each time the function is invoked, where `v` is the next-element in the data structure. The function returns `None` if the traversal is complete. Unlike an iterator, the generator hands over control of the traversal to the client of the library.

Gabriel Scherer’s insightful article on generators, iterators, control and continuations nicely distinguish, motivate and provide implementation of different kinds of iterators and generators for binary trees. While the iterator implementation is obvious and straight-forward, the generator implementation requires translating the code to CPS style and manually performing simplifications for efficient traversal. Since algebraic effects handlers give us a handle to the continuation, we can essentially derive the generator implementation from the iterator.

Let us consider a binary tree with the following type:

We can define an iterator that traverses the tree from left to right as follows:

From this iterator, we derive the generator as follows:

At each step of the iteration, we perform the effect `Next : a -> unit` (line 7), which is handled by saving the continuation to a local reference and returning the value (line 9 - 11). Since the effect handlers are provided with the continuation, we are able to invert the control from the library to the client of the library. This avoids the need to perform manual CPS translation.

## Direct-style asynchronous IO

Since the effect handler has access to the continuation, we can implement minimal asynchronous IO in direct-style as opposed to the monadic style of asynchronous IO libraries such as Lwt and Async. Our asynchronous IO library has the following interface:

Observe that the return type of the non-blocking function calls `accept`, `recv`, `send` and `sleep` are the same as their blocking counterparts from Unix module.

The asynchronous IO implementation works as follows. For each blocking action, if the action can be performed immediately, then it is. Otherwise, the thread performing the blocking task is suspended and add to a pool of threads waiting to perform IO:

The scheduler works by running all of the available threads until there are no more threads to run. At this point, if there are threads that are waiting to complete an IO operation, the scheduler invokes `select()` call and blocks until one of the IO actions becomes available. The scheduler then resumes those threads whose IO actions are now available:

The program implements a simple echo server. The server listens on localhost port 9301. It accepts multiple clients and echoes back to the client any data sent to the server. This server is a direct-style reimplementation of the echo server found here, which implements the echo server in CPS style:

The echo server can be tested with a telnet client by starting the server and on the same machine running `telnet localhost 9301`.

## Conclusion

The aim of the post is to illustrate the variety of alternative programming paradigms that arise due to algebraic effects and handlers, and hopefully kindle interest in reasoning and programming with effects and handlers in OCaml. Algebraic effects and handlers support in OCaml is in active development within the context of multicore OCaml. When you find those inevitable bugs, please report them to the issue tracker.