What is an effect? Link to heading
Effects are the parts of computations outside of what is handled by the input/output of a function or construct (class/struct/etc.). Take a function like the following:
def backwards[A, B](a: A, b: B) = (b, a)
This doesn’t have any effects 1, it just takes two arguments and returns a tuple of them backwards.
Now if we look at this function:
public boolean save(User user) {
return db.save(user);
}
There are several effects happening here, and most of them are untyped/untracked
save
is immediately evaluating and executing. This means we can’t easily compose the effect of saving the user, there’s no effect being tracked by the type system that is returned that allows composition with other effects.db.save
could throw an exception (say if the db is not initialized), this is untyped and implicit. While we can make it explicit with atry/catch
, the compiler isn’t going to help us at all in locating where we need to do this 2.db
is in scope despite not being passed into the function. while this is an effect it’s not usually untyped/implicit, rather it’d likely be defined in the enclosing scope explicitly, so not as bad as the other effects. It being an effect means general mechanisms for effect handling should be able to makedb
available through other mechanisms, which we’ll see later in this post.user
ordb
could benull
. This is an implicit, untyped effect in Java. Some languages tracknull
at the type level, and others use more general mechanisms for handling the effect.
Often times these untyped effects are also referred to as “side effects”, as they happen “on the side” of what the function says it’ll do.
This article will cover different ways of tracking these effects at the type level, and we’ll showcase alternatives to the above save
function with typed/tracked effects. We’ll also create a more advanced function, transform
, that:
simultaneously executes these two tasks
- fetch a user by id
- fetch a set of pending changes for the user id
then applies those changes to the user, deletes the existing user and pending changes, and then saves the new user.
For the rest of this post, the save
and transform
examples will have line numbers, while other code snippets will not.
Untyped Effect Wrapping Link to heading
Untyped effects will usually be the most familiar to non-FP programmers, effects are untracked by the type system and exist solely at runtime. The last section went into an example of untyped effects with the public void save
method.
When you consider that an effect is part of a computation that happens outside of the input/output of a function or construct, you might realize that you can wrap or lift these untyped parts into typed parts. We can:
- use
Either[Failure, Success]
to denote possible failures instead of exceptions - have lazy computation with
() -> A
- have suspension with
CompletableFuture
- replace
null
ables withOptional
s - explicitly pass parameters instead of relying on some larger scope
Applying all these ideas transforms our original Java save function into:
|
|
You might imagine this kind of function is where we’re incurring the largest costs, but actually composing several of these is much more problematic. There’s no general mechanism in Java for composition of single effects, nor is the type system expressive enough to allow composition of n effects generically; we have to create a new combinator for every effect combination we want to represent
For this reason, the transform
function is quite tedious compared to later examples:
|
|
Let’s take this piece-by-piece.
First we create a scope
and fork two threads off of it, meaning those two threads will execute concurrently. scope.join
waits for both of them to complete.
try (var scope = new StructuredTaskScope.ShutdownOnFailure()) {
var oldUserThread = scope.fork(() ->
userRepo.fetch(userId).get());
var changesThread = scope.fork(() ->
changeRepo.pendingFor(userId).get());
scope.join();
(...)
we handle the empty case for the oldUserThread:
var userEitherFuture = oldUserThread.get()
.thenApply(eitherOpt -> eitherOpt.flatMap(opt ->
optToEither(opt, new MyError("user missing"))));
and most of the rest of the function is using the bindEff
combinator to compose CompletableFuture<Either<E, S>>
s. bindEff
has an incredibly similar signature to flatMap
, where flatMap is usually of this shape:
def flatMap[F[_], A, B](fa: F[A])(fn: A => F[B])
flatMap being the core computation of Monads, which we’ll get into later. Having the language allow easy sequencing of monads would greatly improve this code.
Despite using the newest Java release at the time of writing (23) with the structured concurrency preview, async programming is still far behind what other languages offer. Instead of simply having a combinator like <&>
(which we will see later), we instead need to create a structured scope, fork each computation, join the scope, and then retrieve the computed result manually afterwards.
Reified Effects Link to heading
Some languages track specific effects, but don’t have a general mechanism for effect handling. This means handling each kind of effect has different syntax/semantics, and composing them is generally impossible (so every effect has to be unwrapped with syntax specific to it).
Some examples:
- Java checked exceptions
- Kotlin
suspend
,null
tracking - Swift
async
/await
,throws
,nil
tracking, arguably state management
Other kinds of effects 3 are left as untyped, because the languages aren’t setup to specifically handle these effects/monads.
We’ll showcase reified effects with Swift, because it leans heavily on these, more-so than most languages in its class.
To start, let’s remake the save
function
|
|
note: at this point, save
is entirely redundant, as we’re not lifting any untyped components into new type wrappers like in the Java
The effects above are typed, without having to engage in as much manual wrapping as the Java:
- we don’t have to handle nulls because the lack of
?
in a type means it’s non-nullable - async allows easy suspension of the computation (semantically similar to Java’s CompletableFuture + Supplier)
throws(MyError)
means the computation could also throw aMyError
instead of return aBool
Similarly, the transform
function is much more clear than the Java
|
|
async let
is a much more clear mechanism for allowing concurrent computations than Java’s structured concurrency,let rN = try await <expr>
flattens the unwrapping in a clear wayguard let v = <expr> else { <expr2> }
allows easy management of anil
able value
Monads Link to heading
Monads are a more generic mechanism for effect handling as it allows libraries or private repositorities to define and handle their own effects on top of or in addition to more widely used ones, though monads of one type do not compose with monads of another type. We’ll get into a way around this, monad transformers, a bit later.
Monad is trivial to define:
trait Monad[F[_]] extends Functor[F]: // Functor provides `map`
def pure[A](a: A): F[A]
def flatMap[A, B](fa: F[A])(fn: A => F[B]): F[B]
syntax is generally provided to allow fa.flatMap(fn)
instead of someMonad.flatMap(fa)(fn)
, though this would also be easy to define yourself:
extension [F[_], A](fa: F[A])
def flatMap[B](fn: A => F[B])(using m: Monad[F]): F[B] =
m.flatMap(fa)(fn)
Some languages lack the ability to express monads, as you need higher kinded types to define the abstraction. If you’re unfamiliar with HKTs, check out my article on them.
We’ll commonly interface with monadic types through for/monad comprehensions, so instead of something like this:
m1.flatMap: a1 =>
m2.flatMap: a2 =>
m3.map: a3 =>
a1 + a2 + a3
we’d instead write:
for
a1 <- m1
a2 <- m2
a3 <- m3
yield a1 + a2 + a3
Now onto the save/transform examples:
|
|
like the Swift, this save
function is entirely redundant now
And our transform function:
|
|
while this code is notably shorter than the Java code, we still see some of the same complexity because monads don’t compose, though we have better combinators (and for comps) for dealing with some of that complexity, which is why this is half the Java’s length.
Also worth note, this is worse than the Swift in a number of ways:
- unwrapping
r1
/r2
/r3
is more complex (requiring first unwrappingIO
then laterEither
). - composition of multiple effects requires combinators to align the types. When we create a value like
newUserEither
, assigning it to a binding requires managing the effects explicitly.
Luckily this lack of composability was known from the inception of monads, and different approaches can be taken to rectify this.
Monad Transformers Link to heading
Monad Transformers 4 are probably the most common solution to the composability problem with monads. A monad transformer takes two monads and combines them into a single monad. So if you take a computation like IO[Either[MyError, A]]
and pass it into EitherT
, you get EitherT[IO, MyError, A]
, meaning flatMap
ing on it will give you an A
instead of Either[MyError, A]
. This vastly simplifies its usage in monad comprehensions/for comps.
Our save/transform examples using the EitherT monad transformer:
|
|
and
|
|
liftF
is a mechanism to convert F[A]
into EitherT[F, Nothing, A]
. Nothing
as the error type allows easy composition with other EitherT
s, as Nothing | A =:= A
. It’s a bottom type with no inhabitants.
EitherT
’s apply
(what’s called with the EitherT(something)
syntax) converts an F[Either[E, A]]
into EitherT[F, E, A]
.
There are other combinators, like fromOption
, fromEither
, etc. that are used to convert various values into EitherT
.
This transform
is extremely similar structurally to the Swift. I’ve used all the same binding names to highlight the similarities, and the expressions do roughly the same thing. For direct comparison:
async let oldUserOptAsync = userRepo.fetch(byId: userId)
async let changesAsync = changeRepo.pendingFor(byId: userId)
guard let oldUser = try await oldUserOptAsync else {
throw MyError(message: "user missing")
}
let changes = try await changesAsync
let newUser = changes.reduce(oldUser) { user, change in change(user) }
let r1 = try await userRepo.delete(byId: userId)
let r2 = try await changeRepo.deletePendingUserChanges(byId: userId)
let r3 = try await userRepo.save(user: newUser)
vs
oldUserOptAsync <- EitherT.liftF(userRepo.fetch(userId).start)
changesAsync <- EitherT.liftF(changeRepo.pendingFor(userId).start)
oldUser <- EitherT(oldUserOptAsync.joinWithNever).flatMap:
EitherT.fromOption(_, MyError("user missing"))
changes <- EitherT(changesAsync.joinWithNever)
newUser = changes.foldLeft(oldUser)((user, change) => change(user))
r1 <- EitherT(userRepo.delete(userId))
r2 <- EitherT(changeRepo.deletePendingUserChanges(userId))
r3 <- EitherT(userRepo.save(newUser))
Algebraic Effects Link to heading
Algebraic effects (AE) are another generic mechanism for effect handling, and don’t require language-level support for each effect encoding. They are much more composable than standalone monads, or even mtl monads. Algebraic effects can be introduced as a language feature 5 or as a library 6 built on top of monads if the language’s type system is expressive enough (Haskell and Scala 3 hit this bar).
We’ll use kyo in Scala to demonstrate AEs. Our save function using kyo:
|
|
Here, save
returns a Boolean
with the tracked effects Async
and Abort[MyError]
.
Abort
is similar to throws
, though Abort[Absent]
is used to represent empty values, and Abort[Nothing]
for panics. All other Abort
s can be viewed as isomorphic to throws(E)
or Either[E, ?]
.
Similar to the Reader
monad, we have an Env
effect that allows us to require a dependency. Env
is a good alternative to DI, as it has compile-time safe resolution of dependencies, and has very lightweight syntax.
For our save function, if we want to require a Database
, we can do it like this:
|
|
with the use of type inference and map
this can be made much shorter:
|
|
Imagine now that we have a cacheIfMissing
function we want to call here, if it’s typed as Boolean < (Async & Env[Redis])
, we could use it like so:
def saveThenMaybeCache(user: User) = for
db <- Env.get[Database]
r1 <- db.save(user)
r2 <- cacheIfMissing(user)
yield r1 && r2
when you check the type of saveThenMaybeCache
, you’ll find it’s:
Boolean < (Async & Abort[MyError] & Env[Database] & Env[Redis])
- multiple computations can require some effect (like
Async
), but it’ll only be required once in the resulting effect type - in the vast majority of cases, sequencing a new computation (like we did with
cacheIfMissing
) will seamlessly add the new effects to the current expression (e.g the for comp) with intersection types (&
). In the above, anEnv[Redis]
is required, so that requirement is propagated up.
Now, finally onto the transform
function in kyo:
|
|
This is the most composable of all the transform
functions presented, for the same reason it’s also the most concise and (I’d argue) the most clear. Some notes about it:
Env.get
provides us with an alternative to dependency injection that is compile-time safe and provided for entirely at the type level. The return type oftransform
is the sum of all the effects used within the function, so unlike something like theReaderT
monad transformer, it doesn’t add extra complexity to other expressions within the function. It’s all the safety of normal dependencies with the convenience of a DI framework.- While we could use
Async.run
/fork
to mimic the Swift’sasync let
and the mtl Scala’sEitherT.liftF(someIO.start)
, we can also make use of theAsync.parallel
/<&>
, which are very similar to the standalone monadic ScalaIO.both
, meaning instead of:
async let aAsync = fetchA(v)
async let bAsync = fetchB(v)
let a = await aAsync
let b = await bAsync
we can:
(a,b) <- fetchA(v) <&> fetchB(v)
though if we prefer we can still structure it the same as the Swift/mtl Scala:
aAsync <- fetchA(v).fork
bAsync <- fetchB(v).fork
a <- aAsync.get
b <- bAsync.get
- since the effects compose, we don’t need a bunch of disparite syntax to manually combine the effects like you do with Swift, nor to pass it into a monad transformer to flatten it like in the mtl Scala. The
r1
/r2
/r3` code showcases this clearly:
r1 <- userRepo.delete(userId)
r2 <- changeRepo.deletePendingUserChanges(userId)
r3 <- userRepo.save(newUser)
vs
let r1 = try await userRepo.delete(byId: userId)
let r2 = try await changeRepo.deletePendingUserChanges(byId: userId)
let r3 = try await userRepo.save(user: newUser)
These are representing the same effects, save’s return type in scala is Boolean < (Async & Abort[MyError])
, while in Swift it’s async throws(MyError) -> Boolean
.
To highlight AE composition, imagine we add an r4 that has the same return type as r3, except we want to represent a missing value (null/nil/none/etc.), and then propagate this missing value upwards. In the Swift we’d end up with:
let r1 = try await userRepo.delete(byId: userId)
let r2 = try await changeRepo.deletePendingUserChanges(byId: userId)
let r3 = try await userRepo.save(user: newUser)
guard let r4 = try await userRepo.someFn(userId) else { return nil }
return r1 && r2 && r3 && r4
In the mtl Scala we’d end up with:
r1 <- EitherT(userRepo.delete(userId))
r2 <- EitherT(changeRepo.deletePendingUserChanges(userId))
r3 <- EitherT(userRepo.save(newUser))
r4Opt <- EitherT(userRepo.someFn(userId))
yield r4Opt.map(r4 => r1 && r2 && r3 && r4)
while in the kyo Scala, we’d still just have:
r1 <- userRepo.delete(userId)
r2 <- changeRepo.deletePendingUserChanges(userId)
r3 <- userRepo.save(newUser)
r4 <- userRepo.someFn(userId)
yield r1 && r2 && r3 && r4
The effect is seamlessly combined with the other effects in the for comp.
if we didn’t want to propagate the same value, we’d instead recover
or use a similar combinator (which we actually did in the transform
function with the inner fetchUser
function).
The Future of Effects Link to heading
I’d wager most people who are convinced of the benefits of typing in general see the value in tracking effects. While a lot of langauges take the approach of adding effect tracking to the language directly, this is quite limiting.
Not only do we have effects now that can be represented via AE/MTL and rarely are by reified effects 3, but there are future effects that may end up being very important to track safely.
If we take a look at the story of concurrency, we saw a lot of languages in the last half century that did not put concurrent computations at the forefront of language design, which ended up being a problem. It seemed to make sense at the time, most consumer grade computers were single core processors, but eventually multicore processors became the norm in most electronics.
A decent amount of work was required to add concise, safe and capable concurrency to these languages if they couldn’t express monads or AEs.
It’s quite possible that the same story will play out for something like quantum computing. We already see languages with quantum computing at the forefront of language design (Q# from Microsoft for example), but languages like Haskell and Scala already have expressive enough type systems that quantum computations can be tracked as a monad or AE (QIO lib in Haskell).
If we see wide consumer usage of QPUs, it’s likely languages that lack the expressive power to track effects generally will have trouble handling quantum computations, much like languages that lacked concurrency effect tracking fell into “callback hell”.
Further Reading Link to heading
If you want more code comparisons showcasing the different ways to track effects mentioned above, I have a page for that.
if a/b are pure ↩︎
unless checked exceptions are used, but this is generally seen as bad practice in Java because of how poor the ergonomics of exceptions are ↩︎
effects that are rarely tracked by reified effects: Logging, caching/memoization, dependency management (alternative to DI frameworks), resource management (alternative to try/catch/finally or language constructs like
with
in Python), etc. Check out kyo’s core effects for some more examples if you’re interested. ↩︎ ↩︎often referred to as mtl style or just mtl, short for Monad Transformer Library ↩︎
see Unison, Eff, or Effekt for examples of languages built from the start with algebraic effects in mind. ↩︎