Writing a JavaScript interpreter for DBN using PEG.js and canvas (Part II)

20 August 2010, Amsterdam
Send to Kindle

In this article I build an interpreter for the DBN language from the parsed AST generated by the grammar we defined in the previous article in PEG.js. If you haven't read the first part, I strongly recommend to do so, otherwise this will make little sense to you.

It should be quite easy to follow by just looking at the code and its comments. Still, I will be explaining how the interpreter works as I put the code examples in.

Choices and assumptions

Due to little time and given the lack of any reference of the language, I made some assumptions and I left out some advanced features of the language. I hope I can include them soon into the project.

Scope

Since I don't know how scope works in DBN, I assumed Lexical scoping, given that it is the most common among modern programming languages (JavaScript has lexical scoping as well, for example).

The interpreter

The interpreter takes care of evaluating the arguments for each statement and then execute the statement with its parsed arguments and the given scope, if any:

var Interpreter = function(canvas) {
    this.canvas = canvas
    this.ctx = canvas.getContext('2d')
    this.vars = {}
}

Interpreter.prototype = {
    evalType: function (e, scope) {
        return Interpreter.typeTable[e.type].call(this, e, scope)
    },
    evalExpression: function(ast, scope) {
        _.each(ast, function (c) {
            // Parse the arguments real value
            var args = _.map(c.args, function(a) {
                return this.evalType(a, scope)
            }, this)
            Interpreter.expTable[c.name].call(this, {
                args: args,
                block: c.block,
                scope: scope
            })
        }, this)
    },
    reset: function() {
        var ctx = this.ctx
        // Resets all cnavas state and properties
        this.canvas.width = this.canvas.width
        this.r = { vars: {}, cmds: {} }
    }
}

The global variables will reside in the vars property, and the most important methods here are obviously evalType and evalExpression.

Evaluating types

evalType receives the type object and its scope and calls the proper static method in Interpreter.typeTable with the same parameters. Interpreter.typeTable holds the functions that interpret the different types in DBN:

// In DBN, everything is an integer or a set of integers, and the developer has
// the possibility to put the values directly in the code or store them in
// variables.

Interpreter.typeTable = {
    "command": function(e, scope) {
        var values = _.map(e.args, function(a) {
                return this.evalType(a, scope)
            }, this)
        return Interpreter.cmdTable[e.name].apply(this, values)
    },
    "string": function(e, scope) {
        var vars = this.r.vars
        var v = e.value

        if (scope && scope.hasOwnProperty(v)) return scope[v]
        else if (vars.hasOwnProperty(v))      return vars[v]

        return v
    },
    "integer": function(e, scope) { return e.value },
    "point": function(e, scope) {
        return {
            type: "point",
            x: this.evalType(e.x, scope),
            y: this.evalType(e.y, scope)
        }
    }
}

The types are the following:

Command

A user-defined function in DBN jargon. The user can define custom commands with parameters that execute a block of code when called.

String

Used mainly for variable names. Given a string from a generated AST, I check whether the variable is defined in its local scope (in case there is one) or in the global scope. In case it is in neither of them, I assume that it is the name of a parameter and doesn't have an associated value.

Integer

The basic type. Its value is returned right away.

Point

A point refers to a coordinate in the canvas. It contains x and y values that can be integers, variables or arithmetic expressions. Returns an object with the evaluated x and y values.

Evaluating expressions

Expressions are DBN functions. In this interpreter, everything that computes is considered a function, including the arithmetic operators.

evalExpression takes an AST (or a portion of one, as it is done for code blocks) and loops through every statement, resolving the types of its arguments using evalType and calling the proper static method in Interpreter.expTable with them. Interpreter.expTable is a dictionary that stores the supported DBN expressions' equivalents in JavaScript (same as with types).

Inside the Interpreter.expTable we can find the following kinds of expressions:

Arithmetic expressions

"*": function(a, b) { return parseInt(a * b) },
"/": function(a, b) { return parseInt(a / b) },
"+": function(a, b) { return parseInt(a + b) },
"-": function(a, b) { return parseInt(a - b) }

Arithmetic expressions are always used inside other expressions parameters, never by themselves. The functions are called always with 2 arguments that have been already resolved by evalType, so they are integers when they get to the expression.

Drawing expressions

/*
 * paper will fill up the canvas with the specified color (the only argument
 * of the expression)
 */
paper: function(p) {
    var ctx = this.ctx
    var w = ctx.canvas.clientWidth
    var h = ctx.canvas.clientHeight

    ctx.fillStyle = Interpreter.gray2rgb(p.args[0])
    ctx.fillRect(0, 0, w, h)
},
pen: function(p) {
    this.ctx.strokeStyle = Interpreter.gray2rgb(p.args[0])
},
line: function(p) {
    var a = p.args
    var ctx = this.ctx
    var height = ctx.canvas.clientHeight

    ctx.moveTo(a[0], (height-a[1]))
    ctx.lineTo(a[2], (height-a[3]))
    ctx.closePath()
    ctx.stroke()
}

The main difference between the DBN 'canvas' and HTML5 canvas is that the Y coordinate is inverted; in DBN the Y coordinate starts at the bottom whereas in HTML5 canvas it starts at the top. The other important difference is that DBN's pixels color can only be a gray value from 0 (black) to 100 (white), so we have to use the very simple gray2rgb method to translate them to canvas rgb syntax:

/*
 * gray2rgb transforms a 0 to 100 gray value into a rgb
 * string compatible with canvas
 */
Interpreter.gray2rgb = function(gray) {
    var value = Math.ceil(255 - (gray * 2.55))
    return "rgb(" + value + "," + value  +"," + value + ")"
}

With these two changes in place it is quite straightforward to translate drawing functions using the basic HTML5 canvas functions and passing the arguments properly.

Block expressions

A block expression is a statement that contains a block of nested expressions. DBN's repeat and command statements are the ones implemented here that belong to this kind. The peculiarity of block expressions is that they have a local scope:

repeat: function(p) {
    var args = p.args,
        id = args[0], f = args[1], c = args[2],
        // Cloning context object because otherwise we will change
        // properties of the parent context, messing up everything
        scopeObj = _.clone(p.scope) || {}

    _.each(_.range(f, c), function(n) {
        scopeObj[id] = n // Update the 'counter' variable to reflect the current loop number
        this.evalExpression(p.block, scopeObj)
    }, this)
},
command: function(p) {
    var args = _.rest(p.args)

    Interpreter.expTable[p.args[0]] = function(_p) {
        // Cloning context object because otherwise we will change
        // properties of the parent context, messing up everything
        var scopeObj = _.clone(p.scope) || {}

        // Associate every argument name with the given argument
        // value of the command call
        _.each(args, function(p, i) { scopeObj[p] = _p.args[i] })
        this.evalExpression(p.block, scopeObj)
    }
}

The local scope here is implemented in a naive (and a bit inefficient) way. Basically and if it exists, the parent scope of the block expression is cloned and then the local variables of the block are copied on it. After that, the block of nested expressions is executed with the cloned context.

repeat is a 'for' loop that gets as arguments the 'counter' variable, the lower bound of the range and the higher bound of the range. From that it creates a loop that assigns the counter variable to the local scope and executes the block with this scope.

command builds a function from the given name and arguments and the block expression that forms the body of the function. In that case I create a function and store it in Interpreter.expTable so it can be called anywhere in the code. I do the same trick with the scope as in repeat, with the difference that in this case I associate the name of the command arguments with the value passed to the call of the function.

Demo

That's it, you can try a quick demo here. In the demo page you can find some examples and you can play around to better understand how DBN works and what its powers and limitations are.

Conclusion

As you can see this is a very simple implementation, but it is enough to run most of the DBN programs around. Some things like arrays, timers and mouse position and events were left out and will be implemented at some point when I have time, but the actual 'meat' of the interpreter won't change much anyway.

You can find the complete code for this interpreter here and the complete repository here. If I missed something or yo have some suggestions of how to better implement DBN drop me a line, or even better: fork it!


If you'd like, you could follow me on twitter, Google+ or drop me an Email.