The Software Simpleton

Nomadic cattle rustler and inventor of the electric lasso

Emberjs - fillIn Test Helper With Key Events

I’ve imposed a self enforced ban on using observers when using ember. For example, I previously used two way binding in my template to bind the value attribute of an input element to a property

I would then create an observer on this bound value like this:

observer.js
1
2
3
queryDidChange: Ember.observer('query', function(){
  //some transofomation
}

This has generally led to a world of pain that I lamented about in this post.

What I do now in this situation is use something like the input DOM event:

input.js
1
2
3
4
5
  input: function(e) {
    var query = e.target.value || '';

    set(this, 'query', query);
    //do stuff

I can do any transformations in this event handler without the pain of obsevers or 2 way binding, I am in control of what is happening.

This is all well and good but what is not good is that this is not testable with the current ember test helpers.

There is the fillIn test helper but this will just set the value of an input to the supplied string without raising any key events:

fillIn.js
1
2
3
4
5
6
7
8
function fillIn(app, selector, contextOrText, text) {
  //init code

  run(function() {
    $el.val(text).change();
  });
  return app.testHelpers.wait();
}

What I needed was a way for the appropriate key events to be raised after every character. I might also have code in keydown and keyup for example.

With this in mind, I created this test helper to meet my requirements:

fillInWithInputEvents.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function fillInWithInputEvents(app, selector, contextOrText, textOrEvents, events) {
  var $el, context, text;

  if (typeof events === 'undefined') {
    context = null;
    text = contextOrText;
    events = textOrEvents;
  } else {
    context = contextOrText;
    text = textOrEvents;
  }

  if (typeof events === 'string') {
    events = [events];
  }

  $el = app.testHelpers.findWithAssert(selector, context);

  $el.val('');

  focus($el);

  function fillInWithInputEvent(character) {
    var val = $el.val();
    var charCode = character.charCodeAt(0);

    val += character;

    run(function() {
      $el.val(val).change();
    });

    for (var i = 0, l = events.length; i < l; i++) {
      run($el, "trigger", events[i], { keyCode: charCode, which: charCode });
    }
  }

  for (var i = 0, l = text.length; i < l; i++) {
    fillInWithInputEvent(text[i]);
  }

  return app.testHelpers.wait();
}

The above helper will input the text one character at a time and raise any supplied events.

For example if I only want to raise an input event with each character then I would use it like this:

single.js
1
2
  visit('/')
    .fillInWithInputEvents('input.autosuggest', 'Michael', 'input')

Or if I want to raise more than one event then I can supply an array of input events:

multiple.js
1
2
  visit('/')
    .fillInWithInputEvents('input.autosuggest', 'Michael', ['input', 'keydown'])

You can use the helper like this in an ember-cli test-helper and I have created this pull request to get it included with the ember source.

Emberjs - Action Maker

I am currently working on an ember project using 1.7.1 and I’ve reached the point of no return with regard to passing action names down a component hierarchy and then bubbling them back up using sendAction. I believe the problem is still present in recent versions of ember and we need to somehow make this more user friendly.

I will illustrate the problem with an easily grokked todo example before giving a couple of solutions.

Here is a list of todos:

Here I am creating a todo-list component and specifying an action that I want called when a todo is checked to signify it is finished.

Below is a route with a finishTodo action that is referenced in the above code sample:

daddy.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
App.IndexRoute = Ember.Route.extend({
  actions: {
    finishTodo: function(todo) {
      console.log('in root');
      todo.set('isFinished', true);
      todo.save().then(function(){
        console.log('finished');
      });
    }
  },
  model: function(){
    return this.get('store').find('todo');
  }
});

All good so far but with the current state of data down and actions up, I need to pass this action name down to each child component that would use sendAction to call it.

In the example, I need to specify the action name in each todo-item component that the todo-list component creates:

I then need to bubble this up from the child todo-item component:

todo-item.js
1
2
3
4
5
6
7
8
9
App.TodoItemComponent = Ember.Component.extend({
  actions: {
    finishTodo: function(todo) {
      console.log('in child');

      this.sendAction("action", todo);
    }
  }
});

This gets bubbled up to the todo-list component that uses sendAction to bubble this up to the route:

todo-list.js
1
2
3
4
5
6
7
8
9
App.TodoListComponent = Ember.Component.extend({
  actions: {
    finishTodo: function(todo) {
      console.log('finish in parent component');

      this.sendAction("action", todo);
    }
  }
});

Here is a jsbin that shows the up and down duplicity in its entirety.

One sure sign of tight coupling is the number of places/files that you need to change for one method name change. As developers, we should be seeing this type of thing as a red flag that requires attention.

One way round this is to create a helper to package up the action, the context and any arguments that are needed to call the action. This can be achieved with a handlebars subexpression and a handlebars helper.

I can refactor the todo-list component to this:

The above code uses a handlebars subexpression to create a method named action on each todo-item component, I pass in the targetObject which in this case is the controller but you can reference anything that is accessible and has an actions hash, I also pass the action name I want called and any additional arguments.

The subexpression calls this handlebars helper that returns a higher order function:

makeAction.js
1
2
3
4
5
6
7
8
Ember.Handlebars.registerBoundHelper('makeAction', function() {
  var context = arguments[0],
    args = Array.prototype.slice.call(arguments, 1 , -1);

  return function() {
    return context.send.apply(context, args);
  };
});

I can then call this action in the todo-item component:

1
2
3
4
5
6
App.TodoItemComponent = Ember.Component.extend({
  change: function(e) {
    var todo = this.get('todo');
    this.action(todo);
  }
});

Here is a jsbin of the above.

This makes things a little more sane for me and I can eliminate a lot of code. Another alternative that I am considering is to enhance the global event bus I previously blogged about.

The alternative is to carry on with what is currently on offer but I’ve just reached my limit with that.

Emberjs - Simple Global Event Bus

Following on from my last post about Communication Between Components, somebody rightly pointed out in the comments that another way of doing this is to create a global event bus as a service and inject it into any components that need it.

I mentioned in my last post that the requirements are for the publisher and subscriber of events to know nothing about each other. A global event bus fits this bill. A global event bus, allows publish/subscribe communication between components without requiring the components to explicitly register with one another (and thus be aware of each other).

I think this will give us the quickest win for the stated requirements and we can quickly cobble together an Ember.Service that will act as an event bus using Ember.Evented:

event_bus.js
1
2
3
4
5
6
7
8
9
10
11
App.EventBus = Ember.Service.extend(Ember.Evented, {
  publish: function() {
    return this.trigger.apply(this, arguments);
  },
  subscribe: function() {
    return this.on.apply(this, arguments);
  },
  unsubscribe: function() {
    return this.off.apply(this, arguments);
  }
});

An initializer is created to inject the event bus as a singleton into anything that might use it:

initializer.js
1
2
3
4
5
6
7
8
9
10
11
12
13
Ember.Application.initializer({
  name: 'load-services',
  initialize: function(container, application) {
    var eventBus = App.EventBus.create();

    application.register('event-bus:current', eventBus, {
      instantiate: false
    });

    application.inject('component', 'EventBus', 'event-bus:current');
    application.inject('controller', 'EventBus', 'event-bus:current');
  }
});

Now a parent component can pubish events using the injected EventBus

publish.js
1
2
3
4
5
6
7
App.XPeopleComponent = Ember.Component.extend( {
  actions: {
    callChildren: function() {
      this.EventBus.publish('parentCalling');
    }
  }
});

Child components can now subscribe and unsubscribe to these events without referencing the parent component:

subscribe.js
1
2
3
4
5
6
7
8
9
10
11
12
13
App.XPersonComponent = Ember.Component.extend({
  _initialize: Ember.on('init', function(){
    this.EventBus.subscribe('parentCalling', this, 'onParentCalling');
  }),

  onParentCalling: function() {
    alert('parent called for ' + this.get('person.name'));
  },

  _teardown: Ember.on('willDestroyElement', function(){
    this.get('EventBus').unsubscribe('parentCalling');
  })
});

I think this is the quickest path to market right now as it requires little effort. Subscribing to events based on a string literal is less than ideal but this fits my purpose of being outside the bounds of data down and actions up where no data has changed and the publisher and subscriber don’t know anything about each other.

Here is a jsbin that puts it all together.

I am very open to somebody pointing out a better way.

Emberjs - Communication Between Components

Communication Between Components

A question that I see frequently asked is how can a parent component communicate with child components.

A child component can communicate with a parent in a number of ways with the most commmon at this time of writing with ember 1.11.1 is to use sendAction.

For example, a parent component can tell a child component what its primary action is or give a named action to its children:

And the child component can then call this action:

child1.js
1
2
3
4
5
6
App.XPersonComponent = Ember.Component.extend({
  actions: {
    callParent: function(person) {
      this.sendAction("action", person);
    }
  },

I have never warmed to the abstraction of callable actions existing in an actions hash and from what I can tell, it will be possible in ember 2.0 to simply pass actions around as plain old javascript functions which is something that I welcome.

In the mean time, it is possible to simulate this behaviour by creating a handlebars bound helper that returns a higher order function:

makeAction.js
1
2
3
4
5
6
7
8
9
10
11
Ember.Handlebars.registerBoundHelper('makeAction', function(){
  var actionName = arguments[0],
      args = Array.prototype.slice.call(arguments, 1, -1),
      self = this;

  args.unshift(actionName);

  return function() {
    return self.send.apply(self, args);
  };
});

A parent component can then yield this to a child component:

Here is a jsbin that shows this in action.

Parent Component calling Children

A child component calling a parent is fairly straight forward and is well laid out but what about when a parent component wants to call its children?

What do we do if we have a parent that wants its chidren to do something like to zoom to an element or something that is not a reaction to some state mutation? The official ember guidance is you should use the actions up and data down paradigm where you push data changes down to the child components but there are occasions when this does not fit. There are times when you want a child component to do something when no data has changed. You can certainly fudge this but mutating a state change to get a child component to react is pretty awful in my opinion and not something that you should do. This is an occassion when actions up and data down does not go far enough, which I have previously blogged about here and here.

So what do we do?

Subscribe to Parent Events

The first way I solved this was to use Ember.Evented. A component can mix in the Ember.Evented mixin:

people.js
1
2
3
4
5
6
7
8
9
App.XPeopleComponent = Ember.Component.extend(Ember.Evented, {
  actions: {
    callChildren: function() {
      this.trigger('parentCall');
    },

    receiveFromChild: function(person) {
      alert("received " + person.get('name'));
    }

Ember.Evented is mixed into the component and trigger is called on line 3 of the above code sample to broadcast an event to any listening children.

Below is how a child component can subscribe to these events:

child2.js
1
2
3
4
5
6
7
8
9
App.XPersonComponent = Ember.Component.extend({
  _setup: Ember.on('didInsertElement', function(){
    this.get('notifyer').on('parentCall', this, 'onParentCall');
  }),

  onParentCall: function() {
    alert('parent called with ' + this.get('person.name'));
  }
});

Line 3 subscribes to the event and supplies a handler which will be called when the parent triggers the event.

I don’t have a great big problem with this although it is not that nice having to explicitly subscribe via the parent component as opposed to just subscribing to an event.

Here is a jsbin that shows this in action.

Registration with the parent component

Another way of solving this is for the child component to register itself with the parent:

register.js
1
2
3
4
5
6
7
8
9
10
11
App.XPersonComponent = Ember.Component.extend({
  _setup: Ember.on('didInsertElement', function(){
     var parent = this.nearestOfType(App.XPeopleComponent);

     parent.registerChild(this);
  }),

  parentCalling: function() {
    alert('parent called with ' + this.get('person.name'));
  }
});

The child component finds the parent on line 3 of the above and below is the registerChild method that is used to register the child component:

parent2.js
1
2
3
4
5
6
7
App.XPeopleComponent = Ember.Component.extend( {
  children: Ember.A(),

  registerChild: function(child) {
    this.children.pushObject(child);
  }
});

I think this is less favourable because of the very tight coupling. Here is a working jsbin that shows this in action.

Register via Binding

Sam Selikoff offered this way of registering child components via a binding.

First, add a _register method to the component that executes on init:

parent3.js
1
2
3
4
5
6
App.FullscreenMapComponent = Ember.Component.extend({
  _register: function() {
    this.set('register-as', this); // register-as is a new property
  }.on('init')

});

Then, when rendering the component, supply a property to bind register-as to:

Now, the controller has a reference to the component, and can call methods directly on it:

route.js
1
2
3
4
5
6
7
8
App.PinsRoute = Em.Route.extend({
  actions: {
    focusSelectedPin: function() {
      this.controller.get('fullscreenMap').panToSelectedPin();
    }
  }

});

I think this method suffers from the same coupling as the other methods.

So what I want is a way that is less coupled. I want the publisher and the subscriber to know as little about each other as possible. I also do not want to use state mutation as a means of communication.

UPDATE: Somebody mentioned in the comments that a global event bus is anohter way of achieving what is required and I created this post that explains how to achieve this.

clojure’s core.async

I love this quote from the first sentence of this post on the clojure blog about core.async.

There comes a time in all good programs when components or subsystems must stop communicating directly with one another.

The roots of core.async go back to Hoare’s Communicating Sequential Processes (CSP).

I’ve done a good bit of hobby development with clojurescript and I love using core.async channels for communication between components. It can be used synchronously and asynchronously.

With core.async, you create channels which can be thought of as independent threads of activity (I don’t mean threads as in multi-threaded) that can be published to or subscribed to.

I have previously blogged about Handling Mouse Events With core.async.

Core.async has nailed the decoupling of publishers and subscriers via queueable channels.

Epilogue

With core.async the publisher and subscriber know nothing about each other which is really the goal of event based systems and I think both ember and react suffer from the model of handing down functions from parent to child as there is a high degree of coupling.

It would be interesting to see how ember was if we were dealing with channels as a means of communication rather than passing down callable functions.

There is a js-csp library and David Nolen wrote this post about ES6 Generators Deliver Go Style Concurrency.

Ember is going with the data down, actions up meme but there are times when this does not fit and activating state changes as a means of communication can only lead to trouble.

Emberjs - Refactoring Away From arrayComputed

Word on the emberjs street has stated that the reducedComputed familty of computed property macros are to be deprecated. I’ve used these macros in a number of places in my current contract. I also previous blogged about arrayComputed in this post.

In the example, I used arrayComputed to group the number of deals that each particular company had and supplied a total for each grouping. Here is a working jsbin that illustrates the old code. Each deal has a deal state and I group a particular company’s deals by the deal state and give it a total:

I will now begin the refactoring. The first thing I notice after changing the references in the jsbin to point to ember 1.11.0 is that the console is filled with deprecated warnings. The first warning to get rid of is:

Ember.ObjectController is deprecated, please use Ember.Controller and use `model.propertyName`

This referers to line 1 of the following gist:

And below is the ObjectController that the itemController references in the above template:

old.js
1
2
3
4
5
App.CompanyItemController = Ember.ObjectController.extend({
  dealTotals: App.computed.groupable('deals',function(deal){
     return deal.get('state');
  })
});

I believe controllers are on the condemned list and components will be the main unit of currency so the obvious thing to do is replace the itemController with a component. My updated template looks like this:

It is worth noting that the #each foo in bar syntax is also going to be depreceated in favour of the new block syntax that I mentioned in my last post and you can see how it is used on line 2 of the above. This pretty much slays most of the warning messages and I now have a component hierarchy as opposed to nested each blocks.

I have the top level company component that is rendered for each company.

Below is the x-company template:

Each company will render an x-deals component for each group of deals that are grouped by deal state. The x-deals template looks like this:

The x-deals component contains a collection of x-deal components. The x-deal component’s template looks like this:

Refactor to the infamous @each Helper

I now want to replace the arrayComputed macro I created to group the deals. Below is my original macro definition:

oldArrayComputed.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
App.computed = {};

App.computed.groupable = function(dependentKey, groupBy){
  var options = {
    initialValue: [] ,
    initialize: function(array, changeMeta, instanceMeta){
    },
    addedItem: function(array, item, changeMeta, instanceMeta){
      var key = groupBy(item);

      var group = array.findBy('key', key);

      if(!group){
        group = Ember.Object.create({key: key, count: 0});
        array.pushObject(group);
      }

      group.incrementProperty('count');

      return array;
    },
    removedItem: function(array, item, changeMeta, instanceMeta){
      var key = groupBy(key);

      var group = array.findBy('key', key);

      if(!group){
         return;
      }

      var count = group.decrementProperty('count');

      if(count === 0){
         array.removeObject(group);
      }

      return array;
    }
  };
  return Ember.arrayComputed(dependentKey, options);
};

Below is how it was used in the old itemController.

olditem.js
1
2
3
4
5
App.CompanyItemController = Ember.ObjectController.extend({
  dealTotals: App.computed.groupable('deals',function(deal){
     return deal.get('state');
  })
});

What was convenient about arrayComputed was that if any of the company’s deal’s state attributes changed then the whole property would recalculate and group accordingly. I wanted to keep this behaviour so I first of all refactored to something that has caused me problems in the past and that is to use the @each indicator. The @each indicator will observe an array for additions and removals AND also it will observe a proprety of each element in the array for changes.

I refactored the arrayComputed macro to this:

neweach.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
App.computed.groupable = function(dependentKey, eachKey,  groupBy){
  return Ember.computed(dependentKey, eachKey, function(){
    var ret = Ember.A();

    this.get(dependentKey).forEach(function(item){
      var key = groupBy(item),
          group = ret.findBy('key', key) || Ember.Object.create({key: key, count: 0, deals: Ember.A()});
      if(!ret.contains(group)) {
        ret.pushObject(group);
      }

      group.incrementProperty('count');
      group.deals.pushObject(item);
    });

    return ret;
  });
};

The above code simply returns a standard computed property on line 2 and takes a dependentKey that is the array being observed and an eachKey that will contain the @each indicator.

Below is how the x-company component that replaced the old itemController uses the refactored macro. company.deals.@each.state will observe every element of the array for changes to the state attribute.

x-c.js
1
2
3
4
5
App.XCompanyComponent = Ember.Component.extend({
  dealTotals: App.computed.groupable('company.deals.[]', 'company.deals.@each.state', function(deal){
     return deal.get('state');
  })
});

I have created this jsbin to show its usage. I’ve also updated the bin by adding a dropdown for each deal in the group that can be used to update the deal’s state and you can see things recalculate.

Data down and Actions up

I really was not happy about this refactoring, part of the job of arrayComputed was to try and nullify the performance pains and problems of @each. When I first started using ember, @each was a huge performance drain. It has improved but I really don’t know when it is going to be called by the ember runtime and when it is called is outside of my control. As I mentioned in this this post, I really want to stop using things that are outside of my control. I have absolutely no idea when or how many times this macro will be called by the ember runtime and as such, I’m not going to use it. Experience tells me that I will run into surprises and other headaches if I don’t remove it now.

I refactored the computed property macro to a plain old javascript util function:

util.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
App._ = {};

App._.groupBy = function(coll, groupBy) {
  var ret = Ember.A();

  coll.forEach(function(item){
    var key = groupBy(item),
        group = ret.findBy('key', key) || Ember.Object.create({key: key, count: 0, deals: Ember.A()});
    if(!ret.contains(group)) {
      ret.pushObject(group);
    }

    group.incrementProperty('count');
    group.deals.pushObject(item);
  });

  return ret;
};

The top level x-company component now explicity determines when the array grouping is recalculated:

recalc.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
App.XCompanyComponent = Ember.Component.extend({
  actions: {
    regroupDeals: function() {
      this.groupDeals();
    }
  },

  groupBy: function(deal){
    return deal.get('state');
    },

  groupDeals: function() {
    this.set('dealTotals', App._.groupBy(this.get('company.deals'), this.groupBy));
  },

  _setup: Ember.on('didInsertElement', function(){
    this.groupDeals();
  })
});

The didInsertElement handler on line 16 calls a groupDeals method that calls the util method. I also supply a regroupDeals action on line 4 for down level components to call this action when a deal state changes.

For example, the lowest level x-deal component will call an action when the dropdown changes:

This component bubbles the action up when the select element changes:

x-deal.js
1
2
3
4
5
6
7
App.XDealComponent = Ember.Component.extend({
  actions: {
    changeDealState: function(deal) {
      deal.set('state', this.$('select').val());
      this.sendAction();
    }
  },

This is bubbled up to the x-deals component:

x-deals.js
1
2
3
4
5
6
7
App.XDealsComponent = Ember.Component.extend({
  actions: {
    regroupDeals: function() {
      this.sendAction();
    }
  }
});

Which bubbles it up to the x-company component.

I really don’t like having to bubble things up this way but I don’t think that there is a better way available in 1.11.1 but I’m sure there will be at a future day as this is a bit tedious and coupled.

Epilogue

I much, much, much prefer my final refactoring as opposed to using the infamous @each indicator as I am in total control of when things happen. I can also introduce aynchronicity if the dataset grows and I need to call the server for the groups. It is up to me when I return the recalculated dataset.

I would take it further and use pubsub to have a reflux like data store do the recalculation as I mentioned in this post but this will at least do for now.

I think ember should remove the @each helper because people will use it because of its convenience.

I’m on the fence if I consider computed properties an evil but one thing is for sure, I do not think they are needed as often as I see them used.

I want to explicitly state when my collections/objects are available for re-rendering. I think this is the most sensible approach and things work much nicer with a top down approach.

Here is an updated jsbin with the final refactoring.

Emberjs - Passing Block Params From a Component

I have previously blogged about a hack I had to use to get the right context when using a component in its block form.

The example I gave in the post was for an autocomplete component that would give the developer the ability to prepend their own customisation to a selection. The example I gave was prepending an avatar like in the image below.

The original component could be used in its block form like this:

And here is the original component template file:

There is no way in the above to set what the context would be for the code block that is ran when the yield helper is called. The context was non-negotionable and the context would be that of the template it was declared in e.g. the controller. The only way round this was the hack that I described in the previous post.

As of ember 1.10.0, it is possible to pass internal values to a down stream scope with the new block params syntax.

I can refactor my component’s template to look like this:

  • Line 1 uses the each helper with the new block params syntax to specify a context named selection.
  • Line 4 uses the yield helper to pass the block param to the template or code block that is rendered between the component’s definition.

Below is how I can use the block param when the component is declared with a block:

  • line 2 binds the selection var that is passed to this code block via the yield helper in the previous code example.
  • line 3 puts the var to use.

Here is a jsbin with a working simpler example.

Emberjs - Observers the Root of All Evil

Observers Are Like Crack Cocaine only more destructive….

After 2+ years of working on the same emberjs application, I have learned the hard way that the observable primitive that ember exposes is something that you and your team should outlaw this very instant. One problem the ember community has is that a lot of the code examples that you might find online use observers. If you are new to ember then you would have no reason not to trust these well meaning examples.

Below is the first one I plucked from the multitude:

observer.coffee
1
2
3
4
5
6
7
8
App.DynamicBoundTextField = Ember.TextField.extend
  placeholderBinding: 'content.name'
  # Update the remote property's value when the value of
  # our text field changes
  _setRemoteValue:(->
    val = @get('value')
    @set("controller.data.#{@get('content.key')}", val) if val?
  ).observes('value')

This post is not a dig at the person who wrote this as I have gone down this horrible route many times. I am probably more guilty than most. I’ve also used observers in more contrived examples than this. This is definitely a case of let ye without guilt cast the first stone.

The above looks very reasonable and I don’t have to write any code to keep things in sync, I pass that responsibility to ember. For me this is where the problems start. I’ve lost control of the process, what if I want to throttle or debounce the user input? If you have written any sort of user input control then you will know that throttling is a technique to limit the amount of times a function is called in response to user input. If I am using the above code then how do I throttle the user’s input? You could definitely cobble together some sort of hack but you have now lost control and you are making the solution fit the problem.

I recently looked at a bug to do with a component that uses the html5 contenteditable attribute to expose some very, very simple WYSIWYG editing to the user. The component did something similar by observing the value of the contenteditable div and updating a value whenever the content changed. Working with contenteditable can be quite fiddly and if you are changing the markup, you often have to reposition the cursor at the end of the div’s content. The bug I was fixing was that the cursor did not always reposition itself at the right time after the user had finished their input and the ember run loop had flushed the changes. I found the code very difficult to reason about but more importantly it was outside of my control.

I removed the observer and refactored to this:

input.js
1
2
3
4
5
6
7
8
input: function(e) {
  var route, text;
  text = this.$().text();
  this.set('prop', text);
  route = this.routeLink(text);
  this.$().html(route);
  this.setEndOfContentEditble();
}

I am using the input event to do the simple things and update properties manually. I have control of what is going on.

I removed all observers and all computed properties and sanity was instantly returned.

The above is a ridiculously simple example that serves to illustrate how difficult coding can be in a really simple situation when you have lost control of what is going on. With observers and computed properties, it is down to ember, the run loop and a whole host of other contributing factors to decide when updates happen and observers fire. You really do not need the headaches that this can cause. This can get worse if you have computed properties and observers watching the dependant keys as chain reactions and other unexpected events can occurr. This is the antithesis of side effect free coding. This is the wild, wild west. Ember seems to be in the process of removing a lot of complexity and I think they should add observers and computed properties to the list. The more I use ember, the more I just want to use POJO objects and arrays. My worry for ember is that it went to the trouble of creating its own object model that starts at the very root ancestor. There is a lot of complexity inherint in such an approach.

Below are some of the problems and pain that can be caused by illicit use of observers and computed properties.

  • it is difficult to hold a mental model of the code if observers and computed properties are used to orchestrate data flow.
  • You are pushing the responsibility of when things happen to ember and outside of your control.
  • Observers and computed properties drive state/data flow into unexpected and mentally troubling paths.
  • Observers have no context, you have no idea what triggered the change.
  • Observers can cause chain reactions of other observers and can fire multiple times.
  • Mutating state changes in response to an observer firing breaks the law of demeter.

Observers and computed properties are seemingly convenient but they bring large scale trouble into simple situtations.

I would like to see a reflux like data flow story in ember and I blogged more about this here and here.

I’ve also recently started this project which I will flesh out more before blogging about it.

The first path from addiction to these ugly primitives is to admit you have a problem. After that reach out and find the nearest support group in your neighbourhood.

Remember you are not alone.

Emberjs, Reflux, Immutability, No Ember Data, No models….sanity?

Where we are

In my last post, I put forth the argument that the new data flow story of ember next does not go far enough. I now want to suggest a way that we could bring some much needed sanity to our ember applications. I have been on the same ember project for 2+ years and here are some of the problems that I have found with ember during those 2+ years:

  • Ember often seems opaque and disjointed with a lot of magic happening behind the scenes to piece things together.

  • I find the whole bindings, observables and computed properties paradigms hugely problematic. I find it impossible to hold a mental model in my head about how my properties and dependant keys fit together. Using observers and computed properties often causes surprises as a whole host of side effects could happen in both the UI and the data flow of the application. Cascading updates of partially resolved data could happen. Observers and cps can cause chain reactions of other observers and cps to fire. I would go as far as to say that both observers and cps should be depreceated.

  • I found ember-data unusable, I ended up forking my own version of ember-data 0.14 because I was sick of the carpet being pulled from under me with every release. I patched up the code as best I could and we still use this bastardised version to this day but it is far from ideal. Serializing and deserializing models is hugely expensive and does not scale. I want to work with POJOs not these complex resource hoggers.

Where we are heading

Data Down and actions up is the new meme being pumped with ember 2.0 but as I mentioned in my last post, this does not go far enough. Now I fully agree with the data down part but what I disagree with is actions up or more specifically actions being propagated to a parent component.

The problem with this is that a component is not the right place to change application state. What you will end up with is application state changing logic broken up and scattered across the whole application in all these various parent components. The component is not the right place to be dealing with this logic. Probably the main problem with the component handling application state change is that we will get unwanted or surprising UI side effects, this will be compounded if we are start using cps. What is needed is a layer above the components that is charged with changing application state. This layer then notifies subscribers of any changes to application state. This is described by flux or reflux as a unidirectional dataflow. I will shortly flesh this out with an example.

Where we could and probably should go

I have created this TodoMVC style application to illustrate the example and you can find the source code for this application here. I’ve added undo and redo functionality to illustrate how much easier this is with immutable datastructures which we will get to later.

Reflux/flux

The basic premise behind flux or reflux is:

  • There are actions
  • There are data stores (don’t think ember-data store)
  • The dataflow is unidirectional or data flows down.

The basic premise is that components call actions that initiate new data changes in the data stores (don’t confuse these stores with the ember-data store). Mutation of data can only happen through calling the actions. The data stores listen on the actions and mutate the data within the store. This keeps the data structure flat and lets the concerns of data manipulation be the purpose of the store. This totally removes the chance of side effects that may happen if components are charged with handling data on their own.

The stores then let the components know of any new data changes as a result of the actions. When data flows in a single direction like this, it is much easier to follow or reason about what is happening in your application which is in contrast to the state of ember today. Components can only manipulate or mutate data by executing an action.

If we take the example of the todo application, I have a file where I add any new actions that will be needed to manipulate the todos:

actions.js
1
2
3
4
5
6
7
8
9
10
11
export default [
  "addItem",
  "toggleItem",
  "toggleAll",
  "getInitial",
  "getTodos",
  "undo",
  "redo",
  "editItem",
  "destroyItem"
];

I will use creating a todo to illustrate the data flow. The above code lists an array of actions that signify all the operations that were required to manipulate the todos in the application and on line 2 is an addItem action that a component would call to create a todo. I hacked together a basic pubsub mechanism to mimic the role of the dispatcher in the real reflux library. This pubsub mechanism or poor man’s dispatcher is used to raise events from the components to the stores that are subscribed to these actions. I used an initializer to read the array of actions above. A TodoActions object is created and injected into all components. This will decouple the component and the store.

Manipulating todos is done through this UI:

The various components are arranged like this:

1
2
3
4
5
6
7
<section id="todoapp">
  <div>
    {{todo-header}}
    {{todo-list}}
    {{todo-footer}}
  </div>
</section>

The todo-list component in turn creates todo-item components like so:

1
2
3
4
5
6
7
8
<section id="main">
  <input {{action "toggleAll"}} id="toggle-all" type="checkbox">
  <ul id="todo-list">
    {{#each todo in todos}}
      {{todo-item todo=todo tagName="li"}}
    {{/each}}
  </ul>
</section>

The TodoHeader component contains the textbox that listens for keyDown events and if enter is pressed it will call the addItem action on line 6 of the code listing below:

header.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
keyDown: function (e) {
  Ember.run.next(() => {
    let text = e.target.value || '';

    if(e.which === 13 && text.length) {
      this.TodoActions.addItem(text);
      e.target.value = '';
      e.target.focus();
    }
    else if (e.which === 27) {
      e.target.value = '';
    }
    });
},

The pubsub mechanism will then let any subscribed stores know that an addItem event has occurred.

I have created a TodoStore object and included this simple mixin in the TodoStore to subscripe to the array of actions:

connect.js
1
2
3
4
5
6
7
import Ember from 'ember';

export default Ember.Mixin.create({
  connect: Ember.on('init', function(){
    this.Reflux.connectListeners.call(this, this.listenables);
  })
});

The mixin is then included in the TodoStore definition where it pulls in the list of actions via the listenables property.

store.js
1
2
export default Ember.Service.extend(ConnectListenersMixin, {
  listenables: TodoActions,

The convention of reflux is to name your handler onAction and the ConnectListenersmixin will check for the correct handlers on the class that includes it and subscribe the store to the array of actions that was listed earlier.

When TodoActions.addItem is called from the store, the pubsub mechanism will try and route the event to an onAddItem handler in the store.

The TodoStore, onAddItem handler is listed below:

addItem.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
onAddItem: function(description) {
  var newItem = {
    key: UUID4.generate(),
    created: new Date(),
    finished: false,
    description: description
  };

  let newList = mori.conj(this.todos, newItem);

  this.undoList = mori.cons(this.todos, this.undoList);

  this.updateList(newList);
},

The application has undo and redo functionality and I’ve used immutable data structures to make this fairly trivial. I’ve used mori’s persistable data structures because I am familiar with the data structures api from hacking around on clojurescript. Using immutable data structures opens up many doors such as easier comparison checking, diff checking and memoization to name but a few.

Immutable data structures are called persistent datastructures because they persist a previous version of themselves when modified. This is ideal for redo and todo functionality. I simply add the previous version to an undoList vector whenever the todos vector changes on line 11 of the code above. I have undoList and redoList vectors and I simply cons the application state onto the relevant vector that I can pop off when they are called….via actions of course!

The call to mori.conj will create a new persistent datastructure on line 9 of the above code and I then call updateList that looks like this and will then send the data down to any components that are listening for store events. updateList looks like this:

updateList.js
1
2
3
4
5
6
7
8
9
updateList: function(newList) {
  let payload = this.getPayLoad(newList);

  localStorage.setItem(localStorageKey, JSON.stringify(mori.toJs(newList)));

  this.trigger('listUpdated', payload);

  this.todos = newList;
},

The updateList function calls getPayLoad that packages up the updated list for the components to rerender based on the changes:

getPayload.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
getPayLoad: function(list) {
  let filter = get(this, 'filter'),
      todos = null,
      todosLeft = mori.count(mori.filter(filters['active'], list));

  todos = mori.filter(filters[filter], list);

  return {
    todos: mori.toJs(todos),
    canRedo: mori.count(this.redoList) > 0,
    canUndo: mori.count(this.undoList) > 0,
    todosLeft: todosLeft
  };
},

getPayLoad returns the current list of todos and also some additional information that is used to render the various components. Using this technique, I can totally avoid the computed properties that I would normally create for this type of operation. The components know nothing about the internal structure of the todos or that they are immutable data structures in the store as they are converted to normal POJOs on line 9 of the above code block.

I then include the following mixin in all the relevant components that want to listen to store events and re-render the application state changes:

listener.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import Ember from 'ember';
import ConnectListenersMixin from '../mixins/connect-listeners-mixin.js';

let set = Ember.set;

export default Ember.Mixin.create( ConnectListenersMixin, {
  listenables: ['listUpdated'],

  onListUpdated: function(payload){
    set(this, 'todos', payload.todos);
    set(this, 'canUndo', payload.canUndo);
    set(this, 'canRedo', payload.canRedo);
    set(this, 'todosLeft', payload.todosLeft);
  }
});

The store will not push these updates until all application state changing code has executed. I won’t get side effects or other surprises until the store has finished its work and pushed the changed application state back down.

The upshot of this architecture is that it is very easy to reason about, all mutations are happening in a controlled and logical fashion. I have not used a computed property nor have I used an ember-data class but of course this example is very trivial.

All the actions take a similar flow to this, below is the onEditItem TodoStore handler that has to clone the todo first to before making state changes:

editItem.js
1
2
3
4
5
6
7
8
9
10
11
12
13
onEditItem: function(key, description) {
  let existing = getExistingByKey(key, this.todos),
      index = getIndexByKey(key, this.todos),
      cloned = $.extend({}, existing);

  this.undoList = mori.cons(this.todos, this.undoList);

  cloned.description = description;

  var newList = mori.assoc(this.todos, index, cloned);

  this.updateList(newList);
}

Undo/redo is simple in this case as we are not having to roll back the changes on the server but diff checking is considerably easier with immutable data structures and we could use that to see what has changed. Below is how the undo action looks:

undo.js
1
2
3
4
5
6
7
8
onUndo: function() {
  let reverted = mori.first(this.undoList);

  this.redoList = mori.cons(this.todos, this.redoList);
  this.undoList = mori.drop(1, this.undoList);

  this.updateList(reverted);
},

Conclusion

I’m too long in the tooth to get too carried away with this simple example, I have no Ajax calls, web sockets or even nested data structure so the jury is still out on how this would pan out in a real application. Another question would be, why not just use react? I would use react if I was not on my current project but I am not about to advocate refactoring 2+ years of code to a different MVC framework.

What I like about what I have discovered with this simple experiment is:

  • I have not used any computed properties.
  • The data flow is easy to follow and I know where mutation happens.
  • I have not needed any ember data or model classes. After hacking on clojurescript and clojure, I honestly don’t think an expressive model is that important to represent state. I want to see how far I can go with POJOs and arrays.
  • Immutable data structures opens up many exciting possibilities.
  • I have an adequate mental model of what is happening, I am less likely to get surprised by what is happening or the often wild west nature of an ember application.

If you have any feedback on any of this then leave a comment below.

ember.js - Data Down, Actions up…better but Still Not Far Enough

The Ghost of Christmas Present

It is ironic that the thing that first drew me to ember is the thing that ended up causing the most excruciating pain. I am of course talking about two way data binding. An example of this is in this jsbin and in the code below which renders a list of todos. Two way databinding is employed to synchronise the isFinished boolean property of the todo and with the checked property of the input component:

1
2
3
4
5
6
{{#each todo in active}}
  <tr>
    <td>{{input type="checkbox" name="isFinished" checked=todo.isFinished}}</td>
    <td>{{todo.description}}</td>
  </tr>
{{/eachn}}

After years of DOM fiddling with jquery, this was instantly appealing as changes to the DOM are synchronised with the bound model without any extra code on from the developer. While this was great for breath taking ember demos, it led to a pandora’s box full of problems in produciton with earlier version of ember-data. In the first versions of ember-data, binding a model in this way led to the model’s isDirty flag getting set and if the model was not saved or the changes were not rolled back, the model remained in this dirty state and multiple errors would occurr as undefined methods were called on the current dirty state. I hacked around this pain by using the buffered proxy and other outlandish hacks but dealing with this is not something I ever want to experience again and still causes me to scream out in my sleep which is distressing for my partner.

While a lot of this is down to the fragility, rigidity and unforgiving nature of the early ember-data statemanager, the problem remains that it should not be the responsibility of the downstream input component to directly mutate the upstream model field and unexpected side effects occurred because of this. The problem is not particularly bad in this example but it becomes a big problem when you have a tree of nested components and shared data amongst these components, then it becomes difficult or sometimes impossible to reason about or track down what actually mutated the state. A component has its data changed in some other component that shares the same state has no idea where the mutation occurred. Ember needs a data flow story that is currently missing and computed properties and observables make the flow of data in an ember application very difficult to reason about and cascading partial updates from partially resolved asynchronous requests can get very stressful, I’ll elaborate more on this later but the ember core team seems to have reacted (pun intended) to some of the good things that react are doing and one way databinding will be the default as of ember 2.0.

The Ghost of Christams Future

Thankfully with the announcement of the ember 2.0 roadmap, the core team appear to recognise the dangers of this rampant mutation and they want to move a way from two way databinding, at least by default anyway. Databinding will be one way by default in ember 2.0 which greatly simplifies the interaction. The new paradigm that is being promoted goes by the meme data down and actions up. Child components will get their data from parent components, so when the parent component changes, the child component’s UI is updated. Data will flow down to the child components and the child components will notify their parent components of data changes by calling actions or pushing data up. The parent component should have the responsibility of persisting the changes and pushing those changes to the children. Now I fully support the data down approach, this makes absolute sense to me but I think that there are still problems with the data up approach, more on this later. But first let me now flesh out the data down, actions up approach with a refactor of the original example in this jsbin and below is the updated index.hbs template:

1
2
<h1>Todos</h1>
{{todo-list todos=model}}

It seems that the proxying controllers ArrayController and ObjectController are going to be depreceated and components will be the main currency so my todo-list becomes the top level component and below is its template:

1
2
3
4
5
6
7
8
9
<table>
  <tbody>
    {{#each todo in active}}
    <tr>
      {{todo-item todo=todo isFinishedChanged="isFinishedChangedHandler" tagName="td" }}
    </tr>
    {{/each}}
  </tbody>
</table>

The main thing to take away from the above code sample is that I am passing the parent component’s isFinishedChangedhandler to the child todo-item component. There is new syntax planned for actions but at the time of writing, I am using ember 1.10 and this remains the only way of passing handlers down. Below is the component’s code:

todo-list.js
1
2
3
4
5
6
7
8
9
App.TodoListComponent = Ember.Component.extend({
  actions: {
    isFinishedChangedHandler: function(todo) {
      todo.toggleProperty('isFinished');
      todo.save();
    }
  },
  active: Ember.computed.filterBy('todos', 'isFinished', false)
});

The todo-item child component that is rendered from the parent todo-list component has the following template:

1
<input type="checkbox" name="todo"/> {{todo.description}}

Gone is the input component and the bound isFinished property with the input's checked property.

Instead the isFinishedChangedHandler is called by the downstream component in the change event:

todo-item.js
1
2
3
4
5
6
App.TodoItemComponent = Ember.Component.extend({
  change: function(e) {
    this.sendAction('isFinishedChanged', this.get('todo'));
    return false;
  }
});

I’ve used sendAction but I expect this to change in ember 2.0. This is nice and neat in this simple of simplest examples. Once a checkbox is clicked the isFinishedChangedHandler of the parent controller is called and any state changes are synchronised down to the child components via the one way binding.

Ok great, I buy into this with this example but what if we have a more involved form with a number of text input fields, are we saying that we should write handlers for each input? This would very quickly get verbose, in react land, they have the ReactLink and I think in ember they are proposing something along the lines of this:

1
2
<input value={{mut firstName}}>
<input value={{mut lastName}}>

Data Flow in a Real world application

I see a lot of hype about html syntax for components, ok my templates look more like html but what I want from ember is a real dataflow story. React has covered this with flux and even better again with reflux.js where the data flow is unidirectional. In the real world application that I work on, I had a reasonably complex data table where all fields in the table needed to be editable in various ways and I was dealing with a large dataset, the table is infinitely scrolled and every sort operation etc. goes to the server. The sort macro etc. are useless to me in this scenario because all the objects are not in memory. There is a textbox on the top right which will filter the records further by whatever search term is entered. Below is how the table looks: Now where ember really shone was allowing me to add components to each table cell with a little bit of hacking that I blogged about here. This was great, every table cell is editable with a little help from html5’s contenteditable. The backing dataset of this table can have 1000s of records and there are multiple filters and sorting operations that all cause a requery of the external asynchronous data source. How does data come in and out of the the ember application? Currently ember lacks a data flow story which is disappointing in my opinion. How do I orchestrate the data coming from the server with its many filters and sort properties are selected from user input?

So the way I got round this was to use a combination a combination of query params, computed properties and observables. When the user selects a filter from the left menu in the screenshot above, a transitionTo action will occurr to a url with the filter added to the query params, something like addressbook/people/tagged?tag=191&company=856, this will cause execution to return to the route and select the new data. What do we do if a column is sorted or what do we do if some search text is entered to further filter the data? My solution is to maintain through a computed property the current parameters that will be sent to the server:

filterparams.js
1
2
3
4
5
6
7
8
9
10
11
12
13
filterParams: Ember.computed('filter', 'user', 'tag', 'company', function() {
    var company, contactimportjob, params, tag, user;
    params = {
      filter: this.get('filter'),
      page_size: this.get('pageSize')
    };

    params.company = this.get('company');
    params.user = this.get('user');
    params.tag = this.get('tag');

    return params;
  })

I do something similar with the sort which triggers a query param change that goes back to the route to fetch the new data. For the search I use an observer that listens for a bound property change:

search.js
1
2
3
4
5
6
7
8
9
10
11
12
  searchDidChange: Ember.observer("searchText", function() {
    var filterParams, params, searchText;
    if (this.get('filter') === null) {
      return;
    }
    searchText = this.get('searchText');
    filterParams = this.get('filterParams') || {};
    params = Ember.merge(filterParams, {
      like: searchText
    });
    return Ember.run.debounce(this, 'contentChanged', Ember.copy(params), 150);
  })

I could have used query params for this but I did not, I am also having to debounce as the input changes which is less than ideal. The solution I have come up with feels disjointed and I had to remind myself of how it all fits together when I write this. I am also dealing with partial updates happening from data coming in that is not fully resolved from the asynchronous source. You end up putting conditional logic or using inline observers that can really get quite annoying.

The problem with the above is that changes happen with responses to computed properties and observables that cause state mutation in a very disjointed fashion. With something like flux every user initiated change in the UI is communicated to the dispatcher via an action. The same goes for any data coming from a REST endpoint, where an action can be fired to the dispatcher. This is a top down approach that is consistent across the application and I’m not rolling out new ways of tackling problems for each scenario. This is a top down orchestrated workflow and not side effect driven like we have with ember and computed properties. I’ve really lost faith in the computed property and observable paradigm which causes no end of problems with asynchronous data. Ember seems to put more focus on quirky little macros that work on small datasets or nice html syntax for htmlbars which really does not make my life much easier. I can live with bind-attr for now, but I ended up forking and using a bastardised version of ember-data because I was sick of replacing one set of problems for another on every new release. Why is ember-data not the focus, I would love to know. Please feel free to shout me down for this last sentence as this really is just my opinion.

So to sum up, I feel that ember is at least making a move in the right direction with data down, action up but more needs to be done. One way databinding by default is also the right move. But we need a dataflow story and we need to forget about things like nicer html syntax or at least forget about the flashy demo stuff and concentrate on the problems that user’s have with real data on real applications. The fact that ember-data is still not 1.0 is just insane. This gives weight to my argument that ember often lets the more mundane important stuff take a back seat to the flashy nicer stuff, e.g. html syntax for components. Ember has some of the best developers out there working on it so they really can and should address these problems.

With all this said, the application I work on is in production and we have paying users but a lot of time was spent on issues with ember and ember-data rather than creating features. Ember is free and it has helped us in a lot of ways and I find it really useful for a lot of things like creating widgets. I can’t remember the last time I downloaded a jquery plugin. The router is also a thing of great beauty and something that really shines. Ember-cli is also a great tool also. I hope my criticism is constructive and not bitchy as I have a lot of respect for the developers.

React seems to be moving to fully embrace immutable data structures and I find this very exciting. Immutability opens up a new world of possiblities and makes things like change tracking, memoization and undo/redo functionality trivial.

Fast Prime Number Generation in Clojure

I’ve tried to stay away from building anything meaningful while I have been learning clojure and instead I have been solving problems on the various problem sites such as 4Clojure. I want to concentrate on learning the language as much as possible before getting bogged down with the practicalities that accompany building something. I came across the Hackerrank site which has a project euler contest. In this contest, I came across a problem which was one of the first problems I solved on 4clojure, the problem states:

By listing the first six prime numbers: 2,3,5,7,11 and 13, we can see that the 6th prime is 13.
What is the N’th prime number?

Input Format
First line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N.

Output Format
Print the required answer for each test case.

Constraints
1≤T≤103
1≤N≤104

I had a quick look at my original 4clojure code that solved this problem that I wrote months ago and I was disgusted by what I saw, I was totally convinced that I could do much better and this problem would be toast in no time. I quickly rustled up the following solution:

second.clj
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(ns scratch.core
  (require [clojure.string :as str :only (split-lines join)]))

(defn is-prime? [n]
  (empty? (filter #(= 0 (mod n  %)) (range 2 n))))

(defn nth-prime [n]
  (last (take n (filter #(is-prime? %) (iterate inc 2)))))

(defn print-primes [[x & xs]]
  (prn x)
  (if (seq xs)
    (recur xs)))

(let [input "1\n10001"
      ranks (rest (map read-string (str/split-lines input)))
      primes (map nth-prime ranks)]
  (time (print-primes primes))) ; Elapsed time: 103534.576 msecs

The input variable on line 15 simulates how the hackerrank checker gets input into the solution checking program which is in reality via STDIN but I have stubbed it here with one test case of 100001. The checking program checks the results by reading input from STDOUT which is the whole point of the print-primes function on line 10. Hacker rank supplies a number of unknown inputs or tests into your program which you actually never find out what they are but I am simply supplying 100001 as a significantly big number to test against.

I was feeling pretty chuffed with myself after writing this as the code is seriously concise and I was using some techniques that I perceived to be cool techniques such as an infinite lazy sequence in the form of (iterate inc 2) on line 8 which will iterate infinitely unless a constraint is put on the ever expanding sequence. The constraint in this instance is the take n expression on the same line which is further constrained to only prime numbers returned from the lazy sequence via the (filter #(is-prime? %)) expression.

Imagine my horror to discover that this was infinitely slower than my original 4clojure code, coming in at a diet bursting 103534.576 msecs. At this point, I started to have suspicions about the costs of lazy sequences.

I did some research to see if I could improve the algorithm and made a couple of common sense refactorings that are listed below:

third.clj
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(ns scratch.core
  (require [clojure.string :as str :only (split-lines join)]))

(defn is-prime? [n]
  (or (= 2 n)
   (not-any? #(= 0 (mod n %)) (range 3 (inc (Math/sqrt n)) 2))))

(defn nth-prime [n]
  (last (take n (filter #(is-prime? %) (cons 2 (iterate (partial + 2) 3))))))

(defn print-primes [[x & xs]]
  (prn x)
  (if (seq xs)
    (recur xs)))

(let [input "1\n10001"
      ranks (rest (map read-string (str/split-lines input)))
      primes (map nth-prime ranks)]
(time (print-primes primes))) ; Elapsed time: 500.085 msecs

This executes in a significantly faster 500.085 msecs. I will quickly outline the refactorings:

The orignal is-prime? function looked like this:

isprime.clj
1
2
(defn is-prime? [n]
    (empty? (filter #(= 0 (mod n  %)) (range 2 n))))

The first problem with the above is that it will expand out the whole sequence and then check the count to verify that it does not contain any non-prime numbers. What I needed was a way to short circuit this function the first time a non-prime is encountered, as it turns out there is not-any? which will return false the first time it encounters a logical true.

The next problem with is-prime? is that the sequence that I am feeding into the filter function above, which is (range 2 n). The point of this range function is to ineffeciently pull out all the divisors of the number that we are checking is-prime? against. If one of the divisors is divisable by anything other than itself and one then it is a prime number. It turns out that there is a common algorithm to make this more efficient which states that you only need to test the numbers that are equal to or less than the square root of that number. This is because we can always find the divisors of a number in pairs. One member of the pair will be less than the square root and the other will be more.

For example, here are the pairs of divisors of 100:

1 and 100 (because 1 X 100)
2 and 50 (because 2 X 50)
4 and 25 (because 4 X 25)
5 and 20 (because 10 X 20)
10 and 10 (because 10 X 10)

Each number on the left is less than the square root, and each number on the right is more than the square root. Therefore when we look for the divisors of a number, it necessary to look only up to the square root.

The point is:

When we look for divisors of a number,
it is necessary to look only up to its square root.

So if we call (range 2 100) it expands out to (2 3 4 5 6 7 8 9 10 11 12 13 14.....etc...99), but we only need to do is expand out to the square root of 100.

We can refactor the range call to (range 2 (inc (Math/sqrt 100))) which will expand out to a much more efficient (2 3 4 5 6 7 8 9 10).

We can also take it further than that because we can also exclude any number that is greater than 2 and is even or divisable by 2 because it is quite obvioiusly a non prime number. We can refactor the range function to (range 3 (inc (Math/sqrt 100)) 2) which yields (3 5 7 9).

Below is the refactored is-prime? function:

refactoredisprime.clj
1
2
3
(defn is-prime? [n]
  (or (= 2 n)
   (not-any? #(= 0 (mod n %)) (cons 2 (range 3 (inc (Math/sqrt n)) 2)))))

My original nth-prime function also dealt with even numbers:

orig.clj
1
2
(defn nth-prime [n]
  (last (take n (filter #(is-prime? %) (iterate inc 2)))))

I refactored it nth-prime to only include 2 and the subsequent odd numbers:

refactored.clj
1
2
(defn nth-prime [n]
  (last (take n (filter #(is-prime? %) (cons 2 (iterate (partial + 2) 3))))))

I entered my code into hackerank and……the same thing happened, the first 2 tests passed and the remaining tests timed out. I was depressed by these results as I really thought that I could get on with my life afer this.

My next hack was to remove everything lazy and see what the time difference was. The algorithms stayed the same but everything lazy went:

nonlazy.clj
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
(ns scratch.core
  (require [clojure.string :as str :only (split-lines join)]))

(defn is-prime? [n]
  (if (= n 2)
    true
    (let [root (Math/floor (int (Math/sqrt n)))]
      (loop [i 3]
        (if (> i root) true
            (if (= 0 (mod n i)) false
                (recur (+ i 2))))))))

(defn n-primes [n]
  (loop [curr 3 acc [2]]
    (if (= (count acc) n)
      acc
      (recur (+ 2 curr) (if (is-prime? curr)
                          (conj acc curr)
                          acc)))))

(defn nth-prime [n]
  (last (n-primes n)))

(defn print-primes [[x & xs]]
  (prn x)
  (if (seq xs)
    (recur xs)))

(let [input "1\n10001"
      ranks (rest (map read-string (str/split-lines input)))
      primes (map nth-prime ranks)]
  (time (print-primes  primes)))  ; Elapsed time: 178.132

This came in at a much quicker 178.132 msecs and reafirrmed my suspicions that there is indeed a cost to lazyness. The above passed 3 of the 5 hackerrank tests so I guess this was progress but still no cigar.

Back to the drawing board, this was getting personal and I was not going to give up lightly.

My final throw of the dice involved me getting to grips with something that I was avoiding up unitil now, namely the Sieve of Eratosthenes. This is a reknowned alogrithm for marking multiples off any given limit starting with multiples of 2.

My first problem is that all the examples that I could find were using the sieve with numbers up to a certain number or a limit and not the nth number. I hit wikipidea again and found that there is an algorithm for estimating the limit that the nth number would equate to:

1
a(n) = n*(log n + log (log n))

Below is my code that uses the estimation technique (calc-limit) and the now infamous sieve of Eratosthenes:

solongandthanksforallthefish.clj
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
(ns scratch.core
  (require [clojure.string :as str :only (split-lines join)]))

(defn calc-limit [n]
  (let [log (Math/log n)
        loglog (Math/log log)
        logsum (+ log loglog)]
    (-> n (* logsum) int (+ 3))))

(defn primes [n]
  (let [root (-> n (Math/sqrt) inc int)
        sieve (boolean-array n true)]
    (loop [i 2]
      (when (< i (Math/sqrt n))
        (when (aget sieve i)
          (loop [j (* i 2)]
            (when (< j n)
              (aset sieve j false)
              (recur (+ j i)))))
        (recur (inc i))))
    (filter #(aget sieve %) (range 2 n))))

(defn nth-prime [n]
  (cond
    (= n 1) 2
    (= n 2) 3
    :else (last (take n (primes (calc-limit n))))))

(defn print-primes [[x & xs]]
  (prn x)
  (if (seq xs)
    (recur xs)))

(let [input "1\n10001"
      ranks (rest (map read-string (str/split-lines input)))
      primes (map nth-prime ranks)]
  (time (print-primes  primes)))  ; Elapsed time: 52.271 msecs

The sieve eleimates the non primes by:

  1. Crossing off multiples of x, only at and not 2 * x.
  2. Eliminate even numbers from the sieve.
  3. Elmintate further small numbers from the sieve.

This comes in at a very impressive52.271 msecs, I think this is fast but alas it was not fast enough for hackerrank and only 4 of the 5 tests passed.

At this point, I am giving up and moving on with my life. I now know things about prime numbers that I really have no business knowing.

Please feel free to offer a solution to this problem in the comments below. People have solved this hackerrank problem in the time allowed so it is possible but just not by me.

I am defeated on this and it does not feel good.