Finding Closure from jQuery - lessons learned

Yesterday I spoke about an easier method to starting with Closure Tools, you can get the slides here:

http://rhysbrettbowen.github.com/closure_from_jquery/

and the demo you can see in action here:

http://rhysbrettbowen.github.com/weatherdemo/

But what I'd like to talk about are some lessons I've learned, mistakes I made and what I'm going to change for the next time.

My spot to talk was on the second day as the second session after lunch. The second day is hard to get interest going and even harder to keep people awake, they've had an after party the night before and the food is settling nicely in their stomachs from lunch.

My first major mistake I made was to leave the lights off. I did this because the speaker before me had turned them off so I decided to leave it. Not a great thing to do when trying to command the attention of a room of sleepy people.

Another major mistake was how technical my speech was. I wanted to get some core concepts across like how goog.ui.component worked and I went in to too much detail. I showed code and where to put things, a better option would be to have a flow chart of it's lifecycle. Another big issue was that I showed goog.ui.component but what I actually used was mvc.Control which inherits from it. I should have just mentioned the inheritance as an aside and explained it all as if it was part of mvc.Control (from plastonjs).

I also wanted to mention the gotchas of programming to make things AO compatible and I gave two examples. I spent way too much time on the second one (a class variable) when it doesn't come up that often. I should instead have just left it out and put in a quick mention of that being the reason for $$ in the G.

I also went the wrong way about showing code. I showed the entire program, then the entire code. and tried to relate it back to parts of the program. I worked bottom up, showing code first then what it did second. I should have broken down the program in to segments, showed that segment then showed the code for it. That way it would be broken up a bit better.

Also I need to find a better way to describe the benefits rather than diving in to technical details. A presentation is not a classroom, it's a way to get people excited enough to go and find out for themselves. For this I think I need a flashier demo and to show off the compilers compression rather than just tell them it is good. (in case you're wondering here is what I should have shown:)

This shows the gzipped sizes of the javascript needed for each todomvc app at todomvc.com. CanJS doesn't have routing and I actually went through to websites to find the minimized size of javascript libraryies when the unminimized was provided. I left the actual coding for the app unminimized if it wasn't minimized already, but as these were between 1-7kb total I don't believe it would have a great impact on the final result.

So what am I going to do? I'm going to spruce up the presentation and show how each component is built one at a time. I'm not going to focus on closure tools and how it works - just it's advantages and how to get started using plovr, the G and PlastronJS - the actual diving in to closure library can come later once the excitement is there.

Breaking it down with algorithms II: Fibonacci

This series of posts is designed to not only explain how some algorithms work but also how you can think about problems to come up with your own algorithms.

the Fibonacci series is used in teaching Computer Science as it translates well in to a recursive solution - even if the solution is not ideal. The Fibonacci series starts with a 0 and 1, then each following number is worked out by taking the sum of the two previous numbers. This gives us the formula of:

Fib(n) = Fib(n-1) + Fib(n-2)

The reason it's used is because that's already a recursive function and looks something like this:

To look at performance of below solutions you can check out: http://jsperf.com/fibonacci-y-combinator/5

The Recursive Solution:

var Fib = function(n) {
  if (n <= 1)
    return n;
  return Fib(n-1) + Fib(n-2);
}

We can see that if given a formula we can write it out almost as we were give - with the exception of adding in the base conditions. We do have to be careful though as this will duplicate our work, we can see this by putting Fib(n-1) = Fib(n-2) + Fib(n-3) in to our original formula:

Fib(n) = Fib(n-1) + Fib(n-2)
Fib(n) = Fib(n-2) + Fib(n-3) + Fib(n-2)

As you can see we are doing Fib(n-2) more than once, and as we recurse through we will have a lot more duplication of effort. To fix this we instead will memoize our answers so instead of calling back through the recursive chain we will cache answers and return them when we get them back. We can make a general memoize function like so:

var memoize = function(fn) {
  var cache = {};
  return function(arg) {
    if (arg in cache) return cache[arg];
    cache[arg] = fn(arg);
    return cache[arg];
  };
}

So if we do this:

FibMem = memoize(Fib);

We should see a large performance gain. But this basically only puts us on a par with a linear algorithm and we are keeping all of the answers in memory. The great thing about it though is that if we want to work out different numbers several times, at least some of the work will be done for us. However if we want to print out the series of Fibonacci numbers instead of the nth one, then a linear equation should be better.

The Linear Equation

var Fib = function(n) {
var a = 0;
var b = 1;
for(var i = 0; i < n; i++) {
  var temp = b;
  b = a + b;
  a = temp;
}
return a;
}

And this is a good first attempt. For each loop we move along one until we get our answer. This is a pretty easy one to get so I'm going to move on to an optimization that I haven't seen a lot:

The Fast Loop

var Fib = function(n) {
var half = Math.floor((n-1)/2);
for(var i = 0, a = 0, b = 1; i < half; i++,b+=(a+=b)) {}
return n%2==0 ? b : a;
}

or perhaps in a more readable form:

var Fib = function(n) {
var a = 0;
var b = 1;
for(var i = 0; i < n - 2; i += 2) {
  a = a + b;
  b = b + a;
}
if (n % 2)
  return a;
return b;
}

Now first off passing in 0 will give you the wrong number, but we'll ignore that for now. What we've done is change the loop to go two numbers at a time rather than one. Because we do this we can eliminate the need for a temporary variable and we're only doing two assignments to go up two spots rather than three assignments to go up one. If we used destructuring assignment we could change our original algorithm to work without a temporary variable, but because it's not in all versions of javascript it's unlikely you would consider using it as yet (though for those interested it would be [a, b] = [b, a+b]).

The trick with this is to see that once we did a = a + b then we could just do b = b + a to return our a and b to be the smaller and larger numbers respectively. So when you are looping through a series looks for shortcuts, can you calculate more than one variable at a time? if you're going through numbers can you use arithmetic instead of saving a temporary variable?

Divide and Conquer

This is interesting as we've been taught that divide and conquer methods are really good, and that's usually true. The one problem with what I'll show you is that the individual steps are so heavy that for most numbers you'll be calculating up to, it's just not worth it but the higher the number you're calculating the faster it will be and should eventually be faster than the other methods. To do this method we first of all have to know some math.

There is something called the Fibonacci matrix. this matrix will give us the Fibonacci number for N if we multiply itself N times.:

[1, 1] ^ N
[1, 0]

Then it's just a simple matter of using the divide and conquer for powers. The complexity for this algorithm comes in the matrix multiplication and the algorithm goes a little something like this:

//to find the nth number
//fibonacci identity
Fib = [1,1,1,0]
//multiply a 2x2 Matrix
function mult2x2(a,b){
 return(
  [ a[0]*b[0]+a[1]*b[2], a[0]*b[1]+a[1]*b[3],
    a[2]*b[0]+a[3]*b[2], a[2]*b[1]+a[3]*b[3]
  ]
 );
}
function fibRecurse(M,n){
  //if n is one return the identity
  if(n==1)
    return M;
  //get the value of fib^n/2 (divide)
  var fibSoFar = fibRecurse(M,Math.floor(n/2));
  //multiply the two halves (and multiply by 1 more if not an even number) (conquer)
  fibSoFar = mult2x2(fibSoFar,fibSoFar);
  if(n%2==1)
    fibSoFar = mult2x2(fibSoFar,Fib);
  return fibSoFar;
}

Which is far more complicated but will get faster compared to the other algorithms the higher the number.

Conclusion

There are a few other algorithms I won't go through, like the direct formula as it's not as interesting to disect how it works (at least for the purpose of trying to solve a problem) and the Y combinator as it's not generally useful in javascript. I hope that the above has made you think past the usual fibonacci solutions and things like the fast loop method above should make you think about algorithms you were taught and whether or not they are the best method. The more you think about old problems the more likely you will come to new solutions rather than just relying on a memorized method.

Dependency Injection in Closure - IoC with Loader

Github here: Loader

Closure Library deals with dependencies at compile time creating a graph from those goog.require and goog.provide statments at the top of your files. Unfortunately this means that our dependencies are hardcoded to each file and we can get in trouble if there are circular dependencies.

The way to relieve this is to pass in the dependencies to our classes when they are instantiated. This way we can keep the majority of our dependencies in a single file and pass through the implementations that classes need. This means we have code that used to look like this:

goog.require('myImplementation');

myClass = function() {
    this.myImplementation = new myImplementation();
}

can now become this:

myClass = function(myImplementatation)() {
    this.myImplementation = new myImplementation();
};

We've moved the requires from being explicitly defined at the start to being something we have to define when we instantiate the class. If we do this throughout our program we can pass along dependencies all the way from the beginning. This not only means that we don't have to worry about our dependency graph but it has the added bonus that we can pass in mocks and stubs as the dependencies and make it easy to test each individual class without having to rely on our explicitly defined dependencies.

The big issue then is that this may get tricky the larger your program becomes. If you have to start passing along dependencies through parent files just to give them to the children then this can get messy quickly. To make this easier we can use a resource locater that has the ability to find the implementation we need. This is what Loader does for you.

Loader is based off the AngularJS dependency system but is made to work with Advanced Optimizations so differs in how it's used but also has a couple of other features such as instantiation of objects when their dependencies are met, in that way it also has some similarity to AMD

Loader is designed to be required in your main file where you will declare all the dependancies:

require('Ldr');

Once you've done that then Ldr is available for your entire program. The next thing you need to do is write your classes in the method described above, putting your dependencies at the start of your constructor function. If your constructor function also takes other parameters then you can place them afterwards, but your classes really shouldn't have any extra parameters (if they do then you can use them as dependencies only when they are singletons, though they can be instantiated without any problems).

Next you'll need to add a line to the prototype of your class to help Loader get the dependencies for you. It should be an array of strings that are the names for your dependencies:

myClass.prototype.inject_ = ['myImplementation'];

Now your class is Loader friendly with the added bonus that you can still use this class as is even if you copy it to a project where you're not using Loader.

Next thing we need to do is go to the main file and require in all our dependencies. Once they are there we can tell Loader to store the dependencies for when an invocation of a class is needed.

There are three different types of dependencies in Loader:

1. Constants

These are for when you want the dependency passed in as is. For instance you may need to pass in a constructor function, Loader will try and instantiate any dependencies given so if you want the constructor instead of an instance then you'll want to pass it in like this:

Ldr.regConst('name', myConst);

2. Regular

These are for classes that you want to be instantiated before being passed to the class. Though it is made for Classes it can also take objects and will pass them directly through. These are registered like this:

Ldr.reg('name', depClass);

3. Singletons

You can use this if you the object is meant to be a singleton. Although you can also just instantiate the object and pass it in to the regular method this has the added bonus that the singleton will only be instantiated when it's own dependancies are satisfied and will return a promise that you can use to do extra setup like so:

Ldr.regSingle('mediator', app.Mediator, arg1).next(function(mediator) {
    mediator.on('thing', function() {do stuff();});
});

Now that we've registered the dependencies we can go ahead and instantiate our class that has it's own dependencies. It will pass the dependencies in recursively so we only have to call our top class. We can also pass in any arguments it might take like so:

var myInst = Ldr.inst(myClass, arg1);

There may be issues if a dependency is not registered and requested. We can test that all dependencies can be satisfied before instantiating by testing our class like so:

if (Ldr.test(myClass))
    var myInst = Ldr.inst(myClass, arg1);

Or we can instead use the instSoon method which will return a promise that will run functions when the  dependencies are met. This is a great way to get around the circular dependency issue that might come up with the usual method of static dependencies in the Closure Library:

Ldr.instSoon(myClass, arg1)
    .next(function(myInst) {myInst.foo();})
    .next(function(myInst) {myInst.bar();});

There is just one trick left though. Dependencies like this work great for methods you have written, but what happens if you are using third party libraries that can take in constructors that they instantiate using the "new" keyword instead of Ldr.inst? Well we can make it so calling "new" on a function will instead run it through the instantiation steps of Ldr. All we need to do is this:

var toPass = Ldr.makeInst(myClass);

Now we can pass that in to other libraries with methods that take constructors such as PlastronJS and all the dependencies will be resolved when "new" is called on it.

Hopefully that will help you get started managing your dependencies, Loader is still quite new so there may be some changes but I'm sure they will all be for the better.