Functional Side effects with Applicatives, Part 3

Adding effects and composing applicatives

This is the final part of a three-part series on effectful programming with applicative functors. In the last two posts we’ve covered what computational effects are, and how we can use them in conjunction with applicative functors to capture side effects in functional code. In part one we did this to implement composable parsers; in part two we implemented a general applicative representing the effect of reading from an environment and used this to implement an evaluator for an AST representing arithmetic expressions. (If you have not read these posts, I recommend doing so before continuing with this one.)

In this post we’ll expand upon the example from part two, adding support for writing state as well as reading it. We’ll also see how applicative composition gives us an easy way to make our solution handle failures gracefully. Finally we’ll inspect our completed solution, see how its component pieces typify the building blocks involved in effectful applicative programming, and learn how the mathematical notion of “parametricity” gives us confidence that an applicative solution enforces a strong separation of concerns.

Modifying state

Now that our evaluate function supports variables, let’s go a step farther and add the ability to change the value of variables within some scope. This will allow us to evaluate expressions like (let x 1 (+ x 2)), which assigns the value 1 to x and evaluates to 3. As before, we’ll add a new data type to our Expr type:

type Expr
  = Num
  | Plus
  | Times
  | Var
  | Let
  ;
class Let {
  name: string;
  value: number;
  scope: Expr;
  constructor(name: string, value: number, scope: Expr) {
    this.name = name;
    this.value = value;
    this.scope = scope;
  }
}

Adding the support for Let to our evaluate function is as simple as it was for Var: we just add another entry to the conditional. In this case, we’ll offload the logic to an alias function which we have not yet written:

function evaluate(expr: Expr) : InEnv<string, number, number> {
  return expr instanceof Num ? 
    pure(expr.value)
  : expr instanceof Plus ?
    plus(evaluate(expr.left), evaluate(expr.right))
  : expr instanceof Times ?
    times(evaluate(expr.left), evaluate(expr.right))
  : expr instanceof Var ?
    fetch(expr)
  : /* expr is a Let */
    alias(expr.name, expr.value, evaluate(expr.scope));
  }

Note that inside the Let case we recursively evaluate the scope contained by the let block, and then pass the results of that evaluation into alias. If we had implemented evaluate by manually threading the environment through (as we did in our naive implementation in the last section) then we would have needed to modify the environment first, and then pass the modified environment into evaluate. The approach we’re using here can be thought of as “evaluate the inner scope, getting back a value in an InEnv context, and then add the effect of a state change to that context.” In order to model a changing state, alias will return a function which takes an environment, modifies that environment, and then passes that environment into the InEnv function which alias wraps. As usual, we will accomplish this modification by copying the input and modifying the copy:

function alias<X, Y, A>(
  name: X, 
  value: Y, 
  contents: InEnv<X, Y, A>) : InEnv<X, Y, A> {
  return env => {
    const newEnvContents = new Map(env.contents);
    newEnvContents.set(name, value);
    return contents(new Env(newEnvContents));
  };
}

With that, we can see our solution in action:

const env = new Env(new Map([
  ["foo", 2],
  ["bar", 3]
]));
// (+ foo (let bar 5 (+ 1 (* 4 bar))))
const expr = new Plus(
  new Var("foo"),
  new Let(
    "bar", 5,
    new Plus(
      new Num(1),
      new Times(
        new Num(4),
        new Var("bar")))));
console.log(evaluate(expr)(env)); // 23

More effects are possible with our Env type. As an exercise, consider trying to extend the sample code for this post with a Copy type, which works like Let but copies the current value of one variable to another.

Dealing with failure by composing different applicatives

Remember this?

if (!env.contents.has(name))
  throw new Error("Referenced an undefined variable!");

That’s bad.

In cases where a computation can fail, rather than perform a side effect like throwing an exception in the case of failure, we can use an additional applicative context which allows us to express failure as an effect. Fortunately we already have something which will let us do this: Maybe.

We’ll do this by saying that any computation in the InEnv applicative might fail. This is easy to express with a slight change to our types:

type InEnv<X, Y, A> = Env<X, Y> => A;

turns into

type InMaybeEnv<X, Y, A> = InEnv<X, Y, Maybe<A>>;

In my first post on applicatives I mentioned that the composition of applicatives is always applicative. If we have applicatives F<A> and G<A>, then we can mechanically produce the map, ap, and pure functions for F<G<A>>:

type FG<A> = F<G<A>>
function mapFG<A, B>(fn: A => B, a: FG<A>) : FG<B> {
  return mapF(x => mapG(fn, x), a);
}
function pureFG<A>(a: A) : FG<A> {
  return pureF(pureG(a));
}
function ap<A, B>(fn: FG<A => B>, a: FG<A>) : FG<B> {
  return liftA2F(curry2(apG))(fn, a)
}

In our case we can import the map, ap, and pure functions of each applicative as the objects inEnv and maybe, and make our new composed type an applicative like so:

function map<X, Y, A, B>(
  fn: A => B,
  a: InMaybeEnv<X, Y, A>) : InMaybeEnv<X, Y, B> {
  return inEnv.map(x => maybe.map(fn, x), a);
}
function pure<X, Y, A>(a: A) : InMaybeEnv<X, Y, A> {
  return inEnv.pure(maybe.pure(a));
}
function ap<X, Y, A, B>(
  fn: InMaybeEnv<X, Y, A => B>,
  a: InMaybeEnv<X, Y, A>) : InMaybeEnv<X, Y, B> {
  return inEnv.liftA2(curry2(maybe.ap))(fn, a)
}

(Again, we only have to define these by hand because of limits in Flow’s type system. With the right workarounds, we can write a composeA function which takes inEnv and maybe as arguments, and returns an object containing the map, ap and pure defined for the InMaybeEnv type.)

Now that we’re in the Maybe applicative, fetch can be modified to succeed or fail accordingly:

function fetch<X, Y>(name: X) : InMaybeEnv<X, Y, Y> {
  return env => env.contents.has(name) ?
    new Just((env.contents.get(name) : any)) :
    null;
}

Any time we change the structure of an applicative we need to check each of the functions which touch that applicative’s internal structure for breakage. We’ve updated of and fetch, but in this case alias will still work for our nested case without modification.

The applicative context separates our specific application logic from the general effect logic, so no changes are needed to evaluate other than updating its type signature:

function evaluate(expr: Expr) : InMaybeEnv<string, number, number> {
  return expr instanceof Num ? 
    pure(expr.value)
  : expr instanceof Plus ?
    plus(evaluate(expr.left), evaluate(expr.right))
  : expr instanceof Times ?
    times(evaluate(expr.left), evaluate(expr.right))
  : expr instanceof Var ?
    fetch(expr)
  : /* expr is a Let */
    alias(expr.name, expr.value, evaluate(expr.scope));
  }

Because plus and times are defined in terms of liftA2, which is defined in terms of map and ap, our code which combines InMaybeExprs will respond appropriately to the Maybe applicative’s affects, and will cause the whole computation to fail if a failure occurs in any piece of it:

const env = new Env(new Map());
// (+ 1 (* foo 2))
const expr = new Plus(
  new Num(1),
  new Times(
    new Var("foo"),
    new Num(2)))
console.log(evaluate(expr2)(env2)); // null

Much better than throwing an error, and with a minimum of additional code needed.

What have applicatives given us?

Now that we have a complete solution, it’s worth taking a step back and looking at how the characteristics of our code are determined by the choice of an applicative approach.

Our evaluate function has five cases, which fall into two distinct groups:

1. The Plus and Times cases. These functions called in these cases are produced by using liftA on functions which combine plain values, producing functions which combine values inside of applicative contexts.
2. The Num, Var, and Let cases. These cases create applicatives by calling special functions defined for the InEnv or InMaybeEnv applicative. The Var case calls fetch, which provides the effect of reading state, and the Let case calls alias, which provides the effect of modifying state. The Num case calls pure, which produces a value and the “empty” effect.

These are the building blocks of applicative code. The InEnv and InMaybEnv functors provides a context which effects can exist in, and functions which operate on the internal structure of these functors create effects. To know what effects are present or possible within a given functor, we only need to look at what effect-creating functions are available. To do useful things with the values inside our effectful context, we use liftA to lift functions on the wrapped types into our context. The “magic” of applicatives is that no matter what effects are provided by our effect-creating functions, our lifted functions will be able to compose these effects. (So long as our map, ap, and pure implementations follow the functor laws.)

An important part of the effect-creating functions is that they are completely general, and are decoupled from the concerns of evaluating expressions or anything else regarding our present solution. We can see verify this by looking at their signatures:

pure<X, Y, A>(A) : InMaybeEnv<X, Y, A>
fetch<X, Y>(X) : InMaybeEnv<X, Y, Y>
alias<X, Y, A>(X, Y, InMaybeEnv<X, Y, A>) : InMaybeEnv<X, Y, A>

Because no concrete types appear in these function’s signatures, their logic can’t possibly be coupled to any concrete type. In functional programming, this concept is known as “parametricity”: the guarantee that a function whose types are all type parameters (generics) will behave the same when given arguments of any type. When I commented in the last post that there was only one implementation of map, ap, and pure on InEnv which would type check, parametricity was the reason why. There’s only one way that these functions can behave if they’re going to work across all types that they may be given, and the type checker enforces this.

The value of parametricity shouldn’t be underestimated. “Separation of concerns” is considered an important attribute of good software across languages, environments and paradigms, but an exact definition of what constitutes a proper separation of concerns can be hard to pin down. Usually it’s said to mean that “a software component should only have one reason to change”, but this is an incredibly wiggly definition. Looking at a component and asking why it might need to change is largely an exercise of imagination, and decisions about which imagined reasons are worth preemptively guarding against and which aren’t tend to rest on heuristics and gut feelings. When you’re dealing with generic functions, though, you get a rock solid guarantee: a generic function’s concerns cannot possibly be coupled to the concerns of whatever concrete type will eventually be passed to it.

When representing effects using applicatives, this has important implications for our architecture. We’ve separated our logic of how to deal with interpreting an expression (by turning expressions into values and effects) from our logic specifying how to implement a given effect (by reading and writing values in a Map). And importantly, when we look at the system with parametricity in mind, our type system proves that these concerns are indeed separate.

For a less mathematical intuition about this, we can just compare our final code (supporting Var and Let) to our initial, effect-free code. The code looks the same — no extra values threaded through, no new closures or mutable state. By moving ourselves into an applicative context, we’ve gained the ability to work with effects by just applying functions to values, the same way we work with pure, effect-less data. We also know that we’re decoupled because when we changed our InEnv applicative by composing it with the Maybe applicative, the evaluate function which was written in terms of InEnv didn’t need to change; our changes were limited to the effect-creating functions which operated on InEnv's internal structure.

This concludes our present tour through applicative functors. It’s been a long and dense journey, so here is a summary of the major points that we’ve seen so far:

• Functors provide a context which can hold values, and a map function to apply normal functions to functions in values. map can be curried in order to lift single-argument functions on plain values into functions on values in contexts.
• Applicative functors add additional functions and constraints to functors. An applicative gives us a pure function which can lift a value of any type into a functor, and an ap function which lets us apply functions in a context to values in a context.
• Using ap and map, we can define liftA, which lifts multi-argument functions on plain values into functions on values in context.
• The implementations of map, ap, and pure must follow certain laws. These laws ensure that the things we build on top of applicatives will compose in expected ways.
• Purely functional computations return values. Sometimes, though, a computation may return a value plus something extra. This extra thing is called a “computational effect”. We can create data structures which represent these effects.
• In software, “side effects” are the reading or modification of state in a context which is outside of our current software component. If we can encapsulate this state inside of a component, and represent modifications to it immutably, then we can turn the side effect into a well-behaved computational effect.
• When we encapsulate a computational effect inside an applicative functor, then functions lifted with liftA will compose these effects automatically.
• To do effectful applicative programming, we write effect-creating functions, which return an instance of an applicative containing the effect we want. Our effectful code works with the output of these functions, and never touches the internal structure of our applicative context directly.
• The concept of “parametricity” tells us that generic functions are guaranteed to be decoupled from concrete types. Because all of our effect-creating functions are generic, this gives us a mathematical guarantee that we’ve separated our concerns around implementing effects from our concerns around using them.
• Because the composition of applicatives is itself an applicative, we can compose applicatives to add additional effects. When doing so we may need to change our effect-creating functions, but our code that’s written in terms of an applicative will remain unchanged.

The concept of applicative functors can be both deep and subtle, but is an invaluable tool in any functional programmer’s toolbox. Using them allows for the creation of expressive, purely functional code capable of handling cases which are most idiomatically associated with imperative programming. When you find yourself reaching for a side effect, consider how that effect might be expressed as an applicative. You may find your code much more modular and composable as a result.

All code samples from this post may be found here.

As powerful as applicative functors are, there are some cases which they cannot adequately express. In a future post I’ll show some of these cases, and demonstrate how they lead us to a oft-mentioned subtype of applicatives, the monad. You can find all of my posts on algebraic structures here.

Thanks to Lizz Katsnelson for editing this post.