A JavaScript VM that interprets code written in JSON

Question

I have written a simple VM in JavaScript and it interprets source code written in JSON.

The JSON object must have a "exports" property, which is a dictionary that matches a string into a integer value. This value is an index to "entries" property, which is an array of entries.

For each entry it contains a "binds" and a "execs" property. They are all arrays of object that contains callee and params. callee is a single object that contains "type" and name (string) or index (integer). type can be extern (refer to some function implemented in the VM) or "entry" (refer to entries array) or "bind" (refer to binds array) or "param" (at runtime, refer to the parameters given to the call). params is an array of exactly the same type of callee.

At runtime, to call the VM one must specify a name listed in "exports" array, and some parameters. The VM will then look at the referred entry and create bind objects (record all resolved parameters, but not actually call them) for each item in the binds array. And then for each item in the "execs" array, execute at least one of them (how to do so is not specified).

Here is a simple implementation that only execute the first item in the "execs" array, and only provides externs for + - * 1 and < (it also allow to "run" a boolean typed value, the rule is to run the first argument if the value is true otherwise the second argument):

function evalJson(json){
    return eval("(" + json + ")");
}

function RunEngine(){
    var log = function(str){
            var p = document.createElement("p");
            p.appendChild(document.createTextNode(str));
            document.getElementById("log").appendChild(p);
    };

    var externs = {
            "<":function(n1,n2,c){
                log(n1 + " < "+n2+"? " + (n1<n2));
                this.callobj(c,n1<n2);
            }.bind(this),
            "1":1,
            "+":function(n1,n2,c){
                log(n1 + " + "+n2+" = " + (n1+n2));
                this.callobj(c,n1+n2);      
            }.bind(this),
            "-":function(n1,n2,c){
                log(n1 + " - "+n2+" = " + (n1-n2));
                this.callobj(c,n1-n2);
            }.bind(this),
            "*":function(n1,n2,c){
                log(n1 + " * "+n2+" = " + (n1*n2));
                this.callobj(c,n1*n2);      
            }.bind(this)
        };
    this.getExtern = function(name){
        return externs[name];
    };

    var calls=[];
    var running = false;

    this.callobj = function(obj){
        var args=[].slice.apply(arguments);
        args.shift();
        if(typeof(obj)==="boolean") this.callobj(obj?args[0]:args[1]);
        if(typeof(obj)==="function") {
            calls.push(obj.bind.apply(obj,[this].concat(args)));
            if(!running)running=true;
            else return;
            while(calls.length>0){
                calls.pop()();
            }
            running = false;
        };
    };
    this.bindobj = function(obj){
        var args=[].slice.apply(arguments);
        args.shift();
        return this.callobj.bind.apply(this.callobj,[this,obj].concat(args));
    };
}

function JsonVM(code,engine){
    var entries = [];

    var getRefItem = function(refitem,ent,binds,args){
        if(refitem.type==="entry") return ent[refitem.index];
        else if(refitem.type==="bind") return binds[refitem.index];
        else if(refitem.type==="param") return args[refitem.index];
        else if(refitem.type=="extern") return engine.getExtern(refitem.name);
    }.bind(this);
    var getBind = function(callspec,ent,binds,args){
        var objs = [getRefItem(callspec.callee,ent,binds,args)];
        for(var i=0;i<callspec.params.length;++i){
            objs.push(getRefItem(callspec.params[i],ent,binds,args));
        }
        return engine.bindobj.apply(engine,objs);
    }.bind(this);

    var getEntry = function(entry){
        var f = function(){     
            var binds=[];
            var args = [].slice.apply(arguments);
            entry.binds.forEach(function(bind){
                binds.push(getBind(bind,entries,binds,args));
            });
            var v = getBind(entry.execs[0],entries,binds,args);
            engine.callobj(v);
        };
        return f.bind(this);
    }.bind(this);

    code.entries.forEach(function(entry){
        entries.push(getEntry(entry));
    });

    this.runExport = function(name){
        var args=[].slice.apply(arguments);
        args.shift();
        engine.callobj.apply(engine,[entries[code.exports[name]]].concat(args));
    };
}

window.onload = function(){
    document.getElementById("run").onclick=function(){
        var code = evalJson(document.getElementById("code").value);
        var vm = new JsonVM(code,new RunEngine());
        vm.runExport("Factorial",10,function(n){ alert(n); });
    };
};

The following HTML file is associated with it:

<!doctype html>
<html>
<head>
<meta charset="utf-8" />
<title>JSON VM test</title>
<script type="text/javascript" src="jsonvm.js" ></script>
</head>
<body>
<textarea id="code" rows="60" cols="80"></textarea>
<input type="button" id="run" value="run" />
<div id="log" ></div>
</body>
</html>

Here is a sample JSON code that implements the Factorial() function:

{
    "exports":{"Factorial":0},
    "entries":[{
        "binds":[{ 
            "callee":{"type":"entry","index":1},
            "params":[{"type":"param","index":0},
                      {"type":"param","index":1}]
        }],
        "execs":[{
            "callee":{"type":"extern","name":"<"},
            "params":[{"type":"param","index":0},
                      {"type":"extern","name":"1"},
                      {"type":"bind","index":0}]
        }]
    },{ "binds":[{
            "callee":{"type":"param","index":1},
            "params":[{"type":"extern","name":"1"}]
        },{
            "callee":{"type":"entry","index":2},
            "params":[{"type":"param","index":0},
                      {"type":"param","index":1}]
        }],
        "execs":[{
            "callee":{"type":"param","index":2},
            "params":[{"type":"bind","index":0},
                      {"type":"bind","index":1}]
        }]
    },{ "binds":[{
            "callee":{"type":"entry","index":3},
            "params":[{"type":"param","index":0},
                      {"type":"param","index":1}]
        }],
        "execs":[{
            "callee":{"type":"extern","name":"-"},
            "params":[{"type":"param","index":0},
                      {"type":"extern","name":"1"},
                      {"type":"bind","index":0}]
        }]
    },{ "binds":[{
            "callee":{"type":"entry","index":4},
            "params":[{"type":"param","index":0},
                      {"type":"param","index":1}]
        }],
        "execs":[{
            "callee":{"type":"entry","index":0},
            "params":[{"type":"param","index":2},
                      {"type":"bind","index":0}]
        }]
    },{ "binds":[],
        "execs":[{
            "callee":{"type":"extern","name":"*"},
            "params":[{"type":"param","index":0},
                      {"type":"param","index":2},
                      {"type":"param","index":1}]
    }]}]
}

To test, create the js file and the .html file, and open the html file in a browser, and then paste the JSON code to the text area, click "run". an alert will show the result ant prints the steps in the page (may require scrolling)

One more thing needed to know is that this VM implementation uses a trick to avoid keep using the call stack. Without this trick it will be even simpler.

The given code is working good. However, to make it working I have did some dirty hacks (I think). So I want this code to be reviewed and to see how to remove those hacks and makes the code more clear. Also please give me advice about OO design, code style and so on.

NOTES: Please do not advise about evalJson function, I understand using eval is not good but for this simple example it is OK and simple enough. If I were to move it to production I can simply replace the evalJson function implementation.

Answer 1

I have re-written the whole code to make it more modular as well as taking advantage of prototypes. The way your code was written was quite inefficient since everything had to be redefined for every newly created instances of JsonVM or RunEngine, since the whole code was inside constructor functions.

Unfortunately, there is no way to enforce the privacy of non-function instance members without sacrificing the benefits of using prototypes, so I've used a naming convention to identify private members: they start with and underscore _ (it's a very common practice).

You will also notice that I've extracted the logging strategy out of the RunEngine and allowed to inject it instead. I am still unsure about how that feature should be designed (perhaps an AOP approach?), however it's better than having it encapsulated within the class.

Anyway, have a look and let me know what you think.

Note: I haven't changed anything related to the processing logic since I wasn't enough confident.

!function (exports, slice) {

    exports.RunEngine = (function () {

        var externs = ['<', '-', '*', '/'].reduce(function (res, op) {
            res[op] = createOperatorExternFn(op);
            return res;
        }, {
            '1': 1
        });

        function RunEngine(log) {
            this._calls = [];
            this._running = false;
            this._log = log;
        }

        function createOperatorExternFn(op) {
            var fn = new Function('n1, n2, c', [
                'this._log(n1 + " ', op, ' " + n2 + "', (op === '<'? '? ' : ' = '), '" + (n1 ', op , 'n2));',
                'arguments.callee.callObj.call(this, c, n1 ', op, ' n2);'
            ].join(''));

            fn.callObj = callObj;

            return fn;
        }

        function runItem(item) {
            var calls = this._calls,
                fn;

            calls.push(item);

            if (this._running) return;

            this._running = true;

            while (fn = calls.pop()) fn();

            this._running = false;
        }

        function callObj(obj) {
            doCallObj.call(this, obj, slice.call(arguments, 1));
        }

        function doCallObj(obj, args) {

            switch (typeof obj) {
                case 'boolean': doCallObj.call(this, obj? args[0] : args[1]); break;
                case 'function': runItem.call(this, obj.apply.bind(obj, this, args));
            }
        }

        function bindObj(obj, args) {
            var me = this;

            return function () {
                doCallObj.call(me, obj, args.concat(slice.apply(arguments)));
            };
        }

        RunEngine.prototype = {
            constructor: RunEngine,

            getExtern: function (name) {
                return externs[name];
            },

            bindObj: bindObj
        };

        return RunEngine;
    })();

    exports.VM = (function () {

        function VM(code, engine) {
            var entries = this._entries = [];
            this._code = code;
            this._engine = engine;

            code.entries.forEach(function (entry) {
                entries.push(getEntry.call(this, entry));
            }, this);
        }

        function getRefItem(refItem, binds, args) {
            switch (refItem.type) {
                case 'entry': return this._entries[refItem.index];
                case 'bind': return binds[refItem.index];
                case 'param': return args[refItem.index];
                case 'extern': return this._engine.getExtern(refItem.name);
            }
        }

        function getBind(callspec, binds, args) {
            var objs = callspec.params.map(function (param) {
                return getRefItem.call(this, param, binds, args);
            }, this);

            return this._engine.bindObj(
                getRefItem.call(this, callspec.callee, binds, args),
                objs
            );
        }

        function getEntry(entry) {
            var me = this;

            return function () {
                var binds = [],
                    args = arguments;

                entry.binds.forEach(function (bind) {
                    binds.push(getBind.call(me, bind, binds, args));
                });

                entry.execs.forEach(function (exec) {
                    getBind.call(me, exec, binds, args)();
                });
            };
        }

        VM.prototype = {
            constructor: VM,
            runExport: function (name) {
                this._engine.bindObj(
                    this._entries[this._code.exports[name]], 
                    slice.call(arguments, 1)
                )();
            }
        };

        return VM;
    })();

}(
    window.jsonVM = window.jsonVM || {},
    Array.prototype.slice
);

window.addEventListener('load', function () {
    document.getElementById('run').addEventListener('click', function () {

        var code = JSON.parse(document.getElementById("code").value),
            logFn = console.log.bind(console),
            vm = new jsonVM.VM(code, new jsonVM.RunEngine(logFn));

        vm.runExport("Factorial", 10, logFn);
    });
});