MetaES introduction

MetaES is a metacircular interpreter (http://en.wikipedia.org/wiki/Meta-circular_evaluator) written in JavaScript at EcmaScript 5.1 standard, so it can run on pretty any environment that supports ES5, for example modern browsers (both with mobile), nodejs, rhino, nashorn and other ECMAScript interpreters.
For parsing JavaScript it uses esprima http://esprima.org/.

You can learn more about such interpreter in SICP book that is available for free online http://mitpress.mit.edu/sicp/full-text/sicp/book/node76.html

Metacircular interpreter visualization

[Picture 1. Gerald Jay Sussman showing how it works from the big picture]

About MetaES as metacircular interpreter

Metacircular interpreter basically interprets the language that it is written in, but that interpretation is easier,
because there is a lot of features implemented in base interpreter. In case of JavaScript there are, for example, ready for use:

  • binary expressions: +, -, * and the rest
  • literals (true, false, "string", 123, {}, [])
  • functions, function [[Call]], bind, apply, call
  • prototypes – MetaES doesn’t rewrite them
  • standard global objects, like Object, Array, String, Date

So a lot what is needed is already there, just has to be reused.
However, MetaES adds some informations available to JavaScript, that in normal execution is hidden and possibly available only via debugger API specific for each engine, they are:

  • access to scope as the JavaScript object, for example having program like:

    var a, b, c, d = 1;
    

    the scope variables can be accessed in object {a:undefined, b:undefined, c:undefined, d:1}

  • access to the stack as the JavaScript object, for example:

    function a(){
        // here it is possible to get an array like: [function a(){...}, function b(){...}, globalScopeReference]
    }
    function b(){
        a();
    }
    
    b();
  • access to functions closures:

    var a = 1;
    function foo(b) {
        return a+b;
    }
    
    // and it is possible to get scope that `foo` is in, that is scope that contains {a:1}
  • stopping/resuming the execution as it was debugger, in program:

    [1,2,3].map(mappingFunction).reduce(reducingFunction);

    it is possible to stop and lookup execution at [1,2,3]., [1,2,3].map(mappingFunction) or even [1,2 and continue later.

  • execution order, semantics. This means that try {} catch(e) {} finally {} can be executed in any way, for example finally may be executed first, then main try block and catch not at all. Or break statements may be ignored, or rather exeception may be thrown when approached.

  • support for ES6

    Projects like Traceur proved that is it possible to simulate ES6 features in ES5. In case of interpretation that can be even more powerful, because interpreter has power to implement new features behind the scenes using previous ones, just like does native interpreter in C++, without adding special wrappers to executed code. So, with little effort there are ArrowFunctions

    [1,2,3].map((x)=> x*x); // [1, 4, 9]

    ArrayComprehensions:

    [for (let x in [1,2,3]) square(x)]; // [1, 4, 9]

    and they are based on FunctionExpression and ForStatement available in ES5.

    class, import, export are easy as well, not mentioning yield, that just is based on pausing and resuming execution with preserving of the scope. ES7s await may be a subject of implementation as well, if underlaying parser (esprima) parses it correctly.

Saying again, in short, while running MetaES may collects stack, environment, closures, live values and some statistics on token level, so it is possible to introspect any AST node of JavaScript and lookup all the data just as if it was JSON. Most of the time it’s also possible to set up breakpoint at any token, for example [1,2 [breakpoint], 3], not only on lines.

This interpreter can be seen a core library that can be used as a dependency in plugins.

Quite unique feature or this interpreter is native JavaScript interoperability. So you can call functions generated by MetaES interpreter with by those not generated and vice versa. It’s even possible to interpret interpreter inside previous instance of interpreter in order to make some more advanced introspections.
It allows to run most of the application with native speed and slow down only in few important places, for example library code can be run natively, but library client will run in metacircular way.
Nevertheless, it’s possible to run everything in metacircular mode having in mind performance penalty.

Let’s see some API:

This is the signature of function calling the interpreter:

function (text, rootEnvironment, cfg, c, cerr)

The parameters are:

  • text – JavaScript program in String. It may be a function reference as well, it will be converted to string.
  • rootEnvironment – object containing key-values pairs that will be enviroment for text. Can be for example just window, or {a: 1, b:2}, or environment that has previous (outer) environment that should have following properties:

    • name – key-valued object, like previously mentioned {a: 1, b:2}
    • prev – literal or reference to another environment

    For example:

    var 
      outer = {
        names: window,
        prev: null
      },
      env = {
        names: {foo:"bar"},
        prev: outer
      };
    metaes.evaluate("console.log(foo)", env);

    or

    metaes.evaluate("console.log(foo)", {foo:"bar"});
  • cfg – object which may contain following properties:
    • name – name of the VM, can be filename or just any arbitrary name. Leaving it undefined will by default assign name like VMx where x is next natural number.
    • interceptor – function of signature (e, value, env) where
      • e is AST node from esprima,
      • value is a JavaScript value
      • and env is enviroment object compatible with extended rootEnvironment parameter
  • c – function that will be called if evaluation finishes successfully, should have signature

    function(ast, value)

    where the arguments are:

    • ast – AST of parsed program
    • value – value of the last expression
  • cerr – function that will be called if evaluation finishes with error (SyntaxError, ReferenceError of any kind of exception). Function should have signature:

    function(ast, errorName, error);

    where the arguments are:

    • ast – AST of parsed program
    • errorName – can be Error which is native error, SyntaxError or ReferenceError
    • error – error object

and it returns the result of evaluation the same as it was eval call.

metaes.evaluate("2+2", {}) === eval("2+2") // true

Writing for example:

metaes.evaluate("var x = 1 + a, x;", {a:1});

will return 2 of course, but:

metaes.evaluate("var x = 1 + a, x;");

will throw ReferenceError: a is not defined., just like eval.

In case you were curious:

metaes.evaluate("eval(1+2)", {}); // ReferenceError: eval is not defined.
metaes.evaluate("eval(1+2)", {eval:eval}); // 3
eval('metaes.evaluate("eval(1+2)", {eval:eval})'); // 3

The most interesting feature, and in fact crucial, is interceptor. So you can write

function interceptor(e, value, env) {
    console.log("[" + e.type + "]: " + e.subProgram + " (line:" + e.loc.start.line + ", col: " + e.loc.start.column + ")");
    console.log("\t" + value);
}
var fn = metaes.evaluate("(function(x){return x*x})", {}, {interceptor: interceptor});

console.log([1,2,3].map(fn));

And you’ll get…

[FunctionExpression]: function(x){return x*x} (line:1, col: 1) VM245:3
    function(x){return x*x} VM245:4
[ExpressionStatement]: (function(x){return x*x}) (line:1, col: 0) VM245:3
    function(x){return x*x} VM245:4
[Program]: (function(x){return x*x}) (line:1, col: 0) VM245:3
    function(x){return x*x} VM245:4
[Identifier]: undefined (line:1, col: 10) VM245:3
    1 VM245:4
[Identifier]: x (line:1, col: 20) VM245:3
    1 VM245:4
[Identifier]: x (line:1, col: 22) VM245:3
    1 VM245:4
[BinaryExpression]: x*x (line:1, col: 20) VM245:3
    1 VM245:4
[ReturnStatement]: return x*x (line:1, col: 13) VM245:3
    1 VM245:4
[FunctionExpression]: function(x){return x*x} (line:1, col: 1) VM245:3
    function(x){return x*x} VM245:4
[Identifier]: undefined (line:1, col: 10) VM245:3
    2 VM245:4
[Identifier]: x (line:1, col: 20) VM245:3
    2 VM245:4
[Identifier]: x (line:1, col: 22) VM245:3
    2 VM245:4
[BinaryExpression]: x*x (line:1, col: 20) VM245:3
    4 VM245:4
[ReturnStatement]: return x*x (line:1, col: 13) VM245:3
    4 VM245:4
[FunctionExpression]: function(x){return x*x} (line:1, col: 1) VM245:3
    function(x){return x*x} VM245:4
[Identifier]: undefined (line:1, col: 10) VM245:3
    3 VM245:4
[Identifier]: x (line:1, col: 20) VM245:3
    3 VM245:4
[Identifier]: x (line:1, col: 22) VM245:3
    3 VM245:4
[BinaryExpression]: x*x (line:1, col: 20) VM245:3
    9 VM245:4
[ReturnStatement]: return x*x (line:1, col: 13) VM245:3
    9 VM245:4
[FunctionExpression]: function(x){return x*x} (line:1, col: 1) VM245:3
    function(x){return x*x} VM245:4
[1, 4, 9] 

Calling metacircular function can be seen as (pseudocode):

function() {
    return smartEvaluationUsingGivenInterceptor(arguments, this, originalSourceOfTheFunction);
}

where smartEvaluationUsingGivenInterceptor is an internal part of MetaES that is available through the closure.

So this is the example of interoperability with native functions. The opposite way is obvious, but let’s be specific:

function success() {
}

function error() {
}
metaes.evalate("console.log('hello world')"), {console: console}, {name: 'file1.js'}, success, error);

will output

"hello world"

in the console.

Just to play a little, it’s easy to define function that produces metacircular functions from the native one.

function toMetacircular(fn) {
    return metaes.evaluate(fn, {});
}

var metacircularMap = toMetacircular(function(arg){
    return arg * arg;
})

[1,2,3].map(metacircularMap); // [1,4,9]

FAQ

Where is the source code?

The code is still under development. This is still only a side project, therefore is not production ready nor cleaned up. This documentation is kind of promise and sharing the first impressions of working library. But for sure it will be open-sourced at some point.

What is already done?

With MetaES this is possible to create an IDE for better JavaScript development.

This is quite old example, but shows experiments with ES6 and tooltips with values under current token/AST node. Link: https://vimeo.com/87569637.

enter image description here

Here on the right there are values evaluated in each line.

enter image description here

Why don’t add code completion of variables in current scope and members of reference under the cursor?
enter image description here

And why not use it with the most popular library, AngularJS?

enter image description here

To do this, let’s use a helper function, toMetacircular:

app.controller('mainCtrl', toMetacircular(function ($scope) {
  $scope.teams = [
    {
      name: "Poland"
    },
    {
      name: "Germany"
    },
    {
      name: "England"
    }
  ];
  $scope.addGoal = function (team) {
    if (typeof team.goals === "number") {
      team.goals++;
    } else {
      team.goals = 1;
    }
  };
  $scope.removeGoal = function (team) {
    if (typeof team.goals === "number" && team.goals > 0) {
      team.goals--;
    } else {
      team.goals = 0;
    }
  }
}));

By the way, the IDE is written in AngularJS, and can be evaluated in the interpreter, so it is possible to introspect IDE while it executes.

What else could be done with it?

Thinking about development in general, the following use cases are possible:

  • use strict; is not implemented (yet) nor use asm;, but they could be. It is possible to make up own execution directives, like use pure; that will throw Exception every time assignment is used or closure reference is mutated. All that using interceptor without need of changing MetaES source code.
  • code coverage tools: this is almost for free, there should be some kind of receiver code that collects AST tokens and makes statistics based on what comes
  • automatic tests: for each metacicular function it is possible to collect what is its closure, arguments, what part of closure it mutates and what returns. All that information can be used to mock up environment that the function lives in and run it, for example:

    function surroundingFunction(){
        var a = 1;
        function functionThatShouldBeTested(b){ // in fact this function is not testable because of 'a' dependency, and it is not available outside 'surroundingFunction`
            return a + b;
        }
    }
    
    function testGenerator(fn, functionsNamesToAnalyse) {
        function interceptor() {
            // this function can discover execution of 'functionThatShouldBeTested', learn about ReferenceErrors (for example there will be one for "a") and change given environment to proper one, like metaes.evaluate(functionThatShouldBeTested, {a: 1}, ...)
        }
        return metaes.evaluate(fn, {}, {interceptor: interceptor});
    }
    
    testGenerator(surroundingFunction, ["functionThatShouldBeTested"]);
    

    This one seems to be not trivial and probably will require some research and experiments.

  • live coding (changing code while the application is still running): it would require to write function like setMetacircularFunctionSource(metacircularFunction, source) or better setBlockContents(block, newBlock) that would be quite easy. It simplest case it could destroy existing references and closure of mutated function, but there may be set up constrains on it.
  • refactoring systems: if AST nodes (Identifiers) A and B have the same reference to the JavaScript value, it means that they may be renamed. It may work cross files, cross VMs.
  • live coding on mobile devices without a need of restarting the app
  • full implementation of ES6, or even ES7. Not sure if it is 100% possible, but most of features should work, especially those concerning syntactic sugars and execution semantics
  • type hints: having AST node with given value, it is possible to rewrite JavaScript program source code to add hints like

    function a(b){}
    a("hello");

    into

    function a(/*string*/ b){}
    a("hello");

    or create some kind of “sourcemaps” for types that can be loaded by the IDE.

  • statistics for calls, operators, assigments or objects creation

    For example:

    function interceptor(e, value, env) {
        if(e.type === "FunctionExpression" && env.arguments && someCheckOnArguments(env.arguments, env.paramsNames)){
            // count executions of e
        }
    }
    var fn = metaes.evaluate("(function(x){return x*x})", {}, {interceptor: interceptor});

    Because MetaES is based on Esprima project, it means that AST tokens are keps in standard and it is easier to analyse them.

  • semantic searches (for example find every functions that were called at least 2 times with specified shape of arguments): this kind of search can use collected statistics from the previous point and use typical search algorithms, or even put JSONs into search database

  • who knows what else…?

Those above are just loose ideas, not much tests were made around them, but definitely possible.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: