GoF Design patterns and JavaScript: The Builder pattern

[Edit: as some people pointed out, this article got overly big, and I decided
to cut it.  Pieces of text that were thrown away were mostly my contemplation
on how Java and C++ are bad and JS is good, so there's really nothing you
miss since the previous version.]

Stone Idols

I detest to hear people talk about design patterns as an opposite
to.., you know, "ordinary programming".  What a nonsense, god damn it!
You can either make software "in a usual way" or use patterns, and the
second way is widely considered to be much more respectable.

Of course, none of decent programmers make this ridiculous artificial
difference between usual and non-usual programming.  Most realize that
there can be tools and abstractions of differing power, but this
increase in complexity and power is quite gradual, like any other
phenomenon in the nature.

The reason why some people imagine design patterns as being something
special is that design patterns look smart.  They look complex enough
for quite a great fraction of programmers not to be able to easily
comprehend them.  That's why some folks tend to worship them.  Maybe
somewhat like ancient heathens worshiped natural forces they didn't
understand well enough to be able to explain rationally.

And the reason why design patterns look smart is that they push crappy
languages like C++ or Java to their limits.  I mean, the old good Gang
of Four book presents abstractions that are nearly as high-level,
cute, powerful, convenient, etc. as C++ (which was the main language
for the patterns to be implemented, at the time of writing) is
ultimately capable of.

So the patterns are great so much as one is approaching the boundary
of a relatively limited primitive world he or she lives in.  That's
exactly my point.

What JavaScript has instead of patterns?

Well, the real misunderstanding and confusion arise when people with
this kind of pattern-oriented statically-typed thinking find
themselves entangled into JavaScript.  It turns out that "normal"
object-orientation is not supported in JS, neither is static safe
typing; there's no such a thing as "interface", and any function can
be used as a class, which sounds crazy (probably it really is).

The endless stream of complains about JavaScript.

This is not to deny that the language really has some design problems.
In fact, you can find a lot of criticism on the web.  Most of it is
true, I think.  But what I really want to say is that JS doesn't need
all those Java-like things (mentioned above) to get the job done.  JS
presupposes dynamically-typed and function-oriented thinking.  Once a
programmer understands the language, he begins to like it and becomes
more productive.

Now get down to business.  I want to implement classical design
patterns in JS.  More exactly, I wanna show how it is possible to
implement equivalent functionality in JS.  That's what this post is
about.

You will see shortly that, putting details back, JavaScript has
essentially one major paradigm that's powerful enough to substitute
for all the design patterns.  That paradigm is called Higher-Order
Functions.  A related feature which is extremely important is Lexical
Scope.  Besides that, JavaScript is dynamically-typed which gives
great flexibility and saves a programmer a lot of unnecessary
troubles.  The drawback is arguably lesser safety and worse
performance; both are not critical, as practice shows.

Builder

"Builder" is an interesting pattern.  Assume that we know a
construction protocol for a thing and we'd like to abstract off actual
representation of the thing.  That's basically the whole sense of the
pattern.

In "Design Patterns" book by Gamma et al., they suggest the following
diagram:

The classical book says:

"Use the Builder pattern when:

    * the algorithm for creating a complex object should be
independent of the parts that make up the object and how they're
assembled;

    * the construction process must allow different representations
for the object that's constructed."

At Wikipedia, there's an example with pizzas.  Honestly, the example
is so much distant from real-life programming experience that I do not
even want to touch it any more.  Let's deal with something real.

Suppose we want to present some graph structure, such as a map showing
interconnected cities.  The cities correspond to vertices and roads
(highways) between them are edges, as usually.  In the context of
JavaScript, we may want to show this thing by means of SVG or HTML 5
Canvas graphics, or even in raw HTML 4 where cities are represented
with <div>s with rounded corners -- this doesn't really matter.

That seems reasonable to employ the builder pattern here; interface
would be like this:

var mbuilder = new MapBuilder();
mbuilder.add('New York', 'Boston', 305.83);
mbuilder.add('Boston', 'San Francisco', 4336.82);
mbuilder.add(...);
...
var map = mbuilder.get();
use(map.dist('New York', 'Boston'));
...

In this way, we only specify cities (identified by string names) and
distances; we abstract away how the graph is stored in memory.

Builder: implementation number 1

For example, one possible data structure that could have been used
here is just a single great object which is used like this:

var distance = map['Boston']['San Francisco'];


In this case, mbuilder.add() implementation is quite simple:


function add(city1, city2, distance)
{
   map[city1][city2] = distance;
   map[city2][city1] = distance;
}

And the whole implementation would be something like the following:


function MapBuilder1()
{
   var map = {};

   this.add = function (city1, city2, distance) {
                map[city1][city2] = distance;
                map[city2][city1] = distance;
   };

   this.get = function () {
                 return {
                    dist: function (city1, city2) {
                             return map[city1][city2];
                    }
               };
   };
}

Builder: implementation number 2

But you can easily think about some more elaborate needs and more
complex data structures.  Say, there's a necessity to get an array of
all cities at any given point of time during construction, and after
construction is complete.  Some external (library) code may require
it.  Thus, the above implementation is not good, because it has to
create and return a new array of cities every time it is called.
That's O(n).

We should separately store an array of cities mentioned so far.  The
new implementation looks like this:



function MapBuilder2()
{
   var map = {};
   var cities = [];

   function ensureCityPresent(city)
   {
      var tem = cities.indexOf(city);
      if (tem === -1) {
         cities.push(city);
      }
   }

   this.add = function (city1, city2, distance) {
      ensureCityPresent(city1);
      ensureCityPresent(city2);

      map[city1][city2] = distance;
      map[city2][city1] = distance;
   };

   this.get = function () {
      return {
         dist: function (city1, city2) {
            return map[city1][city2];
         },

         cities: function () {
            return cities;
         }
      }
   };

   this.cities = function () {
      return cities;
   };
}

Builder: implementation number 3

Probably someone would need to represent cities as separate objects.
For instance, the interface may be this:


var ny = map.city('New York');
assert(ny.name() === 'New York');
assert(ny.dist('Boston') === 305.83);
var cities = ny.connectedCities();
assert(cities[0] === 'Boston');
assert(cities[1] === 'San Francisco');
assert(ny.numCities() === 2);

So here's still more complicated implementation:



function MapBuilder3()
{
   var cities = [];

   // Implementation of the City "class".
   function City(name)
   {
      this.map = {};
      this.name = name;
   }

   // These are methods that get attached to every city through the
   // prototype.  Cities are retrieved from the map this builder
   // produces.
   City.prototype.name = function () {
      return this.name;
   };

   City.prototype.dist = function (cname) {
      return this.map[cname];
   };

   City.prototype.numCities = function () {
      var count = 0;
      for (var key in this.map) {
         count++;
      }

      return count;
   };

   City.prototype.connectedCities = function () {
      var res = [];
      for (var i = 0; i < cities.length; i++) {
         if (cities[i].name in this.map) {
            res.push(cities[i]);
         }
      }

      return res;
   };


   function findCityByName(city)
   {
      var i = 0;

      for (; i < cities.length; i++) {
         if (cities[i].name === city) {
            return cities[i];
         }
      }
      
      return null;
   }

   function ensureCityPresent(city)
   {
      var tem = findCityByName(city);
      if (tem) {
         return tem;
      }
      
      tem = new City(city);
      cities.push(tem);
      return tem;
   }


   // Implementation of a map's methods.
   this.add = function (city1, city2, distance) {
      var cityObj1 = ensureCityPresent(city1);
      var cityObj2 = ensureCityPresent(city2);

      cityObj1.map[city2] = distance;
      cityObj2.map[city1] = distance;
   };

   this.get = function () {
      // Return the final map now.
      return {
         cities: function () {
            return cities;
         },

         city: function (name) {
            return findCityByName(name);
         }
      };
   };

   this.cities = function () {
      return cities;
   };
}

Comments on the implementations

You can see that all the above code snippets are based on some core
abstractions.  More precisely, they're based on composable data
structures (which are objects and arrays, in JS) and higher-order
functions that capture their environment at the moment of creation
("closures" is what they are called).

Look at MapBuilder1 again.  You can see that the function add captures
the variable map.  So the value that map had when MapBuilder1()
returned doesn't cease to exist.  It is captured by the function which
is stored in add property, and thus won't be garbage-collected for
at least as long as this function itself is not garbage-collected.

In MapBuilder3, look at the City function.  It is used as class, via new

operator.  City is nested with respect to MapBuilder3, which means tha

each invocation of MapBuilder3 produces a new class.  Think how

awesome is that: we create distinct types at runtime!  We're able to do pretty

much everything at runtime, on the fly, and use all the tools and

abstractions we have, and combine them in any fashion.  Okay, back to

MapBuilder3: it returns a map with 3 methods: add, get and cities.

Add and cities are supposed to be used when building is not yet

finished, and get is supposed to be called once the building process

is done.  So get returns a map which is able to return cities with its

city() method.  Consider this:

var b1 = MapBuilder3();
// ...use b1 ...
var m1 = b1.get();

var b2 = MapBuilder3();
// ...use b2 ...
var m2 = b2.get();

Now, m1.city('New York') is not even of the same type as m2.city('New
York'); those kinds of cities are considered distinct as they're
produced by different builders.  This calls for better locality and
encapsulation.