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.

Background

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.

Limitations

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.

Acknowledgements

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