Sunday, June 1, 2008

Sudoku solver in JavaScript

I remember siting once in a bar with my friend. I remember that night very well because it was very interesting otherwise. For whatever reason quite unknown to me, at some time of the evening I decided to take a look at her new phone. Quite cute little phone she had, but I am not a gadget-maniac, no. This wouldn't keep my attention that long - if there wasn't a games section. Well, not even that - but it had Sudoku. OK, it's not a very interesting game compared to, say, Civilization, Counter Strike or such masterpieces.

However, it was interesting. What kept me to it was one very simple thing. Here, take a look at the sample Sudoku board (taken from the above article about Sudoku on Wikipedia):

Nothing special - 81 squares, some of which (30, to be exact) have digits (1-9 only), some of which are empty. Rules? Very simple: no row, column and block (block is a set of 3x3 squares, separated by thick lines on the picture) can have more then one instance of the same digit. To solve it, you need to fill all the digits in. Did I mention it's nothing special? Exactly my point - so simple, but not so simple to solve. If you look at Algorithmics of sudoku, under Exceptionally difficult Sudokus, you will see that there are ones that are even impossible to be solved by applying only logic rules (i.e. without any guessing of the digits). At least, that is how it stands right now.

The above Wikipedia pages explain pretty well the different ways you can solve many Sudoku puzzles. To use it to solve the Sudoku, you generally need two methods - using only them is pretty efficient. Here are the two methods:

  • Neighbors elimination
  • Singles extraction
This is especially true if you are a computer - in that case, even if you don't solve using the above two methods, you can significantly reduce the number of possibilities. This is when so-called guessing comes in - you can call it brute force solving.

Let me explain the above two methods in short.

Neighbors elimination


Eliminating neighbors is basically applying the first rule given above: no row, column and block can have more then one instance of the same digit. This is rather simple - if you have a square which has only one digit as the possibility, no other square in the same row, column and block can have that digit as a possibility. By removing this, we reduce the number of choices, possibly clearing some other squares to only one possibility - and that is our goal at the end.

Here is what can be eliminated

Since there can be only one 3 in the marked row and the 3 in the cell at the bottom is the only available choice, the three in the cell at the top can be freely cleared - it is not a choice if we want to solve the board.

Singles extraction


Applying the second rule gives this method. The second rule says: to solve it, you need to fill all the digits in. While this is not explicitly mentioned in the rule, is it obvious that a filled Sudoku board means that there are no empty squares. This leads us to another significant conclusion when combined with the first rule. Say there is a row, column or block containing only one square with a specific digit as a possibility. In that case, that square must be filled with that digit. Otherwise, we could not put that digit in any of the other squares and some square would, thus, be left empty, which violates the second rule.

If you take a look at the marked block, you can see that the circled 3 is the only 3 in the whole block. This means that 3 must be in the cell. Otherwise, it could not go to any other cell in the block, so the board could not be solved properly.

Solving by the computer


The above solutions are right as applied. However, they cannot lead to solution in many cases, even when applied one after another more then one time. There are other, more complex, techniques. Even the best of them cannot be used to solve some boards - "Qassim Hamza" is one of them. While these may be solved if some new method of solving is invented in the future, the key point is that using the above techniques the number of possible variants is very narrowed. After that, very few number of guesses need to be performed and the solution can be found.

The "very few" can be very much for a human. The problem is that you basically need to keep track of all the possibilities, which becomes tiresome very quickly. Luckily, our PCs are very good at not getting bored quickly. We, thus, can use them and the brute force algorithm to solve the board.

The way brute force algorithm works is rather simple. Take a look at the following board:

Applying any of the two non-guessing methods presented above yields nothing - you cannot eliminate any digit. What brute force solving does is the following:

It takes one of the circled digits in the first cell, starting from left-top corner and going right, then down, which has more then one digit in it. It then takes the first digit - 1. It assumes that that cell has only that digit. After that, you in essence have the new board with virtually fixed digit 1 at that cell. What the program needs to do is solve that board.

Now, as we already mentioned, using the previous two non-guessing methods is rather fast comparing to brute force algorithm and yields boards that are in many cases much easier to solve. Thus, brute force solver actually applies the above two methods on the new board, until they cannot be applied anymore. There are three cases:
  • The board is invalid at some time, meaning that our guess was certainly not right, so we backtrack. That means - return to the starting board and take the next digit - 5 in our case and do the same thing again,
  • The board is not invalid, but still not solved. In that case, we are at the next "milestone". We have a board for which we need to guess another digit. We again take the first cell that has at least two digits and apply the same method,
  • The board is solved.
The given solution is quite fast even in JavaScript. It solved all the boards I tried in less then half a minute on a P4 2.8 GHz. If you would like to play with it or the code (it's GPL 3), take it from here.

Tuesday, May 13, 2008

MVP in JavaScript

I started with some OO-like concepts in JavaScript with my previous 2-part post. I would like to continue using the mentioned concepts in building something I think is a good way to make applications - MVP.

MVP = Model View Presenter


If you are interested in MVP, take a look here. As you can see, it was "retired" by Fowler. I sill like to call it like this, but be aware that I will be talking about what he calls Passive View. In other words - be aware that there are many ways to implement MVP, depending on your needs. Another similar way is using MVC. There are differences between them, but I like to look at them as a set of options which are very similar, but have enough differences that you can use one over another depending on your needs.

MVP implemented as Passive View is the one I like for several reasons. First, it allows very big degree of separation. Presenter sits in between and there is nothing in View that will ever touch Model. View doesn't depend on the Model. For efficiency reasons, you might transfer Model classes, but generally Presenter handles all transfers. As common to all MXX architectures, Model is already separated by Observer pattern from other two, in this case from the Presenter. Presenter contains all the business logic, whatever that may be. Model can contain only domain logic (e.g. data manipulation methods, which are most of the time rather simple). Presenter never contains any GUI-related code. It acts on the events from the View and sends updates, but doesn't inherently think about the structure of the View. This allows for View switching - you can have multiple views or even Views that are built in different frameworks - for example, Web (HTML) and WebService (SOAP) views.

Ingredients


As you have seen, MVP = Model + View + Presenter. I will try to explain how MVP works on a simple example. Do you (or did you) ever play Sudoku? If you did, you will not have a problem following this article. If you didn't, take a look at the link on Wikipedia. In essence, it is quite simple. You have a 9x9 (in standard Sudoku, which I will stick to) square matrix. It contains 9 rows, 9 columns and 9 blocks (block is a 3x3 sub-square). Here is a picture, taken from Wikipedia:



The goal is also very simple. Think of each of the 9 rows, 9 columns and 9 blocks as a zone. Thus, you have 27 zones. Each of the zones must contain numbers 1-9. Since each zone has exactly 9 little squares, you can also deduce from this that there are no duplicate numbers - each of the numbers 1-9 must appear once and only once.

Now, while the above definition of the objective is quite simple, solving it can be very hard in some cases. Another article on Wikipedia lists two of them at the bottom, named "Top 1465 Number 77" and "Qassim Hamza", in the part called "Exceptionally difficult Sudokus". They are... Or are they? Well, they are if you are a human. Don't, however, forget that there are computers - they can solve the above in seconds, even in JavaScript, which, according to The Computer Language Benchmarks Game is not quite the fastest programming language humans invented...

To explain MVP, I will try to make a structure that will allow you to play, help you with solving and solve automatically the Sudoku puzzles. I chose this one because:
  • It is a simple game that everyone can learn
  • Apparently there are a lot of people playing it or at least being interested in it - this is what Google contrives as the possible number of matches:



    Quite a lot, wouldn't you say?
  • It is not that hard to implement a computer solver that is moderately fast even in JavaScript
  • I installed M-SudoKu on my phone. Quite nice implementation, lot of options (even for cheating, which I never used - what's the challenge if you use it). Darn, it generates very hard puzzles on the most difficult level. I tend not to use any paper for solving them and it can take me hours to solve just one. It's a war!
OK, so this is somewhat how I have been thinking. The first thing - I started from is Model. What's a model? A model is generally the set of data classes - the thing you will be transforming in different ways to satisfy your business (or, in this case, gaming) requirements. It can be a lot of things - you can imagine applications requiring objects like Person, Address, Mail, WeatherCondition, Car, InsurancePolicy, Stock, TrainStation, AirlineTicket and such. What do we need in Sudoku? I thought I needed only three:
  • Cell, representing the small square on the board
  • Board, representing the whole board (which equals to 9x9 Cells)
  • Messages, which is a set of messages that will be displayed to the user
Thus, we have these three classes as model classes, which I put in the folder named model. These classes are all extended from Model (abstract) class. I'll explain it right away.

Model


Each model is the subject in the Observer pattern. In MVP, Presenters are the observers. They subscribe to the underlying model - each Presenter usually have one dedicated or shared model they look after. There is, however, nothing that dictates this - you can have one presenter overlook ten models if you want. There can be a presenter that doesn't have a model it subscribes to. A good example are delegating presenters, which overlook other (sub-)presenters. Look at your top level Presenter. It's the application presenter. In some cases it only groups separate parts of your application - other presenters - and delegate actions between them, connects them. Usually, however, even these presenters have a (small) model.

In the example I am giving, all presenters overlook one model, but some share the same model - Board, in this case. Generally, I think it is wise to have one model per presenter. If you need more things to overlook, I choose to make the artificial layer (facade) between them. This way you can separate the part of the model world into two parts:
  • Top level parts are used directly by the presenters.
  • Their subparts (and other levels more deep) are used by both presenters and model parts above.
In my example, Board is the top level model. It is directly manipulated by the user. Cell is the subpart. While you do show cells, you generally don't show one Cell only. Thus, they are second-level objects compared to Board.

If I ever had the need to overlook two model parts in one presenter - say Board and Timer, a fictional class that would represent time spent on solving the current puzzle - I would make another class (maybe BoardTimer), combine Board and Timer into it and subscribe to notifications from that class, which will in turn subscribe to Board and Timer and just resend the messages up. This is not a good practice (boilerplate code), but it somewhat simplifies things and is not very common not to have meaningful top-level objects, but to have to "invent the hot water" like this.

Now, here is the abstract Model class. It's quite simple, here:
function Model() {
this.setObservers([]);
this.setChanging({});
}
Klass.create(Model);

Model.prototype.notifyAll = function() {
if(this.properties == null)
return;

for(var i = 0; i < this.properties.length; i++) {
this.notify(this.properties[i]);
}
}

Model.prototype.addObserver = function(observer) {
this.getObservers().push(observer);
}

Model.prototype.notify = function(propName) {
if(this.getChanging()[propName])
return;

this.getChanging()[propName] = true;
for(var i = 0; i < this.getObservers().length; i++) {
var observer = this.getObservers()[i];
var method = observer[propName + 'Changed'];
if(method != null)
method.call(observer, this[propName]);
}
delete this.getChanging()[propName];
}

Model.prototype.removeObserver = function(observer) {
for(var i = 0; i < this.getObservers().length; i++) {
if(this.getObservers()[i] == observer) {
this.getObservers().splice(i, 1);
break;
}
}
}

Model.addProperty = function(klass, propName, options) {
var propNameUpper = propName[0].toUpperCase() + propName.substr(1);
var getter = 'get' + propNameUpper;
var setter = 'set' + propNameUpper;
if(options) {
if(options.liftGet)
getter = '_' + getter;
if(options.liftSet)
setter = '_' + setter;
}
prototype = klass.prototype;
prototype[getter] = function() {
return this[propName];
}
prototype[setter] = function(newValue) {
if(this[propName] != newValue) {
this[propName] = newValue;
this.notify(propName);
}
}
if(prototype.properties == null)
prototype.properties = [];
prototype.properties.push(propName);
}

Property.addProperty(Model, 'observers');
Property.addProperty(Model, 'changing');

There are several things to take a look here. Start from the end - there are two properties in this class. Property is the utility singleton that looks like this:
Property = {
addProperty : function(klass, propName, options) {
var propNameUpper = propName[0].toUpperCase() + propName.substr(1);
var getter = 'get' + propNameUpper;
var setter = 'set' + propNameUpper;
if(options) {
if(options.liftGet)
getter = '_' + getter;
if(options.liftSet)
setter = '_' + setter;
}
prototype = klass.prototype;
prototype[getter] = function() {
return this[propName];
}
prototype[setter] = function(newValue) {
if(this[propName] != newValue)
this[propName] = newValue;
}
}
}

Very simple - when you say:
Property.addProperty(Model, 'observers');

it will add a property to the class Model. What is a property? If you come from Java, you could call this getters and setters. After the previous line, all instances of Model will have getObservers and setObservers methods. You could (and should) use these to change the instance. This allows the class to change get/set operations to implements some more logic then the simple get/set. For example, one useful thing is that you can simply override the methods to provide logging, like this:
Property.addProperty(Model, 'observers', { liftGet: true });

Model.prototype.getObservers = function() {
log.debug('getObservers called');
return this._getObservers();
}

Note the liftGet in the property definition - it tells the Property utility singleton to make getter with the underscore. This way, you still have the intended getter for your convenience, so you can call it when necessary. The same thing is liftSet, only this applies to the setter method. In overridden setters you can put e.g. some validation logic:
Property.addProperty(Model, 'observers', { liftSet: true });

Model.prototype.setObservers = function(newObservers) {
if(!(newObservers instanceof Array))
throw 'Array must be given to setObservers';
return this._setObservers(newObservers);
}

Going up the Model class, you find even more important thing for using the properties. As you can see, Model defines addProperty method. This is similar to Property.addProperty, except that there is the extra notification code. This code is used to automatically notify observers of this model whenever the value of the property changes.

For that, Model.notify is used. It will first check for loop-notification. This is a very big problem that can occur sometimes. For example, let's say you have two properties, called number and square. Assume that the outside force (i.e. presenter or higher-level model) can set any of the above and the other gets calculated by the simple formulas square = number * number and number = Math.sqrt(square). If you do nothing about this, then setting the number will trigger setting the square, which in turn will trigger setting the number and so on until you start feeling dizzy.

To stop this, Model has the other property called changing. When it starts notifying about the change of one property, it will set the corresponding key in changing map to true. Whenever the loop is about to occur - in other words, the notification about the change of the same property happens - it will just silently ignore to continue notification. Quite logical - why notify twice when you are sure the notification is already in progress?

The other important thing to notify about the notify method is that it uses JavaScript's dynamic nature. Observer made this way will notify its observers of the property changes by simply invoking a method on the observer. For example, if the property named 'number' has changed, it will call the method 'numberChanged' on the observer. However, not all observers want to observer every property. This is where dynamics kick in - if the method is not present, then the given observer (of all observers that are looped over) will just be skipped, as if it has not been the observer. This is in fully what we want - subscribe and get notified only about the things that we care.

There are three more methods. notifyAll is the simplest of all - it just notifies all the observers that all the properties changed. This is very useful for one thing. The creation order in MVP is Model/View then Presenter - because Presenter needs both a model and a view to work properly. However, this means that whatever startup notification happened will simply be lost. To circumvent this, you can easily simulate it - Presenter, in its constructor, calls this method (after it subscribed as the observer to the model) to, effectively, notify itself of the starting state of the model. This is the initial setup procedure.

The other two methods seem fairly self-explanatory - addObserver adds the observer to the model, making it the target of all notifications. Method removeObserver does the opposite - removes the observer, which will stop getting the notifications about model's property changes.

I used MVP in a few projects, liked it quite a bit. It's not for small projects. You can use it - no benefit, though. For larger projects, it is very useful.

Wednesday, April 2, 2008

HTML/CSS text shadows

I was trying to do a quick HTML/CSS shadow the other day. It happens often you need a noticeable title to specify what the page is doing if it is not too complex (i.e. you have enough space). I just wanted a simple shadow behind it.

It is quite simple, here:

<html>
<head>
<title>Shadow text example</title>
<style>
#title {
position: relative;
}

h1.clear, h1.primary, h1.shadow {
font: 56px Arial;
font-weight: bold;
font-style: italic;
padding-bottom: 20px;
margin: 0px;
}

h1.primary, h1.shadow {
text-decoration: underline;
color: #dda020;
position: absolute;
}

h1.shadow {
color: #808080;
left: 3px;
top: 3px;
}

#other_content {
position: relative;
}
</style>
</head>
<body>
<div id="title">
<h1 class="shadow"><nobr>Sudoku solver</nobr></h1>
<h1 class="primary"><nobr>Sudoku solver</nobr></h1>
<h1 class="clear">&nbsp;</h1>
</div>
<div id="other_content">More content goes here...</div>
</body>
</html>

Take a look here.

Here you have a few elements:
  • div#title - This is the element that represents the title. It contains three children:
    • h1#shadow - The shadow of the title,
    • h1#primary - Primary text of the title. This one and the previous one should have the same text in them,
    • h1#clear - The clearing element,
  • div#other_content - The other content that follows the title.

The h1#primary is the text that is displayed and it should be made as a normal text without a shadow - set its color or whatever else to your preferences. Shadow should probably only change the color and the "depth", as was done above. The clearing element is there only to give the size to the div#title. The reason is that whenever you do a position: absolute on the element, it will get out of the normal flow of elements. This also means that its size will not affect the size of the other elements, including its parent.

The clearing element is a fake element with only one non-breaking space. This space makes it high as the other two (primary and shadow). All three elements have the same font, padding and margin settings, so they will occupy the same space. The nobr elements are there to make the width appropriate. Otherwise, if you shrink the width of the browser, it will break the text, so the single space in the clearing element will not be high enough to allocate the space for the other two.

There are other solutions - one of them is, for example, this one. I liked this one because it works with the layout of the HTML elements.

Thursday, March 27, 2008

BDD in JavaScript

BDD is a way of building applications in a question-answer-test way. Before you build some part of the application, you make a set of questions, then you answer them and make tests which the code should pass. The tests are made to satisfy the answers. A simple, probably often used example: assume you are making a calculator. One of its operations is addition. You ask: "What should 2 + 3 be?", then you answer "5" and you write a test that, when executes, checks your code with the given inputs (2 and 3) and the expected output (5).

In JavaScript, you can use JSSpec (or JSSpec) framework to do your BDD. Let's say you have written the following function to represent the wanted addition:

function addition(a, b) {
return a + b;
}

Here is the BDD description of the test mentioned above:
describe('Addition', {
'2 + 3 = 5': function() {
expect(addition(2, 3)).should_be(5);
}
});

Download the file containing this simple test from here.

This is the basis of BDD. The basic pattern is:
  • Take a problem that needs to be solved next
  • Make a set of questions about the problem
  • Answer the questions
  • Make a BDD description out of the answers
  • Make the code
  • Test the code using the BDD description
  • Fix the code until the test passes successfully
It is common to make one test per class or module, depending what you are testing. You should cover everything in a class, that is test every non-private method in a class. You can test even private methods, but a good rule of thumb is that if you need to test private methods, then they probably belong to some other class. The sole need to test private methods means they are important. Everything that is important needs to be tested. Play by ear here. Often you have private methods that are only utility methods - extracted parts of other methods to simplify the code.

Try to test small pieces of code (for example, at least one test per method is a good thing) and to test everything, especially the corner cases. The above is written assuming you are using JSSpec to test your code. Take a look at their Wiki for more details - although, at the time of this writing, the documentation is still unfinished and rather sparse. The basics are covered well, however, so you won't have too much trouble if you are not pushing the limits.

The above example is not very exciting by itself. I will make another one, which incorporates the description for the class I am going to use in the near future. The class is called Model. It will probably be clearer why it's used in the next post - it is the part of the MVP pattern. For now, I will give only the simplified view of this class. This is a good thing anyway - BDD should be used in a minimalistic way, in my opinion (you might say this is YAGNI).

Say we need the class to represent some data in our application. For example, if application is dealing with issuing airline tickets, you might need information like how many airplanes you have, how many passengers fit into the airplanes, how many flights you have planned for some day and at which times, etc. Being a good OO, you should find out all the objects that are interesting to your application (e.g. airplane, ticket, passenger, ...). It will probably happen that you will display information about many (if not all) of these.

MVP suggests that these classes be separated into the M part - the Model part. This way you will have the option to subscribe to the notifications from them when some of their properties change. For example, if you have the Airplane class representing the airplane and it has a numberOfPassengers property, you can subscribe to the notifications about the changes of this property. This allows you to, for example, forbid booking any more tickets for that flight if the number of passengers equals to the number of seats in that airplane.

It would be daunting, however, to have to write the boilerplate code that does the notifications for each of the classes. It is quite normal for the model classes to be rather short and many times they only represent the data. This is very similar to Java beans. The only difference is, in fact, that they should have the Observer pattern implanted into them. This pattern is very simple to factor into the parent class - the Model class I mentioned above.

How would we develop this class using BDD? The problem definition is quite easy in this case. What we need to define is based on a black-box way of thinking. Essentially, you define how the instances of this class will behave from the outside. This is how BDD is implemented. For our Model class, we need a class that will:
  • Allow the set of properties be defined (which will be subject to observation),
  • Allow others to subscribe or unsubscribe to the notifications about the changes on any property of the class,
  • Notify every observer of the current state of the instance.
The above is the basis for our BDD test suite. Here is a very short Model BDD description:
describe('Model', {
before_all: function() {
// Sample class inheriting from Model we are going to test.
MyModel = function() {
Model.call(this);
}
Klass.extend(MyModel, Model);
Model.addProperty(MyModel, 'number');
Model.addProperty(MyModel, 'color', {liftSet: true});

model = new MyModel();
model.setColor = function(newValue) {
this._setColor('Color is ' + newValue);
}
},

'Properties should work': function() {
model.setNumber(11);
expect(model.getNumber()).should_be(11);

model.setColor('green');
expect(model.getColor()).should_be('Color is green');
},

'Should notify observers properly': function() {
var fired = false;
var mockObserver = {
numberChanged: function() {
fired = true;
}
};
model.addObserver(mockObserver);
model.setNumber(55);
expect(fired).should_be(true);

fired = false;
model.removeObserver(mockObserver);
model.setNumber(44);
expect(fired).should_be(false);
}
});

It starts with the standard BDD 'describe', which says it describes 'Model' with the three methods object. The first method - before_all - it the method that will be executed when BDD testing starts, once and before all the real tests (i.e. before the other two methods). In before_all, there is a definition of the sample class called MyModel, which inherits from Model. MyModel has two properties: number and color. You can see that color property has the setter overridden, which will do something irregular (i.e. it's not the standard setter that only sets the property, but does more work).

The actual BDD tests follow. These tests have their names: 'Properties should work' and 'Should notify observers properly'. The names should be as descriptive as possible about what this part of BDD description actually tests. It should be the part of the business definition of our Model - the three-item list before the code. As you can see 'Properties should work' describes the first item - allow the properties to be defined. 'Should notify observers properly', on the other hand, combines the second and the third item - allow observers to be added/removed and acutally notify them.

In BDD, this is the first step. We have a description that we can automatically run and test whether the class that we write is what we wanted. If the tests pass, we are good. If they fail, the class is not good. It must be noted that the BDD description can change if the requirements change, which is quite usual when you are agile. However, you should always follow "write tests, then write class" order.

The above description also is YAGNI. Let me give you an example. If you need to go to the grocery store (this seems like a simple and common problem to take as an example), you have many options:
  • Walk,
  • Take a bike,
  • Take a train or a bus,
  • Drive in a car,
  • Use a helicopter.
Any of the above options are possible and quite reasonable in different situations. If you don't have a bike, train, car or a helicopter (and you don't want to die of starvation), you would walk. The next three options are mostly a matter of preference (if they are available). If the grocery store is on the island, a helicopter might be the best option. The important thing is - even if you had a helicopter, you probably wouldn't fly if the store is a block away...

The same is with writing the code. To satisfy the above BDD description, you can write the very simple Model class or you can write a 10K lines monster. The question is - do you need a 10K monster? No. If you did, the BDD description would include everything in there, because BDD description should include everything you need. Simply put - if it's not in BDD, then either don't build it (YAGNI) or amend the BDD description to include the missing thing(s).

At the end - how would you run the above BDD spec? Go to JSSpec User Guide. There is a "Define new specification" part. Replace the text: "// Your spec goes here" with the above description and that is it. In fact, it is not - you need to write the class (Model) and include it (in the normal way JavaScript files are included - using script tag). I will give the example Model implementation in my post about MVP in JavaScript.

Sunday, March 23, 2008

New York Auto Show

March 22nd, New York Auto Show. Breathtaking.











JavaScript OO, part 2

Look at my previous post for the first part - the introduction about OO in JavaScript.

Inheritance


Just a small digression if you didn't come across this. In JavaScript, there is a 'call' method on any function. For example:
function f(a, b) {
alert([this.hi, a, b]);
}

var passAsThis = { hi: 'Hello!' }
f.call(passAsThis, 55, 66);

What the above will output is Hello!,55,66. The f.call(passAsThis, 55, 66) call is doing something interesting. It calls the given function (in this example - 'f') passing the first argument ('passAsThis') to it as 'this' and all other arguments (55, 66) normally. This means that inside the function, 'this' refers to whatever you passed, which is convenient to do simulate parent class method calling. If you have a method on parent class you want to call instead of the overridden method in the child class, you could do this:
function ParentClass(number) {
this.number = number;
}

ParentClass.prototype.displayNumber = function() {
alert(['ParentClass', this.number]);
}

function ChildClass(number) {
this.number = number * number;
}

ChildClass.prototype = new ParentClass();

// @Override (just joking - but in Java you could)
ChildClass.prototype.displayNumber = function() {
alert('ChildClass');
ParentClass.prototype.displayNumber.call(this);
}

var child = new ChildClass(5);
child.displayNumber();

This will output: ChildClass and ParentClass,25. It's a little clumsy, but the call: ParentClass.prototype.displayNumber.call(this) is what in Java you would write as super.displayNumber(). A lot of characters thrown away. This can be a hard thing when you have to call parent class a lot.

Inheritance is an important OO concept. JavaScript doesn't support this very well. Some propose the following solution:
function Person(name, age) {
this.name = name;
this.age = age;
}

Person.prototype.display = function() {
alert('My name is ' + this.name + ' and I am ' + this.age);
}

function Teacher(name, age, subject) {
Person.call(this, name, age);
this.subject = subject;
}

Teacher.prototype = new Person();

Teacher.prototype.teach = function() {
alert('Teaching ' + this.subject);
}

This "almost" works in the sense that you get the right hierarchy. For example, you could now do:
var teacher = new Teacher('Foo Bar', 35, 'math');
teacher.display();
teacher.teach();

This means that you inherited the 'display' method from Person class and you could add a new method 'teach'. This is basics of OO inheritance, so we are OK. Take a look at this for a very good explanation of this method. This method is very acceptable if you don't mess to much into OO.

However, the call: Teacher.prototype = new Person() is really a function call, so all your code in Person gets executed. This is OK if you don't have any side effects, but if your class was WebServiceClient and you would connect to Web service in the constructor, this would not be a good solution at all. First, every time you attempt to inherit from WebServiceClient, you would try to execute the code in the constructor - really not what you intended. Second, when you execute it, you don't get any parameters, so you could possibly go even worse. Not a good situation at all.

One more problem is global state modified in constructors. Assume you have a PersonsCache, which would hold all the Person objects ever created. You could not put adding the just-made instance in the constructor of Person, like this:
function Person(name, age) {
this.name = name;
this.age = age;
PersonsCache.addPerson(this);
}

Every time you do the inheritance Teacher.prototype = new Person(), you would call the constructor and add something. That something is a dangling reference to your new instance object. You will normally never use it, but what is more important - you will have more persons then you really have...

Similar to this, if you ever touch the DOM or any HTML-related stuff, this will break. The problem is that you inherit while the script is loading, which is before body of the document is created. You can circumvent this by e.g. putting everything inside body onLoad event handler, but again - that is just clumsy boilerplate and distracts you from what you should be doing.

Another problem, common to all "solutions" (both the one above and all of the mentioned below) is that method overriding is not supported very well. Assume you have three classes: B, C and D. Assume C inherits from B, D inherits from C. Assume all of the classes have one method called 'sayHi'. Now, you could override the method only in class D, for example. To call the base methods from that method, you need to supply the actual base class. This may seem strange - you always know your base classes! Not true, though. Say I now change the hierarchy by inheriting B from class A, so we have A -> B -> C -> D. If the method 'sayHi' stays in B, that is OK. If it, however, gets moved to class A for some reason, you would have to find all calls like B.sayHi.call(this, ...) and change them to A.sayHi.call(this, ...). In Java, it would still be super.sayHi(...). Maybe I am nitpicking here - if you override in both C and D, even in Java you couldn't do it without casting (i.e. ((A)this).sayHi() would call sayHi from class A). Here is Java code that is an example of this:
class A {
public void sayHi() {
System.out.println("A");
}
}

class B extends A {
public void sayHi() {
System.out.println("B");
}
}

class C extends B {
public void sayHi() {
System.out.println("C");
}
}

class D extends C {
public void sayHi() {
super.sayHi();
System.out.println("D");
}
}

public class Inherit {
public static void main(String[] args) {
new D().sayHi();
}
}

Try commenting out different sayHi methods in base classes and see how it behaves. In Java, super.sayHi() finds the "first method up the hierarchy".

There are ways to circumvent some of JavaScript's inheritance "features". Discussion below is about inheritance without calling the base constructors during inheritance.

Use empty constructors and construct using special constructor method


Back to empty-constructor method. This could look like this for the above Person & Teacher example:
function Person() {}
Person.ctor = function(name, age) {
this.name = name;
this.age = age;
}

Person.prototype.display = function() {
alert('My name is ' + this.name + ' and I am ' + this.age);
}

function Teacher() {}
Teacher.prototype = new Person();
Teacher.ctor = function(name, age, subject) {
Person.ctor.call(this, name, age);
this.subject = subject;
}

Teacher.prototype.teach = function() {
alert('Teaching ' + this.subject);
}

var teacher = new Teacher();
// #1
Teacher.ctor.call(teacher, 'Foo Bar', 35, 'math');
teacher.display();
teacher.teach();

It obviously works pretty well, since we have removed the unwanted call when doing the inheritance. It also obviously looks very clumsy and there are much more characters to type with no good reason.

This is not very OO in another sense. The construction process is separated. If you would try to call teacher.display() in place of #1 comment, you actually could and you would get incorrect results, of course.

Copy prototype


Some recommend doing a straight prototype-copy. I used this one on two of my projects and it worked very well.

The idea here is very simple. It gets answered when you ask - what means "to inherit" in JavaScript? Take a look at the above ways to implement inheritance. What all they do is take the parent class' prototype on the start. This is what happens when you say something like Teacher.prototype = new Person(). Actually, this does something else, but the end result is the same - Teacher.prototype becomes the reference to parts that parent class' prototype contains. The keyword is "copy". JavaScript is dynamic, so we can verify this:
function Parent() {
}

Parent.prototype.display = function() {
alert('Parent.display');
}

Parent.prototype.callDisplay = function() {
this.display();
}

function Child() {
}

Child.prototype = new Parent();

// Change parent's definition of display.
Parent.prototype.display = function() {
alert('Parent.display - modified')
}

var parent = new Parent();
parent.callDisplay();
var child = new Child();
child.callDisplay();

As you can see, Child's prototype now contains a definition of 'display' inherited from Parent and it changes as it should. How is this a copy then? Again, see this for a very good explanation. How this really works is like this. When you say new Child(), you actually get the object which has __proto__ key. Take a look:

var s = '';
var childProto = new Child().__proto__;
for(var i in childProto) {
s += i + ': ' + childProto[i] + '\n';
}
alert(s)

You see the display method. That is child's display method? No, it's Parent's. How JavaScript uses this thing is rather interesting - it walks it as a tree. Here:
var childProto = new Child().__proto__;
var parentProto = childProto.__proto__;
alert(childProto == Parent.prototype)

Say you have var child = new Child(). This child has it's __proto__ pointing to Child.prototype. Each next reference to __proto__ gets you one level upper the inheritance chain, thus child.__proto__.__proto__ gives you Parent.prototype. If we had more levels, we would have got GrandParent.prototype and so on.

The same thing, however, happens when you pick a variable or method. Say you want to do child.display(). JavaScript first looks in child - do you have a display? Nope. OK, go one level up - look at child.__proto__. Child doesn't define display, sorry. OK, how about child.__proto__.__proto__? Now, since child.__proto__.__proto__ == Parent.prototype, you have a display here. So it gets called. You can think of this as a sum of all things up the inheritance chain, but child classes have precedence - if they override something, it is overridden as they want. You can even override something on an object-level:
var s = '';
var child1 = new Child();
var child2 = new Child();
child2.display = function() {
alert('child2 - modified');
}
child1.display();
child2.display();

You will get 'Parent.display - modified' and 'child2 - modified'.

We need a little more help from here. If you take a look, it says what var child = new Child() does:
  • Makes new object (i.e. new Object()) - let's call it 'cobj'
  • Calls Child constructor, passing the created 'cobj' object as this
  • Implicitly sets cobj.__proto__ to Child.prototype
  • Sets child to cobj
Hm... Now, what would Child.prototype = new Parent() do? It would set Child.prototype.__proto__ to Parent.prototype. This is how it all works. Let's take a look again at what var child = new Child() does:
  • Makes new object (i.e. new Object()) - let's call it 'cobj'
  • Calls Child constructor, passing the created 'cobj' object as this
  • Implicitly sets cobj.__proto__ to Child.prototype
  • Remember child.__proto__ == cobj.__proto__ == Child.prototype, but also Child.prototype.__proto__ == Parent.prototype.
  • Thus, child.__proto__.__proto__ == Parent.prototype and this is how it all can work nicely
Back to our "copy" - what gets copied is this __proto__ thing - the fact that Child.prototype.__proto__ == Parent.prototype. Let's say that our classes would never change in the "future". That is, whenever we make a class, we would never change it later - we will not do the things we did in the previous example. This is a quite reasonable assumption. You can change your classes in JavaScript, even in Java using reflection, but that is not very OO, right? Kinda hacky and we don't want to have hacky code.

If you have all the above assumptions in place and you are OK with them, then you can simulate the above mechanism. The only thing you actually need to do is copy the things from Parent.prototype to Child.prototype and that is it. You lose __proto__ hierarchy, true, but you can simulate that, too (although not completely). It works, however, pretty nice. Here is how I did it on my last project:
Klass = {
extend: function(klassChild, klassParent) {
var pkChild = klassChild.prototype;
var pkParent = klassParent.prototype;
for(var i in pkParent)
pkChild[i] = pkParent[i];
pkChild.constructor = klassChild;
pkChild.parent = klassParent;
pkChild.klassName = Klass.name(klassChild);
},
create: function(klass) {
var prototype = klass.prototype;
prototype.constructor = klass;
prototype.klassName = Klass.name(klass);
},
name: function(klass) {
return klass.toString().match(/function (.*)\(/)[1];
}
}

The Klass is the utility object which can be used like this:
function Parent() {
}
Klass.create(Parent);

Parent.prototype.display = function() {
alert('Parent.display: ' + this.value);
}

Parent.prototype.callDisplay = function() {
this.display();
}

Parent.prototype.value = 1;

function Child() {
}
Klass.extend(Child, Parent);

Child.prototype.value = 2;

var child = new Child();
child.callDisplay();

Here, instanceof doesn't work, class changes do not reflect to child classes. These are the imperfections.

Check arguments for inheritance-related info


Another method is to stop inheritance calls in their roots. For example:
var ONGOING_INHERITANCE = {};

function Person(name, age) {
if(arguments[0] == ONGOING_INHERITANCE) return;

this.name = name;
this.age = age;
}

Person.prototype.display = function() {
alert('My name is ' + this.name + ' and I am ' + this.age);
}

function Teacher(name, age, subject) {
if(arguments[0] == ONGOING_INHERITANCE) return;

Person.call(this, name, age);
this.subject = subject;
}

Teacher.prototype = new Person(ONGOING_INHERITANCE);

Teacher.prototype.teach = function() {
alert('Teaching ' + this.subject);
}

var teacher = new Teacher('Foo Bar', 35, 'math');
teacher.display();
teacher.teach();
alert(teacher instanceof Person);

This code works as expected. It is lot less clumsy then the previous solutions. The last line tells you that it gives the right results, i.e. teacher really is the instance of Person class.

For the alternative approach to this, take a look at this page.

This is most of what should be considered basic JavaScript OO-like programming. Hope you enjoyed it.

Saturday, March 15, 2008

JavaScript OO, part 1

According to Wikipedia, JavaScript is:

JavaScript is a scripting language most often used for client-side web development. It was the originating dialect of the ECMAScript standard. It is a dynamic, weakly typed, prototype-based language with first-class functions.

What is interesting in the previous definition is that there is no mention of object orientation. While there is nothing that says that you must write OO programs, it definitely one of the most common ways the programs are built these days. While there are other paradigms (functional programming, logic programming, structural programming, ...), JavaScript is nowadays mostly used in either simple imperative/structural or more complex OO-like ways. OO-like and not OO because JavaScript is not OO-capable language. For example, it doesn't support any protection mechanisms - everything is public. It supports something called prototype-based development. However, most people still call it OO - I suppose it's just "good enough".

Classes


Let's take a look at it. I will assume you are using JavaScript from within a standard browser. This is what it is:
function Person(name, age) {
this.name = name;
this.age = age;
}

Person.prototype.display = function() {
alert('My name is ' + this.name + ' and I am ' + this.age);
}

function main() {
var person = new Person('Foo Bar', 33);
person.display();
}

If you somehow run method 'main' (e.g. by having it in your body onload event), you would see:
My name is Foo Bar and I am 33
in a dialog that pops up.

Although there is nothing even resembling a class in the above code if you compare it to e.g. Java classes, the above code actually is a basic example of a JavaScript class. The class is called Person.

Multiple constructors


In JavaScript, you cannot have multiple constructors as in other languages (e.g. C++, Java, C#, Ruby, Scala, ...). The reason for this is that classes are represented as functions. JavaScript doesn't have a concept of method overloading, as e.g. Java has. For example, in Java you can write:
public class MethodOverload {
public void method(int a) {}
public void method(String b) {}
public void method(double[] c) {}
}

The above code means that every instance of MethodOverload class have three methods with the same name. Which one gets called depends on the input parameters. If you would do the following:
MethodOverload mo = new MethodOverload();
mo.method(1);
mo.method("Hi");
mo.method(new double[]{ 1.0d, 2.0d });

then the above three calls would call the methods in order as given in the class definition. method(1) would call method(int a), method("Hi") would call method(String b) and method(new double[]{ 1.0d, 2.0d }) would call method(double[] c).

JavaScript, however, doesn't have this capability. In fact, in JavaScript, you can define multiple functions with the same name, but only the last one will "stick". To demonstrate this, try running the following:
function fun(a) {
alert('first: ' + a);
}

function fun(a) {
alert('second: ' + a);
}
fun(55);

The above code would display 'second: 55'. The interpreter will not even complain - the above code is valid. As if the first function hadn't even existed. You can circumvent this by using either optional named arguments or unnamed arguments. Optional named arguments means that you have one constructor which does all the work, while all other constructors are just the utility constructors for the user to be able to write the shorter code. For example:
function Person(firstName, lastName, sex, age, email, socialSecurityNumber, personalPhone, businessPhone, personalAddress, businessAddress, blogPage) {
this.firstName = firstName;
this.lastName = lastName;
if(typeof(sex) == 'undefined') {
// sex is not given.
this.sexDefined = 'no';
} else {
// sex is given.
this.sexDefined = 'yes';
}
// The same for all other optional arguments.
}

Assume that only firstname and lastName are required. You could instantiate it by:
var person = new Person('Foo', 'Bar');
alert([person.firstName, person.lastName, person.sexDefined]);
var person = new Person('Foo', 'Bar', 'male');
alert([person.firstName, person.lastName, person.sexDefined]);

The above would display 'Foo,Bar,no' and 'Foo,Bar,yes'. For the above two lines, you would accomplish the same thing in Java by writing two constructors:
public class Person {
private String firstName;
private String lastName;
private String sex;

public Person(String firstName, String lastName, String sex) {
this.firstName = firstName;
this.lastName = lastName;
this.sex = sex;
}

public Person(String firstName, String lastName) {
this(firstName, lastName, null);
}
}

The constructor would have to check whether all other things are undefined or not. A small digression - it is not enough to check for null in this case, for example:
function f(a) {
alert([a == null, typeof(a), typeof(a) == 'undefined']);
}

f(1);
f(null);

The above would display:
- f(1) => false, number, false
- f(null) => true, object, false
To check whether the argument is defined, always use typeof, except if you are sure that you will not have nulls as inupts.

The other option for multiple constructors is to use variable arguments:
function f() {
var s = '';
for(var i = 0; i < arguments.length; i++)
s += (i == 0 ? '' : ', ') + i + ': ' + arguments[i];
alert(s);
}

f('a')
f('b', 888)

The above would display:
- f('a') => 0: a
- f('b', 888) => 0: b, 1: 888

Using the above you could make the constructor take any parameter, decide what to do based on the length and types of the arguments, etc. Both options require checking whether the arguments are defined. The variable arguments is even more obscure, since you don't know how to call the constructor, except if you put a comment before it. That is maybe the reason why you don't see too much of these in real life, i.e. one constructor classes are the most common in JavaScript. For that reason, I will stick to one-constructor classes and occasionally use the optional arguments constructors.

Instance variables and methods


Back to the first example:
function Person(name, age) {
this.name = name;
this.age = age;
}

Person.prototype.display = function() {
alert('My name is ' + this.name + ' and I am ' + this.age);
}

function main() {
var person = new Person('Foo Bar', 33);
person.display();
}

variables are used directly on an object, similar to way you do it in e.g. Java. When you say this.name, it refers to 'name' variable in the current instance. Note, however, that using of 'this' is obligatory, contrary to many situations in Java. When you say person.display(), it calls the method 'display' on the 'person' object, which happens to be the instance of the Person class.

JavaScript is both dynamically and weakly typed. This means that it resolves the type of the object in the runtime and you never supply it in the code. When you say
var person = new Person('Foo Bar', 33);
person.display();

it doesn't say anywhere in the code what person is - this is determined at runtime. You could do, for example, the following:
var person = new Person('Foo Bar', 33);
person = new SomeOtherClass();
person.display();

Depending whether SomeOtherClass has 'display' method, this will either call that method or raise an 'undefined function'-kind of error in JavaScript interpreter.

The same way you can have object methods, you can have object variables defined. This is something similar to class-level initialization in Java:
function Person(name, age) {
this.name = name;
this.age = age;
}

Person.prototype.display = function() {
alert('My name is ' + this.name + ' and I am ' + this.age + '. I am from ' + this.planet);
}

Person.prototype.planet = 'Earth';

function main() {
var person = new Person('Foo Bar', 33);
person.display();
}

Note that 'planet' is the object-level, not class-level variable. To demonstrate that, try the following in main():
var person1 = new Person('Foo Bar', 33);
person1.planet = 'Mars';
person1.display();
var person2 = new Person('Baz Geez', 22);
person2.display();
person1.planet = 'Jupiter';
person2.planet = 'Neptune';
person1.display();
person2.display();

The output will be:
My name is Foo Bar and I am 33. I am from Mars
My name is Baz Geez and I am 22. I am from Earth
My name is Foo Bar and I am 33. I am from Jupiter
My name is Baz Geez and I am 22. I am from Neptune
As you can see, changing planet of person1 did not have any effect on planet of person2 and vice versa.

Class-level (a.k.a. static) methods and variables


You can have static methods and static variables in JavaScript - just omit the 'prototype' from the definition and that's it. For example:
function Person(name, age) {
this.name = name;
this.age = age;
}

Person.findOldest = function(persons) {
if(persons.length == 0)
return null;

var oldest = persons[0];
for(var i = 1; i < persons.length; i++)
if(persons[i].age > oldest.age)
oldest = persons[i];
return oldest;
}

var persons = [
new Person('Very Young', 10),
new Person('Just Right', 25),
new Person('Middle Age', 50),
new Person('Very Old', 70)
];
var oldest = Person.findOldest(persons);
alert([oldest.name, oldest.age]);

Person class now has 'findOldest' method. This method is a static method. You call it by giving the name of the class: Person.findOldest.

To comment, the previous, this is just a convention. This is again just a consequence that JavaScript is really not OO language. There is nothing wrong if you define the method as:
Person.prototype.findOldest = function(persons) {
...
}

I use the first convention since:
- In the second case, every object would have findOldest, so you couldn't really distinguish what is a static method and what is not
- More typing if you follow another convention (which I do) - static methods should be called with the name of the class instead of the object instance name.

In fact, you could have noticed that '.prototype' is just the object. It is a special object, since when you say 'new Person' it will make the object and copy everything from Person's prototype object into the instance. However, with static methods, you could very well do something like this:
Person.staticMethods = {};
Person.staticMethods.findOldest = function(persons) {
...
}

Try it - works the same. I omit everything both prototype, staticMethods or whatever else you could put there. It is clear without these qualifications that this is a static method if you always follow this convention (not hard).

The same way works for static variables:
function Person(name, age) {
this.name = name;
this.age = age;
}

Person.prototype.isAdult = function() {
return this.age >= Person.adultAge;
}

Person.adultAge = 18;

var persons = [
new Person('Very Young', 10),
new Person('Just Right', 25),
new Person('Middle Age', 50),
new Person('Very Old', 70)
];
for(var i = 0; i < persons.length; i++)
alert(persons[i].isAdult());

'adultAge' is a static variable in Person class. The above will output: false, true, true, true, since only 'Very Young' is not adult.

Hope this helped a little. In the next part, I'll write about inheritance.