# A JavaScript VM that interprets code written in JSON

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));
};
}

document.getElementById("run").onclick=function(){
var code = evalJson(document.getElementById("code").value);
var vm = new JsonVM(code,new RunEngine());
};
};


The following HTML file is associated with it:

<!doctype html>
<html>
<meta charset="utf-8" />
<title>JSON VM test</title>
<script type="text/javascript" src="jsonvm.js" ></script>
<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.

• You mentioned 'move it to production', can you tell us what you are trying to solve? Is the JSON generated from yet another programming language? – konijn Mar 28 '13 at 12:56
• Yes, I'm planning to create a Web UI for it. But now it is far too early to that step. – Earth Engine Apr 2 '13 at 5:32
• @plalx Umm... Maybe I need more explanation. I think the example in the code above shall already implemented a VM with simple arithmetic operations as atomic functions, so it is ready to interpret the given Json code for "Factorial" function, so it is an example of how to use it. Roughly speaking, you write JsonVM function once only, and adjust RunEngine function whenever you want to add more atomic operations, to interpret an existing program that written in my JSON format given above. – Earth Engine Oct 21 '13 at 3:25
• @EarthEngine Yeah, I get the concept, however it's not that easy to follow the implementation through all these callObj, doCallObj, bindObj etc. Perhaps if you could add comments in the code so that it would be easier to understand. Otherwise I'll draw the execution plan once I have time to have a better understanding. – plalx Oct 21 '13 at 13:57
• Emm... in this implementation callObj is just a wrapper to call doCallObj in order to make it work with varidic parameters (arguments in javascript). bindObj is just a lazy vesion of callObj, so calling bindObj just returns a function which when called, do the real jobs. This shall be clear when you look at the updated version of the code. Furthermore, bindObj is part of the public interface of the RunEngine but callObj is not. Also remember bindObj and getExtern are the only two methods required by the VM, an both of them return something executable. – Earth Engine Oct 21 '13 at 23:29

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
);