topics: functional programming, concurrency, web-development, REST, dynamic languages

Tuesday, July 29, 2008

Syntax-highlighting in web pages

You shouldn't see this page really ;-) I've moved the blog to:

http://blog.higher-order.net

Please update your feed reader, and go to:

http://blog.higher-order.net/2008/07/29/syntax-highlighting-in-web-pages/

to read the post.

Monday, July 21, 2008

Moving blog...

I am moving my blog to: blog.higher-order.net.

Please go to that URL for further updates...


-- Karl

Friday, July 4, 2008

Manual code specialization:a poor-mans partial evaluation in JavaScript

Recall the object function that Douglas Crockford is promoting in his work on prototypal inheritance in JavaScript:

function object(p) {
function F(){}
F.prototype = p;
return new F();
}

The object function creates a new object which has the input object (p) as it's prototype.

On the comp.lang.javascript newsgroup Richard Cornford showed a functionally equivalent version which has better performance in general:


var object = (function(){
function F(){}
return function(p){
F.prototype = p;
return new F();
};
})();


In this version, all invocations of object share the same F which has its prototype mutated with each call. Cornford argues:


[The first version of 'object']... is an example of the process that clearly expresses what is being done, but is not particularly efficient as it creates a new - F - function each time it is executed, but all of those - F - functions are essentially identical. If this is to be done often then a more efficient approach would be to only create a single - F - function and put it where it could not be modified by external code.


Now, it is important to notice that in general one has to be careful when applying this technique to recursive functions as a variable mutation in one level of recursion may affect others. Also, if we were to put threads into JavaScript, this code would go from being thread-safe in the original form to non-thread safe in the optimized form. However, for now, this technique can be applied in performance-critical functions.


In fact, there is a general technique here that one might call code specialization via higher-order functions (which can be seen as a poor-mans form of partial evaluation). Here is a simple example of that general technique: The 'mk_tag' function creates the string for an html tag with a class attribute and a text-contents.


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


Using code specialization via higher-order functions (by currying), we can make specialized functions for writing e.g. 'div' tags, and specialized (faster) functions for making 'div' tags with certain classes. The trick is to compute as much as is possible with the given inputs before returning the specialized function:


//a curried version which specializes to it's input
function curried_mk_tag(tag_name) {
var tag_hd = '<'+tag_name+' class="',
tag_tail = '</'+tag_name+'>';

return function(clazz) {
var head = tag_hd+clazz+'">';
return function(contents) {
return head+contents+tag_tail;
}
}
}

var mk_div = curried_mk_tag("div")
var mk_div_green = mk_div("green")
var mk_div_blue = mk_div("blue")
mk_div_green("karl")//<-- "<div class="green">karl</div>"
mk_div_blue("karl")//<-- "<div class="blue">karl</div>"


This is elegant as functions can be reused, e.g., 'mk_div_green("karl");mk_div_green("krukow")'. But notice that it is more efficient than simply using a general currier (e.g., Diaz); essentially it is a form of manual partial evaluation.


I'll post some performance measurements in a later posting, but initial results show that we can reduce execution time by roughly 40% by using the sharing form of the object function.


More Examples


I'm not sure how many JavaScript programmers are familiar with this type of optimization. Here are a bunch of real-world examples where it can be applied:

Prototype - Ajax.request function

var Ajax = {//original
getTransport: function() {
return Try.these(
function() {return new XMLHttpRequest()},
function() {return new ActiveXObject('Msxml2.XMLHTTP')},
function() {return new ActiveXObject('Microsoft.XMLHTTP')}
) || false;
},

activeRequestCount: 0
};

The thing to notice here is that every time getTransport is called prototype will recompute which XMLHttp transport to use. However, the result of Try.these will always be the same in a particular run of Prototype, i.e., the showing of a page in one browser. So we might as well precompute which object is the correct one:

var Ajax = {//modified form
getTransport: Try.these(
function() { new XMLHttpRequest(); //test if it exists
return function() {return new XMLHttpRequest();}
},
function() { new ActiveXObject('Msxml2.XMLHTTP'); //test
return function() {return new ActiveXObject('Msxml2.XMLHTTP'); }
},
function() { new ActiveXObject('Microsoft.XMLHTTP');
return function() {return new ActiveXObject('Microsoft.XMLHTTP'); }
}),

activeRequestCount: 0
};


jQuery - attr function

//original...
attr: function( name, value, type ) {
var options = name;

// Look for the case where we're accessing a style value
if ( name.constructor == String )
if ( value === undefined )
return this[0] && jQuery[ type || "attr" ]( this[0], name );

else {
options = {};
options[ name ] = value;
}

// Check to see if we're setting style values
return this.each(function(i){
// Set all the styles
for ( name in options )
jQuery.attr(
type ?
this.style :
this,
name, jQuery.prop( this, options[ name ], type, i, name )
);
});
}


With jQuery we can't write a curried form as that would break compatability. However, we can still perform optimizations like what we had with the 'object' function. Notice that the function supplied to 'each' is created with each invocation of 'attr', you can also see a for-loop where a check to 'type' is made with each iteration. In our optimized version, attr chooses which inner function to give to 'each' by checking type first.

//modified form
jQuery.fn.attr = (function(){
var type,
options,
inner_type = function(i){
// Set all the styles
var t = type,
s = this.style;
for (var name in options ) {
jQuery.attr(s,
name,
jQuery.prop( this, options[ name ], t, i, name )
);
}
},
inner_no_type = function(i) {
for (var name in options ) {
jQuery.attr(this,
name,
jQuery.prop( this, options[ name ], null, i, name )
);
}

};

return function( name, value, t ) {
type = t;
options = name;
// Look for the case where we're accessing a style value
if ( name.constructor == String )
if ( value === undefined )
return this[0] && jQuery[ type || "attr" ]( this[0], name );

else {
options = {};
options[ name ] = value;
}

// Check to see if we're setting style values
return this.each(t ? inner_type : inner_no_type);
};
})();