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> => A
As 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> => number
which 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.