## What is a Reducer?

A reducer is an actor that takes something large and turns it into something smaller. In programming it is a construct that recursively applies a function over a data structure in order to produce a single value.

In JavaScript, you could reduce an array of integers to a single sum with the following code.

```
var integers = [1, 2, 3, 4, 5, 6];
var sum = integers.reduce(function(memo, next){ return memo + next; }, 0);
// sum === 21
```

## Shift Reducer

Shape Security has provided a reducer to use in building tooling for the Shift format AST. The reducer folds a Shift format AST into a summary value, much like `Array.prototype.reduce`

folds an array. Of course, reducing an array is much less complex than reducing an AST. Only one function is required to reduce an array, while reducing an AST requires one function for each different type of node.

Shape’s reducer library exposes a single function that runs the reduction, and two base structures that are meant to be extended with your own reducing behaviors: `Reducer`

and `MonoidalReducer`

.

## Reducer

Use `Reducer`

when the reduction requires unique behavior for each different type of node. It is a clean slate. Extending `Reducer`

requires every single reduction method (`reduceXXX`

) to be overridden. Code generation or AST serialisation are examples of when it is appropriate to base your reducer on `Reducer`

.

## MonoidalReducer

The majority of Shift implementations will benefit from basing their reducer off of `MonoidalReducer`

. Extending `MonoidalReducer`

requires that the summary value that each reduction method returns is a *Monoid*. Its default implementations of the reduction methods take advantage of the monoidal structure of your summary value so that only the reduction methods for the pertinent nodes need to be overridden by you. For all others, the Monoid’s identity will be used.

That may have been a lot to take in. Don’t worry if you’re not familiar with the terminology! As a programmer, you likely run into Monoids *every single day*, but the term can cause confusion. Let’s see if we can clear up the term a little bit.

### Monoids

A monoid is structure that relates the elements in a set with a closed, associative, binary operation that we will call `append`

, coupled with one special element in that set that we will call the `identity`

element.

Let’s break monoids down a little further.

#### What is a binary operation?

A binary operation is an operation that operates on two inputs.

```
0 + 1; // + is a binary operator
function append(a, b){} // append is a binary function
```

#### What is a closed operation?

An operation is closed if performing the operation on members of a set always produces a member of the same set.

#### What is associativity?

We learned the concept of associativity back in elementary school and it is core to our understanding of algebraic operations. Associativity, as the name implies, means that *grouping* of operations does not affect the result.

```
(a + b) + c === a + (b + c)
```

Remember, associativity is not commutativity. That would mean that the *order* of the values given to the operation does not affect the result.

```
a + b + c === c + b + a
```

#### What is an identity?

An identity is a value for a specific operation that when passed to an operator with any other value returns the other value. You may remember this via the additive identity, `0`

, or the multiplicative identity, `1`

.

```
x + 0 === x;
0 + x === x;
x * 1 === x;
1 * x === x;
append(x, identity) === x;
append(identity, x) === x;
```

#### Putting it all together

Using the above examples we could write out the Sum Monoid in arithmetic expressions.

```
sumIdentity = 0
sumAppend(x, y) = x + y
```

Or we could write the Sum Monoid JavaScript implementation. For this, we will use the conventional Fantasy Land names, `empty`

and `concat`

.

```
//es6
class Sum {
constructor(number) {
this.value = number;
}
// always return the identity element
static empty() {
return new Sum(0);
}
// the binary operation acts on its `this` value and its parameter
concat(other) {
return new Sum(this.value + other.value);
}
}
new Sum(5).concat(new Sum(2)).value; // 7
```

## Walkthrough: Making something with the MonoidalReducer

Now that we understand monoids, let’s walk through making a small program with the Shift `MonoidalReducer`

that counts how many identifiers are in a program.

### Setup

Install dependencies.

```
$ npm install --save shift-reducer shift-parser 6to5
```

### Making an Identifier counter

First we need to flesh out our basic program.

```
//es6
import parse from "shift-parser";
import reduce, {MonoidalReducer} from "shift-reducer";
// a monoid over integers and addition
class Sum() {
constructor(number) {
this.value = number;
}
// by default reduce any node to the identity, zero
static empty() {
return new Sum(0);
}
// combine Sum instances by summing their values
concat(other) {
return new Sum(this.value + other.value);
}
}
class IdentifierCounter extends MonoidalReducer {
constructor() {
// let MonoidalReducer know that we're going to use Sum as our monoid
super(Sum)
}
// a convenience function for performing the reduction and extracting a result
static count(program) {
return reduce(new this, program).value;
}
// add 1 to the count for each IdentifierExpression node
reduceIdentifierExpression(node) {
return new Sum(1);
}
/*
In this case, the only node we care about overriding is the
IdentifierExpression node; the rest can be reduced using the default
methods from MonoidalReducer.
*/
}
// test program code
var program = "function f() { hello(world); }";
console.dir(IdentifierCounter.count(parse(program)));
```

Run it!

```
$ node_modules/.bin/6to5-node count-identifiers.js
```

### Wrapping Up

Let’s walk through what’s been done. We’ve created a new Reducer by extending the `MonoidalReducer`

, overridden the necessary reduction methods (in this case only `reduceIdentifierExpression`

), and parsed and run our new reducer over a program.

We wrote this example in ES6 because we believe it’s clearer. An ES5 version of the identifier counter is available in this gist.

## Taking it Further

At this point, we’ve used a fairly trivial example in order to expose the fundamentals of using the `MonoidalReducer`

. Next, we will look at the design of a more significant project that makes use of the`MonoidalReducer`

: the Shift Validator.

### Shift Validator

The Shift Validator validates a Shift format AST from the bottom up. But how does it do this when many of the restrictions it is enforcing are context sensitive? The `ValidationContext`

object that the Validator uses allows *possible* errors to be registered on it and, if we determine (with new information about the possible error’s context) that the error actually does not apply, it can clear possible errors as well. Only when we are certain an error will not be cleared do we move it from its temporary error list to the official `errors`

list in the `ValidationContext`

object. Let’s look at a concrete example:

When the Validator reduces a `ReturnStatement`

, we call the `addFreeReturnStatement`

helper method of our `ValidationContext`

state object, giving it an error that this `ReturnStatement`

must be contained within a function (top-level return is illegal in JavaScript). We don’t know whether this `ReturnStatement`

is actually in an illegal position, but we assume it is until we better understand its context. In the reduction methods for `FunctionDeclaration`

, `FunctionExpression`

, `Getter`

, and `Setter`

nodes, we then call the `clearFreeReturnStatements`

helper method of our `ValidationContext`

state object clearing out all of the `ReturnStatement`

errors we collected while reducing `ReturnStatement`

nodes below us in the AST. Finally, when we reduce a `Script`

node (the head of the AST), we move the `ReturnStatement`

errors from their temporary holding list to the confirmed errors list using the`enforceFreeReturnStatementErrors`

helper method. We do this at this point because we know we won’t be reducing any more functions that will cancel out a `ReturnStatement`

error.

## Final Round Up

To pull it all together, we’ve gone over the Shift `Reducer`

and `MonoidalReducer`

. Both can be used to build tooling based on the Shift AST. We’ve gone over the fundamentals behind the `MonoidalReducer`

and explored both a simple `MonoidalReducer`

example, as well as a more complex example, the Shift Validator. Hopefully, now you feel comfortable building your own tools based on Shift’s AST.