Sunday, November 11, 2012

Prototypal inheritance decoration

Javascript is a mixed bag. You can use a functional style or you can do it with OO. When you do OO you can use prototypal inheritance or you can use it with classical inheritance (it still uses prototypes but the pattern is more classical). I usually use Classical inheritance because it is well understood, performs well and because it's embedded in Closure Tools. But like OO and functional styles we can mix the two together, so should we always stick to one type? If you read my last post then you know there are new features coming for PlastronJS, and one of them in particular has started me thinking about using the prototypal inheritance.

mvc.Collection will soon be changed so that it will not have sort order, instead to apply a filter or a sort order you will need to make a new object. However I want that new object to still have the same features as mvc.Collection and in particular if you add a new model to the new object I actually want it to be put on the original collection. I'm basically decorating the mvc.Collection with new functionality (kind of like decorating a function). To do this with classical inheritance I would need to create a class for these new functions, pass in the collection and reproduce each of the functions to call the corresponding function on the collection. This would be nice and easy using the new Proxy object as I could just say if the name doesn't exist on the object then try call it on the collection, but it's not supported everywhere yet. So what I really want to do is put the collection in the prototype chain and here is where the fun begins.

inheriting


let's call the mvc.Collection class A. I create a new collection: a

now I'd like to have an mvc.Filter class B. What I need to do is something like this:

F = function();
F.prototype = a;
f = new F();
B.prototype = f;
B.prototype.collection_ = a;
b = new B();

I could just as easily have done: B.prototype = a; but the issue is then any methods I put on B.prototype might overwrite a's methods. I've also put in collection_ so I have a reference directly to the collection. So how does this differ from the current use of goog.inherits for classical inheritance? Well the biggest difference is that we're seting the prototype to an instantiated object rather than just the prototype of a class which means we now have access to the instance properties.

this

now the tricky bit. "this" will refer to the object that I call. So if I have b then any time I call:

b.method();

then this will point to b. That isn't an issue if you're worried about getting/setting items that are only on b, but what about when we want to access and change items on our original collection? Well we're safe as long as we don't use '='. Here is the problem:

a.a = '1';
a.inc = function(num) {
  this.a = this.a + 1;
};
a.inc(); // b.a == 2 - number is from object 'a';
b.inc(); // b.a == 3 - number is from object 'b';
a.a; // 2

when we called inc we did it with the context being 'b'. Because we used the assignment operator we created a new property on the instance of 'b', effectively hiding the property of 'a' which is what we really wanted to change. We can either redefine any method on B to call itself on the collection (so the collection becomes the context) which may be a pain or we can instead design A to never use the assignment operator (after the constructor).

No More Assignments

There does have to be some assignments obviously, but you should try to restrict these to the constructor, or on scoped variables (variables without a preceding "this"). But how can that be done? What if I wanted to do something like this:

A = function() {
  this.country = 'USA';
}

a.setCountry = function(country) {
  this.country = country;
}

a.getCountry = function(country) {
  return this.country;
}

The problem here is that country is a simple type that can not be changed. If we do anything to a string the system creates a new object in memory and points to that. We want the 'this.something' to point to the same bit of memory and there are two types that work like that: objects and arrays. So we have two options:

A = function() {
  this.country = ['USA'];
}

a.setCountry = function(country) {
  this.country[0] = country;
}

a.getCountry = function(country) {
  return this.country[0];
}

// or

A = function() {
  this.country = {val: country};
}

a.setCountry = function(country) {
  this.country.val = country;
}

a.getCountry = function(country) {
  return this.country.val;
}

You may think that you could get away with wrapping any simple mutable properties you're putting on an object like this:

A = function() {
  this.properties = {
    prop1: 'a',
    prop2: 'b'
  }
};

but this makes it difficult if you have a chain of objects each with it's own property object. Instead of just getting b.property[0] you will have to recurse through all the prototypes looking in each 'properties' object until you find the one you need, rather than just letting javascript go up the chain for you.

This looks like a fair bit of effort, and it is, but hopefully you won't have too many mutable properties on an object. There is another step of complication though, what about objects and arrays.

object and array setting

In mvc.Collection it currently will make an unsafe copy of the attributes so they can be compared. This means we have something like:

this.prev_ = goog.unsafeClone(this.attr_);

which you can see is an assignment. However there is a lot of setting of the attr_ object and I wouldn't like to put it all under another array or object. If you're using an array or object then you can instead set them by clearing all the keys/values and copying over the keys/values from the other object. This has the unfortunate side affect that your new set object will not satisfy a comparison with the original object.

Calling the super


calling methods on the super should be pretty easy actually, just put in this.collection_.mehod() and you're done

And that's about it - the real trick is knowing what 'this' pertains to.

Monday, November 5, 2012

The Future of PlastronJS

It's been a little while since I wrote something about PlastronJS and although it isn't old I've had time to consider it's direction. There has been a lot of features added to the code recently and there is more coming, here are a few that are either in or looking to be put in the next month:

mvc.Layout

mvc.Control gives you some great functionality on top of goog.ui.Component as well as hooking up a model. But what if you want all that goodness without a model? Well now mvc.Layout inherits from goog.ui.Component and mvc.Control inherits now inherits from mvc.Layout. This means that you can use this.getEls, override addChild using this.placeChild_ and most importantly use the component level event system (this will be improved even more in the near future).

Dot property get/set/bind

In the same release as mvc.Layout comes dot property access. Ever wanted to listen to changes like this:

this.bind('address.country', function(country) {...});

You can even use get and set with dot property access, and all properties of an object that have changes below them will be enumerated:

a = new mvc.Model({'a': {'a': 1, 'b': 1}});
a.get('a.a'); // 1
a.bind('a', function() {alert('a');});
a.bind('a.a', function() {alert('a.a');});
a.bind('a.b', function() {alert('a.b');});
a.set('a.a', 2, true);
a.getChanges(); // ['a', 'a.a'];
a.change(); // alert a, alert a.a - but won't alert a.b

Also now any objects set will use a recursive check for changes by default.

One last handy thing is that this will even work with objects returned by computed properties.

Router ordering

Now the router will only run the first route that matches - also a route will not run when it's been added, you should run router.checkRoutes() when all routes have been added to fire the first time.

mvc.View

And now we move to the future. mvc.View will be an interface that much like that described in http://modernjavascript.blogspot.com/2012/06/v-in-mvc.html It will act almost like an mvc.Model where you can get and set and bind to changes. This means that the view itself will have an extra layer - or you could even use an mvc.Model as an mvc.View and bind two of them together with a control. I'll be providing some examples of how it could be used, but the possibilities are almost endless. One of the first implementations I will make will go through the DOM and use attributes on nodes to let the mvc.View know what data should be provided and how it should be interacted with (much like the in HTML binding clues given by Ender, Knockout or Angular). Another will be form based, and there will even be one that can aggregate views together. I'm hoping that I can show the flexibility and power of this idea in the near future.

mvc.Pool and filters/ordering

mvc.Collection is great but it is limited to only having one set of models and one sort order at a time. There will be a new model type soon that is a pool of models, like an unordered collection. What you can do beyond this is have something that inherits from mvc.Model and will have a filter and order that can be imposed on a pool that is passed to it. This means that if you have one set of models in a pool you can create two different order and give the pool to each, they will then both respond as if they were a collection but the pool will still manage it's own sync, only the filtering and sorting will be done by the object, the rest (like adding models) will be passed along to the pool. If you want to change sort order on a control you can do so by creating a new filter/sort, passing the pool in to that and setting the model of the control to the new filter/sort. Most likely mvc.Collection will actually become the filtering/sorting and if you instantiate it with models it will create a new mvc.Pool so that it is backwards compatible.

I'm planning to keep backwards compatibility with all these new features and improvements as well as going back over the code and improving it, so don't be afraid to dive in now and offer any suggestions as to what you'd like to see.


Wednesday, October 17, 2012

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.

Tuesday, October 9, 2012

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.

Monday, October 8, 2012

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.

Wednesday, September 26, 2012

Box-sizing and Layouts

If you've switched over to using border-box like recommended in http://paulirish.com/2012/box-sizing-border-box-ftw/ then you'll find a bit of trouble getting your content size to play nicely with padding.

The trick is that if you have a border-box with padding then the inner div with the same sizing won't respect the padding if it's given width: 100%. So how do we get it to respect the padding without using absolute positioning.

The trick is that you're going to have to mix our box sizing models. We'll use two divs - the outer div will be used for positioning and padding while the inner div is used to respect the content width. You'll need a structure like this:

<div class="column">
<div class="content">
    <!-- content goes in here -->
</div>
</div>

The div with a class of column should already have the border-box from the link. Now we'll just give it some padding.

.column {
    padding: 0 10px;
}

Now we can have a class for content that looks like this:

.content {
    width: 100%;
    -moz-box-sizing: content-box;
    -webkit-box-sizing: content-box;
    box-sizing: content-box;
}

viola! we can now position everything in the content div and it'll respect the padding.

Wednesday, September 5, 2012

Breaking it down with algoritms I: the round table

Breaking it down with algoritms I:

This series is about looking at a problem and solutions in javascript. We will have a look at which algorithms offer a solution and how we can arrive at them or at least understand how they work. I'll be showing code and will try to break down the code to a mental model of how it works. I have met a few people who have trouble coming to a correct algorithm and this is almost always because they can't break down the solution in to steps - they just don't know how to think about the problem. Hopefully this will help those who need it and give a little more insight in to the wonderful world of algorithms for the rest of us.

This will not be your algorithms 101 course where we look at well known algorithms, instead we will be trying to build new ones from scratch (and if we arrive at well proven algorithms that can be found in a textbook then we've done our job!)

The circular table

The problem goes like this:
There are 100 people sat at a circular table. You go around the table asking every second person to leave (starting by asking the guy at seat 1 to leave) until there is one person left. Which seat is left?

You can see the solutions at: http://jsperf.com/chair-ring/7

Solution 1: using an array


Usually when I hear a problem like this I try to put everyone in an array. I can see that I'm removing every second person so I can do a filter on the array to remove every second person (I'm starting at 1 which is index 0 so I can just remove all the even indexes). Using a filter like this makes things easier for us because we can forget about all the operations in the middle. What we care about now is when we start the second pass through which chair do we start at? In this case we'll ask 99 to leave keep 100 and then start again at 2.

If we think about the end we can see there are two cases, one where we remove the last guy and one where we remove the second last guy and this will tell us whether to start filtering at the first chair or the second chair. This all depends on whether the length of the array is even or odd. We can see that when we get an odd length we will start removing from the second chair in the array.

If we think about this a bit more though it's not as simple as whether the previous length was even or odd, if we have 4 chairs (it often helps to think of simple cases) and we start at the second chair then wil will still be on the second chair in the next round, so odd numbers change which chair we start at.

Now we can start coding:

// setup array
var chairArr = [];
for (var i = 1; i <= 100; i++)
     chairArr.push(i);

// whether to remove odd or even chairs
var odd = 0;

// while there are still chairs
while (chairArr.length > 1) {

     // remember the initial length
     var last = chairArr.length;

     // filter odd or even chairs
     chairArr = chairArr.filter(function (val, ind) {
          return (ind + odd) % 2
     });

     // used to decide odd or even chairs next round
     odd += last;
}

// return the answer
chairArr[0];

First thing is first - we need an array of 100 chairs which is easily done.
We also know that we're either starting at the first or second chair on each pass through so we'll want to remember that.
We then need to keep making passes until we are left with our final chair.
The next is perhaps the most important line although it looks really easy - we need to remember whether the last length of the array was even or odd so we'll save this.
Then comes the filtering, this is easier than it looks, I just need to modify the index by adding on an odd number if the previous length was odd and then see if it is divisible by 2.

Last thing I need to do is keep whether I'm starting at the first or second chair for the next pass. Since I'm using a modulus to check later I don't need this as a 0 or 1, and odd or even number will do so I just have to add on the length. Adding on an odd number will make that number odd and keep it there until the next odd number is added which will represent the switch of starting on the first or second chair when an odd length is found. Don't worry if you think you won't write it exactly this way the first time - I certainly didn't. It took a couple of iterations to realize I could just do this instead. Originally I was using a boolean for true or false about whether to start at the first chair. It might make more sense if you write something like this instead:

if(last%2==1)
    odd = !odd;

so if the last length was odd then change whether to start at the odd or even chair.

This solution is fine and works but it's not the best way to go. Trying to keep in mind whether we change the next start chair slows us down but the biggest slow down is the filter method. Filtering an array is slow and may not be native on older browsers (for those you can use a shim https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Array/filter).

Let's try something a little different:

Solution 2: use a custom data structure

We're talking about a ring of seats right? so why not just build one. All we need is 100 objects which hold their seat number and a reference to the next seat. Then all we have to do is go around and remove each seat in between.

A quick way to remove a seat is to just change the reference to the next seat to point to the seat past that. It's like if we had everyone pointing to the person next to them then went around telling each person to point to the person past the next person and moving along to the person they're now pointing at and then doing the same thing again until it was just one person pointing at themselves. There isn't any filtering of arrays so it should be faster as we're only updating references and moving along them.

// setup chair ring
var start = {num:1};
var one = start;
for(var i = 2; i <= 100; i++) {
        var temp = {num:i};
        start.next = temp;
        start = temp;   
}
start.next = one;
one = null;

// go around removing chairs
while(start.next != start) {
        start.next = start.next.next;
        start = start.next;
}
start.num;

The above should do that for us. This is the answer that you should probably give in an interview and is probably the closest to how we would solve it in real life. But when I did this I couldn't help the feeling it could be done a bit quicker. Changing pointers isn't too slow but there will be some garbage collection when the chairs are removed, also we have to setup Objects for each chair. So let's go back to our array solution and see if we can't make it a bit better.

Solution 3: Return of the array

An array is more like a line of chairs. What if we told every second person to go sit in a new line of chairs, then we go through that line and do the same. By doing this we can copy each number in the array rather than filtering (which is expensive). Now if we run through this we can also see that when we get to the end of the first line we just go straight to the start of the next one. Now here is the mental leap, we can forget about whether the last length was odd or even by just treating the start of the next line of chairs as if it is joined to the current line. All we need to do is keep telling every person to go sit at the end of the line until there is no-one else to skip. Let's see some code:

// setup array
var chairArr = [];
for (var i = 1; i <= 100; i++)
      chairArr.push(i);

// copy every second element to the end of the array
for (i = 1; i < chairArr.length; i+=2)
     chairArr.push(chairArr[i]);

// return the answer
chairArr.pop();

Nice and simple. It's made a lot easier by the fact that you can change the length of arrays - there would be a couple of hoops to jump through if this was Java for instance - but we don't have to worry about that. All we're doing is adding every second element to the end until we reach the end and grabbing that last answer. I would say this is the best solution for flexibility (it's easy to modify for every third or two of every three) code size and ease of understanding. But we want to go FAST. The big thing to see is that it's every second chair which should tell you something being a computer guy. Binary.

*EDIT*

The above will take about 2N space with the array (actually 2N-2). But we can do better. We can re-use the space of the array that we have already gone past. In the above solution we basically have 2 counts, the first is the count that goes every second chair the second is the count for where we copy that seat number in to. Because we were just placing it at the end of the array we didn't really need to keep that number around as a push() will place the number in to the correct chair. Instead we're going to take that push() and change it to overwrite numbers at the start of the array. This shouldn't be a problem because our chair skipping index won't go past the chair placing index.

One thing we need to change though is the for loop end condition. Before we were just going until we hit the chairArr.length, in other words we kept going until we hit our last chair placing index. We could do this, or there are two other options. We could go until we hit the same chair twice in a row (so something like for (...; chairArr[chairSkipIndex] != chairArr[chairSkipIndex - 2]; ...) or we can work out the index to stop at. I'm going to use the latter one, I know that the array will expand to 2N-2 and where we should start at the chairArr.length (N) I'm going to start at the beginning of the array so I only need to keep going until the chair placing index is at N-2. Here is the algorithm:

// setup array
var length = 100;
var chairArr = [];
for (var i = 1; i <= length; i++)
    chairArr.push(i);

// copy every second element to the end of the array
for (i = 0; i < chairArr.length - 2; i++) {
    chairArr[i] = chairArr[(i * 2 + 1) % length];
}

// return the answer
chairArr[i - 1];

We setup the array like normal, and keep going until the chair placing index is at N-2. The important part is the next part. We can work out what our chair skipping index is from the index (it'll be the index * 2 and add one because array indices start at 0). The next thing there is called the modulo operator (or you may think of it as the remainder).

Most people when starting coding with loops over an array will start after a for loop with a condition like:

if(i > arr.length)
    i = i - arr.length;

This allows the index to iterate past the end of the array and come back from the beginning. This is exactly the same as adding on the modulo operator.

And there we have it, instead of push we just copy the chair number back in to the array and iterate until we hit out end condition, we're done! it works exactly the same as above but will re-use the space in the array we were just leaving behind.

Solution 4: Math

First of all thanks to imbcmdth for this solution.

This is going to be the hardest to wrap your head around but bear with me. Instead of actually moving around seats we're just going to keep tabs on which seat we start on because once we get to the length of 1 the seat we start on will be the only seat left. Next we have to realize that on every pass we're going to remove every 2^N chair. So the first round we're moving every 2nd chair, then every 4th then every 8th and so on.

So what we need to do is move the start chair by that amount on every pass. So lets start with the chair at 2. After the first pass we've removed every 2nd chair and we'll remove chair number 2 so we will have the start as being 4 (that's 2^1 chairs along from the previous start chair). The next time it's be 8 (that's 2^2 chairs along from the previous start chair). You'll notice we're actually keeping track of the NEXT start chair rather than the one we were just on.

Now we will remove the start chair if we go through an even number of chairs, else we'll skip that one and remove the second. So it's important to only add on the 2^N when we will remove an even number. We can get whether we're going through an odd or even number of chairs by counting the number of times we can go 2^N from out starting chair.

The last thing we need to know is how many times we have to do this loop. We need to know how high N can go in 2^N until we reach 100. So we do the reverse of 2^N which is a logarithm (who says you don't need math to program?).

// number of chairs
var totalLength = 100;

// number of iterations
var numIterations = Math.round(Math.log(totalLength) / Math.LN2);

// start at the second chair
var startingPoint = 2;
var currentLength = totalLength;

// magic happens
for(var count = 1; count < numIterations; count++) {
     startingPoint += ((currentLength + 1) & 1) << count;
     currentLength = (totalLength - startingPoint) >> count;
}

// answer
startingPoint;

Don't worry if you don't understand this straight away - it contains a lot optimizations using binary calculation. Here is an easier to understand version that was whittled away until you get what you see above.


var totalLength = 10000;
var powerOfTwo = 2;
var startingPoint = 2;
var currentLength = totalLength;

while(currentLength > 1) {
     if(currentLength % 2 === 0) {
          // currentLength was even change starting point
          startingPoint += powerOfTwo;
     }
     currentLength = Math.floor((totalLength - startingPoint) / powerOfTwo);
     powerOfTwo *= 2;
}

// answer
console.log(startingPoint);

In this version you can see that the first thing we do in a loop is change the starting point, which lets you know that it's the previous length of the array that matters. The current length is then calculated as how many times 2^N it takes to get to the end of the array from the starting point.

If we have a look at the optimized version we can see the logic is still there, the &1 is basically the same as %2 which gives us 0 or 1 and << count means times 2^N (powerOfTwo). Because we're doing binary we just use << and >> instead of * and /

Solution 5: the formula

Thanks go to Medieval_Peasant for this one

Up until now we've been running a loop. Usually when solving a problem there will be a loop somewhere, but every once in a while it can be solved with pure mathematics. We already know now that 2^N is special. What happens when the number of chairs are 2^N? well one method I like is to try it out on smaller numbers. Try running through at 4, 8 & 16. You'll notice that the chair that is left is always the last chair. So what happens if we add in a chair, so for 2^N+1 chairs? (try 5 or 9) you'll notice that the start chair is pushed to 2. Try it out for 2^N + 2. You'll see it is pushed to 4. If we keep going we can see that every new chair we push on to the table will move the chair we end up at by 2.

This means we want to calculate the largest 2^N number that can fit in our length, we can then find out how many chairs we have added to that, then multiply that by 2 and we get our answer.

One small adjustment we'll make though is that if 2^N fits exactly in to the number of chairs then we'll actually take the 2^(N-1). This will make the math a little easier as otherwise we'd have 0 left over chairs and a start chair of 0 wouldn't make sense (in fact it means take the chair before the first one which would be the length). Below I did this by taking the log of length - 1, so if the length was 64 we'd actually try for 63 and round down to 32.

Here are the components broken up:

// find the largest 2^N that fits in to length (minus one)
var largest2n = Math.pow( 2, ( Math.floor( Math.log( length - 1 ) / Math.LN2 ) ) )

// get the left over chairs
var leftover = length - largest2n

// multiply to get the answer
var answer = seriesIndex * 2;

and here is the formula in all it's glory:


2 * (length - Math.pow(2, (Math.floor(Math.log(length - 1) / Math.LN2))));

Conclusion

So what we can take from this is that if we visualize how we would solve a problem in real life we can put that in to an algorithm. We can start off with a couple of premises (like start with an array and iterate, or if the number 2 is prominent there is probably a solution using binary) to come to other solutions that may not occur to us naturally. Most important is to iterate on a solution. We might iterate over a couple of solutions in our head and whether they are wrong or right they're all important as thinking about each will help you drill down to the answer

Which solution is the best? Well the math solution is definitely the cleverest and fastest, but it is also the least flexible and hardest to maintain. I'd use it if performance was the key concern and there was no chance of change. Otherwise I would stick with the third solution as it's easier to maintain, less code and fast enough (it may be 30-40x slower but for a small problem it's only milliseconds and the user won't see the difference). If you're in an interview though I'd go for the second solution as it's easiest for the interviewer to understand, is quick to come up with and you won't need to iterate on it much to optimize.

as a bonus if you go to jsperf I've also put in an example with regex, but this should be avoided in practice

Monday, August 6, 2012

caching MVC objects


usually when caching I like to try and cache the network requests. The reason for this is that it is easy to add on to a program without effecting anything else. Unfortunately this is not always the best way - especially when we can receive an object through more than one request. This can happen easily when using a framework that can request single objects and collections.

In my current project this is easily handled as a collection only returns a summary of the object, which means the only true way to get the full object is through a single request just for that. The problem comes when you can make a request for a collection that has the full information on an object. This isn't really an issue if we get the single object first and then get the collection - because we don't know what objects are in the collection. For single object caches to be useful when calling a collection we would need to be able to pass some indicator to the server which objects we already have in cache and then for the server to only pass back that those objects are in the collection rather than the entire information about the object. Then we'd need to change our collection reading to first try and get the object out of cache when parsing that collection.

Where this matters will be if a collection is read in first - providing all the information for an object - then we try to get that single object. If you're using a central store for your objects then this would be a good place to save the information. You can change the flow so that any part of the program that gets a model tries the store first (which it should anyway) and only then if it doesn't exist in the store should it try to query the server. We can then set the object's sync when reading from teh server to save it's information to some persistent local storage.

The trick is then where we read the local storage from. There are two options that I would consider. The first would be to update the store so that it reads all the saved information in at readtime. This is the quickest way as it can read in all the storage at once, however it may slow down the initialization of your program as it will have to parse the json in to your objects before becoming available.

The second solution would be to include the reading in to your sync. Instead of calling the server straight away it can look in local storage for the json data and use that. This is my preferred method as it keeps all caching code in the object sync - however if you have many different types of objects then it could lead to duplicate code across the different syncs, however you may be able to write some middleware or a mixin to handle this cache. It also means that you are only reading what you need out of local storage so although it may mean more reads (and it will have to check local storage everytime it tries to read an object externally) you will only bring in the information that is needed so there will be less memory usage and the reads will be spread out rather than all at once at the start of the application.

Wednesday, June 13, 2012

The V in MVC

I just read http://addyosmani.com/blog/digesting-javascript-mvc-pattern-abuse-or-evolution/ and it's got some good points. The main points you should take away is that there are already some great frameworks to work with and that there are many different approaches to the classic pattern. Most of these approaches are similar enough that you won't feel out of place if you switch between frameworks.

There is one point that I disagree with however, and that is that a view must know about the existence of models. I agree this is how a lot of frameworks work, especially when you think about ones that offer binding through templates or attributes on dom elements - but it doesn't have to.

I wrote PlastronJS and it follows a similar model as most MV* frameworks out there where the view is really little more than a template. The reason for this is that it's easier to get started and usually when you're doing a single page application there is no need for a great deal of abstraction.

So we turn our attention to the V in MVC. How can we have a view without knowing about the model? Well the easiest way is to build a view before building anything else. The second is to give it an interface that we can get, set and listen to and that's it. Here is a rather simple example:

View = function(text) {
  this.element = $('<div>').text(text);
}

View.prototype.setText = function(text) {
  this.element.text(text);
  this.emit('textChanged');
}

View.prototype.getText = function() {
  return this.element.text();
}

We've created a view. It can be updated by passing in text and if anyone makes a change to the view then it will emit that the text has been changed and the text can be read. It doesn't know anything about a models existence - nor what type of model. We could hook up any type of model to this view. Knowing about the model is the job of the control. The control is what knows about the model and the view.

So what is the advantages of having a separate view like this and not including it in with the controller or binding it in the DOM? Well for one thing the view does not have to know about the model. You can make simple and generic views that do things like display a text area or a graph and then re-use those views. You can also easily swap out views for different devices. If you want to change the view you won't have to change the rest of the control and it's bindings (unless it implements a different interface). There is also the possibility of building up larger views by adding together smaller views (it's like point-free programming for UI!)

So why don't more frameworks (including my own) do this? Well it's just harder to get started with and takes more code. You have to defined these views to begin with. Most people will look at it and think it's an awful lot of work to do to get a single page app going, and it is. You won't see and advantage to building an app with an abstracted view until much later in development.

**EDIT**

here is a little more detail about how to use it. Let's take the text view from above - we can use this to display any model. Let's say we have the user as a model - the user might have many different things on it (like usage limits) but we want to display the username at the top of the page. All we need to do is create a Control that pipes in the username of the model. So something like:

UsernameControl = function(model, view) {
  this.model = model;
  this.view = view;
  this.view.setText(model.get('username');
  this.model.on('username:change', function(username) {
    view.setText(username);
  });

usernameC = new UsernameControl(user, new View());

Now we may also have a shopping cart model and want to to display the amount, we can do exactly the same but create a shoppingCartControl, pass in a new instance of the view and hook up the total to the text. The trick is that the view stays generic and it's the control that hooks up what should be displayed. This is a simple example with only one parameter being passed through but you could build up views from smaller views or even have a view factory (one that will replicate the "text" div however many times you need for different values).

Friday, June 8, 2012

Initial Closure Meetup review

First of all, thanks to everyone that attended. We had around 35 people show up which is more than I ever expected when this was first put together. I think it shows the interest out there in the tool set and means that there is the ability to grow a solid community around the technology.

Thanks also to Nathan Naze who organized the space and took those newer to Closure under his wing - I'm sure they all learned a lot and there will be new users coming in.

The topics ranged throughout the talk and we covered a lot of bases as it was a round table discussion. One of the main subjects was work processes and how everyone used the tools. A lot of people use http://plovr.com/ or are now going to give it a go. The rest just use the scripts that come with the library with make or ant. Because of the interest our next meetup will be called "show us your stack" and I'm hoping to get a few people to take us through their workflow. I've put it up for a couple of months time at: http://www.meetup.com/Closure-Tools/events/68334272/ though it is far from confirmed. Let me know if you would like to share your setup, I'm thinking that a quick run through of a few people's setup will help (so anywhere from 5-30 mins just let me know how long you need).

Another important topic was the sharing of closure specific libraries. At the moment you can find projects in the wiki at: http://code.google.com/p/closure-library/wiki/RelatedProjects but it can be hard to find especially for new users. I'd like to see a communtiy driven website which can list libraries, externs, IDE setups etc. that we can share with each other. Anyone good at website design?

I also talked about a "starter pack" that would include projects like plovr, http://bolinfest.com/coffee/features.html, https://github.com/rhysbrettbowen/PlastronJS, https://github.com/rhysbrettbowen/G-closure and some gss style sheets (ala bootstrap), IDE components and a tutorial that could help users start on single page apps using interfaces and patterns that are familiar to them. I haven't started on the project yet but I'm hoping for contributions (especially with the IDE components) so we can lower the bar for entry into the toolset.

There was also some discussion about a package manager (perhaps a fork of NPM) which would help users with discovery and use of modules.

These are all really exciting propositions and the future looks bright.

Monday, June 4, 2012

Routing and state

A little while ago I read and article about routing in ember which was a big surprise to me, not so much their approach but that people weren't already doing it. At the moment it seems that a router is being used across a program and individual components are listening for specific routes. The issue with this is that you end up with your routs being defined across a number of components so if you update your URL structure then you're going to have problems hunting down all those routes that were defined.

So have a read of the routing in Ember.js article then come back because we're going to take it one step further.

What I currently do is extend the router and call it State.js and then make it a singleton that is available to the whole program. This is the central repository for my state and is also where all the routing will be handled. If a user wants to change the state when clicking a link I can just send the variables that need changing to the state. This will then change it's internal variables, output it's state as a URL and then push that in to the history. The big advantage of this is that instead of declaring the whole URL on that link you only need to know which variables change. For instance if you had several filters that could be applied to a search page you could just call your State.setFilter(...) and have that added. The state then knows to keep the rest of it's filters intact and will generate the new URL with the filters it already has on still in the URL.

This makes it easier to apply URLs where you may have several filters at one. Today most routers handle tree like structures well but are difficult to use when you want  to do things like apply size and colour filters on - things which don't have an order and can be expressed many ways. The best way to put this in a URL is outside the path. Usually I like to put whatever I can in the path like structure and then give the rest of the variables as a query string on the end.

Now we've decoupled setting state, but how about reading it or running things from different controls on different states. For that I use the mediator. The router should be setup to accept all the possible routes and can then pass the changes with all the information needed through a mediator. This means that you can also do special processing of the urls in the mediator too if need be. Because we've done this the individual components will only be listening to events that you define and not to URLs that may change.

That is what I currently do, but it has struck me there might be an even better approach and one which I will be experimenting with in future. State is really just a whole lot of variables and a router is a way of setting and getting state back from the URL. This sounds just like a model and a sync. Next time I'm writing a program I'm going to see if I can create a state model with it's sync being the router and then I should be able to bind on changes to that model and send those changes through a mediator to the rest of the program. This means the logic for the binding between state variables and the URL will be pushed in to the sync, or as an interface between the model and the router and the program will only have to worry about the state model. The benefits of this should be that models already have binding magic and so should cut down on code.

Tuesday, May 29, 2012

JSGentleman Rule #4: write libraries

We all know that decoupling is a good thing and the best way to do that when writing an application is to write libraries instead of application code.

What you can do now is to take parts of code that you have written, minimize it's dependancies and then generalize the input. Viola - a library that can be used in future projects.

Whenever I start a new project I try and identify parts of the program that can be abstracted, give it an API and make sure I don't pull in dependancies from elsewhere in the program (unless necessary and explicitly stated). Working like this helps decouple the project and stating dependancies and an interface will help future developers working on your project, but there are also more benefits.

Writing as a library will allow you to easily open-source non-critical parts of your project which can help the community, promote your company, and get feedback to improve the code. It also means that other people will be looking at your code which means you'll stay a bit more alert about writing good clean code, documentation and testing.

When working on your new library you may also put in extra functionality that isn't necessary in your project. This is good practice as it can help you in future iterations. I find sometimes I like to work on a library separate of a project to add in new features, only to then realize I can actually use these new features in the product. It's a win-win, and if you're using a minified like Closure-Compiler you won't have to worry about bloat as it removes unused functions.

The final reason is that it's a good abstraction. You might start writing out parts of the program only to realize that someone else has done a better job and because you started with a decoupled design it shouldn't be too hard to swap out for another library.

So next time you start on a new part of your program think about how you can generalize it, then stick it up on github.

Thursday, May 24, 2012

using JQuery functionally

I was looking at the code on a site recently and it was all blocks of JQuery. The first thing I saw was that there was a lot of lines that were almost the same - basically that there was a selector then 3-4 methods chained off it. First thing I thought was why not put that in a function, something like:

var doStuff = function(selector) {
$(selector).method1().method2().method3();
};

which would allow you just to call the doStuff method with the selector. It then hit me that we're just abstracting away the functionality of JQuery which is a good thing. Then I wondered if I could change it in to functional style (without writing the whole of JQuery).


The first thing is to realize is that Javascript allows us to change scope using call or apply. You can pretty much write OO code in a functional style using those. So basically these are the same:

// OO
obj.method(param);

// Functional
Obj.prototype.method.call(obj, param);

Now JQuery makes it easy to get to it's prototype for adding plugins. This mean we can call a jquery method like:

$.fn.method.call($(selector));

Ah, now we can see that the $() is a function itself. So now we can use composition f.g(x) == f(g(x)):

compose($.fn.method, $)(selector);

There is still a problem though, compose will call the method with a different context and pass in the JQuery object as the first argument. There are two solutions and they're both fairly useful. The first is that we could have a special bind for JQuery methods:

var $bind = function(fn) {
  var args = arguments;
  return function($object) {
    return fn.apply($object, args.splice(1));
  };
};

so we could bind the method and pass it in to compose or even just use it:

var $method = $bind(method);
var $elems = $(selector);
$method($elems);

// or

compose($method, $)(selector);

The major difference is that $bind will take in other arguments when bound, whereas compose methods only accept one argument.

But we can probably do on better. We could just check to see if it's a jquery function and apply it inside compose. So let's make $compose:

var $compose = function(var_args) {
  var args = [].slice.call(arguments);
  return function(arg) {
    var ret = arg;
    for (var i = args.length; i; i--) {
      if(args[i - 1] in JQuery.fn)
        ret = $bind(args[i - 1])(ret);
      else
        ret = args[i - 1](ret);
    }
    return ret;
  };
};

Now we can just pass in the jquery methods to compose as they are. So let's compare:

// OO style
var doStuff = function(selector) {
  $(selector).method1().method2().method3();
};

doStuff(selector);

// Functional style
var doStuff = $compose($.fn.method3, $.fn.method2, $.fn.method1, $);

doStuff(selector);

So there we have it. JQuery being used functionally. I haven't tested or tried any of the code so not sure if it will just work but hopefully it's enough to get you interested and I'd love to see what other people can do with it. Keep in mind though that compose functions take one argument so it's great for things like $.fn.hide but you may want to bind other methods:

var makeRed = $bind($.fn.css, {'background': 'red'});
compose(makeRed, $)(selector);

You may want to make some improvements in $bind and $compose like automatically wrap whatever is passed in with the JQuery object.

Thursday, May 17, 2012

Starting Closure

There has never been a better time to start using Closure.

The closure set of tools has been open sourced for a couple of years now and the last piece of the puzzle has landed, namely Closure Stylesheets. Now there is a full set of tools that are out there for you to use, not only that but the tools have been out long enough that there is help available.

Closure tools has been created fir a large team to create large applications. This has been the main hurdle to new developers wanting to learn. Most new developers will begin to learn closure at work in a team. Luckily there are now tools out there to help single programmers start for any size of project. Here is what you need to start:

Closure: The definitive guide

If you want to start with the tolls a great way to start is to understand the thinking behind it. The book will give great insights in to how the tools work and how you can use them. There are great books out there for every library, and closure is no exception.

Plovr

Plovr is a tool written by Michael Bolin and makes using the library, compiler, templates and tests a breeze.

G-Closure

I'm guessing you already know jquery. Let's face it, it's almost analogous to javascript. One of the concerns that people have is that the closure library is long-winded. The library was written in a functional style and namespaced so you have to type out the namespace then the function and pass in the object you need. JQuery is a bit easier as you already have the object and you can just call functions on that, not only that but you have the famous chaining API. G-Closure lets you use DOM, Array and Object functions in the closure-library like you would JQuery. This means you don't even need to know the library to start, if you know jquery you can already build a webpage using the library.

PlastronJS

You probably use backbone.js or some other MVC. Well now closure tools has an MVC too, PlastronJS. If you read this blog you should know all about it by now. It's designed to be familiar but also, like the closure library, have many more features you can choose to call on or disregard depending on your needs.

Et al.

An honorable mention should go towards the closure coffeescript fork which does a great job removing the "wordiness" of the library.

But Wait!

If you were about to go hop off and try Closure Tools for the first time I recommend waiting just a little bit more. Closure Tools now has a meetup which means the community is going to get stronger and the toolset is going to get easier. In fact I'll have another little project to announce very soon that should help you on your way. In the meantime I recommend starting by reading the book and keeping your eyes peeled on this blog for further announcements.

Wednesday, May 16, 2012

Functional Closure

When you look at it, the closure library is perfect for functional style programming. The whole library is given to you as functions rather than methods that have to be put on objects.

Unfortunately it is lacking though. goog.bind and goog.partial only get us some of the way and there could be a better way to do it. That's why I'm happy to introduce Functional Closure which will help all your dreams come true (well, at least help you in your functional style efforts).

The main function in functional closure is func.curry. This will not only allow you to partially apply only the variables you select but will also return a function that will continue to curry itself until you tell it to stop. You can also set a minimum number of inputs which when passed will give you back a value.

So how does it work? say we want to find the maximum of 10 numbers. We can curry Math.max like so:

var max = func.curry(Math.max, 10);
max = max(1,2,3); // we can pass in any number of values at a time
max = max(undefined, 5); // we can pass in undefined to skip a value
max = max(4)(6)(7); // you can pass in values like this (the 4 will be used where the undefined was put)
second = max(8) // the curry returns a new function you can assign to another function
second(); // 8 - passing no arguments will execute the function as it stands
max(8, 9, 10, 11, 12); // 12 - once you pass the minimum passed in you get a result

You can also not pass a minimum to just keep returning the curry until you call it with no arguments.

Great, now what else does it have? Well now we have curry we might want another way to curry the right arguments. Here we have func.flip. Say you want to map something that will increment the number, you can flip around the closure libraries array functions to do that for you:

var addOneToAll = func.curry(func.flip(goog.array.map), 2)(function(a) {return a+1;});

Want even more? Well the library already has these made for you. You can just use func.map which is already curried so the above is equivalent to:


var addOneToAll = func.map(function(a) {return a+1;});

There are a range of functions you can use - checkout the read me for more information.

Great, how about point-free style? Well we've got that covered to. func.compose will let you join up functions the way you want to. For instance let's say I want a filter function that will look at the models of an object and see if they're not in an array of existing models:

var notInModels = func.compose('!x', func.isIn(models), 'x.getModel()');

WOAH! slow down there, what happened? Well most the 'func' functions can also take strings and convert them to functions. If you want a simple lambda that's a single line just write it with x as the input and it will return the result.

Want to learn more? Checkout the github repository. The library is built to run with closure tools and is built with inspiration from functional javascript and http://drboolean.tumblr.com/


Sunday, May 13, 2012

PlastronJS - the todomvc example walkthrough



A walkthrough of the code for the PlastronJS TodoMVC example

Dot vs square bracket notations in Closure

In javascript you can use square brackets and dot notation almost interchangeably:

a['property'] === a.property


Which is great and you can do things like:

function createGet(property, fn) {
  A['get'+property] = fn(A[property]);
}

so you can then put getters on an object (in this case A). e.g:

A.one = 1;
A.two = 2;
var sayNumber = function(num) {return "number is: " + num;};
createGet('one', sayNumber);
createGet('two', sayNumber);
A.getOne(); // "number is : 1"
A.getTwo(); // "number is : 2"

There are some other great uses as well such as the delegateEvents in backbone.js

But unfortunately in closure we can't do this because after compilation:


a['property'] !== a.property


This is because string literals will not be compiled, but properties with dot notation will be renamed. Fear not however because we don't actually need to mix these two and it does help if you think about these not being the same.

If you have a look at plastronjs you'll notice that setting a schema will look like:

var schema = {
  'prop1' : {
    get: function ...
    set: function ...
  },
  'prop2' : {
    get: function ...
    set: function ...
  }
};

so the properties have strings and the get and set don't. Closure will rename strings but not properties. The reason they are like this is that property will be called on using model.set() and model.get() that take a string as the first argument and those can either be sent or received through a sync. So basically prop1 and prop2 can be EXTERNAL. get and set are only ever used inside our program so they are INTERNAL.

so how about the options object that gets passed to a model? it takes:

'attr', 'sync', 'schema' etc. Why are those in quotes? Well the fact is that I've allowed you to just pass through ordinary properties at the top level, so who is to say when those are compiled (sat attr -> a) that you haven't defined 'a' as a property? I'm allowing you to mix external and internals so to be safe I have to use the quotes. In doing that I then have to refer to the options object for object['attr'] instead of object.attr so we're losing a little compiled space but making things much easier to pass through attributes.

Just to make things easier I've also given you a special method in mvc.Model which will allow you to get around typing the string every time you need an attribute. What we can do is bind a function to that attribute to make things easier. Say we have an attribute 'star' that is either true or false. If I reuse it a lot, instead of doing model.get('star') I'd like something a bit easier. mvc.Model#getBinder to the rescue. Now you can do this:

var star = model.getBinder('star');
star(); // true
star(false);
star(); // false

The getBinder method is simple and looks like this:

mvc.Model.prototype.getBinder = function(key) {
  return goog.bind(function(val) {
    if (goog.isDef(val)) {
      this.set(key, val);
    } else {
      return this.get(key);
    }
  }, this);
};

It will allow you to get and set through a function whose name can be compiled and also makes it easy to call.

So what is the moral of the story? Well there are three:

  1. If a property is visible externally or is mixed with external properties that use square brackets
  2. If a property is internal only to the project then use dot
  3. If you're using a lot of square brackets think about binding it to a function

Keep these in mind when you start and after a bit of practice you won't miss being able to mix notations, and it will certainly help you keep down differences between the compiled and uncompiled versions of your code.

Saturday, May 12, 2012

TodoMVC PlastronJS example



Here is a run through of how to get the todoMVC example, checkout the uncompiled code and how to compile changes you make.

If you're having trouble seeing the characters try clicking the youtube button on the video and watching it in fullscreen.

Wednesday, May 9, 2012

Functional Javascript

There's been a bit of buzz about Functional javascript lately. It's easy to see why as javascript is such a flexible language that you can use it in both the functional and Imperative style. When I talk about functional style I'll mostly be referencing a style called point-free.

I'm a big advocate of the Closure Library and believe it will port well over to the functional style - even though it hasn't got all the right tools... yet.

So just what is the difference? Well Functional style is made up of functions (thus the name) and not objects. An object is something that has state (this "this" variables) and this is the enemy of the pure function. A pure function is what you strive for in a functional language and it's a pretty simple thing. A pure function is a function that when given an input will always return the same output for that input with no side effects. e.g:

// Pure function:
function pure(x) {return x;}

// Not a pure function:
var a = 0;
function impure(x) {return x+a};

now these functions are similar... until someone changes a. even if you change a (a = x) it is impure because now it has a side-effect (a is changed).

So why do we like pure functions? several reasons:


  • Pure function outputs can be memorized (as the same input gives the same output)
  • Pure functions are easy to test (no having to text different states)
  • Pure function allows code to run in parallel


Unfortunately the running in parallel doesn't really help us yet, but eventually javascript engines may be able to realize when a function is pure and run it. For example take the .map() function that runs a function on each element. If we know that function is pure we know that each function will not change the output on the next variable - so each map function can safely be run in parallel. If that function changes state however and the function uses that state for the output then we have to run them sequentially as the function needs to know what the state has changed to.

Right so pure functions are good, why can't we use them in the imperial style then? Well the fact is you probably already are. things like .map() .filter() and other new array functions come from functional style. Concepts also like partial application and currying are also from functional style. So we're already starting to use some concepts today.

So is there any more cool stuff we can use? Sure. Plenty. Function composition. In fact underscore has a nice little function that allows you to use it. What function composition allows you to do is chain together functions to create a single function you can use.

I hope that has whetted your appetite a little. I'll probably go over some more in later posts but for now there is more you can do learn. First check out this talk and visit the links. Teach yourself Haskell with a good book and stay tuned.

Tuesday, May 8, 2012

how to display a collection

There are two options when displaying a collection of controls, both with their drawbacks.

Refresh

The easiest one to master is the refresh. All you need to do is listen to any change to the collection then scrap all the child controls and re-render new ones. It's simple and means that your child controls won't need listeners on the models to change presentation - instead you can put logic in your templates to display the control with the model's current state.

This is the approach I've taken with the todomvc. It uses a lot less code (in fact compiled it is the smallest example on the entire site including the pure closure example - and it includes extra feats like routing!) and is pretty efficient for small lists. It can be slow though as it removes all the controls first and re-renders them and can cause memory leaks.

You should be cleaning up listeners on elements every time you remove a control. Luckily the closure library uses good.ui.component and automatically will cleanup listeners for you when you call dispose(). This wonderful mechanism has been used by mvc.Control so anytime you call a this.on, this.click, this.bind, etc. the handler is registered on the control and will be removed when you call mvc.Control#dispose().

Pretty neat eh? So PlastronJS has all the mechanisms you need to make this happen. It can cleanup for you on the refresh and can listen to any changes on a child that need you to refresh (anyModelChange).

Individual Updates

Now to the tricky part. What happens if you have complex child controls? well PlastronJS helps you with this as well. the collection has a listener for modelChange which only fires when the shape of the children change. Now what do I mean by shape?

The shape of the children refers to changes in sort order, or adding or removing children. If you want you can think of it as comparing an array of just the child model ids. So if you update a child but the list order doesn't change then modelChange will not fire. This means no re-rendering the entire list just for one small change.

But this comes at the price of complexity. The child models now have to manage their own display with listeners on their models. You will also need to write a function to run through the controls children and match the existing controls with it's collections child models, but what it means is less changes to the DOM and a faster site.

The truth is it can be complex managing this - (what happens if the child control disposes itself? how should you shuffle around the resorted nodes?) and as yet PlastronJS leaves you with the details.

In the next iteration though I'm planning some way of letting you attach what a child control should look like and have PlastronJS deal with the shape changes by moving controls in the least amount of steps. This will probably come as a new mvc.ListControl that inherits from mvc.Control so stay tuned!

Principles of an MVC design

One of the things that I had to figure out when first using an MVC design was how things slot together. You have collections of models and collections of controls that all fit together somehow and you also have all the dependancies and listeners between them.

One of the things I disagree with in Backbone.js is the way a model has a link to it's collection. To me it felt like spaghetti code, why should an individual model need access to it's collection? It doesn't and this is one of the things that I baked in to PlastronJS.

I'm guessing this link was given so when a change was made to the model you could then pass the change up to it's collection - but this means the model knows it is in a collection. Instead in PlastronJS the collection will register handlers on each new model connected to it and so the collection model is in charge of it's changes and the model only deals with it's own. But how do you pass changes across? You do it in the control.

If you have a look at my todomvc example I have listeners on modelChange and anyModelChange which are fired by the collection when it's listeners on it's models are fired. Because it knows there is a change it can then do the calculations that are needed without having the models in the collection have an explicit link to it's collection.

This is the fundamental idea behind the interaction with the MVC. The user interacts with the view which is listened to by the control. The control then changes the model which alerts anything listening to it. So if I have a completed count on the list and the user ticks a completed button the interaction goes like this:

user click completed on view -> control listener executes and changes the model -> the model changes and alerts all listeners -> the collection which has a listener on that model fires a change event -> the control for the list picks up the event from the collection and updates it's view

As you can see all interactions should go from the view down to the model and back up to the view. Which leads to 2 basic rules when setting up event listeners in a control:


  1. listeners on the view should only update the model
  2. listeners on the model should update the view
There may be times when you want a change in a model to update another model, but I like to think of this as linking up the two models separately and should be done outside of a controller.

The reason to stick to this is simple - you don't want to repeat yourself. If you want to put a class "done" on an object when a checkbox is clicked and change the model to complete you don't want to do both on clicking the checkbox. For this you need two listeners, one that sets the model to complete when the checkbox is checked and a listener on the model that will set the class when it's checked attribute is set. That means that any new interactions you put in will automagically set the done class (say if later you want that item to be shared and can get updated in realtime through a web socket or long polling).

Stick to those rules and you'll write less code, more flexible code and just plain better code.

Now how about when you click a "select all" in the collection's control? Easy, the collection's control should have a reference to all the children controls and pass along the call to them to set it's model as completed.

You can also do things like have a child set itself as the only one to complete by passing up to it's parent (this is allowed because they are controls - not models - and live in a definite tree structure on the page) itself and have the collection have a setOnlyChildComplete() method which could go through it's own children and only set the given one to complete.