What is Algebraic about Algebraic Effects?

what does the word “algebraic” mean when used in the context of programming langs?
– a random tweet

I’d wondered the same thing about “Algebraic Effects”, and was excited to find a talk on YouTube titled What’s Algebraic About Algebraic Effects and Handlers? Unfortunately, I’m not the target audience. As an engineer that doesn’t shy away from math, it was still out of my depth.

I found some time this past spring looking into Algebraic Effects, and I think I have a decent answer to the question.

Algebra in the context of programming

My view of “Algebra” in the context of programming is a particular kind of compositionality, where there’s a structure.

In contrast, mainstream developers often talk about compositionality as just two obj/function that can interoperate due to the same interface, but not much more can be inferred about properties of the interop between the two obj/functions.

So often times, we get some collection of objects/functions that go together in an arbitrary way according to the taste of the developer that wrote it. If they’re any good, it feels intuitive. But more often than not, it feels arbitrary. The effect is magnified if you look into the codebase. To a newcomer, it feels like a mess, in the same way that a house built by piling stones high feels like a mess: there’s no apparent or easily recognizable structure.

A tangential detour into abstract algebra

In abstract algebra, structure is often where you take some math object 𝛂 (like an int, or matrix), and you pair it with an operation, (like + or *), and you say: integers can be composed with op `+`, but we can ALSO infer properties in these combos–or laws.

So a common one we know is: integer (ℤ) with addition (+) has implied properties that always hold. And the elements (ℤ), the op (+), and the properties together constrain outcomes, and this is what gives us structure. A house with structure feels like it’s built with arches, rather than a pile of rocks. What are the properties of (ℤ) and (+)? Due to how ℤ and + are defined, we get these properties:

1. Closure: ℤ + ℤ always gives you another ℤ.

Sometimes devs write code that doesn’t give you back the same thing.

2. Associativity: (a + b) + c = a + (b + c) where a, b, c are in ℤ.

This familiar, as they were drilled in grade school. But often devs don’t write code that fulfill this property.

The last two are:

3. identity: ℤ has an element that doesn’t change when we use +.
Here, it’s zero: a + 0 = a

4. inverse: every ℤ has a matching ℤ that give us the identity when we use + on it: a + (-a) = 0, where a and -a are in ℤ.

Taken together, math peeps gave this kind of structure a name: Groups. So if someone says [a struct] and [an op] together form a group, I can automatically can assume those properties. It’s a shorthand.

If you add even more constraints/properties to how ℤ and + behave together, you get another algebraic structure. There’s a whole host and families of these. So if we add another constraint, we get an Abelian Group:

5. Commutativity: a+b = b+a, where a, b are in ℤ

Surmounting the network with algebra

Why write constraining data structure and op pairings? It’s quite useful if you want to guarantee specific properties of your system. For example, it’s well known that syncing is hard, because of the Eight Fallacies of Distributed Systems.

1. The network is reliable;
2. Latency is zero;
3. Bandwidth is infinite;
4. The network is secure;
5. Topology doesn’t change;
6. There is one administrator;
7. Transport cost is zero;
8. The network is homogeneous.

That means your data, when sent over the network will likely arrive out of order. Worse, clocks can be out of sync, so it can look like data arrived from the future. How can we tame the underlying unreliable system? By constraining our data and operations to have properties.

CRDTs are nowadays used to enforce eventually consistent syncs. It achieves this by pairing a data structure with a merge operation, which together form an algebraic structure called a semi-lattice. The properties of a semi-lattice are:

• Closure: For all a, b in the set S, the result of a ∘ b is also in S.
• Associativity: a ∘ (b ∘ c)=(a ∘ b) ∘ c for all a, b, c ∈ S.
• Commutativity: a ∘ b = b ∘ a for all a, b ∈ S.
• Idempotence: a ∘ a = a for all a ∈ S.

Together, this is enough to counteract the network mixing up your data when sending it over the network. I wrote about that here:

A simple way to understand CRDTs

🔰If CRDTs (Conflict-free Replicated Data Types) are new to you, check out this previous post. There’s a simple way to understand CRDTs: It leverages algebra to unmix the inevitable mixing of data when syncing over an unreliable network. Why are networks unreliable? For one, it’d be really expensive to build

So by constraining the power of what our code can do, we can ensure the system has specific desirable properties that achieve the goal of syncing data over an unreliable network. It’s where we say: “If we compose this kind of data structure in this constrained way with this kind of merge function, then we can guarantee these properties always hold. And with this structure, our data can survive sync over an unreliable network with other syncers.”

From Monads to Algebraic Effects

This is why people also like Monads. Monads are about how to compose code, but with specific properties (Monadic laws) so we can achieve some goal in how they compose. I won’t go into it here, as this is already long, but that’s the core idea.

However, not all types of Monads compose well together. Here’s where I’m out of my depth, but I’ve read and I’m told that this is why there are Monad Transformers, so you can fit different domain Monads together.

Hence, some people have started looking at Algebraic Effects, as a way to achieve the same compositional powers of monads, but in a different way. Most descriptions of Algebraic Effects actually ignore the `algebraic` part, because describing `effects` is already a big leap.

The effects part, is often explained as “resumable exceptions”. I wrote a short description of what algebraic effects are from that perspective, so I won’t expound on that here.

Elm should have had Algebraic Effects

If Elm had Algebraic Effects, it would have made it more adaptable to these multi-message processing.

But the algebraic part of algebraic effects is that the effects that you raise as a “resumable exception” can be composed together! Not just in any way: design them so when composed, they have *guaranteed properties* just like the stuff you saw above!

For example, if we had a key/value store that we interface with using get and put, we could express what we expect to happen through some algebraic properties.

1. Idempotence of consecutive reads (get-get): get k; get k ≡ get x

This says, two consecutive gets is functionally equivalent to a single get. This guarantees that get is a pure observation: it doesn’t consume or advance anything. If this law didn’t hold, reading could “drain” or “advance” some hidden cursor. By making it a law, we make it an explicit behavior for our users, so they’re not surprised by bugs down the line when their assumptions veer from this property.

2. Last write wins (put-put): put k v1; put k v2 ≡ put k v2

Easy. The two puts together is the functional equivalent of only executing the last one. Hence, the last put is the value that’s currently sitting in key k. This encodes overwriting semantics, and without it, put might append, merge, or accumulate. It wouldn’t be what users would expect.

3. Read after write (put-get): put k v; get k ≡ put k v; return v

Executing a put and then an immediate get is the functional equivalent of just executing the put, but then just returning the value v you already have in hand, instead of executing get. This is important to guarantee the consistency of reads right after writes. Without this, you could write v and then not see v immediately, which would break the intuitive model of state in a key/value store.

4. Write back same value (get-put): get k >>= (λv. put k v) ≡ return ()

If you read the value of a key and then immediately write it back unchanged, that’s functionally equivalent of doing nothing (returning unit).

5. Independence across keys For k1 ≠ k2:

put k1 v1; put k2 v2  ≡  put k2 v2; put k1 v1
get k1; get k2        ≡  get k2; get k1
put k1 v; get k2      ≡  get k2; put k1 v

Operations on different keys commute, and the store treats each key as an independent cell. This is what makes it a key/value store, rather than some entangled data structure.

Hence, just because you are writing effects, doesn’t automatically mean they’re algebraic. You have to consciously design them to be so, in order to give properties or guarantees that you want your users to have. Most current programming languages have no way of enforcing these equational axioms, so even esoteric languages that feature algebraic effects don’t even try to enforce them.

Languages which feature dependent types, such as Coq, Agda, Idris 2, and Lean are the only languages that can encode these equational axioms explicitly and be able to prove their veracity. Typically, these languages are used by mathematicians to do proofs in math. But interestingly, Lean has been getting a lot of momentum, and it can compile to C. It can be a practical in-road to using these in practice.

And, in my own words, that’s what’s algebraic about algebraic effects.

Epilogue

Alan Kay was known to lament that 1 million lines in a code base is unconscionable. It’s no more a skyscraper than a pile of rocks. That’s because there’s often no structure. Eventually we figured out arches: they’re structure that give strength with less material.

Hence, we can build higher without using more material. By analogy, we’re starting to discover what this structure looks like in software. And it looks like math. There’s a lot of resistance to this, and will be for a long time.

And maybe with LLMs, it might not matter for a wide swath of applications. But still, there’s ever progress moving forward in this direction, where these pure functional programming or math-y ideas filter down to more mainstream languages.

Keep your files stored safely and securely with the SanDisk 2TB Extreme Portable SSD. With over 69,505 ratings and an impressive 4.6 out of 5 stars, this product has been purchased over 8K+ times in the past month. At only $129.99, this Amazon’s Choice product is a must-have for secure file storage.

Help keep private content private with the included password protection featuring 256-bit AES hardware encryption. Order now for just $129.99 on Amazon!

Help Power Techcratic’s Future – Scan To Support

If Techcratic’s content and insights have helped you, consider giving back by supporting the platform with crypto. Every contribution makes a difference, whether it’s for high-quality content, server maintenance, or future updates. Techcratic is constantly evolving, and your support helps drive that progress.

As a solo operator who wears all the hats, creating content, managing the tech, and running the site, your support allows me to stay focused on delivering valuable resources. Your support keeps everything running smoothly and enables me to continue creating the content you love. I’m deeply grateful for your support, it truly means the world to me! Thank you!