Thursday 8 September 2011

Linked lists in JSON

It's time for another Javascript post! This time it will be about efficiency, which is not only a subject dear to my heart, but abnormally important for web development in Javascript. Javascript is a slow, interpreted language that runs on the browsers on people's phones, so we need tightly focused code to avoid slowing down things even more. More specifically, efficient data structures. Even more specifically, efficient lists.

A sea of lists

A list is conceptually simple: A finite ordered collection of things. There. That's it. So, why does there exist nine gadzillion different variations of it? Efficient programming boils down to choosing the right data structures for the task at hand. Even the simple list has many different implementations, each suited to tackling a different set of problems.

The most common list implementations are:
  1. Arrays. Just data stacked end-to-end in a long line. Efficient for random access reading, but costly to manipulate. To remove an element in the middle, you will have to traverse over the full list and shift all successive elements 1 index back.
  2. Generators. Aka "lazy lists". These are just code that emit one data element at a time. Very efficient memory usage, as elements are conjured only when needed. Horribly inefficient for lookup.
  3. Linked lists. A loose collection of nodes, where each node contains one data element, and has a reference to the next node in the list. Inefficient for lookup, but very efficient for manipulation and insertion.
In Javascript, and consequently JSON, only Arrays are natively supported. But that's fine, because Generators and Linked lists are easy to implement yourself. And that's what we're going to do today!

We're going to create a function for transforming Javascript arrays into JSON linked lists.

The Array to JSON Linked list translator

Array.prototype.toJSONll = function (idx) {
  idx = idx || 0;
  if (idx >= this.length) return "null";
  idxS = idx.toString();
  valueS = JSON.stringify(this[idx]);
  nextS = this.toJSONll(idx + 1);
  return ("{idx: " + idxS +
          ", value: " + valueS +
          ", next: " + nextS + "}");
  var idxS = null;
  var valueS = null;
  var nextS = null;
};
For convenience, it is implemented as an extension method to the standard Javascript Array class. This means you can include this snippet in your code, and voila! All your existing arrays now have a .toJSONll() method!

I've embedded the code into this actual webpage, so if you want to test it out, type a valid Javascript array into the text field below and push the button:
You can't test this, because you don't have Javascript enabled.  SYNTAX ERROR
That's all for this time! I might make my next post about encoding lazy lists in JSON. What do you guys think?

Tuesday 2 August 2011

Variable closure in Javascript

First off; why should we care about Javascript? Silverlight rocks hard and is vastly superior to Javascript both in expressiveness and in standard library toolbox brevity.

A few years into the future, the above question will hopefully be answered with "what the hell is Javascript"?

Unfortunately, Silverlight adoption has not spread to all devices and platforms. For normal development, that is not a problem. Your customers are very likely using Silverlight ready platforms anyway.

The real world, however, is a cruel mistress. Business decisions - or local law - may force you to make your application available to as wide an audience as possible. In those cases, you need to use Javascript. And, when using Javascript, you need to be very careful what you do. It is a terribly undisciplined language with a weak standard library, inefficient arrays, variable types, no proper object orientation, and really weird variable scope.

This short post will focus on the latter problem: keeping your variables properly scoped.

Take the following example code, which is basically an extension method to the String type. It is a handy utility to count the number of characters in a string. If you implement it in your project, the expression "this".count() will evaluate to 4:

String.prototype.count = function (idxParam) {
  idx = idxParam || 0;
  returnValue = 0;
  if (this[idx])
    returnValue = 1 + this.count(idx + 1);
  return returnValue;
};

While this code works perfectly (try it!), there is one small problem with it. Can you spot it? Look closely. Closer. No? Unless you are a seasoned Javascript developer, the problem is impossible to spot and will likely remain invisible for a long time.

Remember I said Javascript has weird variable scope? In the above code, the variables have not been properly closed off and will leak out of the function and into the global namespace. After executing the above function, the variables "idx" and "returnValue" will be available to all functions everywhere. This may not sound like a real problem, but if some other functions also use variables with those names, they will re-use the above variables instead of receiving their own. Needless to say, this is likely to cause problems down the road. (Especially if you introduce multithreading!)

To check this, try to run the following code:
"Hello world!".count();

if (typeof(idx) !== "undefined")
  alert("Oopsie!");

So, how do we fix this? You need to "close" the variables off, so to speak. By nulling them out, you signal to Javascript that they are no longer needed when you exit the function:

String.prototype.count = function (idxParam) {
  idx = idxParam || 0;
  returnValue = 0;
  if (this[idx])
    returnValue = 1 + this.count(idx + 1);
  return returnValue;
  // close variables
  var idx = null;
  var returnValue = null;
};

// Do a quick check that "idx" is now scoped.
idx = undefined;
"Hello world!".count();
if (typeof(idx) === "undefined")
  alert("It works!");

Simple as that. Note that the var keyword is vital here. Without it, the last two lines would be normal program statements, and consequently would not be executed as they occur after the return statement. The magic var statements, on the other hand, are always executed.

The above hack works everywhere - I've tested in IE, Opera, Mozilla, Chrome, in Windows and on mobile devices. In the world of Javascript, this means it is practically defined behaviour. I recommend you adopt this as a best practice and remember it whenever you happen to step in some Javascript.