Software

I’m proud to have completed the first ever offering of the MOOC in Artificial Intelligence, run by Sebastian Thrun and Peter Norvig through Stanford University.

It was intriguing, challenging, and ultimately fun to get a first bit of working knowledge of things like spam filters, robot localization, and computer vision.

I’ve written a little Bayes filter based on the model introduced in that course.  I’ve hooked it up to my IRC client to alert me about the most interesting messages.  As they say though, the hardest part is the training and data collection - it’s hard and time-consuming to come up with enough good data to form a workable model.

The main things I’ve gained from the course is an appreciation of the kinds of problems AI can solve, as well as an idea of what tool to use in a given situation.

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.

It seems I’m obsessed with finding new applications for GPS data.  The latest is an idea called Smart Trax: a hypothetical social application for discovering and sharing cycle routes. Imagine if you could upload a route (recorded via GPS), and find “similar” routes.  These similar routes can then be compared to your own.  It turns out there are a number of applications for this. Operation Duck Pond It’s the weekend, you’re a keen cyclist, and your bike is getting lonely.  You draw back the curtains, and see only blue sky and sunshine.  Ignoring the washing up, you fill up a water bottle and jump onto the saddle. But where to go?  Well, there was that circular route on quiet roads around the Thames Valley, published in Cycling Plus a few months back.  You feel fairly confident you can remember the route, and are too impatient to dig out the magazine. Never mind, it’ll be OK.  Just one last thing: you grab your iPhone, fire up a GPS app and press Record.  Stick it in your pocket and off you go. As you pass the pretty duck pond in Barnes though, it all goes wrong.  Taking a wrong turning, you find yourself on a hectic A Road, dodging juggernauts and choking on exhaust fumes.  Eventually, tapping into ancient wisdom, you sniff the air and somehow find your way back onto the planned route. When you arrive home, invigorated and exhausted, you wonder how you got so lost.  So you upload your route data from your iPhone to the “Smart Trax” website.  The website searches through its history of routes uploaded by other users, and finds the closest matches.  Fortunately for you, there will be many matches because the route is a well-known one (published in a major magazine). You see a map of your route appear on the screen.  A red dot appears at the start position (that’s you).  Other dots of different colours appear alongside yours (that’s the others who took the same route).  You then “play back” the route, watching the different dots progress in their different ways.  As your red dot approaches the duck pond in Barnes, it makes the fatal decision of going straight ahead, while all the other dots turn left.  That’s where you went wrong. Racing Dots As well as the described scenario, Smart Trax has competitive, ‘gaming’ applications, for example racing against other cyclists over the same route at different times.  For example, many competitive cyclists compare lap times of Richmond Park.  It would be interesting to overlay a number of cyclists on the same map, and watch them race side-by-side at a later time, even though they showed up on different days. Commuters could find value in Smart Trax, too.  If you cycle from Hammersmith to Baker Street, you might think you have to slog through Oxford Street traffic.  No matter, there are many others on Smart Trax who took routes with similar start and end points, but were more prudent by cutting through side-streets.  These will show up when you look for similar routes.  The alternative routes would appear as differently-coloured paths. Long-distance tourers and charity riders would benefit too.  Cyclists who are considering the “Lands End to John O’Groats” challenge might like to see real routes side-by-side, perhaps looking for the fastest, most scenic or shortest route.  Smart Trax would automatically detect LeJOG routes and group them together, because they’re all similar on a large scale. Challenges There are several technical challenges with this idea: - Algorithms to find closest matches.  It would be necessary to smooth the (sometimes erratic) GPS samples, and allow fuzzy-matching because relatively small deviations shouldn’t matter.  It should also be possible to scan for incomplete matches on routes.  For example, I might join a typical route half-way along, but I still want to know how my shorter route compared with others who did the whole hog. - Interface design.  The obvious choice would be to use public APIs and toolkits such as Google Maps.  But this might not provide the flexibility required for features such as “racing dots”.  So, a starting point would simply be paths traced over an opaque background, with pixels mapped to GPS co-ordinates.  A map or satellite background could be added later on. Personally, I might kick this idea off by comparing my daily commutes side-by-side.  It would be interesting to see one “dot” surge forward ahead of the others and wonder “what happened on that day?”  Perhaps the system would detect a particularly interesting “dot” and highlight it with annotations created at the time of upload, such as “mighty tailwind”, or “took the scooter for a change”.

I had an idea to create a road map for cyclists, colour-coded by the likelihood of congestion, using GPS data. Here’s some background.  I’ve been plotting a cycle commuting route from the West End to the Kingston area.  On the map, Fulham Road looked like the most direct route: a relatively straight diagonal to the SW. But when I jumped on the bike to try it out, I found that Fulham Road is narrow, and so there is no way to filter past heavy traffic.  The moral of the story is that the most direct route is not always the fastest. Now, I record all my routes via GPS, so I have data files containing time-stamped way-point data. In theory, if I looked back at the extract I would see that some roads were fast and others were slow, by working out the average speed between splits. I could then turn that GPS data into a nice colour-coded map: red roads for slow, and green roads for fast. Anybody who looked at that map would know to avoid Fulham Road at the time I hit it. Now what if thousands of cyclists did this, and the data was aggregated? You’d eventually have a road map of the British Isles, colour-coded by the likelihood of congestion given the time of day. Taking it further, you could ask for a suggestion of the route from A to B which is least likely to be a wall of steel and exhaust fumes. You could get even warnings or suggestions from your smartphone in real time. This does rely on having access to a large number of GPS recordings from cyclists, so there needs to be an incentive to participate. That’s where the route suggestions come in. I don’t know how practical this would be. There are certainly a number of snags with linking average speed to congestion … Time of day, hills, fitness levels, filtering abilities, “traffic light etiquette” and more. I get the impression that Tom Tom works in a similar way - collecting time-stamped GPS data from a large number of users. But Tom Tom is fairly closed, commercial and car-centric.  I want something tweak-able, for cyclists. Time-permitting, I’ll try this with my own data first as a proof-of-concept. EDIT: I’ve cooled down on this idea.  Once you aggregate large data sets, controlling for outside factors (hills, speed bumps, fitness levels and the like) would be far too complex.  The idea could be re-positioned as simply a “how fast do cyclists go” map for general interest.  I doubt this would get enough interest to justify the effort, though.

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.

Up to now, I’ve always declined to set up security questions on my Yahoo Mail account, simply because I have no fears of forgetting my password.  I’ve never really thought much about the whole thing. But to my annoyance, today I was forced to select two security questions and answers, before I could even log into my account.  Through pure annoyance I nearly lapsed into parody (Question: “Do I really give a F—?”) but then realised this would leave my account wide open for somebody to easily recover my password! This caused me to realise just how big a loophole the security question model is.  Upon reflection, I felt was being forced to provide an additional - and less secure - means of access to my account.  Even if I selected one of the provided questions (”What was the name of the hospital you were born in?”), this could be easily learned through a little social engineering.  Most likely, family members and those in close relationships would have a good chance at correctly answering the security questions for each other. But a further gap exists where it is possible to provide your own question and answer, which may not be chosen with security in mind.  How many people will opt for “What is my favourite colour?” (even a stranger could guess that after a few tries), or even worse “Do I really give a f—” as I nearly set up in my annoyance (the answer to this rhetorical question is obvious). Ideally, we would all set up our own question which only we can answer, but in practice a lot of people will be lax on this. I wonder why Yahoo made security questions mandatory all of a sudden? Presumably I did not choose any when I registered, and perhaps Yahoo are spending a lot of money manually recovering accounts. Although there needs to be a way to recover lost email accounts, the security question model seems far from ideal.  Is there a better way to recover lost email accounts without invoking a manual process?  To answer this, we are really asking the question of “what alternatives are there to passwords - which I can easily forget”?