Functional Side effects with Applicatives, Part 2
Modeling the reading of state
--
This is part two of a three-part series on effectful programming with applicative functors. In part one we saw that many imperative side effects can be encapsulated into well-behaved computational effects by modeling the side effect as a modification to state within a given context and then making this context into an applicative functor. We used this to implement a simple applicative parser, which provided the effects of consuming input and potentially failing, and saw that liftA let us compose the effects of parsers in order to easily parse compound data structures. (If you haven’t read part one, I highly recommend doing so before continuing.)
This post will implement a solution to another problem in much the same way that we approached parsing. Our motivating example will be a simple evaluator for lisp-like arithmetic expressions. We’ll work with ASTs (abstract syntax trees, data structures describing the results of parsing a programming language) representing terms like these:
(+ 1 (* 4 2))
(+ foo (* 4 bar))
(+ foo (let bar 5 (+ 1 (* 4 bar))))We’ll start with an implementation of plain arithmetic, and then see how we can use applicatives to extend this implementation to support reading and writing the values of variables within our expressions. We’ll also see some useful patterns for doing typed functional programming in JavaScript along the way.
The base implementation
First, let’s write a beginning implementation which doesn’t support expressions with variables. Here’s a definition of our AST:
type Expr
= Val
| Plus
| Times
;class Num {
value: number;
constructor(value: number) {
this.value = value;
}
}class Plus {
left: Expr;
right: Expr;
constructor(left: Expr, right: Expr) {
this.left = left;
this.right = right;
}
}class Times {
left: Expr;
right: Expr;
constructor(left: Expr, right: Expr) {
this.left = left;
this.right = right;
}
}
We declare Expr as a union type, which can hold three different types of data: a value, an addition, or a multiplication. Each of these types of data is declared as its own class; this will make it easy for us to differentiate them later.
Next we’ll implement a function which evaluates an expression to a number. Our Expr data type is recursive, so the most trivial implementation of a function on it will be too:
const plus = (a, b) => a + b,
times = (a, b) => a * b;function evaluate(expr: Expr) : number {
return expr instanceof Num ?
expr.value : expr instanceof Plus ?
plus(evaluate(expr.left), evaluate(expr.right)) : /* expr is a Times */
times(evaluate(expr.left), evaluate(expr.right));
}
(If you’re not familiar with nested ternary expressions, I’d recommend reading the MDN docs. This was the motivation for representing our data as classes; instanceof gives us an infallible way to distinguish them, and Flow’s type refinements allow our type system to know what concrete type we’re dealing with in each case.)
To use this, we just create an AST corresponding to a given expression and evaluate it:
// corresponds to (+ 1 (* 4 2))
const expr = new Plus(
new Num(1),
new Times(
new Num(4),
new Num(2)));console.log(evaluate(expr)); // 9
Supporting variables by adding an environment
Operating on plain numbers is fine, but we also want to be able to evaluate expressions like (+ foo (* 4 bar)), where “foo” and “bar” are variables in a larger scope. To support this, we need to add a context where names are bound to values. We’ll call this Env:
export class Env<X, Y> {
contents: Map<X, Y>;
constructor(contents: Map<X, Y>) {
this.contents = contents;
}
}We could consume an Env by manually pulling it apart and interacting with its contents field, but this would be a poor separation of concerns. Rather than couple our business logic to the internal structure of Env, we’ll write a helper to fetch the value corresponding to a particular name:
function fetch<X, Y>(name: X, env: Env<X, Y>) : Y {
if (!env.contents.has(name))
throw new Error("Referenced an undefined variable!"); return (env.contents.get(name) : any);
}
There are a couple of alarming things about this function. One is the unsafe typecast, and this has a good explanation: Flow’s type refinements don’t extend to functions like has, so while we know that contents.get will return a value corresponding to a key, Flow thinks that get might return undefined for a missing key. We can’t do an undefined check on the return value of the get, though, because then our function wouldn’t be properly generic: if someone bound the value undefined to the name foo, then fetching "foo" had better return undefined. Thus, an unsafe cast is the least of possible evils here.
The second alarming thing in this function is that it throws an error, a very non-functional way of dealing with failure. We do so for simplicity’s sake, and will remedy this in part three of this series.
We also need to add an AST node for our variable nodes. We’ll call this new type Var, and we’ll add it to our Expr type:
type Expr
= Num
| Plus
| Times
| Var
;class Var {
name: string;
constructor(name: string) {
this.name = name;
}
}
Here’s where the effectful nature of this example comes into play. When we evaluate a node, the value no longer depends solely on that individual node, but also on the state of a larger context (the Env associated with this node.) We could handle this naively by threading the Env through the computation:
function evaluate(expr: Expr, env: Env<string, number>) : number {
return expr instanceof Num ?
expr.value : expr instanceof Plus ?
plus(evaluate(expr.left, env), evaluate(expr.right, env)) : expr instanceof Times ?
times(evaluate(expr.left, env), evaluate(expr.right, env)) : /* expr is a Var */
fetch(expr.name, env);
}
This is very similar to our first parser implementation from part 1. We’ve taken the step of handling a side effect (dependence on values from an outside context) by threading that context’s state through our computation. The downside is that we now have env as an extra argument that has to be passed to each invocation of evaluate, which makes for unsatisfying boilerplate. We’ve also solved the problem for our specific case without saying anything about how to work with computations that depend on an Env in general.
We can do better. We’ll back up and define a general type for computations which depend on an Env. When we want to have a computation depend on a value, the natural way to do this is to pass the value to the computation as a function argument. Thus this will be our type:
type InEnv<X, Y, A> = Env<X, Y> => AAs one might expect for a post on applicatives, InEnv turns out to be an applicative functor. Here is its implementation:
export function map<X, Y, A, B>(
fn: A => B,
a: InEnv<X, Y, A>) : InEnv<X, Y, B> { return env => fn(a(env));
}export function pure<X, Y, A>(a: A) : InEnv<X, Y, A> {
return env => a;
}export function ap<X, Y, A, B>(
fn: InEnv<X, Y, A => B>,
a: InEnv<X, Y, A>) : InEnv<X, Y, B> { return env => fn(env)(a(env));
}
map creates a new InEnv, which passes the environment through to the computation it’s given, and transforms that function’s result with the given function on the way out. pure creates a new InEnv which discards whatever Env its given and returns the selected value. (This gives good background for why pure is named as such; if our applicative represents some kind of effect, pure creates a value which doesn’t make any use of that effect. In the previous post our Parser applicative had the effect of consuming input and possibly failing, and our pure implementation consumed no input and always succeeded. In this case our InEnv applicative provides the effect of dependence on an environment, and pure disregards that effect by ignoring its env argument.) Finally, ap produces a function which takes an Env and uses it to produce a function A => B and an A, and applies the first to the second to get a B.
These functions all have the nice property of only having one possible implementation which typechecks, making implementing them straightforward.
These signatures may seem strange, because in examples so far map and ap have always had two type variables, and pure has always had one. Here they have four and three, and that’s okay. X and Y are simply passed through as part of the signature, and don’t appear in the function body at all. You can imagine them merging into the InEnv type itself, and the signatures here being something like
map(fn: InEnvXY<A => B>, a: InEnvXY<A>) : InEnvXY<B>The key is that, if you can imagine “partially applying” generics, then for any types X and Y, an InEnv<X, Y><A> is an applicative taking one generic argument, just like all of the applicatives we’ve seen so far.
We can also implement liftA on our new applicative in the usual way:
export function liftA2<X, Y, A, B, R>(fn: A => B => R)
: (InEnv<X, Y, A>, InEnv<X, Y, B>) => InEnv<X, Y, R> {
return (a, b) => ap(map(fn, a), b);
}(As I mentioned in my post introducing applicatives, there are ways to derive the implementation of liftA from the implementations of ap and map automatically, but limitations in Flow means that this requires type system tricks which are beyond the scope of these post.)
Now that we have a type and applicative instance for our environment-dependent computations, let’s reimplement evaluation. evaluate takes an Expr and returns a value which depends on an environment, and it specializes the types of the names and values involved to strings and numbers, so it will have the type:
Expr => InEnv<string, number, number>If we expand out the definition of InEnv, we can see that this is the type
Expr => Env<string, number> => numberwhich is the curried form of our naive evalutate function’s signature.
To fill out the implementation of evaluate, we‘ll need a case for each of the types in Expr: Num, Plus, Times and Val. We have what we need for the first three of these:
const plus = liftA2(a => b => a + b),
times = liftA2(a => b => a * b);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 is a Var */
?????????????
}
For the Num case, we have a plain number, and we want a number wrapped in the InEnv functor. pure gives us what we need here.
For Plus and Times, we want to apply a normal function (adding and multiplying numbers) to the results of a recursive invocation of evaluate, which will return a number inside an InEnv context. This is the essential purpose of an applicative functor; we just need to liftA our addition and multiplication functions into the relevant functor.
It’s worth going back and comparing what we have now to our first, variable-less implementation of evaluate. The type signature returns a functor instead of a plain value, the Num case has changed to use pure instead of returning the value directly, and plus and times refer to lifted functions rather than normal ones, but the structure of the Num, Plus and Times cases are otherwise unchanged. This is the essence of applicatives: writing normal code which applies functions to values even though we’re inside an effectful context.
To complete evaluate, we need to handle the Var case. To do this, lets modify our fetch function to match our new signatures:
function fetch<X, Y>(name: X) : InEnv<X, Y, Y> {
return env => {
if (!env.contents.has(name))
throw new Error("Referenced an undefined variable!"); return (env.contents.get(name) : any);
};
}
If we piece apart the type signature of fetch like we did with evaluate, we can see that all we’ve done here is curried our initial fetch function. Now that fetch returns the same type as evaluate, completing our implementation is easy:
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 is a Var */
fetch(expr);
}
We can test this by manually creating and evaluating an expression in an environment:
const env = new Env(new Map([
["foo", 2],
["bar", 3]
]));// corresponds to (+ foo (* 4 bar))
const expr = new Plus(
new Var("foo"),
new Times(
new Num(4),
new Var("bar")));console.log(evaluate(expr)(env)); // 14
Success.
In this post we saw a more realistic example of a case where applicatives can be useful, and walked through the process of refactoring a messy solution using manual state threading into a cleaner applicative one. We started with a pure, effect-free arithmetic evaluator, and added support for the effect of reading state from an environment. Importantly, we did so in a generic and composable way, by implementing a reusable InEnv abstraction and then lifting our arithmetic logic into InEnv’s context. In part three of this series we’ll take this a step further by adding another effect to InEnv which allows the writing of state. This will let us fully implement our arithmetic evaluator by adding a Let node to our AST which modifies state within its scope. We’ll also see how we can add additional effects by composing InEnv with other applicatives, and dig into the common building blocks of effectful applicative solutions.
All code samples from this post may be found here.
This is part of my series on algebraic structures. A list of all posts in the series may be found here.
Thanks to Lizz Katsnelson for editing this post.
