Petrucci: A Rockstar interpreter in TypeScript: Part 1 & 2

Happy New Year, readers. 2020 is done, 2021 is here – and it’s time to do a new thing. I had a blast streaming Advent of Code on Twitch during December, and so for the next month or so I’m going to be building a Rockstar interpreter, using TypeScript, live on Twitch, and then writing about it here. If you want to join and watch live, I’m on twitch.tv/dylanbeattie most days around 16:00 UTC – and if you want to catch up afterwards, there’s a YouTube playlist of the videos.

Why TypeScript? Partly because I want to learn it. I’ve not worked with TypeScript before, at all, but I hear lots of very good things about it, and given it was designed by Anders Hejlsberg, who created C#, I suspect I’ll quite like working with it. I also want something that transpiles to JavaScript, so I can ship code into the wild and stick it up on a website where anybody can run it in their browser or on their phone. And partly because I really enjoy working with JavaScript; it’s a fun language that can do a lot of very cool things but which also affords a lot of experimentation and exploration, and I’m really interested in the TypeScript philosophy of allowing you to enhance JS with types and compile-time type checks if you want to, and allowing you to run plain old vanilla JS when that’s what you need.

So… part 1 (YouTube) was literally getting up and running. Installing TypeScript, having a look at Deno, figuring out how to get a PEG.js parser working nicely with TypeScript classes. Part 2 (YouTube) took this idea a bit further, and got as far as a very simple grammar for a tiny language, a parser and an interpreter for that language.

What makes things a little more interesting is that PEGjs, the parser generator that I’m planning to use on this project, only understands plain JavaScript - no TypeScript. So the high-level architecture looks something like this.

syntax.ts is the abstract syntax tree node classes - AdditionNode, MultiplicationNode, NumberNode, and so on. This is referenced directly by interpreter.ts (which is fine, because they’re both TypeScript), but I also need to include a reference to these classes in the parser that’s generated by PEGjs, and because PEGjs can’t understand TypeScript, I need to use the TypeScript > JavaScript compiler, tsc, to transpile syntax.ts into syntax.js. PEGjs uses the require() syntax, so there’s a line in the header block of the grammar file to require('syntax.js'). The pegjs tool translates the PEG grammar definition, parser.peg, into a parser.js file containing the actual parser. Finally, interpreter.ts imports the parser and the syntax definitions.

Because each different kind of language feature – addition, multiplication, output, etc – is now implemented as TypeScript class, it’s possible to implement an evaluate() method on each of these node types, which makes the design of the interpreter itself beautifully simple.

The interpreter presented here supports the following language constructs:

• Arithmetic: integer literals, addition, multiplication, and parentheses.
• Output: the say keyword will print the subsequent expression to STDOUT.
• Flow control: the return keyword will halt the program with the specified return code.

Here’s a sample program:

output 1
output (4+5)*(6+7)
return 0
output 9

The parse tree for this program should be something like:

output:
  number: 1
output
  product:
    lhs: sum:
      lhs: number: 4
      rhs: number: 5
    lhs: sum:
      lhs: number: 6
      rhs: number: 7
return:
  number: 0
output
  number: 9

The output from this program should be:

1
117

and it should exit cleanly with the operating system return code (aka error level) 0. The final output 9 should NOT be executed.

Here’s the full code so far - this is also on Github

syntax.ts

This file contains the TypeScript classes for building the nodes of our abstract syntax tree.

// syntax.ts: abstract syntax tree nodes
export abstract class LanguageNode {
    abstract evaluate(): Result;
}

export enum Action { None, Return }

export class Result {
    value: any;
    action: Action;
    constructor(value: any, action = Action.None) {
        this.value = value;
        this.action = action;
    }
}

export abstract class BinaryNode implements LanguageNode {
    abstract evaluate(): Result;
    lhs: LanguageNode;
    rhs: LanguageNode;
    constructor(lhs: LanguageNode, rhs: LanguageNode) {
        this.lhs = lhs;
        this.rhs = rhs;
    }
}

export class AdditionNode extends BinaryNode {
    evaluate() { 
        return new Result(this.lhs.evaluate().value + this.rhs.evaluate().value);  
    }
}

export class MultiplicationNode extends BinaryNode {
    evaluate() { 
        return new Result(this.lhs.evaluate().value * this.rhs.evaluate().value); 
    }
}

export class NumberNode extends LanguageNode {
    value: Number;
    constructor(value: Number) {
        super();
        this.value = value;
    }
    evaluate() { return new Result(this.value); }
}

export class OutputNode extends LanguageNode {
    node: LanguageNode;
    constructor(node: LanguageNode) {
        super();
        this.node = node;
    }
    evaluate() {
        let value = this.node.evaluate().value;
        console.log(value);
        return new Result(value);
    }
}

export class ReturnNode extends LanguageNode {
    node: LanguageNode;
    constructor(node: LanguageNode) {
        super();
        this.node = node;
    }
    evaluate() {   
        let value = this.node.evaluate().value;
        return new Result(value, Action.Return);
    }
}

parser.peg

The grammar definition for the language supporting in this prototype:

{ const Syntax = require('./syntax.js'); }

program = head:statement EOL tail:program { return [ head ].concat(tail) }
        / item:statement { return [ item ] }

statement = output / return

output = 'output' _ node:expression { return new Syntax.OutputNode(node) }
return = 'return' _ node:expression { return new Syntax.ReturnNode(node) }

expression = sum

sum = lhs:product _ "+" _ rhs:sum { return new Syntax.AdditionNode(lhs, rhs) }
    / product

product = lhs:primary _ "*" _ rhs:product { return new Syntax.MultiplicationNode(lhs, rhs) }
        / primary

primary = number
        / "(" expr:expression ")" { return expr; }

number = digits:$[0-9]+ { return new  Syntax.NumberNode(parseInt(digits)) }

_ = [ \t]*
EOL = '\r'? '\n'

interpreter.ts

Finally, the interpreter, with the program itself inline as a JavaScript multiline string literal:

import * as Parser from "./parser.js";
import * as Syntax from './syntax';

let program = `output 1
output (4+5)*(6+7)
return 2
output 9`

let ast = Parser.parse(program);
ast.forEach(node => {
    var result = node.evaluate();
    switch(result.action) { 
        case Syntax.Action.Return: process.exit(result.value);
    }
});

To run this via the command line, you’ll need to:

1. Install NodeJS. I’m running v12.16.2 but this should all work with any version > 12.
2. Install TypeScript: npm install -g typescript
3. Install PEGjs: npm install pegjs

To build and run the example, type node run start - or to run each step individually:

$ tsc syntax.ts
$ pegjs parser.peg
$ tsc interpreter.ts
$ node interpreter.js

In the next instalment, I’ll be setting up some tooling to make things a little easier to work with, and figuring how to start incorporating some of the existing test fixtures and coverage from Rockstar into the project.

Oh, and the name I’ve chosen for this one is Petrucci… the current JS interpreter for Rockstar is Satriani, after Joe Satriani (JS), and, well, John Petrucci is definitely younger than Satch, he’s more technically ambitious, and folks who are so inclined could get into a long argument about whether he’s better or not. But the world is definitely a better place for having both of them in it – and as it is with virtuoso metal guitar players, so it is with Rockstar interpreters. 😎

Links:

• The YouTube playlist where I’m publishing video of this project
• The Petrucci code repo on GitHub
• The Rockstar language website and language specification
• twitch.tv/dylanbeattie, where I’m streaming live most days around 16:00 UTC