Multi-threaded Javascript using an interpreter

Posted: January 13th, 2015 | By Amitay Dobo | Filed under: Development | Tags: async, interpreter, Javascript, multithreading, programming, threads | No Comments »

In this post I’m going to explore running multiple threads of javascript code in the browser, executing the javascript code through an interpreter which runs in the browser.

Each thread has its own sandbox, with a restricted access to runtime which executes code in the browser.

Demo: http://www.doboism.com/projects/JS-Interpreter/asyncDemo/asyncDemo.html

Source code on github:  https://github.com/amitayd/JS-Interpreter

A brief explanation of the different parts that make it run:

• “Native” environment: In this case the browser, the single global scope it provides. The interpreter is executed in it.
• Interpreter: A javascript interpreter, implemented in javascript, written by Neil Fraser - https://neil.fraser.name/software/JS-Interpreter/ . Takes code in javascript (as a string), and executes it in something like a virtual machine, in an isolated scope
• Runtime: a library that executes in native environment, intended for the interpreted code to use. In this case, a simple LOGO like library that can rotate and move an object, and print text on it.
• Native-to-Interpreter Adapter A bi-directional adapter between “native” (browser’s javascript) and “interpreter” (interpreter’s javascript) code. Part of the adapter code is providing a way to handle asynchronous function calls in the runtime, returning control to the interpreter when a result is received.
• Interpreted code:  The javascript code that is being passed to the interpreter to be executed. Has access (through the adapter) to the runtime objects.
• Scheduler: Controls the execution and allocated time for multiple interpreters, each running a “thread” of interpreted code. In the demo we use a simple round-robin scheduler, which switches between the different interpreter threads, giving each a time quota before switching to the next one (cyclically).

The following code was written mostly to explore and demonstrate the concepts, it is by no means production ready, but may help as a guideline if for some reason you want to continue upon this work or do something similar.

Why?

I came to this experiment from working on a project for an in-browser environment for learners to write and execute code. The environment for coding was somewhat similar to MIT’s scratch, meaning that the code wasn’t written as text, but using code blocks. Code blocks in the prototype were converted to javascript (using Blockly).

However, we had some requirements regarding the execution of that javascript code:

• It should only be allowed to access a specific API (runtime) – not the entire browser environment. This is wanted both allowing code to be shared safely, and preventing learners from shooting their own leg.
• Execution should be finely controlled for two reasons: Debugging (step by step execution, highlighting the currently executing statements, etc), and stability – allowing to stop the execution at any time.
• Multiple threads of code should be executed in parallel (i.e. two threads for the shapes moving around in the same time).
• For simplicity, blocking code should be allowed, for routines which their implementation in the runtime is actually asynchronous.

To elaborate on the last point:

Since the browser is single threaded, a routine that blocks for 2 seconds will cause  the browser to freeze, it’s a practice to use callbacks for actions that take a period of time.

For example, let’s say we want to move a shape left for 2 seconds, and then right. In “native” javascript I might write something like this:

shape1.move({x:50, y:0, duration:2000}, function() {
  shape1.move({x:0, y:0, duration: 2000}, function() {
    console.log('done');
  });
});

(yes, this could be somewhat less verbose using promises, but still will require multiple closures).

For learners code, I would want to simplify it to something like:

shape1.move({x:50, y:0, duration:2000});
shape1.move({x:0, y:0, duration:2000});
console.log('done');

The interpreter

(interpreter.js)

The project uses an interpreter by Neil Fraser (forked from https://github.com/NeilFraser/JS-Interpreter), written in javascript, which parses a string of javascript code and executes it in a separate environment, with its own unique scope (using something like a virtual machine).

I won’t go into the detail into the interpreter, though it’s probably the most interesting part, since I just picked up one and used it, and it has more or less just worked.

The extension of the interpreter is done using a callback provided for its initialization, allowing us to add objects to the global scope.

The performance of the interpreter is probably way worse than the direct execution in the browser. For for the goals of the project this was not a big concern, since the code is used mostly to “orchestrate” the runtime, which does the heavy-lifting, and is executed in the native environment.

I’m also not sure how complete is the javascript language coverage of the interpreter, but it’s sufficient for the demo purposes.

Native-Interpreter adapter

(nativeHelpers.js)

The helper lets us do the following:

• Interpreter to native conversion (interpreterValueToNative): Convert from an object or primitive from interpreter internal representation to a native (‘regular’) javascript one. It works recursively on object properties.
• Native to interpreter conversion (nativeValueToInterpreter): Convert a javascript object or primitive to an interpreter one.
  If an object is passed, its properties are converted to properties in the interpreter object (recursively). If a function is passed, a wrapper is created (see below).
  This can be used to convert an API to the interpreter representation, and expose it somewhere on the global scope of the interpreted code using the interpreter init function.
• Native function invocation wrapping (createGenericNativeWrapper): Wraps  a native function so before the function invocation on the native function from within the interpreted code, converts the arguments to native ones (in run-time). The return value of the native function are converted to interpreter value.

Note that object conversions are done by value and not by reference, so something like this:

var nativeObject = {
  val: 'some Value'
};

interpreter.setProperty(scope, 'wrappedObject', helper.nativeValueToInterpreter(nativeObject));

will create a wrappedObject.val which changes to  will not be reflected in the native object and vice-versa.
Creating getters and setters for properties can be used as a workaround.

Asynchronous function invocation - AsyncInterpreterRunner

Async execution of native code is done by using AsyncInterpreterRunner on top of the interpreter. It allows us to call native code which executes asynchronously and uses a callback on completion. From the interpreted code, it seems like the method was executed synchronously.

This is done as follows:
The async runner adds two objects to the global scope, asyncWait, and asyncResult.
When a native function is executed through its wrapper with an asyncWait argument, the argument is being substituted  by a special callback provided by the runner.
The interpreter execution is halted until the runner’s callback is called from the native code.
When the runner’s callback is called, the results are stored in the asyncResult object in the interpreted code scope.

For example:
Interpreted code:

wrappedObject.someAsyncFunction(5, asyncWait);
var myResult = asyncResult.result;

Code:

var nativeObject = {
  someAsyncFunction: function (n, callback) {
    window.setTimeout(function () {
      callback(null, n + 1);
    }, 100);
  }
};

var initInterpreter = function (interpreter, scope, helper) {
  interpreter.setProperty(scope, 'wrappedObject',
  helper.nativeValueToInterpreter(nativeObject));
};

var code = 'wrappedObject.someAsyncFunction(5, asyncWait);\n' +
           'asyncResult.result';

var myInterpreter = new AsyncInterpreterRunner(code, initInterpreter);
myInterpreter.run(function interpreterDone() {
  console.log('done');
});

Using asyncWait makes the author of the interpreted code responsible for making function to block until its completion.
A possible alternative implementation would be to somehow let the runner know which methods should be invoked asynchronously and add the callback argument by itself.

 

The scheduler - AsyncScheduler

The very basic round-robin scheduler gets AsyncInterpreterRunner instances submitted to it, and switches between the interpreters, giving each a time quota to execute before switching to the next one.

The implementation is very simple and limited (more of a POC really). It is missing some important things as notifications when all jobs are completed, allowing to halt execution, stats on the different jobs, etc.

Example code:

   var initInterpreter = function (interpreter, scope, helper) {
      interpreter.setProperty(scope, 'console',
        helper.nativeValueToInterpreter(window.console));
    };


    var scheduler = new AsyncScheduler();
    for (var i = 0; i < 5; i++) {
      var code = 'for (var i = 0; i < 10; i++) {console.log(' + i + ',i);}';
      var runner = new AsyncInterpreterRunner(code, initInterpreter);
      scheduler.submit(runner, 'runner' + i);
    }

    scheduler.run(function () {
      console.log('done');
    });

The demo

The demo is under asyncDemo/asyncDemo.html (or live at http://www.doboism.com/projects/JS-Interpreter/asyncDemo/asyncDemo.html)

It consists of a (very raw) UI to edit the interpreted code of 5 different threads.
On the initialization of each thread some elements are created on the DOM for it. A runtime object to manipulate the elements is created, and the interpreted code is given access to it using the native helper..

The runtime includes methods such as setText(), left(), right(), rotate(), forward() and waitForClick().
All the methods but setText, can be executed with asyncWait so they’ll block and wait for completion in the runtime.

Simpler test cases can be found at the test spec files in the tests folder.

Hope it’d help anyone who thought of doing something similar, or at least be fun to play with. Feel free to share with me (or just fork) any ideas.

by

---