#### Wednesday, February 11, 2015

# Reducing with the Shift Reducer

## 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.