101companies in jQuery and Javascript

jQuery is a library for DOM manipulation in Javascript. The DOM is a tree structured view of a HTML page and jQuery allows programming this tree with a “select and manipulate” style. Term-rewriting is a style of programming which adopts a “traverse and match” approach. Rules are written which fire on any matching value and all values in the program are checked against that rule during a traversal of data. While “select and manipulate” is not quite the same as “traverse and match” style, the overlap is considerable.

jQuery (and other libraries using the same “select and manipulate” approach) completely dominate web-application front-end development. Broadly speaking, “select and manipulate” is how modern user interfaces are programmed. Term-rewriting however is a niche idea that has seen very little mainstream take-up. It is my thesis that UI programming of a declarative scene graph is a natural fit with term-rewriting systems and that jQuery’s popularity is anecdotal evidence of this. In this article I show how some term-rewriting problems can be solved with jQuery. This is one step on the path to finding out if term-rewriting is a great way to program user interfaces.

101 Companies

101 companies is a corpus of code in many programming languages encoding a number of functions over a hypothetical company structure. Four of the functions are; total the salaries of all employees, cut the salaries in half company-wide, calculate the depth of the company’s hierarchy and check managers are given a greater salary (precedence) than anyone who works under them. The total and cut problems are typical term-rewriting tasks. They require all nodes of a certain type in a tree to either be re-written (as in cut) or contribute to an accumulated value (as in total). The depth and precedence problems are not so typical of term-rewriting, but do benefit greatly from being able to find the children of any node without reference to it’s type.

The Solution

One of the great benefits of programming with HTML/DOM and Javascript is that anyone can run your code in a browser. The solution we describe here is hosted on this site for you to play with. The static HTML is a single company structure and four buttons allow you to run the four example functions on the current state of the company. Each 101 companies problem is solved by a single javascript function, which uses jQuery for most of the heavy lifting.

The Code

The datatype

We don’t have a datatype definition for the company structure, it is simply encoded “sensibly” in HTML. However, there are many different ways we could have done this, so here we describe this “sensible” encoding.

All values in the system are encoded as div nodes, the types are DOM classes, so a “manager” node is a div with an attribute class="manager" and a salary node is a div with an attribute class="salary". Children of a value are div nodes nested below it. We don’t use collections, if there are more than one of something, each is a child of the surrounding value. For example, a department with three employees is

<div class="department" ...
  <div class="string" ...   <!-- department name -->
  <div class="manager" ...  <!-- department manager -->
  <div class="employee" ... <!-- first employeed -->
  <div class="employee" ... <!-- second employeed -->
  <div class="employee" ... <!-- third employeed -->
</div>

This encoding can’t work in general because it loses information, but in the company structure for this task all values which may be multiplies are the last children of their parent value, so we can find them when we need them.

total

Total calculates the total salary in the company, adding up all managers and all employees. This is completely trivial in jQuery since we can use a single selector to find all such salaries. We then loop over all salaries found, adding their values to an accumulator

function total(){
  var t = 0;
  $(".salary > .int").contents().each(function(){
    t = t + extractFloat(this);
  });  
  alert(t);
}

cut

Cut is similarly simple because again we can identify the values to be cut with a single selector. This time we modify those nodes to have new salary values.

function cut(){
  $(".salary > .int").contents().each(function(){
    var old = extractFloat(this);
    setFloat(this, old/2);
  });
}

extractFloat and setFloat are helper methods that allow us to manipulate the floating point number stored as a string in the DOM nodes (DOM nodes only hold strings or other DOM nodes).

depth

The depth task is also solved in a term-rewriting style. The depth function takes in a dom node (as a jQuery object) and looks for all departments within it, using a selector which picks all nodes with class="department". For each department it finds, it calculates the depth of all of its children. The result of this call is the maximum depth of all children plus one if this node is also a department. This particular encoding wastes effort because it calculates the depth of all departments at depth n, n times.

function depth(jqo){
  var depts = $(jqo).find(".department")
  var depths = jQuery.map(depts,function(a){return depth($(a));});
  var add = 0;
  if (jqo.attr("class") == "department"){add = 1;}
  if (depths.length == 0) {return add;} else {return  (Math.max.apply(null, depths) + add);}
}

precedence

The precedence function is not strictly coded in a term-rewriting style, but we use the fact that jQuery can get all the children of a node to allow a concise description of an explicit traversal of the DOM. The check_precedence function takes two arguments, the maximum allowed salary for all employees below this point in the DOM and the node in the DOM that we are inspecting. You will notice that extracting the salary value from a node is somewhat … messy. I have attempted to stick with jQuery commands rather than bringing in other approaches and jQuery is not well suited to the kind of “by-hand” traversal needed for this job.

function check_precedence(m,jqo){
  if (jqo.attr("class") ==  "department") {
    var manager_sal = parseFloat(jqo.children().slice(1,2).children().slice(2,3).first().text())
    return allTrue(jqo.children().slice(2).map(function(){return check_precedence(manager_sal, $(this))}));
  }
  else if (jqo.attr("class") ==  "employee") {
    var employee_sal = parseFloat(jqo.children().slice(2,3).first().text());
    return (m > employee_sal);
  }
  else if (jqo.attr("class") ==  "manager") {
    var manager_sal = parseFloat(jqo.children().slice(2,3).first().text());
    return (m > manager_sal);
  }
  else { 
    return allTrue(jqo.children().map(function(){return check_precedence(m, $(this))}));
  }
}

If a department is found, we set that department’s manager’s salary to the new maximum salary allowed and traverse into each child. If an employee or manager is found we check their salary does not exceed the maximum allowed. For all other nodes we simply traverse into each child node.

Note

I use jQuery every now and then when I have to do web-development, and I have used it in some big projects, but I am by no means an expert. I will be very happy to accept suggestions on how these functions can be better encoded with jQuery.

Repository

The latest version of the code in this article can be found in a dedicated repository.