Javablogs

It’s common to see “find the number of possibilities” problems in Computer Science. This kind of problem stems from Discrete Maths - an important pre-requisite for doing anything beyond the trivial, for example Cryptography or Graph Theory.

I found one of these problems on Project Euler.  Project Euler is a collection of mathematically-inclined programming problems - probably more than you could ever solve in a lifetime (some of them are still unsolved by anybody). The particular problem which drew my attention doesn’t actually require any programming to solve.  

The problem is based on the idea of finding routes between two points on a grid:

Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner. 
How many routes are there through a 20x20 grid?

This is pretty fundamental maths, but I find these kind of techniques are always worth re-visiting, as it seems to be a case of “use it or lose it”.

Following is my approach, so don’t read any further if you want to try it yourself first!

I started by drawing a tree structure for the 2x2 grid, where each node had two choices = ‘R’ or ‘D’ (for go Right, or Down).  This gave me a feel for things.  Towards the end of some paths, there was clearly some pruning - where the only option is to head for the goal (rather than back-tracking or going out of bounds).

It then became clear that any plan for getting to the goal simply involved two Rs and two Ds.  You clearly need to take two steps Right, and two steps Down to reach the goal, whatever your route.  So the problem can be re-stated as “how many ways are there of arranging two Rs and two Ds?”  Or more vividly: “If I have a bag containing two Kit-Kats and two Mars Bars, how many distinct ways can I eat them in sequence?”

Of course, the stated problem involves twenty each of Kit-Kats and Mars Bars.  So if I was really hungry, how many ways could I eat them all? Suitably motivated, it’s time for some fun with combinatorics.  

For the moment, let’s go back to the 2x2 grid, and ignore the repetition of Right and Down moves.  This means we must take four distinct steps to reach the goal.  So let’s assume that we have a bag of four chocolate bars - all different.  How many ways can we draw them in sequence?  Or more properly, how many permutations are there?

For the first choice, we have four options.  Once we’ve made this first selection, we have three left to choose from.  Then two, and finally there’s only one left.  This naturally leads us to the factorial function:

4! = 4 x 3 x 2 x 1 = 24

So there are 24 ways (permutations) to draw four tasty, chocolate treats. Now let’s amend our calculation, taking into account that two of the chocolate bars are identical.  Say, two Milky Ways, one Kit-Kat, and one Mars Bar. This is easy to work out - out of our 24 original permutations, we need to omit the repeated permutations of the two identical items.  There are 2! (2 x 1 = 2) ways to arrange two chocolate bars, so we adjust our answer for this.

4!/2! = 12 permutations

Now, it’s only one more step to re-discover the example solution, by taking into account that there are two classes of two identical ‘objects’ (Right moves and Down moves), and so we end up with:

4!/(2!*2!) = 6 permutations.

Now it’s really easy to solve the stated problem - I won’t give away the solution of course!

I was reminded of the power of automated testing by this talk by Rod Johnson, the original creator of the Spring framework. It is a little dated (2007), but what he says is still highly relevant.  The content mainly covers things we should already be practicing as developers, but it’s worth a reminder every now and then. Following are the main points I took away from the presentation.

First, there are several key concepts to bear in mind.  These came up again and again in the talk:

• Test Early, Test Often
• Test at Multiple Levels
• Automate Everything

Unit Testing

As developers, we know we should do lots of unit testing.  We do this by targeting classes in isolation, and mocking out collaborators.

To be clear, unit testing is looking at your class “in the lab”, not in the real world.  A unit test should not interact with Spring, or the database, or any infrastructure concerns.  Therefore, unit tests should run extremely fast: of the order of tens of thousands of tests per minute.  It shouldn’t be painful to run a suite of unit tests.

Do Test-Driven Development. Not only does this help you discover APIs organically, but it’s a way of relieving stress.  Once a defect is detected, you can write a failing test for it, then come back to fix it later on.  The failing test is a big red beacon reminding you to finish the job.

Use tools such as Clover to measure the code-coverage of your tests.  80% is a useful rule of thumb.  Any more than this, and the benefits are not worth the cost.  Any less than 70%, and the risk of defects becomes significant.

Integration Testing

We should also do integration testing - for example to ensure our application is wired up correctly, and SQL statements are correct.  

But how many of us are still clicking through flows in a browser?  Ad-hoc testing by deploying to an application server and clicking around is very time-consuming and error-prone.  If it’s not automated, chances are it won’t happen.  If it doesn’t happen or occurs late in the project cycle, defects will be expensive to fix.

So instead, maintain a suite of integration tests.  It should be possible to run hundreds or thousands of these per minute and again, they should be automated so they just happen.

Use Spring’s Integration Testing support.  Among other things, this provides superclasses which can perform each test in a transaction, and roll it back upon completion to avoid side-effects across tests.  This avoids the need to re-seed the database upon each test.

Another benefit of Spring Integration Testing is that the Spring context is cached between tests.  This means that the highly expensive construction of the Hibernate SessionFactory (if you use one) only happens once.  This context caching is usually impossible, because the test class is reconstructed by JUnit upon each test.

Remember to test behaviour in the database.  Stored procedures, triggers, views - regressions at the schema level should be caught early, in an automated fashion.

Integration tests should be deterministic - that is, they should not rely on the time of day, or random side-effects from previous tests.  This should be obvious, but when testing concerns such as scheduling, this can become difficult.  One strategy is to abstract out the concept of the current time of day.  This could be done by replacing a literal call to System.getCurrentTime() with a call to a private method.  This method would check for an override property set only during testing, the existence of which would cause a static Date to be returned to your application code.

Performance Testing

This should begin as early as possible.  Use scriptable frameworks such as The Grinder, so performance testing is cheap to execute early and often.  This means performance regressions will be caught immediately, for example if somebody drops an index.

Many performance problems are due to lack of understanding of ORM frameworks.  Learn to use your framework, for example relating to fetch strategies.  A common idiom is to eagerly fetch a collection of child entities up-front, rather than invoking the “N+1 Selects” problem by lazily loading each child record in a loop.  Additionally, consider evicting objects from the Session at appropriate points, to avoid memory overhead and to prevent the need for dirty-checking upon flushing of the Session.

One strategy to dive deeply into database performance concerns, is to enable SQL logging in your persistence framework.  A large number of SELECT statements per-use case will quickly become apparent.

Conclusion

Developers should Invest time into writing automated tests at multiple levels.  Even with a dedicated QA team in place, defects will only be caught early and fixed cheaply through an intelligent approach to automation. Along with adoption of best practices such as Dependency Injection and separation of concerns, the industry has many tools on offer to make comprehensive testing cheap and easy.

References / Further Reading

• JUnit: http://www.junit.org/
• Spring Testing: http://static.springsource.org/spring/docs/2.5.x/reference/testing.html
• The Grinder: http://grinder.sourceforge.net/ TDD (essay):  http://www.agiledata.org/essays/tdd.html
• Clover (test coverage): http://www.atlassian.com/software/clover/
• JWebUnit: http://jwebunit.sourceforge.net/

I was wondering: if I change class Foo, how do I determine 100% which use-cases to include in my regression tests? It would be useful to know with 100% certainty that I must consider the Acme login process, as well as the WidgetCo webservice authentication.  And nothing else. Can my IDE help me with this? 

Well, in some cases it’s straightforward to analyse for backward dependencies.  If I change class Foo, then static analysis tells me that webservice WSFoo, and controller Bar are the only upstream entry points to your application affected by this change.  So you test those flows, and that’s about it.

Good time management is a bit like computer programming, in some ways at least … How do you keep track of tasks which can’t be carried forward, until some outside event has taken place?  Perhaps you’re waiting for a response from a vendor, or a decision from your manager on which option to take. ‘Hanging’ tasks like this can compete for your attention: you can’t do anything for the time being, but you don’t want to forget about them.  Tasks like this aren’t really a “to do” item, there’s no action you can take.  Therefore on some level, your mind keeps telling you to check their progress over and over.  You just can’t let it lie and get on with something else. Polling and the Postman’s Knock To risk a slightly contrived analogy, imagine ordering a book from Amazon: a reference book you need before you can carry on with your project.  What do you do after you fire off the order?  There are only two basic options: keep checking your letterbox until it arrives, or get on with something else and wait for the postman to knock.  In computer parlance, the first approach is called polling, and the second is interrupt-based. Polling for an event is quite terrible as far as efficiency is concerned.  You just keep checking for the event to occur, over and over, without getting anything done in the meantime. You’d only want to do this in unusual situations: perhaps the postman won’t come right to your door, and leaves the parcel at the end of your drive instead.  In that case you would have to keep looking out the window for the parcel.  However, the upside is that since you’re continually checking for the arrival, it will be more obvious if it’s been delayed. The polling approach is fairly inept in general, assuming you have other things to do with your time.  It carries the cynical view that “I can’t trust anybody, I have to do everything myself!”  It takes an inaccurate view of responsibilities and feels like a generalised form of nagging (“Is it done yet? … Is it done yet? …”) Conversely the interrupt-based approach applies the inversion of control principle.  Rather than taking the burden yourself, this places responsibility where it is due.  The postman carries knowledge of your parcel’s arrival, so he can knock on your door when its time.  This allows you to forget about the order, depending purely on the ‘postman’s knock’ which acts as an interrupt.  At least in that case you could get on with something else in the meantime. However, there are several disadvantages to using interrupts.  First, you might forget you ordered the parcel, and it never arrives.  You had the luxury to get on with something else, but this distracted you from the pending task which never completed.  The second disadvantage is that when the postman finally knocks, you might be disturbed from what you were doing, allured by the shiny new tome in your haste to read it cover-to-cover. Ideally we want an approach to time management which gives us all the upsides, but controls for the risks.  “Give me a call when it’s ready, but I’ll keep one eye open in case that call never comes.” Fortunately, patterns to solve this problem exist, deep in the guts of your favourite multitasking operating system. Processes and I/O The polling approach may be seen in specialised single-process, real-time or embedded systems.  If only one special task is running, and that task is waiting for an event, then there is no harm in spinning in a loop. However, in typical multitasking systems, polling would be expensive and quite unnecessary.  Other more important tasks may be able to proceed while a task is waiting for its data. Therefore an interrupt-based ‘postman’s knock’ mechanism is favoured.  This design ensures that a multitasking operating system can maintain its guarantee that processes should be scheduled in priority order (in simple terms).  The interrupt-based approach is fair: I submit a request for the data, then I sleep while other things happen.  Subsequently I get a nudge once my data is ready. Let’s see how this happens in more detail.  When a process reads from disk, that request is sent to the disk controller, then the process is suspended (and placed onto a special Blocked queue).  Processes on the Blocked queue are waiting for some outside event to complete, and will never get any processing time until then. The hard disk (which can operate independently of the CPU itself) begins seeking the requested data in the background.  Meanwhile, the operating system switches to another process, say updating the screen or listening for mouse clicks.  It’s as though the pending “disk read” is out of mind, giving the luxury of a responsive system in the meantime. Later on, the hard disk finishes its work.  The hard disk controller is an actor in its own right, and gives the operating system a nudge (or interrupt): “Hey, someone requested some data - here it is”. How does the operating system respond to the interrupt?  Instead of immediately switching to the program that was waiting for the data (which might disturb a higher-priority task), the operating system moves the waiting process from the Blocked queue, to the Ready queue.  The Ready queue contains all the programs that can proceed with their work, often according to some priority order.  Once this is done, the operating system takes the opportunity to pick a new task from the Ready queue according to some priority order.  It may or may not be the task which requested the data. Once the waiting task gets its turn to run, it will proceed at the very next instruction after the call to read, with the pending data now in context.  This emerges as an elegant programming model - the application programmer does not have to explicitly do anything to deal with the complex mechanism under the hood. One issue is that a process may have to wait a very long time to receive its data, creating a ‘hang’.  What if some remedial action should be taken if a time limit is surpassed?  There’s no way the waiting process can implement this requirement - it’s in stasis on the Blocked queue and will never execute any code until the interrupt comes. To deal with this, a timeout value has to be passed to the operating system no later than when the call to read is invoked.  This suggests that the operating system must do some housekeeping on the Blocked queue; perhaps its items are ordered by a “time to live”.  This strategy appears to be utilised in the socket timeout parameter often available on calls to read data from a network. Maintaining your own Blocked and Ready Queues The scenarios described are similar to situations where a task on your to-do list is blocked on some outside event. Clearly we would want to take an interrupt-based approach in real life.  But how do we avoid the twin perils of (i) losing track of the time spent waiting, and (ii) becoming distracted by incoming ‘data’ as it arrives? The solution to both of these concerns is the “Waiting For” and “Next Actions” lists described in the Getting Things Done system.  The “Waiting For” list is your Blocked Queue - a list of items requiring a response from an outside party, each with an optional ’time to live’ before something has to be done to expedite it. Your “Waiting For” list is separate from your “Next Actions” (your very own Ready Queue).  It doesn’t pollute your everyday consciousness; you only have to review the “Waiting For” list as often as you really have to.  This ‘housekeeping’ prevents any items from sliding off the “Waiting For” list, and being forgotten. The second concern is easily solved.  When something you are waiting for becomes available, instead of becoming side-tracked by it, you simply move it from the “Waiting For” list to an appropriate addition to the “Next Actions” list.  Appropriately recorded, this frees your mind to focus on one task at a time.  You can then either continue what you were doing, or pick something from your “Next Items” (or Ready Queue) according to priority.

Good time management is a bit like computer programming, in some ways at least … How do you handle large tasks, without being overwhelmed by their size? Streams Computer programs generally read data from some location, process it, then output it somehow. For example, a video player will read data from the disk, decode it, then draw frames on the screen. Now, what is the best policy for this? How much data should be read from the disk, before it’s processed and flung out at the screen? In reality, it’s best to read a bite-sized chunk of data into a small buffer area, process it, output the result, clear the buffer, then proceed with the next chunk. If instead an entire video file was read in one go, on-board memory would be quickly exhausted or at least severely compromised. Streams provide this kind of functionality.  When you read from a stream, you just get the next chunk, without concern to how much input is yet to come. We often stream things from the net.  You can play an infinitely long audio stream (e.g. net radio), even with a relatively small amount of memory.   The audio player periodically engages in a buffering process - reading the next chunk of data from the network.  Therefore, an infinite audio stream should be just as “challenging” to process as a tiny sound file. It scales nicely.

I just pushed my most recent changes to NaturalNum - a python library for natural language representation of integer values.  E.g. usage:

$ python example.py 123456 en_GB [‘one’, ‘hundred’, ‘and’, ’twenty’, ’three’, ’thousand’, ‘four’, ‘hundred’,‘and’, ‘fifty’, ‘six’] $ python example.py 123456 fr_FR [‘cent’, ‘vingt’, ’trois’, ‘mille’, ‘quatre’, ‘cent’, ‘cinquante’, ‘six’]

Currently, only English and French are supported, for values up to hundreds of thousands. More languages will be added as inspiration strikes.  The library can be downloaded from github.  I stress that the implementation is a Proof of Concept, and is not a shining example of best practices. Really, it took far too much work to parse and validate the rules.  I didn’t want to write a full-blown DSL as I thought the requirements were fairly simple.  In future, I would not attempt this kind of thing with manually hand-crafted code.  There is heavy use of regexps for validation, and it is probably quite hard to understand what the code is doing.  Pyparsing could perhaps yield an alternative implementation. NaturalNum NaturalNum is a python module for easy conversion of numeric values to natural language, with full internationalization. E.g. “2100” can be mapped to “two thousand one hundred”, “deux mille cent”, “2.wav,1000.wav,1.wav,100.wav”, or any other representation, according to rules-based configuration. Quick Start The script example.py provides an example usage of the library, allowing command line evaluation of natural language. E.g.:

I’m trialling expert systems, in order to abstract away some tricky internationalization logic in an IVR application. Drools Expert might be what I need and will hopefully save time, compared with devil-in-the-details DSLs. The idea of a Rules Engine is that business rules are abstracted out of your application. Business rules are likely to change, so ideally they should not be in the source tree. Additionally, rules may be consulted or modified by business users, so ideally would be free from syntactic mess, and should be self-documenting. The idea in Drools is that a domain object (in this case an Applicant for a driving license) is injected into a rule. A rule is specified in a form which looks a bit like pseudo-code. The rule contains knowledge on what should happen to the Applicant depending on the values of its properties (for example if age is greater than 18). As conditions are satisfied, properties may be set on the object (e.g. setting valid to true or false). So when the Applicant has ‘passed through’ the rule, its state will reflect the outcome of the application. I wanted to get a quick example up and running, so I can gradually tweak it towards what I want. But I had some trouble with the Quick Start tutorial in the user guide. Here’s what I did to get a simple unit test passing in IntelliJ 9.