Vjeux

JSLint imposes us to do manual hoisting of variables. What if we did it but at the end of the function? 😛

function print_array (array) {
  var length = array.length;
  for (var i = 0; i < length; ++i) {
    var elem = array[i];
    console.log(elem);
  }
}

function print_array (array) {
  var length, elem, i;
 
  length = array.length;
  for (i = 0; i < length; ++i) {
    elem = array[i];
    console.log(elem);
  }
}

function print_array (array) {
  length = array.length;
  for (i = 0; i < length; ++i) {
    elem = array[i];
    console.log(elem);
  }
 
  var length, elem, i;
}

I have no idea if that could be of any use but it amused me 🙂

Writing a parser for a structured binary format such as a 3D model is extremely annoying. You have first to declare your file structure, and then go over every structure again and make a proper code to parse it. This is mainly caused because the lack of introspection of C/C++ and for performance reasons.

In Javascript, it does not have to be that way! jParser is a class that only asks you to write a JSON version of the structure. It will parse the file automatically for you.

Here is an example of what you could write with jParser:

var description = {
  header: {
    magic: ['string', 4],
    version: 'uint32'
  },
  model: {
    header: 'header'
  }
};
 
var model = new jParser(file, description).parse('model');
console.log(model);
// {
//   header: {
//     magic: 'MD20',
//     version: 272
//   }
// }

Description

Standard Structure

The description object defines blocks that needs to be parsed. In the previous example, we define two blocks header and model where each block is a list of labelled sub-blocks.

Default blocks such as int32, char, double are provided by jDataView.

This organization makes it easy to reproduce C structures. Let's see the description of the BMP format.

// Javascript Description
header: {
  header_sz: 	'uint32',
  width: 	'int32',
  height: 	'int32',
  nplanes: 	'uint16',
  bitspp: 	'uint16',
  compress_type:'uint32',
  bmp_bytesz: 	'uint32',
  hres: 	'int32',
  vres: 	'int32',
  ncolors: 	'uint32',
  nimpcolors: 	'uint32'
}

// C Structure
typedef struct {
  uint32_t header_sz;
  int32_t  width;
  int32_t  height;
  uint16_t nplanes;
  uint16_t bitspp;
  uint32_t compress_type;
  uint32_t bmp_bytesz;
  int32_t  hres;
  int32_t  vres;
  uint32_t ncolors;
  uint32_t nimpcolors;
} BITMAPINFOHEADER;

Reference Structures

As you already noticed, instead of using basic blocks, we can use our own blocks. In the following example, uvAnimation uses animationBlock that uses nofs:

nofs: {
  count: 'uint32',
  offset: 'uint32'
},
 
animationBlock: {
  interpolationType: 'uint16',
  globalSequenceID: 'int16',
  timestamps: 'nofs',
  keyFrame: 'nofs'
},
 
uvAnimation: {
  translation: 'animationBlock',
  rotation: 'animationBlock',
  scaling: 'animationBlock'
}

Functions

At this point, it is possible to express any C structure and parse files that could be loaded using a simple read. We now need to integrate a logic within our parser using anonymous functions.

Recursive Parsing

It is a common operation to read consecutive blocks. It is possible to make an array block that takes a block name and a count. It parses all theses blocks and aggregates them into a Javascript array.

array: function (type, length) {
  var array = [];
  for (var i = 0; i < length; ++i) {
    array.push(this.parse(type));
  }
  return array;
},

In order to call a function, we use an array literal where the first element is the block name and the rest are the arguments. We can easily define float[234].

float2: ['array', 'float', 2],
float3: ['array', 'float', 3],
float4: ['array', 'float', 4]

We can use the array block to build a string block. We parse an array of char and join it.

string: function (length) {
  return this.parse(['array', 'char', length]).join('');
},
 
filename: ['string', 32]

Seek & Tell

In the World of Warcraft models, there is a small structure called nofs that tells us "There are [count] consecutive [type] at [offset]". We build a struct block in order to parse this pattern. It will use seek and tell to navigate through the file.

nofs: {
  count: 'uint32',
  offset: 'uint32'
},
 
struct: function (type) {
  // Read the count & offset
  var nofs = this.parse('nofs');
 
  // Save the current offset & Seek to the new one
  var pos = this.tell();
  this.seek(nofs.offset);
 
  // Read the array
  var result = this.parse(['array', type, nofs.count]);
 
  // Seek back & Return the result
  this.seek(pos);
  return result;
},
 
triangles: ['struct', 'uint16'],
properties: ['struct', 'boneIndices']

Code

The code that powers this is only 30 lines long (70 including the standard integral types). It just handles each possible data type.

parse: function (description, param) {
  var type = typeof description;
 
  // Function
  if (type === 'function') {
    return description.apply(this, [this.param].concat(param));
  }
 
  // Shortcut: 'string' == ['string']
  if (type === 'string') {
    description = [description];
  }
 
  // Array: Function Call
  if (description instanceof Array) {
    return this.parse(this.description[description[0]], description.slice(1));
  }
 
  // Object: Structure
  if (type === 'object') {
    var output = {};
    for (var key in description) {
      if (description.hasOwnProperty(key)) {
        output[key] = this.parse(description[key]);
      }
    }
    return output;
  }
 
  throw new Error('Unknown description type ' + description);
}

Conclusion

This little parser is an example of how to extensively use all the dynamic characteristics of Javascript such as Object Literals, Anonymous Functions and Dynamic Typing in order to build a powerful and easy to use tool.

I don't want to release the library just yet as I need to explore more use cases and find elegant solution for them too. But I hope it will give you inspiration to use full Javascript power.

Demo

You can see it in action in my 0.1% completed Javascript WoW Model Viewer demo. The two following files are important:

• m2.js: The model description
• jParser.js: The parsing library

During the course "Introduction to Model Checking" by Alexandre Duret-Lutz we've been assigned to create a Binary Decision Diagram library. Contrary to most people, I've been writing mine in Javascript instead of C++. Overall it is running slower but by an acceptable factor (around x5).

Display

I've written a BDD display using the graph library called Dracula which is built on-top of RaphaëlJS. The API of the lib is really neat but there are only 2 available node layout algorithms and none of them really fit my needs. I'd love to have the ones available in GraphViz.

In order to enter a formula, I've written a small parser that accepts most common binary operations. The little dice gives you some random formula. Also, on the left, you have all the evaluations that satisfy your formula.

Use Case

Binary Decision Diagram are used in Boolean Satisfiability Problem and Model Checking. As a benchmark example, we use the BDD to solve the 8-Queens problem.

A version using web-workers is available. However, using more than one worker will be slower as the cost of communication (through JSON serialization) is really high (hundreds of thousands nodes). You can also try to use a random ordering for the variables, but beware, the execution time varies a lot (up to x100 for the fastest/slowest)!

Conclusion

It was a really fun project to do. You can view the sources and probably use them as a base if you ever need to use a BDD in your life 😛

During the last 6 months as part of the LRDE (EPITA Research & Development Lab), I've been working on Climb, a Common Lisp image processing library. I've written a report and presented it. You can download the slides and report.

Climb - Chaining Operators & Component Trees

Abstract: Climb is a generic image processing library designed to be used for rapid prototyping. The implementation of two component trees algorithms impacts Climb in several ways: the definition of values is extended, new site sets are added and debugging utilities are improved.

A detour is taken to understand the Method Chaining design pattern popularized by the Javascript jQuery library. The pattern is adapted to both the image processing domain and Common Lisp and is extended to introduce a parallel notation as well as better control flows.

Everywhere on the web we read that Javascript has prototypal inheritance. However Javascript only provides by default a specific case of prototypal inheritance with the new operator. Therefore, most of the explanations are really confusing to read. This article aims to clarify what is prototypal inheritance and how to really use it on Javascript.

Prototypal Inheritance Definition

When you read about Javascript prototypal inheritance, you often see a definition like this:

When accessing the properties of an object, JavaScript will traverse the prototype chain upwards until it finds a property with the requested name. Javascript Garden

Most Javascript implementations use __proto__ property to represent the next object in the prototype chain. We will see along this article what is the difference between __proto__ and prototype.

The following code shows how the Javascript engine retrieves a property (for reading).

function getProperty(obj, prop) {
  if (obj.hasOwnProperty(prop))
    return obj[prop]
 
  else if (obj.__proto__ !== null)
    return getProperty(obj.__proto__, prop)
 
  else
    return undefined
}

Let's take the usual class example: a 2D Point. A Point has two coordinates x, y and a method print.

Using the definition of the prototypal inheritance written before, we will make an object Point with three properties: x, y and print. In order to create a new point, we just make a new object with __proto__ set to Point.

var Point = {
  x: 0,
  y: 0,
  print: function () { console.log(this.x, this.y); }
};
 
var p = {x: 10, y: 20, __proto__: Point};
p.print(); // 10 20

Javascript Weird Prototypal Inheritance

What is confusing is that everyone teaches Javascript prototypal inheritance with this definition but does not give this code. Instead they give something like this:

function Point(x, y) {
  this.x = x;
  this.y = y;
}
Point.prototype = {
  print: function () { console.log(this.x, this.y); }
};
 
var p = new Point(10, 20);
p.print(); // 10 20

This is completely different from the code given above. Point is now a function, we use a prototype property, the new operator. What the hell!?

How new works

Brendan Eich wanted Javascript to look like traditional Object Oriented programming languages such as Java and C++. In those, we use the new operator to make a new instance of a class. So he wrote a new operator for Javascript.

• C++ has the notion of constructor, that initializes the instance attributes. Therefore, the new operator must target a function.
• We need to put the methods of the object somewhere. Since we are working on a prototypal language, let's put it in the prototype property of the function.

The new operator takes a function F and arguments: new F(arguments...). It does three easy steps:

1. Create the instance of the class. It is an empty object with its __proto__ property set to F.prototype.
2. Initialize the instance. The function F is called with the arguments passed and this set to be the instance.
3. Return the instance

Now that we understand what the new operator does, we can implement it in Javascript.

     function New (f) {
/*1*/  var n = { '__proto__': f.prototype };
       return function () {
/*2*/    f.apply(n, arguments);
/*3*/    return n;
       };
     }

And just a small test to see that it works.

function Point(x, y) {
  this.x = x;
  this.y = y;
}
Point.prototype = {
  print: function () { console.log(this.x, this.y); }
};
 
var p1 = new Point(10, 20);
p1.print(); // 10 20
console.log(p1 instanceof Point); // true
 
var p2 = New (Point)(10, 20);
p2.print(); // 10 20
console.log(p2 instanceof Point); // true

Real Prototypal Inheritance in Javascript

The Javascript specifications only gives us the new operator to work with. However, Douglas Crockford found a way to exploit the new operator to do real Prototypal Inheritance! He wrote the Object.create function.

Object.create = function (parent) {
  function F() {}
  F.prototype = parent;
  return new F();
};

This looks really strange but what it does is really simple. It just creates a new object with its prototype set to whatever you want. It could be written as this if we allow the use of __proto__:

Object.create = function (parent) {
  return { '__proto__': parent };
};

The following code is our Point example with the use of real prototypal inheritance.

var Point = {
  x: 0,
  y: 0,
  print: function () { console.log(this.x, this.y); }
};
 
var p = Object.create(Point);
p.x = 10;
p.y = 20;
p.print(); // 10 20

Conclusion

We have seen what prototypal inheritance is and how Javascript implements only a specific way to do it.

However, the use of real prototypal inheritance (Object.create and __proto__) has some downsides:

• Not standard: __proto__ is non-standard and even deprecated. Also native Object.create and Douglas Crockford implementation are not exactly equivalent.
• Not optimized: Object.create (native or custom) has not yet been as heavily optimized as the new construction. It can be up to 10 times slower.

Some further reading:

• Douglas Crockford: Prototypal Inheritance
• MDC Documentation: __proto__
• John Resig: getPrototypeOf
• Javascript Garden: Object.prototype
• Dmitry Shoshnikov: OOP: ECMAScript Implementation
• Angus Croll: Understanding Javascript prototypes
• Yehuda Katz: Understanding JavaScript Function Invocation and “this”

Bonus

If you can understand with this picture (from the ECMAScript standard) how Prototypal Inheritance works, you get a free cookie!