Shift Semantics

A few months ago, Shape released Shift Semantics, the newest tool in the Shift family of ECMAScript tooling.

The Shift Semantics library defines a structure for representing the behaviour of an ECMAScript program as well as a function for deriving one of these structures from a Shift AST.


While ECMAScript has many syntactic features, not every one of them maps to a unique behaviour. For instance, all static member accesses (a.b) can be represented in terms of computed member accesses on strings (a['b']), and all for loops can be written in terms of while loops. Shift Semantics defines a data structure called an abstract semantic graph (ASG) which has a node for each individual operation that an ECMAScript interpreter would need to be able to interpret all ECMAScript programs. When an ASG is created, information about the original syntactic representation is lost. Only the important bit about what that program is supposed to do remains.

Why is this useful?

Many use cases for ECMAScript tooling do not involve knowledge of the original representation of the program. For instance, if one is compiling an ECMAScript program to another lower-level language, it is convenient to define a compilation once for all loops instead of repeating much of the same code for each looping construct in the language. This greatly reduces the number of structures you have to consider for your transformation/analysis and eliminates any need for code duplication.

What does it look like?

There are 52 ASG nodes. Many of them have an obvious meaning: Loop, MemberAccess, GlobalReference, LiteralNumber, etc. Others are not as obvious. Keys is an Object.keys analogue, used to represent the for-in behaviour of retrieiving enumerable keys of an object before looping over them. RequireObjectCoercible represents the internal spec operation of the same name. Halt explicitly indicates that the program has run to completion, though it’s also allowed to be used in other places within the graph if one desires.

Update: If you’d like to see GraphViz visualisations, see the examples in Pull Request #8 or run the visualiser yourself on a program of your choosing.

How do I use it?

If you don’t already have a Shift AST for your program, you will need to use the parser to create one:

import com.shapesecurity.shift.parser.Parser;

String js = "f(0);";

// if you have a script
Script script = Parser.parseScript(js);
// if you have a module
Module module = Parser.parseModule(js);

Once you have your Shift AST, pass it to the Explicator:

import com.shapesecurity.shift.semantics.Explicator;

Semantics semantics = Explicator.deriveSemantics(program);

The Semantics object’s fields, including the ASG, can be accessed directly. One can also define a reducer, in the same way a reducer is defined over a Shift AST: subclassing the ReconstructingReducer. Note that our ASG reducers have not yet been open-sourced, but will be soon.


Currently, WithStatements and direct calls to eval are explicated into Halt nodes. There’s no reason that these cannot be supported, but they were not part of the initial effort. Similarly, not all of ECMAScript 2015 and beyond is supported. We will be adding support for newer ECMAScript features piece by piece as development continues.


Thanks to Shape engineer Kevin Gibbons for figuring out all the hard problems during the design of the ASG.

Announcing Bandolier

Today Shape Security is releasing Bandolier, a Java library that bundles JavaScript written with ES2015 module syntax.

Bandolier takes JavaScript code like this:

import { b } from './foo.js'
console.log(42 + b);

where the foo module is defined as:

// foo.js
export var b = 100;

and produces a single script without ES2015 module syntax that can run in a JavaScript environment that does not yet support import/export:

(function(global) {
  "use strict";

  function require(file, parentModule) {
    // eliding the definition of require
    // ...

  require.define("1", function(module, exports, __dirname, __filename) {
    var __resolver = require("2", module);
    var b = __resolver["b"];
    console.log(42 + b);
  require.define("2", function(module, exports, __dirname, __filename) {
    var b = 100;
    exports["b"] = b;
  return require("1");
}.call(this, this));

Bandolier is a good example of a non-trivial project built using the Shift AST; Bandolier essentially takes a bunch of Module ASTs that contain import and export declarations and appropriately merges them into a single Script AST.

Bandolier works by first parsing the given JavaScript file into a Module AST using the Shift Java parser. It then transforms the AST by resolving each import declaration’s module specifier (e.g. converting import foo from "some/module" to import foo from "/full/path/to/some/module"). Once all the imports are resolved, each imported module is recursively loaded and stored in memory.

Finally, the bundled script is created by generating the module loading boilerplate (the function wrapper and the require function) and then each loaded module is transformed by changing import declarations to require calls and export declarations to updates to the exports object.

One particularly useful feature of Bandolier is that both the resolving and loading phases are pluggable. Bandolier comes with a few choices built-in including:

  • a FileSystemResolver that just normalizes relative paths
  • a NodeResolver that follows the node require.resolve algorithm
  • a FileLoader for loading resources from the file system
  • a ClassResourceLoader for loading resources inside a JAR.

Writing your own custom loader or resolver is as simple as implementing the IResolver and IResourceLoader interfaces.

Note that Bandolier is not a full transpiler like babel; it only transforms import and export statements. That said, the Shift parser fully supports ES2015 so you can, for example, use ES2015 classes and the bundled output will work in any JavaScript environment that supports classes (e.g. recent versions of node).

Also note that Bandolier only bundles ES2015 modules so if you need to do something more complex, like bundling CommonJS modules, you will probably be more happy with something like browserify, CommonJS Everywhere, or webpack.

What sets Bandolier apart from similar projects, and why we built it at Shape, is that it allows you to easily integrate JavaScript bundling into a Java application. We use it to dynamically generate and bundle our JavaScript resources on-the-fly inside a Java server. So, if you have similar needs (or are just interested in how to use the Shift AST) check out the project on github.

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.


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.


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.


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.

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.


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";

// 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

  // 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); }";

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.

A Technical Comparison of the Shift and SpiderMonkey AST Formats

Since publishing our announcement of the Shift AST specification, many developers have asked for more details about how the Shift AST format compares to the SpiderMonkey AST format. We should first enumerate what we consider to be the properties of a good AST format.

A good AST format…

  • minimizes the number of inhabitants that do not represent a program.
  • is at least partially homogenous to allow for a simple and efficient visitor.
  • does not impede moving, copying, or replacing subtrees.
  • discourages duplication in code that operates on it.


The following is a list of differences that we consider improvements over the SpiderMonkey AST format.

  • The top-level node returned from any successful parse is named Script, not Program, to ease upgrade to ECMAScript 6. ECMAScript 6 parsers need two modes: one mode that produces a Script and one mode that produces a Module. Modules allow import/export declarations at the top level and are always in strict mode.
  • Functions (including getters/setters) represent their body using a FunctionBody, not a BlockStatement, to support directives and because a function’s body is neither a generic statement position nor a block.
  • Script contains a FunctionBody, not a [Statement], to support top-level directives and for uniform handling of the shared FunctionBody structure.
  • The concepts of BlockStatement and Block have been separated. A BlockStatement contains a Block, not a [Statement]. A Block contains a [Statement]. This is better for transformation: a BlockStatement may be replaced by any other Statement, but a Block must be replaced only by another Block. Block is also used to represent the body and finalizer of a TryFinallyStatement and body of a CatchClause (all of which cannot be arbitrary statements).
  • Similarly, the concepts of VariableDeclarationStatement and VariableDeclaration have been separated. A VariableDeclaration is used within for and for-in statements (both of which cannot contain arbitrary statements in that position).
  • The VariableDeclaration declarators list is required to be non-empty.
  • The concepts of IdentifierExpression and Identifier have been separated. An IdentifierExpression contains an Identifier in expression position. Identifiers are also used for function names, break labels, and static member access property names.
  • MemberExpression has been separated into StaticMemberExpression and ComputedMemberExpression so that the computed flag and the type of property cannot conflict.
  • SwitchStatementWithDefault has been separated out of SwitchStatement to guarantee that a SwitchStatement has no more than one default clause.
  • TryStatement has been separated into TryFinallyStatement (try/catch/finally and try/finally) and TryCatchStatement (try/catch) to disallow a TryStatement with no handler and no finalizer.
  • SequenceExpression and LogicalExpression are just BinaryExpressions. AssignmentExpression remains separate in preparation for ECMAScript 6, where its left operand will need to be a Binding.
  • Separated Literal into LiteralBooleanExpression, LiteralNullExpression, LiteralNumericExpression, LiteralRegExpExpression, and LiteralStringExpression. The SpiderMonkey Literal node is overloaded to the point that it is not used anywhere without qualifying that only a subset of its values may be used.
  • LiteralRegExpExpression is represented by a string, not a RegExp. This allows for JSON serialization and a simpler equivalence definition.
  • Property has been separated into Getter, Setter, and DataProperty, each of which have a PropertyName. PropertyName has a kind (“identifier”, “string”, or “number”) and string value. FunctionExpressions are much too permissive to represent getters/setters, and the Property kind could conflict with the value.
  • Added UseStrictDirective and UnknownDirective nodes to represent directives. These nodes will be replaced with a single Directive node in the future.
  • Removed support for SpiderMonkey-specific language extensions (expression closures, multiple catch clauses, for-each-in, etc.) other than block-scoped declarations.

Insignificant Differences

The following is a list of differences that we believe are insignificant improvements over the SpiderMonkey AST format.

  • SourceLocation format. Source position information was not originally part of the Shift specification because it was not important for any of Shape Security’s usages. Support for source position tracking was only recently added with this experimental interface. If a use case for tracking end position without source content is identified, that information may be added to SourceLocation.
  • Names. We tried to be internally consistent with names like binding, value, and body. We made no effort to carry over SpiderMonkey naming conventions.
  • UpdateExpression and UnaryExpression are replaced by PrefixExpression and PostfixExpression. Ignoring the fact that the prefix flag on SpiderMonkey’s UnaryExpression is unnecessary, there are pros and cons to each way this set of operations is grouped. For example, during scope analysis, it is easier to group the increment/decrement operators together to generate write references, but during code generation it is easier to group the prefix/postfix operators separately.

Deviations From ECMAScript 5

The following is a list of intentional supported extensions to ECMAScript 5.

  • VariableDeclarationKind contains let and const, which should only be allowed in ECMAScript 6, but popular implementations had widespread support for these declaration kinds long before they had support for any other ECMAScript 6 feature. Because of this, many people consider them to be an unofficial extension to ECMAScript 5.
  • Similarly, FunctionDeclarations in arbitrary Statement position were allowed by many ECMAScript 5 implementations (with varying semantics), so the Declaration interface was removed, and FunctionDeclaration was moved to Statement.

Remaining Problems

The following is a list of restrictions that must be checked in addition to the structural correctness to ensure that a Shift AST represents an ECMAScript program. Ideally, this list would be as small as possible, but because of the context sensitivity inherent in the design of the ECMAScript language, these additional restrictions are either impossible or infeasible to enforce in the AST structure. The reason we want this list to be small is because each program that operates on a Shift format AST needs to either be aware of all of these restrictions and handle them gracefully or require consumers to guarantee that the input AST is valid.

Luckily for developers, at the time of the initial Shift specification announcement we made available the Shift validator, which both validates and enumerates validation errors for a given Shift format AST. This makes it very easy to ensure that a Shift format AST does not include any of the below listed problems, as well as debugging problems when they are detected.

  • BreakStatement without a label must be nested within an IterationStatement, SwitchCase, or SwitchDefault. BreakStatement with a label must be nested within a LabeledStatement with an equivalent label (without crossing a function boundary).
  • ContinueStatement without a label must be nested within an IterationStatement. ContinueStatement with a label must be nested within an IterationStatement that is labeled with an equivalent label (without crossing a function boundary).
  • LiteralRegExpExpression value must represent a valid RegExp.
  • Identifier name must always be an IdentifierName, and must not be a reserved word in any position other than a StaticMemberExpression property.
  • An IfStatement with alternate must not have another IfStatement without alternate nested within its consequent in a way that does not represent a valid program. See isProblematicIfStatement in estools/esutils for more details.
  • LabeledStatement must not be nested within a LabeledStatement with the same label name.
  • LiteralNumericExpression value must be non-negative, finite, and non-NaN.
  • ObjectExpression cannot contain data/getter or data/setter properties with the same name.
  • ObjectExpression cannot contain more than one data property with the name `__proto__`.
  • A PropertyName with kind of “number” can have a non-numeric value, and a PropertyName with a kind of “identifier” can have a non-IdentifierName value. It is possible this may one day be fixed.
  • ReturnStatement must be nested within a FunctionExpression, FunctionDeclaration, Getter, or Setter.
  • VariableDeclaration as ForInStatement left must have exactly one declarator. This can (and likely will) be fixed.
  • In strict mode (in other words, nested within a FunctionBody that has a UseStrictDirective), function names, function parameters, catch bindings, setter parameters, prefix/postfix increment/decrement operands, assignment bindings, and variable declaration bindings must not be restricted words (arguments or eval).
  • In strict mode, function parameters must be unique within their containing parameter list.
  • In strict mode, Identifier name must not be a future reserved word in expression position.
  • In strict mode, a PrefixExpression must not have both a delete operator and an Identifier operand.
  • In strict mode, WithStatement is disallowed.

Hopefully this has cleared up the questions you had about the Shift AST. If you think of anything we haven’t, or if you have additional questions, leave a comment below so that others may benefit from the discussion.

Edit: A previous version of this post did not distinguish BreakStatement/ContinueStatement nodes with a label from those without.

Announcing the Shift JavaScript AST Specification

In time for the holidays, we are happy to release Shape Security’s first open source contributions: a new JavaScript AST specification named Shift, and a suite of tools to help you get started working with it.

What is an AST?

An Abstract Syntax Tree is simply a tree representation of a program’s source code. The nodes in an AST represent individual aspects of the language such as identifiers, statements, and literals. This structure is commonly the result of a successful parse of source code.

What can I do with it?

Having an easy to use data structure that represents a program’s source code allows you to write programs that treat code as they would any other piece of data. You can reliably generate new source, transform between languages, replace subtrees, analyze, lint, and auto-format code. ASTs are used by anything that needs to operate on code: IDEs, parsers, linters, analyzers, optimizers, compilers, and more. AST formats that are publicly standardized enable developers to centralize their efforts over a common structure, reducing duplicate work and allowing tools to be composed together.

This doesn’t exist already?

Mozilla exposed the SpiderMonkey Reflect.parse API in 2010 to encourage better tooling for JavaScript. This proved to be incredibly useful to the JavaScript community, enabling the creation of parsers like Esprima and Acorn and catalyzing a vast ecosystem of tools. Hundreds of projects rely upon these tools, including eslint, plato, istanbul, jscs, browserify, and many more.

However, the SpiderMonkey AST format was not specifically created for these tools. The SpiderMonkey AST originated as the internal representation of a JavaScript program in the SpiderMonkey engine, which was intended to be used only for interpretation. As tools were created and more use cases for a standard AST were recognized, many difficulties in dealing with SpiderMonkey format ASTs surfaced.

The SpiderMonkey AST and its ecosystem of tools and parsers is formidable and we don’t take deviation lightly. Our work at Shape Security has presented us with many problems that involve deep analysis and transformation of JavaScript. We have been forced to rethink what it means to represent and transform a JavaScript program, and in doing so developed this alternative AST format. The main advantages of using the Shift AST format are that it makes it much more difficult to accidentally perform a transformation that creates an invalid AST, and the nodes align more closely to the syntactic features they represent.

More than just the AST

An AST specification doesn’t have much value without a surrounding ecosystem. We’ve open-sourced JavaScript and Java implementations of the foundational tooling necessary to foster development of a supporting ecosystem around the Shift AST format. The following tools have been made available for both environments.

  • AST Node Constructors
  • Parser
  • Code Generator
  • Reducer
  • Validator
  • Scope Analyzer

In addition, we’ve released a tool for converting back and forth between the Shift and SpiderMonkey AST formats. All of these are available on the Shape Security Github account.

The road forward

We will continue to develop tooling based on the Shift AST format and will iterate on the existing libraries, optimize for performance, and add ECMAScript 6 support.

The Shift AST format was developed with ECMAScript 6 in mind. The es6 branches of both the specification and the JavaScript AST constructors already include full support for ECMAScript 6, and we plan to add support to all of the tooling we have released so far. Contributors

Some of the developers behind the Shift AST format and associated tools are active contributors and maintainers of JavaScript language tools that are popular in the JavaScript community. Work on those tools is not ending, nor does the work here immediately affect any future plans for those tools.