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.

jParser is available on Github. It works on both NodeJS and Browser.

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:

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.

Note: __proto__ is non-standard and should not be used in your code. It is used in the article to explain how Javascript inheritance works.

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:

Bonus

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

C++ has a new standard called C++0x (Wikipedia, Bjarne Stroustrup) that includes many interesting features such as Lambda, For Each, List Initialization ... Those features are so powerful that they allow to write C++ as if it was Javascript.

The goal of this project is to transform C++ into Javascript. We want to be able to copy & paste Javascript into C++ and be able to run it. While this is not 100% feasible, the result is quite amazing.

This is only a prototype. In about 600 lines of code we manage to make the core of the Javascript language.

You can view the source and compile examples at the JSPP Github Repository.

JSON

The Javascript Object notation can be emulated thanks to C++0x initialization lists and a bit of operator overload hackery. _ has an operator [] that returns a KeyValue object, that has an operator = overload that fills both keys and values. For each value of the initialization listL If that's an objet, it is treated like an Array (add one to the lenght and use the length as key). If that's a KeyValue, both key and value are set.

There is an ambiguity with nested initialization lists, we use _() to cast the list into an Object. It is probably possible to fix it.

C++

var json = {
    _["number"] = 42,
    _["string"] = "vjeux",
    _["array"] = {1, 2, "three"},
 
    _["nested"] = _({
        _["first"] = 1
    })
};
 
std::cout < < json;
// {array: [1, 2, three], nested: {first: 1},
//  number: 42, string: vjeux}
Javascript

var json = {
    "number": 42,
    "string": "vjeux",
    "array": [1, 2, "three"],
 
    "nested": {
        "first": 1
    }
};
 
console.log(json);
// {number: 42, string: 'vjeux',
//  array: [1, 2, three], nested: {first: 1}}

Function

C++0x added lambda to the language with the following syntax: [capture] (arguments) -> returnType { body }. function is a macro that transforms function (var i) into [=] (Object This, Object arguments, var i) -> Object. This allows to use the Javascript syntax and let us sneakily add the this and arguments magic variables.

C++ is strongly typed and even lambdas have types. We can overload the Object constructor on
lambda arity and have a typed container for each one. Then, we overload the () operator that will call the stored lambda. We we carefully add undefined values for unspecified arguments and fill the This and arguments variables.

In Javascript, when a function does not return a value, it returns undefined. Sadly, we cannot have a default return value in C++, you have to write it yourself.

Since everything must be typed in C++, we have to add var before the argument name.

C++

var Utils = {
  _["map"] = function (var array, var func) {
    for (var i = 0; i < array["length"]; ++i) {
      array[i] = func(i, array[i]);
    }
    return undefined;
  }
};
 
var a = {"a", "b", "c"};
std::cout << a;
// [a, b, c]
 
Utils["map"](a, function (var key, var value) {
  return "(" + key + ":" + value + ")";
});
std::cout << a;
// [(0:a), (1:b), (2:c)]
Javascript

var Utils = {
  "map": function (array, func) {
    for (var i = 0; i < array["length"]; ++i) {
      array[i] = func(i, array[i]);
    }
 
  }
};
 
var a = ["a", "b", "c"];
console.log(a);
// [a, b, c]
 
Utils["map"](a, function (key, value) {
  return "(" + key + ":" + value + ")";
});
console.log(a);
// [(0:a), (1:b), (2:c)]

Closure

There are two ways to capture variables with lambda in C++: either by reference or by value. What we would like is to capture by reference in order for all the variables to be bound to the same object. However, when the initial variable gets out of scope it is destroyed, and any attempt to read it results in a Segmentation Fault!

Instead, we have to capture it by value. It means that a new object is created for each lambda capturing the variable. Our objects are manipulated by reference, meaning that assigning a new value to the object will just update it and not all the other copies. We introduce a new assignement operator obj |= value that updates all the copies.

C++

var container = function (var data) { 
  var secret = data;
 
  return {
    _["set"] = function (var x) {
        secret |= x;
        return undefined;
    },
    _["get"] = function () { return secret; }
  };
};
 
var a = container("secret-a");
var b = container("secret-b");
 
a["set"]("override-a");
 
std::cout < < a["get"](); // override-a
std::cout << b["get"](); // secret-b
Javascript

var container = function (data) {
  var secret = data;
 
  return {
    set: function (x) {
        secret = x;
 
    },
    get: function () { return secret; }
  };
};
 
var a = container("secret-a");
var b = container("secret-b");
 
a.set("override-a");
 
console.log(a.get()); // override-a
console.log(b.get()); // secret-b

This

There are four ways to set the this value:

  • Function call: foo(). this is set to the global object. As this is not a proper way to do things, I set it to undefined.
  • Method call: object.foo(). this is set to object.
  • Constructor: new foo(). foo is called with a new instance of this.
  • Explicit: foo.call(this, arguments...). We explicitely set the this value.

All four ways are implemented in jspp but in a different way than Javascript. In Javascript, the language knows the construction and therefore can deduce what this is going to be. In C++, on the other hand, have a local view of what is going on. We have to develop another strategy for setting this that works for usual usage patterns.

We associate a this value for every object, by default being undefined. If we obtain the object through another object(test.foo), this is set to be the base object.

New creates a new function object with this set to itself. Therefore it can be called to initialize the object. Contrary to Javascript, the constructor function has to return this.

C++

var f = function (var x, var y) {
    std::cout < < "this: " << this;
    this["x"] = x;
    this["y"] = y;
    return this;
};
 
// New creates a new object this
var a = new (f)(1, 2); // this: [function 40d0]
var b = new (f)(3, 4); // this: [function 48e0]
 
// Unbound call, 
var c = f(5, 6); // this: undefined
 
// Bound call
var obj = {42};
obj["f"] = f;
 
var d = obj["f"](1, 2); // this: [42]
 
// Call
var e = f["call"](obj, 1, 2); // this: [42]
Javascript

var f = function (x, y) {
    console.log("this:", this);
    this["x"] = x;
    this["y"] = y;
 
};
 
// New creates a new object this
var a = new f(1, 2); // this: [object]
var b = new f(3, 4); // this: [object]
 
// Unbound call, 
var c = f(5, 6); // this: global object
 
// Bound call
var obj = [42];
obj["f"] = f;
 
var d = obj["f"](1, 2); // this: [42]
 
// Call
var e = f["call"](obj, 1, 2); // this: [42]

Prototypal Inheritance

In order to use prototypal inheritance, we can use Douglas Crockford Object.Create.

When reading a property, we try to read it on the current object, and if it does not exist we try again on the prototype. However, when writing a property we want to write it on the object itself. Therefore the returned object contains in fact two objects, one used for reading and one for writing.

C++

var createObject = function (var o) {
    var F = function () {return this;};
    F["prototype"] = o;
    return new (F)();
};
 
var Person = {
    _["name"] = "Default",
    _["greet"] = function () {
        return "My name is " + this["name"];
    }
};
 
var vjeux = createObject(Person);
vjeux["name"] = "Vjeux";
 
var blog = createObject(Person);
blog["name"] = "Blog";
 
var def = createObject(Person);
 
std::cout < < vjeux["greet"](); // Vjeux
std::cout << blog["greet"]();  // Blog
std::cout << def["greet"]();   // Default
Javascript

var createObject = function (o) {
    var F = function () {};
    F.prototype = o;
    return new F();
};
 
var Person = {
    name: "Default",
    greet: function () {
        return "My name is " + this.name;
    }
};
 
var vjeux = createObject(Person);
vjeux.name = "Vjeux";
 
var blog = createObject(Person);
blog.name = "Blog";
 
var def = createObject(Person);
 
console.log(vjeux.greet()); // Vjeux
console.log(blog.greet());  // Blog
console.log(def.greet());   // Default

Iteration

We use the new iteration facility of C++0x to deal with for(var in) Javascript syntax. We just define in to be :.

As this is a prototype, it currently loops over all the keys of the object. However, it is possible to implement the isEnumerable functionnality.

C++

var array = {10, 42, 30};
for (var i in array) {
    std::cout < < i << " - " << array[i];
}
// 0 - 10
// 1 - 42
// 2 - 30
// length - 3
// prototype - undefined
 
var object = {
    _["a"] = 1,
    _["b"] = 2,
    _["c"] = 3
};
for (var i in object) {
    std::cout << i << " - " << object[i];
}
// a - 1
// b - 2
// c - 3
// prototype - undefined
Javascript

var array = [10, 42, 30];
for (var i in array) {
    console.log(i, array[i]);
}
// 0 - 10
// 1 - 42
// 2 - 30
 
 
 
var object = {
    "a": 1,
    "b": 2,
    "c": 3
};
for (var i in object) {
    console.log(i, object[i]);
}
// a - 1
// b - 2
// c - 3
//

Dynamic Typing

There is only one class called var. All the operators +, +=, ++, < , * ... are overloaded in order to make the right behavior. Since this is only a prototype, all of them are not working properly nor following the ECMAScript standard.

C++

var repeat = function (var str, var times) {
    var ret = "";
    for (var i = 0; i < times; ++i) {
        ret += str + i;
    }
    return ret;
};
 
std::cout << repeat(" js++", 3);
// " js++0 js++1 js++2"
Javascript

var repeat = function (str, times) {
    var ret = "";
    for (var i = 0; i < times; ++i) {
        ret += str + i;
    }
    return ret;
};
 
console.log(repeat(" js++", 3));
// " js++0 js++1 js++2"

Scope

Scope management is done with lambdas. Since they are implemented in C++0x, it works without pain.

C++

var global = "global";
var $ = "prototype";
var jQuery = "jQuery";
 
_(function (var $) {
    var global = "local";
 
    std::cout < < "Inside:      $ = " << $;
    std::cout << "Inside: global = " << global;
 
    // Inside:      $ = jQuery
    // Inside: global = local
 
    return undefined;
})(jQuery);
 
std::cout << "Outside:      $ = " << $;
std::cout << "Outside: global = " << global;
 
// Outside:      $ = prototype
// Outside: global = global
Javascript

var global = "global";
var $ = "prototype";
var jQuery = "jQuery";
 
(function ($) {
    var global = "local";
 
    console.log("Inside:      $ = ", $);
    console.log("Inside: global = ", global);
 
    // Inside:      $ = jQuery
    // Inside: global = local
 
    return undefined;
})(jQuery);
 
console.log("Outside:      $ = ", $);
console.log("Outside: global = ", global);
 
// Outside:      $ = prototype
// Outside: global = global

Reference

As in Javascript, everything is passed by reference. The current implementation uses a simple reference count to handle garbage collection.

C++

var a = {};
a["key"] = "old";
 
var b = a;
b["key"] = "new";
 
std::cout < < a["key"] << " " << b["key"];
// new new
Javascript

var a = {};
a["key"] = "old";
 
var b = a;
b["key"] = "new";
 
console.log(a["key"], b["key"]);
// new new

Exception

Javascript exception mechanism is directly borrowed from C++, therefore we can use the native one.

We need to throw a Javascript object. We can either throw a new instance of a Javascript function or use _() to cast a string into an object.

C++

var go_die = function () {
    throw "Exception!";
};
 
try {
    go_die();
} catch (e) {
    std::cout < < "Error: " << e;
}
// Error: Exception!
Javascript

var go_die = function () {
    throw "Exception!";
};
 
try {
    go_die();
} catch (e) {
    console.log("Error:", e);
}
// Error: Exception!

How to use

Note: Only the strict minimum of code able to run the examples has been written. It is a prototype, do not try to use it for any serious development.

The library can be compiled under g++ 4.6, Visual Studio 2010 and the latest version of ICC. However Visual Studio and ICC do not support the initialization lists, so you cannot use the JSON syntax. But all the other examples will compile.

All the examples of this page are available in the example/ folder. The following execution will let you run the examples.

> make
g++ -o example/dynamic.jspp example/dynamic.cpp -Wall -std=gnu++0x
g++ -o example/exception.jspp example/exception.cpp -Wall -std=gnu++0x
...
> cd example
> ./json.jspp
{array: [1, 2, three], nested: {first: 1}, number: 42, string: vjeux}
> node json.js
{ number: 42,
  string: 'vjeux',
  array: [ 1, 2, 'three' ],
  nested: { first: 1 } }

Pro / Cons

The awesome part is the fact that it is possible to develop nearly all the concepts of Javascript in C++.

Pros

  • Write C++ in a dynamic fashion!
  • Extremely easy to integrate all the existing C++ code base.
  • Fun 🙂

Cons

  • Not possible to optimize as much as the latest Javascript engines.
  • Some features are impossible to write such as eval, with, named functions ...
  • No REPL.
  • A bit more verbose than Javascript.

How to Improve

  • Code the arguments management.
  • Develop the Javascript standard library (operators, Array, Regex ...).
  • Find ways to minimize the C++ overhead (remove the use of _()).
  • Find concepts that I did not introduce.

Stoyan Stefanov did a similar proof of concept but instead of targetting C++ he did it for PHP.