Higher Order Blog

The purpose of this posting is to show that is is possible to create an online partial evaluator for JavaScript, written also in JavaScript. As far as I know, this has been not been done before. This post is the first in a series describing the inner workings of Jeene. A what? A partial evaluator (or program specializer) is a program which takes two inputs: another program and an environment mapping variables to values; it outputs a specialized (i.e., more efficient) version of the input program with respect to the environment. One can think of a partial evaluator as a mix between an interpreter and a compiler: it interprets the static parts of the program and emits code for the dynamic parts. For a simple example of code specialization, consider the following function for creating a string corresponding to an HTML tag:

var mk_tag = function(tag_name,clazz,contents) {
   return '<'+tag_name+' class="'+clazz+'">'+contents+'</'+tag_name+'>';
};

If we are only interested in making 'div' tags with a class of 'green' then a more efficient version would be:

var mk_div_green = function(contents) {
   return '<div class="green">'+contents+'</div>';
};

since it would require fewer string concatenations per call. We can think of 'mk_div_green' as a version of 'mk_tag' which is specialized for writing 'div' tags with a class of 'green'. A partial evaluator for JavaScript could automatically derive the 'mk_div_green' function from the 'mk_tag' function.

This is exactly what we can do with the evaluator in this posting.

//This code actually works ;-)
Function.prototype.specialize = net.higherorder.jeene.Jeene.make();

var mk_tag = function(tag,clz,cont) {
   return "<"+tag+" class='"+clz+"'>"+cont+"</"+tag+">";
};


var mk_div_green = mk_tag.specialize({tag:'div', clz: 'green'});



mk_div_green("Pratt rocks!");
//result: <div class='green'>Pratt rocks!</div>


mk_div_green.toSource ? mk_div_green.toSource() : mk_div_green.toString();
//result:
//(function (cont) {return ("<div class='green'>" + cont) + "</div>";})

This last line, shows that the output function is much more efficient than what is created by general JavaScript curriers which have been seen before: these functions merely wait evaluating the function until all parameters are supplied; instead, a partial evaluator will create specialized function taking advantage of the information given. The first goal is for the partial evaluator to process any function written in an extension of "simplified JavaScript" (a subset of full JavaScript corresponding to what Crockford calls the "good parts"). This partial evaluator will have a number of useful features: it

• can easily be extended to full JavaScript;
• is written in simplified JavaScript (think Futamura projections);
• is a fast extension of Douglas Crockford's Pratt parser;
• because functions implement the toString method, it can be run on dynamically generated functions (e.g., a specialized function can be further specialized);
• can be embedded in any full JavaScript program as long as it is only used to specialize functions which are syntactically in simplified JavaScript;

I have started a new open source project, Jeene, which aims to create an efficient partial evaluator for full JavaScript that works in any ECMAScript 3 compliant implementation (e.g., all major browsers, Rhino, TraceMonkey, V8 etc). Right now the project is at a very early stage; a proof of concept, for example it cannot specialize itself. Let me know if you are interested in contributing: I will use a 1 patch threshold like Rubinius: if you submit one patch which is accepted, you get commit rights. Stay tuned here for more information about how Jeene is designed and implemented.