Overlap

Though the typical mathematics-heavy curriculum for 'Computer Science' studies seems to suggest otherwise, even in its simplest form with only one dimension this is probably the most advanced mathematical problem many programmers ever encounter in their jobs: "Do two intervals overlap?" Naturally, a whole range of applications need to have such a check in place with respect to the scheduling of resources within a time frame.

Over time I've stumbled on a number of implementations in production code by different programmers who undoubtedly set out to take the task very seriously. I imagine sheets of paper with pairs of bars in all mutual configurations possible... (No, my imagination is not usually that creative... Let's say I know someone... And no, I am not mocking anybody.) Still, the resulting code was either overly complicated or flat out wrong, possibly because one possible configuration of two intervals was overlooked. The possibility of open ended intervals, sometimes in combination with using separate fields for date and time, didn't help in keeping the intent of the code immediately obvious, let alone easy to review for correctness.

Of course the solution to the 'interval overlap' question is very simple and the code can be very short and understandable. In mathematical terms: two intervals [a₁, a₂] and [b₁, b₂] overlap if and only if a₁ < b₂ ∧ a₂ > b₁.

The details of writing that in your language of choice, dealing with open ended intervals and separate fields for date and time are left as an exercise to the reader.

"But wait...", you say. "That looks so simple it can't be true. That expression can't possibly cover all the bar configurations I drew on these sheets of paper... Oh well, I can check with them of course. Hmm, it seems it might be true after all..."

That was my voice (perhaps without the drama added here for effect). My colleague challenged me to proof that the expression above holds after all. Only months later, after encountering yet another piece of complex code that was written with the exact same goal, did I sit down to take up the challenge. Trying to remember from 'Analytics' class how one goes about proving stuff, not much more came up than just the phrases 'Complete Induction' and 'Complete Intimidation'. The latter proving technique is pretty attractive and often rather effective as well, but it's really frowned upon by the elite (of which I obviously want to be part desperately). As the Induction technique didn't seem suitable either... well, I came up with the following, which I think is conclusive enough:

Intervals [a₁, a₂] and [b₁, b₂] overlap if a c exists that is part of both intervals:
   a₁ ≦ c ≦ a₂
   b₁ ≦ c ≦ b₂

From these equations one can easily deduce that:
    (a₁ ≦ b₂) ∧ (b₁ ≦ a₂)

Note that when
    (a₁ = b₂) ∨ (b₁ = a₂)
the overlap has a length of 0, which you wouldn't consider an actual overlap. So, for an overlap with length>0 the condition remains:
    a₁ < b₂ ∧ a₂ > b₁

Q.E.D.

Please let me know if I'm oversimplifying things... although you may be forgiven for thinking I just 'overcomplicated' the issue. And in case you were really looking for something slightly more challenging, please have a go at this. ;-)

Update:An anonymous commenter points out that I was indeed oversimplifying and provides the remainder of the proof. Thanks for that! ;-)

I really like it when a little thinking helps to keep our code base maintainable by expressing the logic as compactly (yet readable) as possible! I do hope however that the above is hardly my most important contribution towards that goal...

Writing elsewhere

At the start of this year I resolved to seriously invest time in writing online about (among other things) the coding puzzles I encounter. A number of the reasons that people generally give for blogging would apply (basically: they say it makes you smarter...). Unfortunately, I never even finished the post outlining those reasons (just as well) and got stuck writing another highly profound and insightful post... ;-)

At least Twitter helped me over the threshold to express some thoughts in public, but of those 140 character observations a few could 'easily' have been expanded upon, if only I had the discipline... :-)

This week I did upload a longer piece with my thinking as a software developer, but put it as a comment under somebody else's blog... So, I'm clearly not giving this blog the priority I resolved to, but by linking to that particular comment on a proposal for 'Asynchronous cache updates', I can at least give the impression of activity in this space... :-)

B.t.w. I regret bringing up the 'code ownership' question in that comment. It is beside the point and says more about me (being somewhat intimidated by the hairy legal issues involved in reusing utility code between organisations) than about my former colleague, who did nothing wrong.

Faster failing JavaScript

Though having applied JavaScript as a 'necessary evil' ;-) in the web applications I work on, I have rarely delved into its powerful OO and meta-programming capabilities. Then, last week, I built a small HTML component that could be opened from (or embedded in) any other HTML page. Values would be retrieved and returned through a small number of callback functions. Consequently, these callbacks became the contract between my little component and any page that would open/embed it.

Not being able to enforce such an 'interface contract' in the dynamically typed JavaScript posed us with a maintainability challenge. So far we've not been able to automate testing of the mostly context specific JavaScript within our dynamically generated HTML and therefore we have always needed to rely on the intrinsically unreliable manual labor of clicking through the application to see if everything works the way it should. In this modus operandi the addition of a new feature can easily break an existing feature, and that mistake can go unnoticed for a long time if the original feature isn't used much, even though it might be vital for the overall quality of the product. Fortunately, our sharp test team would catch it in Beta most of the time, but that of course is not nearly as efficient as finding and dealing with it in the development stage. Therefore we now asked ourselves the question how we could help ourselves noticing breakage as soon as possible in case the 'contract' to the component would need to change in the future and some dependent HTML pages would get overlooked in that refactoring.

I was aware that others had run into similar challenges with the also dynamically typed Python language and came up with tools like Zope interfaces and PyProtocols, neither of which I have used or studied, because... in my small spare time projects the need just hasn't arisen. :-) Even though so far I have not been able to find a similar solution in the land of JavaScript (filled with many powerful libraries/toolkits of which I only know the name, if at all), I find it hard to believe that nobody has picked up this challenge and tackled it, so I probably did not search thoroughly enough. My apologies for reinventing that wheel, though I admit to greatly enjoying the exercise. It certainly helped me grow a better understanding of JavaScript's OO mechanics.

Here is the simple utility that I came up with:

/**
 * JSInterface is a class that allows to specify an interface and
 * test/assert whether an object implements it.
 */
function JSInterface(functions) {
   this.functions = functions;
}
Function.prototype.getName = function() {
   if (this.name == undefined) {
       // necessary for IE; not for FF
       this.name = this.toString().match(/function\s*(\w*)\s*\(/)[1];
   }
   return this.name;
}
JSInterface.prototype.assertCompliance = function (obj) {
   for (i in this.functions) {
       functionName = this.functions[i].getName();
       f = obj[functionName];
       if (!f || typeof(f) != 'function') {
           throw "Interface compliance assertion fails: '" +
                 functionName + "' is missing on object.";
       }
       if (f.length != this.functions[i].length) {
           throw "Interface compliance assertion fails: number of arguments for '" +
                 functionName + "' is different from what's expected.";
       }
   }
   return true;
}
JSInterface.prototype.testCompliance = function (obj) {
   try {
       return this.assertCompliance(obj);
   } catch (e) {
       return false;
   }
}
JSInterface.prototype.signalIfNotCompliant = function (obj) {
   try {
       return this.assertCompliance(obj);
   } catch (e) {
       document.write(e);
       document.close();
       alert(e);
       document.location = "about:blank";
   }
}

With this JSInterface class in place, a specific interface can be declared as:

/**
 * FooEmbedderContract:
 *     required to be implemented by pages that embed the Foo component
 */
FooEmbedderContract = new JSInterface([
   function getFooInput() {},
   function getBarStatus() {},
   function setFooStatus(status) {},
   function setFooResult(result) {}
]);

Can you tell that I attempted to design this to somewhat resemble a Java interface definition? ;-)

The idea is to link to this code (should be in a separate .js file) in all pages that intend to implement the contract and put the "fail faster" check after the functions that implement the interface, like so:

function getFooInput() {
   return document.getElementById("fooInput").value;
}
function getBarStatus() {
   return barStatus;
}
function setFooStatus(status) {
   fooStatus = status;
}
function setFooResult(result) {
   document.getElementById("fooResult").value = result;
   barForm.submit();
}

FooEmbedderContract.signalIfNotCompliant(window);

The FooEmbedderContract object simply tests whether all functions that should be in window are there, each with the same number of arguments as specified in the interface definition. The signalIfNotCompliant function is meant to give immediate feedback in an HTML document context (although that feedback looks really raw in this implementation, it simply is not supposed to ever occur in a production situation), while the assertCompliance and testCompliance functions can be useful in a pure JavaScript context.

It is a good idea to also make the interface contract explicit within the component itself (increasing readability of the code), by testing the opening/embedding window against the interface at the start of the component's HTML (effectively carrying out the same test twice, but that should not really be a problem performance wise).

This approach doesn't of course take away the need to test the application by clicking through it, but it can signal problems with features behind links and buttons that are not yet clicked (and might not get clicked in a hurried test). As we're optimizing for failing as fast as possible in case of an error, this utility should at least help in 'failing faster' than would have been the case without it. Now, for maximal benefit, we have some work to do in starting to introduce these interface declarations and assertions in more places in our existing code base...

'Why Ruby should never be taught'

The title shamelessly refers to this post by Ka Ping Yee (via Tim Bray).

As I finally started to really learn to decipher Ruby by reading the Pickaxe (2nd edition), I came across one example that I knew must contain a typo of some sort. I fired up irb just to make sure... but came away horrified:

irb(main):001:0> def a
irb(main):002:1>   2
irb(main):003:1> end
=> nil
irb(main):004:0> a = 3
=> 3
irb(main):005:0> a
=> 3
irb(main):006:0> a()
=> 2

A single name within a single scope that refers to two different things!

It took me quite a while to realise that in many languages (including Java which I use almost exclusively at work) this isn't so bizarre at all, because those grammars make a very clear distinction between variables on the one hand and functions/methods on the other.

When studying Ruby, I am apparently reasoning from a Python and JavaScript mindset, because I expect Ruby to share with those languages the dynamic typing nature and the combination of OO and functional programming influences. In Python and JavaScript the above is simply unimaginable.

It is obvious that I have quite a number of obstacles to overcome in getting used to Ruby...

Reluctantly started to make some sense

Adding features to an old code base is hard and often not much fun. It is especially hard when not enough time could be budgetted to really get to understand what that particular piece of code is trying to accomplish, let alone to figure out by which coincidence it is actually almost accomplishing that original goal most of the time.

But of course, if you want to stand a chance of successfully shoveling all the 'accidental features' that you and your teammates introduced in the previous release candidate under the carpet, at the end of the day you need to get pretty familiar with whatever logic apparently appeared most intuitive to a bunch of other clowns.

So this week, after spending hours doing my very best to avoid making 'new major changes', which many of us claiming experience with such matters consider risky at the project stage we're in, I had to concede that I didn't really understand much of what some esteemed predecessor had thought was a good solution to the problem at hand. And if we wanted our users to enjoy working with an application that behaves in a somewhat predictable fashion, the last programmer leaving his mark should at least be able to predict that behaviour rather precisely from what he'd observed. As it was, all of us unlucky enough to have witnessed that particular string of characters were manically trying our best to eventually forget that painful sight.

Coming to realise that there would not be any other way out apparently was the hardest part. Finally, yet another unexpected 'accidental feature' side effect broke what was left of my resistance and I set out to do what we had all agreed by oath to never do... With a next release candidate scheduled for yesterday (or the day before), I was going to seriously touch untouchable code... I started to slowly replace all kinds of magic numbers with self-describing semi-constants (say what?) and flattened deeply nested if-then structures by introducing just enough well defined boolean variables. Eventually a satisfying sense of logic started to emerge... Even the readable and predictable kind of logic that I was looking for! But then, with the spaghetti straigthened out and all alligned, and some initial testing confirming that the program was actually doing what I now believed it should, the scary thing was that quite a number of lines appeared to be missing in action...

Not to worry though! Let's just say "less is more" and 'what he says' etc. etc. and hope nobody is going to actually, you know, miss those lines ;-).

And if you think that I am completely full of myself because of my little far fetched success story... well, you might be right, but I tend to consider this more of a humbling experience really. And don't forget that I now have many boring hours ahead of testing just about all the different scenario's the code attempts to deal with... which was probably the real reason I was putting off this refactoring for so long in the first place. And, err, no, unit tests were not exactly available or straightfoward to introduce in this 'JSP heavy' environment.... :-(

Anyway, what I enjoy about this is that dealing with legacy code can actually become rather satisfying and good fun as soon as you dare fixing things up, even in small ways. That, and that it gave me an excuse to link to a great blog post that advocates keeping code bases small, but loses all credibility by being way too long itself... :-)

Spoken

(A story in Dutch...)

Ben wordt wakker. Alweer. Het is donker en hij is nog ontzettend moe. Hij draait zich maar eens om. Het liefst valt hij nu gelijk weer in slaap. Maar dan dringt het tot hem door dat dat niet gaat lukken. Rustig blijven! Niet weer in paniek raken... Te laat. De stress is niet te stoppen en giert al gauw door z'n hele lijf.

De laatste nachten was het steeds opnieuw raak. Er moet een oplossing zijn! Verzin toch iets! Dan kun je daarna weer rustig gaan slapen. Maar hij ziet geen uitweg. Waarom kan hij het weer niet zelf? Ach, hij kan het heus wel, maar niet nu, niet in deze situatie. Natuurlijk had hij het ook nooit zover moeten laten komen! Nu moet hij zich gewoon neerleggen... maar dat lukt juist niet. Hij heeft dat al zo vaak geprobeerd. Het is allemaal zo vermoeiend!

Hij denkt terug aan z'n uitbarsting van vanmiddag. Hij was het zat om genegeerd te worden, steeds het idee te hebben dat niemand echt luistert naar wat je te zeggen hebt. Z'n leidinggevende toonde wel begrip, maar vond ook dat ie moeilijk deed. Hij kan zich voorstellen dat ze hem er straks gewoon uitgooien. Misschien is dat ook wel het beste... Van hem hoeft het allemaal niet meer zo nodig. In het begin was alles nog nieuw en leuk, maar nu...? Kon hij het ze maar duidelijk maken! Weinig kans. De communicatie loopt al zo stroef. Misschien gaat dat over een tijdje beter... Het is in elk geval niet zo dat hij daar niet z'n best voor doet.

Op dit moment heeft hij daar niets aan. Hij kijkt naar de schimmen van de meubels in de kamer. Zo kan hij niet slapen. Zijn wereld staat op z'n kop! Als z'n ouders het eens wisten... Ze zouden zijn frustratie wel begrijpen, maar zij hebben juist steeds gezegd dat hij het zelf moet kunnen. Ja, tuurlijk! Maar zij slepen niet de ballast met zich mee waarmee ze hem hebben opgezadeld.

Hij weet dat hij hulp zal moeten inschakelen. Maar tot nu toe won de schaamte het steeds van dat besef. Er beginnen tranen te stromen. En dan schreeuwt hij het uit in de stilte van de nacht. Z'n adem stokt en hij hoort weer alleen die stilte. Er zal toch vast iemand zijn die hem hoort?! Hij zal blijven schreeuwen... Nee, het lucht niet op. Helemaal niet. Het helpt hem geen steek verder. Maar wat moet hij anders? Blijven ademhalen, want dat zou je nog vergeten. Maar dan stoot hij z'n vers gevulde longen weer leeg in de volgende oerkreet.

De deur van z'n kamer gaat open.
"Hallo meneer, wat is er aan de hand?"
Een mannenstem. Hij kent die stem wel.

"O, ben je op je buik gedraaid?! Maar jochie, waarom draai je je niet gewoon lekker weer op je rug? Ja, ik snap wel dat je dat moeilijk vindt met je slaapzak aan. Nou stil maar, kom maar even mee naar mama... misschien mag je wel even aan de borst! En je had al zo weinig geslapen vandaag, want in het kinderdagverblijf wilde je niet. Ja, ja, rustig maar... Kijk eens wie daar is!"

Ben schokt nog wat na, maar hij weet dat het nu allemaal goed komt.

I never thought I'd get here... and I wonder if I'll stay.
It's tempting to just run away, as this freedom makes me fear
that I'd be talking into thin air, with nobody to care ;-)