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);
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;
function append(a, b){}
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.
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.
class Sum {
constructor(number) {
this.value = number;
}
static empty() {
return new Sum(0);
}
concat(other) {
return new Sum(this.value + other.value);
}
}
new Sum(5).concat(new Sum(2)).value;
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.
import parse from "shift-parser";
import reduce, {MonoidalReducer} from "shift-reducer";
class Sum() {
constructor(number) {
this.value = number;
}
static empty() {
return new Sum(0);
}
concat(other) {
return new Sum(this.value + other.value);
}
}
class IdentifierCounter extends MonoidalReducer {
constructor() {
super(Sum)
}
static count(program) {
return reduce(new this, program).value;
}
reduceIdentifierExpression(node) {
return new Sum(1);
}
}
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 theMonoidalReducer: 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 theenforceFreeReturnStatementErrors 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.
Like this:
Like Loading...
