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.

Moving blog...

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

Please go to that URL for further updates...


-- Karl

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

fun with with - part II

Here is one implementation of a function 'scope' which lets us write code like:

with (scope({ sn : dk.ourclient.supernavigator, 
              u : com.trifork.utils})) {
  
            
  with(sn) include()(model,view)
  with(u) include()(Format)
  
  run(function(mod,view,fm){
        //do stuff
  });
}

The function that is given to 'run' will be called with variable 'mod' bound to dk.ourclient.supernavigator.model, 'view' bound to dk.ourclient.supernavigator.view and with 'fm' bound to com.trifork.utils.Format.

Note that it is important that the function given to run is executed in a scope that does not see the functions introduced by the outer 'with' statement - this would be dangerous. In order t acheive this, the variable 'run' 'include' and 'sn' and 'u' are written so that they can only be used one time: once called they delete the reference to them selves. Similarly, suppose com.trifork.utils has a property 'include' then if we did:

 with(u) include()(Format,include)

we would expect the 'include' from u, and not the include function from our "package DSL".

This code does that (though I haven't tested it thoroughly):

function scope(spec){
    if (spec.hasOwnProperty('module')) {
        throw new Error('Reserved word "module" may not be used.');
    }
    if (spec.hasOwnProperty('run')) {
        throw new Error('Reserved word "run" may not be used.');
    }
    
    var objects = [];
    
    for (var p in spec) if (spec.hasOwnProperty(p)) {
       spec[p] = object(spec[p])
       spec[p].include = function(){
          delete this.include;
          return function(){
              for (var i=0,N=arguments.length;i<N;i++){
                  objects.push(arguments[i]);
              }  
          };    
       };
    }
    spec.run = function(fn){
          for(var p in this) {if (this.hasOwnProperty(p)) {
              delete this[p];         
          }}
          return fn.apply(objects[0],objects);
    }
    return spec;
}

fun with with

WARNING: After reading this blog you may start playing around with the evil 'with' statement in JavaScript. It's actually quite fun, but note that I'm not encouraging it's use in general.

In a previous blog I advocated the use of namespacing in JavaScript programs. To support namespacing I presented a pair of functions 'namespace' and 'using'. The former introduces a namespace, e.g.,

 namespace({
     com:
       trifork:
         tribook: ['model','view','controller']});

ensures that object 'com' exists with a property 'trifork' which in turn has a property 'tribook', etc. The using function brings such a 'package' or 'module' object into scope. For example

 using(com.trifork.tribook.model,
       com.trifork.tribook.view).run(function(model,view){

   var meet = new model.Room('meeting 1');

 });

Now, in the last couple of months I have been working in several projects using these functions, and I feel they have really helped me structure the JavaScript code -- one project has several thousands of lines of JS code structured in files and modules mirroring the package structure (i.e., dk.ourclient. ...). In these projects, a usage pattern occurs. Many files started:

namespace('dk.ourclient.supernavigator.controller');

using(dk.ourclient.supernavigator.view,
     dk.ourclient.supernavigator.model,
     dk.ourclient.supernavigator.controller).run(function(v,m,c) {

     c.ContactController = function(spec) {
       //... m.xxx, v.yy
     };

});

I was annoyed with the WET (i.e. as opposed to DRY) repeated occurrence of 'dk.ourclient.supernavigator'. One alternative pattern would be:

namespace('dk.ourclient.supernavigator.controller');

using(dk.ourclient.supernavigator).run(function(sn) {
     var m = sn.model,
         c = sn.controller,
         v = sn.view;

     c.ContactController = function(spec) {
       //... m.xxx, v.yy
     };

});

Which is what we started using. However I was looking at an alternative way to bring sub-modules or packages into scope. I experimented with several forms; here is one of them.


You can think of the following as a small DSL for importing or using package objects in javascript (note, part of the DSL is the JavaScript with statement). It uses a form: (where 'obj' is a package object to be used)

with(f(obj)) {
   //code
}

By introducing an intermediate function 'f' and using 'f(obj)' instead of 'obj' itself, we can avoid some of the issues with 'with'.

Question: Does the following code make sense: (with an appropriate definition of the 'scope' function, this is valid working JS code!)

with (scope({ sn : dk.ourclient.supernavigator, 
              u : com.trifork.utils})) {
  
            
  with(sn) include()(model,view)
  with(u) include()(Format)
  
  run(function(mod,view,fm){
        //do stuff
  });
}

What does it do? Wait and think before you read on...

I will post an update with code that makes this work later. Hope this is good fun to you, but note that in our project we used the simpler form mentioned previously:

using(dk.ourclient.supernavigator).run(function(sn) {
     var m = sn.model,
         c = sn.controller,
         v = sn.view;

     c.ContactController = function(spec) {
       //... m.xxx, v.yy
     };

});

and I'm sure that Crockford would prefer this too ;-).

/Karl

HTML-free Web-applications with ExtJS [Designing client/server web-apps, Part I, Section III]

Recap

This article is Part I, Section III of a series discussing the development of client/server web-applications where the client is written in JavaScript and running in a browser. The first article discusses the use of namespacing in large JavaScript applications; it can be found here. The second article gives a high-level overview of our design, and introduces the model part of Model-View-Controller.

This third section of Part I discusses the View in MVC, introducing the concept of HTML-free views in web-applications.

Below is a sample image of the GUI for our client application. It is no so much the application that it interestering, but rather it's design and implementation.

TriBook - a simple room-booking client application

Click for large image


The view package object
The package object com.trifork.tribook.view contains all the objects and constructor functions related to the graphical user interface of the client. Particularly, it contains a special singleton object, View, which is an observable object, observed by the Controller; view objects also observe the model, reacting to and reflecting changes.

Apart for the singleton View, the package also contains constructor functions for the various components that exist in the client GUI. In our example room-booking application, TriBook, we have a few such components:

• com.trifork.tribook.view.RoomForm
  a form-component for entering query data about available rooms


• com.trifork.tribook.view.RoomReserveView a list component that shows a list of rooms to reserve at certain times


• com.trifork.tribook.view.RoomView a list component showing the list of available rooms that match the current query in the RoomFoom component.

The View object composes the view using these three components. For example, View contains this code:

namespace("com.trifork.tribook.view");
using(com.trifork.tribook.view).run(function(v) {
 
  v.View = (function() {//singleton module pattern
   var view = new Ext.util.Observable(),
       events = ['addreservation','removereservation','query','reserve'];
   
   Ext.each(events,function(e){view.addEvents(e);});
  
   return Ext.apply(view, {
       init : function() {
     
         Ext.each(['search','book','result'], function(id){
              Ext.fly(id).boxWrap();
         });//make a nice graphical box on dom el
         
         var roomform = v.RoomForm();
         roomform.render('search-inner');
     
         var roomview = v.RoomView();
         roomview.render('result-inner');
     
         var roomreserve = v.RoomReserveView();
         roomreserve.render('book-inner');
    
       }//some details omitted here
     });
  })();
});

The code constructs the custom components and tell them to render themselves to various dom elements, e.g., 'search-inner'.

The other important role of View is to define a collection of 'logical' or 'application' or 'domain' events, which the controller (and other view components) may react to. The application events in our room booking app are defined in the events array, e.g., 'query' fires when the user changes the current query in the RoomForm, representing the action of searching for available rooms in a certain time period. 'addreservation' adds a room and a period to the queue of rooms to be reserved (represented as a com.trifork.tribook.model.Reservation object). 'reserve' represents the event that the user wants to actually commit to reserving the rooms in the queue of reservations.

The View object itself doesn't actually contain the code that fires the application events; this code is in the individual view components. E.g., RoomForm fires the 'query' event on View in response to the user changing the form field values (if they validate).

Another way of thinking of this is in terms of event bubbling. Just as DOM events bubble up the dom tree, one can think of the application event 'query' bubbling from the RoomForm object to its parent, the View object. In this way, interested listerners can listen centrally on View and doesn't have to be aware of the structure (i.e. the individual components) of the GUI.

Regarding the use of machine code... (HTML)
The client UI is written without using HTML.

Actually that last statement is not true... However, using ExtJS with say YUI as a base, one has a multitude of high-quality, easily composable and configurable GUI components that are much more high-level than the ubiquitous text markup language. In our view markup is used in two ways: for highly specialized view components and for representing page structure at a high-level. For the latter, the HTML (declaratively) describes the logical placement of three components at the same level: a form, a component for showing a list of rooms, and a component for showing a list of reservations. That is it. The divs are transformed into specialized components using JavaScript. For the second point (highly customized components) we still leverage JavaScript (specifically ExtJS components, XTemplate and DataView).


First let us take a look at a form for entering room search criteria. It's a pretty standard web application form except that it is built entirely in JavaScript. The components are so standard that we just need to compose the fields and specify validation and event handling; no HTML or CSS involved. Here's a sample image:

TriBook - search form with input assistance and validation





Lets look at some code. One interesting thing to notice in the code below is that although we are writing UI code in JavaScript, the ExtJS framework allows for a highly declarative specification of UI components using configuration object literals (the *Cfg variables below).

namespace("com.trifork.tribook.view");

using(com.trifork.tribook.view).run(function(view){
 
 var model = com.trifork.tribook.model,
     ctrl = com.trifork.tribook.controller;
 //utility fields and functions defined below
 var dateField,fromField,untilField,minField, getCurrentPeriod, filter;

 view.RoomForm = function() {
       var dateCfg = {
            id: 'roomform.date',
            xtype:'datefield',
            fieldLabel: 'Date',
            format: 'd/m/y',
            name: 'date',
            listeners: {
               'change': filter,
            'select': filter
            }
           },
           fromCfg = {
            id: 'roomform.from',
            xtype:'timefield',
            fieldLabel: 'Free from',
            name: 'time',
            format: 'H:i',
            increment: 30,
            minValue: '09:00',
            maxValue: '17:00',
            listeners: {
                  'change': filter,
                  'select': filter
            }
           }, 
           untilCfg = { ... },
           minCfg = {
             id: 'roomform.min',
             fieldLabel: 'Min. size',
             name: 'size',
             validator: function(v) {
                 if (isNaN(Number(v))) {
                    return 'Please enter the least number of people that must be supported by the room.';
                 }
                  return true;
             },
           listeners: {
              'change': filter
           }
     };
  
 
     var form = new Ext.FormPanel({
         labelWidth: 75, // label settings here cascade unless overridden
         frame:false,
         bodyStyle:'padding:5px 5px 0',
         width: 310,
         defaults: {width: 200},
         defaultType: 'textfield',
         items: [dateCfg , fromCfg, untilCfg, minCfg],
         listeners: {
          'render': function(){
              dateField = Ext.getCmp('roomform.date');
              fromField = Ext.getCmp('roomform.from');
              untilField = Ext.getCmp('roomform.until');
              minField = Ext.getCmp('roomform.min');     
          }
         }
       });
 
       model.Model.rooms.get().on('load',filter);
  
       return form;
     };
        //detail omitted
});

The filter function that is called when ever the form changes will validate the form; if valid, an event 'query' is fired signaling that the user has queried for available rooms. Notice that the 'query' event carries a parameter, a domain object called a RoomQuery that captures the essence of the query.

...
function filter() {
   var p = getCurrentPeriod(),
       v = +minField.getValue(); 

   if (p === null || isNaN(v)) {//Not valid
 return;
   }
   
   view.View.fireEvent('query', new model.RoomQuery({
      start_at: p.start,
      end_at: p.end,
      min_size: v
   }));
}
...

The main points...

• Events and event bubbling. Our application is event driven. Just like dom events bubble up the dom tree and listernes can listen at different levels, our application event bubble up the component tree, e.g., from the RoomForm to the View object. This principle is useful for decoupling for two reasons: (1) observers can attach listerners at different levels of abstraction, e.g. other view objects which may know about the view structure may listen directly on a view component, while listeners in the controller package object may listen directly on the View object, not caring which concrete UI component is the source of the event. (2) individual UI components can focus on mapping dom events to application events with domain concept parameters; they need not be concerned with how those application events are handled.


• HTML-free views. Except for highly customized components, the view is HTML free. This lets us work at a much higher level of abstraction, i.e., configuring and composing components rather than creating markup tags, and manipulating the dom tree.


• ExtJS (once again). In version 2 of Ext, components can be specified mostly in a declarative manner which is much more succinct and less error prone. Components are highly customizable and extensible. Even when low-level specialized components are needed ExtJS has support. The brilliant function Ext.DataView combined with Ext.XTemplate provides a powerful tool for presenting lists with tailored HTML; the lists are neatly abstracted with the Ext.data.Store function. You must really check out that trinity!

There is still HOPE for templates...

I am interested in JavaScript. One reason I got interested in JavaScript was a discussion about templating languages with Trifork colleagues Joakim and Kresten (or perhaps it would be more correct to say that we were discussing better ways of implementing the View-part of traditional Model-View-Controller web applications). I ended up liking the idea that the best approach was to dump templates altogether and write the whole client application in a high-level language, i.e., JavaScript, rather than using any of the existing templating languages. Hence, the interest in JavaScript. In fact, I got so interested in JavaScript that I forgot all about templating languages again. That was until recently when I remembered the original discussion, and started thinking about templating again. It was actually some good fun thinking about this -- who would have thought? Anyway, enough about me... Here is the idea.

The language is called HOPE Templates, or just HOPE. The acronym is for Higher-Order Partially Evaluated Templates. Obviously two important ideas are (i) higher-order: templates are a type of functions and the input and output of these functions can be templates; (ii) templates are partially evaluated, meaning that general templates with multiple inputs can be specialized with respect to each input.

That's it! These two powerful concepts are the core of the language. I'll illustrate the HOPE idea through a series of examples.

Simple Template 1:

Hello World!

Any string is a (zero-order) template; when applied, the above template always outputs 'Hello World!'

Simple Template 2:

HelloTpl = λx.Hello x!
RuleTpl = λx.x, you rule!

This defines two named templates, e.g., 'HelloTpl' takes an input 'x' and outputs "Hello x!", where 'x' is replaced with what-ever the template is applied to. Note the use of λ for template abstraction -- this is to suggest the higher-order functional nature of templates (and it is concise too).

An important concept here is that any text in the program that is not a bound variable (or any language syntax) is just zero-order templates. Conversely, if a variable is bound by a lambda, then its occurrence means to 'insert the input template here'. We allow the α-conversion from the lambda calculus so that λx. Hello x! is the same as λy. Hello y!. This means that we can insert/apply templates without having to escape characters: if there is a clash we can always just α-convert.

So far nothing new.

Simple Template 3:

ConcatTpl = λx,y,arg. (x arg)(y arg)

This template is meant to be used as a higher-order template that takes two templates (x,y) and an argument (arg). It applies each template to the argument.

Example 1:

ConcatTpl HelloTpl RuleTpl ~
  λarg.(HelloTpl arg)(RuleTpl arg) ~
     λarg.(Hello arg!)(arg you rule!)

The application of a template is left-associative so the first line is (ConcatTpl applied to HelloTpl) applied to RuleTpl. The ~ is an equivalence relation invented for this blog posting. You can think of it as meaning 'is the same template as'. I haven't defined it formally, but it must be similar to the lambda calculus conversion rules.

I'm not sure about brackets yet. They are needed for grouping and are definitely not part of the output.

Partial evaluation. Consider the following template:

Tag = λname,clz,content.
<name class="clz">
  content
</name>

This is just a normal curried function so we have

Tag div ~
λclz,content.
<div class="clz">
  content
</div>

However, we can do also partial evaluation (application with respect to one or more named arguments). For example

Tag clz:selected ~
λname,content.
<name class="selected">
  content
</name>


Now I think it starts to get interesting ;-)

A final concept I would like is something like the following called operator definition. A simple definition could be:

Mine = λx.I own x!

An operator definition generalizes a simple definition by having variables on both sides of the equality symbol. For example:

x.y = λx,y,z.<x class="y">z</x>

This does several things. First it defines a named template '.', like

. = λx,y,z.<x class="y">z</x>

But it does more! It also allows for the following syntactic sugar: .highlight meaning

.highlight ~λx,z.<x class="highlight">z</x>

and e.g.

div.highlight ~ λz.<div class="highlight">z</div>

so

div.highlight HOPE! ~ <div class="highlight">HOPE!</div>


Combined with a notion of default values, this looks similar to something we seen before and like ;-), but I believe that it is much more powerful!

Here are a few notes to myself:

• How do you implement it efficiently? I don't know. But on my language get-to-know-better list is Scheme, and it think this might be a good candidate language to use when implementing this. HOPEfully I will blog about that one day.


• Dealing with data: lists and maps. Pattern-matching on data types. How much do we need?


• Modules and imports... namespacing


• whitespace


• flexible language syntax: an idea where the language syntax can be redefined locally in case it overlaps too much with the template content...


• This could make templating fun again ;-), but remember to stay within templating.