Why algebraic effects matter in F#

Side effects

Side effects are impossible to avoid in imperative code, but they can make reasoning about the behavior of a program very difficult. F# allows us to use imperative side effects, but it's often better not to. How can we avoid side effects while still implementing effectful requirements?

As an example, let's take a very simple and common effectful example: logging. Say we're writing a function that computes the length of the hypotenuse of a right triangle from the lengths of the other two sides:

let hypotenuse a b =
    printfn "Side a: %g" a
    printfn "Side b: %g" b
    let c = sqrt <| (a*a + b*b)
    printfn "Side c: %g" c
    c

Every time this function is called, we log the input and output to the console as a side effect. This is fine in a single-threaded application, but what happens if hypotenuse is called simultaneously from two different threads? That's trouble.

A common approach in the imperative/OO world is to use dependency injection (or plain old interfaces) to separate the logging API from its implementation. However, the resulting code still causes side effects. Is it possible to define an effectful hypotenuse function that doesn't have any side effects? It sounds almost like a contradiction in terms, but it can be done, and the solution is very interesting.

Algebraic effects

The approach is to explicitly declare effects using an Effect type:

type Effect<'result> =
    | Log of string * (unit -> Effect<'result>)
    | Result of 'result

In this simple example, there are only two effects:

• Log is what we use to write a string to a logger. This constructor takes an additional continuation function that is to be executed after the string is logged.
• Result simply holds a value and doesn't cause an effect.

Note that this type is an example of the free monad. Log corresponds to the Free constructor and Result corresponds to Pure. The free monad is useful here because it can chain effects together. For example, we could rewrite our calculation like this:

let hypotenuse a b =
    Log ((sprintf "Side a: %g" a), fun () ->
        Log ((sprintf "Side b: %g" b), fun () ->
            let c = sqrt <| (a*a + b*b)
            Log ((sprintf "Side c: %g" c), fun () ->
                Result c)))

It's important to understand that this version of the function returns an Effect<float> rather than a float itself. You can think of this type as an "effectful" computation that will return a float when it is executed. However, until it is executed it does nothing - in particular, it has no side effects. It simply defines a computation.

Handling effects

In order to actually compute a result, we need some additional code that can "handle" our effects, just like an exception handler handles exceptions (which are also a kind of effect). Let's write a handler that accumulates log messages in a list while performing a calculation:

let handle effect =

    let rec loop log = function
        | Log (str, cont) ->
            let log' = str :: log
            loop log' (cont ())
        | Result result -> result, log

    let result, log = loop [] effect
    result, log |> List.rev

When we pass an effectful computation to handle, we get two things back: the final result of the computation, and a list of all the log messages that were written during the computation:

let c, log =
    hypotenuse a b
        |> handle

Note that handle is also a pure function - it doesn't write anything to the console or perform any other side effect. If we want, we could then write the resulting log to the console, but we'd have to be careful at that point to consider the actual side effects involved. The important thing is that we've successfully separated a pure functional calculation from the impure side effects of writing a log to the console. By solving those two problems separately, we've made it much easier to understand how our program behaves.

Syntactic sugar

Of course, no one wants to write ugly nested Log invocations like this because they completely distract from the logic of the computation itself. Fortunately, we know that the free monad can help us here by providing a workflow:

let rec bind f = function
    | Log (str, cont) ->
        Log (str, fun () ->
            cont () |> bind f)
    | Result result -> f result

type EffectBuilder() =
    member __.Return(value) = Result value
    member __.Bind(effect, f) = bind f effect

let effect = EffectBuilder()

This is the standard bind implementation for the free monad: it simply passes the binding function down the chain until the end, at which time the two effects are bound together by applying the function.

We also need some helper functions that "lift" a log string into the monad:

let log str = Log (str, fun () -> Result ())
let logf fmt = Printf.ksprintf log fmt

Again, this follows the same pattern we've seen before with the free monad. With these tools in hand, we can rewrite our computation much more elegantly:

let hypotenuse a b =
    effect {
        do! logf "Side a: %g" a
        do! logf "Side b: %g" b
        let c = sqrt <| (a*a + b*b)
        do! logf "Side c: %g" c
        return c
    }

This version of the function produces an Effect<float> that is identical to the previous one. It's just much easier to understand, and is essentially no more complex than the original version of hypotenuse that wrote directly to the console.

Limitations

We can easily support additional effects by adding union cases to our Effect type. However, this sort of master list of all effects in a system isn't very practical. Ideally, we'd like to modularize effects so that they can be composed together. For example, we'd like to be able to handle log effects separately from exception effects and separately from stateful effects. Unfortunately, this isn't particularly easy to do in F# yet, but there is a library called Eff that serves as a proof of concept. (I wouldn't use it in production, though, because the handlers are rather ugly.)

In the future, I expect that algebraic effects will become mainstream, and support for explicit effect types will be baked into both functional and imperative languages. That's still several years away, though, but at least now you know it's (probably) coming.

Comments

[Mohamed Dahir]

Interesting. First time I heard about algebraic effects was from Dan Abramov's algebraic effects for the rest of us. But now, I am a little bit confused. Is algebraic effect about deferring side effects as outlined here or is it about leaving the concrete implementation of side effects to the calling function?

[Brian Berns]

I think of algebraic effects as separating an effect from the handler for that effect. Exceptions are the most familiar example: You can "raise" an exception without knowing where or how that exception will be handled. Algebraic effects extend that same idea to other impure operations, such as writing to a file.

[jim108dev]

Thank you for submitting this article. I have the following questions/remarks:

1. "A common approach in the imperative/OO world is to use dependency injection (or plain old interfaces) to separate the logging API from its implementation. However, the resulting code still causes side effects."

let hypotenuse (log:string -> unit) a b =
    log $"Side a: {a}"
    log $"Side b: {b}"
    let c = sqrt <| (a*a + b*b)
    log $"Side c: {c}"
    c

let dummy _ = ()
let r2 = hypotenuse dummy 5.0 0.0

dummy does not cause a side effect, does it?
'2. If the function in your example causes an exception for some reason only the exception is shown but not the log statements up to this point.

[Brian Berns]

1. You're right that dummy doesn't cause a side-effect, because it throws away its input. We're more interested here in logging functions that actually produce a log in the end.

2. Yes, it's probably not a good idea to mix plain .NET exceptions with the sort of pure functional effect handling described here. At some point in the future, exceptions will perhaps become just another kind of pure functional effect, but we're not there yet.