Fork me on GitHub

part of the Shift suite

Shift Reducer

a framework for defining a bottom-up summarisation of a Shift AST

Introduction

The Shift Reducer (pun completely unintentional) is a framework for definining instructions for summarising a Shift AST and executing those instructions. This is similar to how Array.prototype.reduce summarises an array using a function as its instructions. This very powerful abstraction is used to create projects as diverse as the Shift Scope Analyser, the Shift Validator, the Shift Early Error Checker (included in the Shift Parser), the Shift Code Generator, and the simple demo right on this page.

Demo

In this demo, a reducer is given as the default export of the program on the left. It can be run against itself, after which the final reduction state will be displayed as JSON on the right. ECMAScript 2015 syntax may be used.

The initially loaded reducer will collect all identifiers in expression position into a list. Try changing reduceIdentifierExpression to reduceBindingIdentifier, or replace node.name with node.

Reducer

(function() { let EMPTY; class Collector { constructor(x) { this.value = x; } static empty() { return EMPTY; } concat(a) { return new Collector(this.value.concat(a.value)); } extract() { return this.value; } } EMPTY = new Collector([]); return class IdentifierCollector extends MonoidalReducer { constructor() { super(Collector); } reduceModule(node, state) { return super.reduceModule(node, state).extract(); } reduceBindingIdentifier(node, state) { return new Collector(['binding: ' + node.name]); } reduceIdentifierExpression(node, state) { return new Collector(['reference: ' + node.name]); } } })();
Input Program
Reducer Output
"use strict"; let [x,y,z] = [1,2,3].map(_ => _ * 2); class Person { constructor(name) { this.name = name; } }

Usage

A reducer needs to define a reduction method for each and every Shift AST node type. The reduction methods tell the director how to combine the state objects generated by the children of nodes of that type, or, for leaf nodes, the value to use as the initial state.

Most of the time, we won't want to define a reduction method for every Shift AST node type. Not only is that a lot of work, but in these cases it would be very repetitive. When we can define an associative combining operation and a special state object which can be combined with any other state object to produce the other state object, we can take advantage of the MonoidalReducer. This allows us to define only the reduction methods that we care about.

Once we have a reducer, we simply pass an instance of it to the director, the Shift Reducer default export, along with the Shift AST on which we would like to run the reduction. 

import reduceUsing, {MonoidalReducer} from "shift-reducer";
import parse from "shift-parser";

class MyState {
  static empty() { /* TODO: return the identity instance */ }
  concat(otherState) { /* TODO: combine this and otherState */ }
}

class MyReducer extends MonoidalReducer {
  constructor() {
    super(MyState);
  }
  
  /* TODO: override any reduction methods we care about */
}

let program = parse("function hello(){ return world; }");
let finalState = reduceUsing(new MyReducer, program);

© Shape Security, Inc.