To my Muslim friends, Happy Fasting during the Holy Month of Ramadhan!

May the Divine’s Blessings be with us (on any month, really, is the wish :P). I humbly apologise for any errors I have committed.

If you managed to read through the rather long post title… let’s move on to a much longer post.

I recently came across an interesting bug at work which was rather eye-opening on just how nasty backwards-compatibility (which prompted type erasure!) can be. Credits are due to my friend and colleague Marcus Hasslinger who reasoned through the issue with me from a backwards compatibility viewpoint.

Some background: we use Java 5 and EJB 3, we also make use of annotated methods that are inspected by custom EJB 3 interceptor(s). A sample EJB might implementation might be:

In the above, the interceptor (TransactionHandlerInterceptor) is an around-invoke type interceptor which intercepts doSomething(), reads the annotation on it (RollbackWhen) and decides some rollback logic.

The defect was that in a particular EJB, it would not detect the method as having this annotation, and thus the necessary rollback logic was never executed. Thus begins our saga. Rather than going through work artifacts (which I probably can’t show anyway) and bore you with our business domain, I’ll create an essentially similar example using the classic ‘Shape’ set of objects (I know.. I know…).

This particular EJB had the following structure:

The issue was that whenever the interceptor intercepted CircleServiceImpl.draw(), it would not detect that it was annotated with @RollbackWhen. So I printed out the actual method.toString() output from within the interceptor – this turned out to be:

instead of the expected:

Obviously draw(Shape) is not annotated with @RollbackWhen, draw(Circle) is. Hmm. So where exactly does draw(Shape) come from though, we only ever implemented draw(Circle) in CircleServiceImpl. It’s time to look at type-erasure in action under the hood using ‘javap’ – a useful little bytecode disassembler that comes as part of the stock JDK. The following output was obtained by running ‘javap -c ’ (without the .class).

Let’s start with the simple cases: Shape and Circle – Shape is a simple interface, all fine and dandy. Circle is a class implementing Shape, we can see the default constructor generated since we didn’t provide one of our own.

Next we look at ShapeService – a bit more interesting – it has an abstract method draw(Shape). Generics information is erased, there’s no ‘T’ anywhere. T is replaced by its upperbound, i.e. Shape. Thus the generated method too is draw(Shape). So far so good.

Moving on to CircleService – once more, the parameterisation is nowhere to be seen, there’s therefore no notion of Circle in CircleService, it simply extends ShapeService, and thus inherits the same method signature: draw(Shape). This is what got me – it of course, needs to be this way due to type erasure. You get the illusion of full type-safety, as if a new method draw(Circle) is automatically generated in CircleService – since after all, compile-time code completion, etc. in your IDE works just dandy on a reference of type CircleService – CircleService.draw(Circle) – never does it show CircleService.draw(Shape)!

Let’s move on further – things are getting more interesting. CircleServiceImpl has 2 overloaded methods, draw(Circle) which is our code converted to bytecode, and a compiler generated draw(Shape) – which casts (or at least does a cast-check – haven’t read the bytecode description) to ensure the supplied Shape is indeed a Circle, and then delegates on to our draw(Circle). Think about this for a moment – by itself, it’s just madness – but from a backwards compatibility viewpoint — 2 methods need to be there, our own draw(Circle) which as you can see, did not override any method in the interface as such(!), and draw(Shape) the compiler generated one – which is needed to satisfy the type-erased interfaces we implemented!

One final piece of the puzzle — client code: once more we see a default constructor is generated since we didn’t create one. And then the main() method which in fact calls draw(Shape), not draw(Circle). This is once more correct in a backwards-compatible-whacky way — as we saw above CircleService only ever had draw(Shape) — since we used the CircleService reference, that’s the method we got. And thus the implementation class needs to generate draw(Shape) and delegate to our draw(Circle).

In as far as our defect goes — this is exactly why it did not detect the annotation — it was intercepting the client-invoked, compiler-generated draw(Shape) which in turn invoked draw(Circle). draw(Circle) is of course an internal invocation, not accessed via the EJB proxy anymore, and hence never intercepted again.

Ah backwards compatibility.

That aside, there are a few observations to be made:

• A generics call in the above fashion will always incur an additional cast check and method call, not a big deal for most code, but within a loop, etc. best to measure it. On the bright side, the checkcast is a single JVM instruction. Another optimisation – if you can even call it that! – is to explicitly declare a method draw(Circle) in CircleService – then it is generated as per normal, and client code goes directly to CircleServiceImpl.draw(Circle) – at this time, this is our workaround for the defect. I’ll leave the discussion of where the annotation should belong for another time (i.e. implementation class or interface – this is more a design principle/responsibility issue)
• It’s interesting that specifically from an EJB 3 interception and transactional semantics viewpoint – this is quite nasty since you do not intercept a method that you think is part of your EJB interface, nor does the transactional semantics get applied (apart from the default ‘required’ of course)! I wonder if it might be better, if in an EJB 3 class, the generated draw(Shape) method did not do a plain invocation of draw(Circle), but accessed it via an internal EJB proxy reference (circleServiceEjbRef.draw(Circle)) – this would ensure proper transactional semantics and interception. Wait – the generated method in fact should not enforce any transaction type either — it should just be (if I recall correctly) using ‘supports’ semantics. As it stands, if draw(Circle) were annotated with a transaction attribute other than ‘required’ – this would not be picked up at all since it was a direct invocation, not via the EJB transactional proxy! Nasty, nasty! It could lead to some very obscure bugs!

Hmm.. I never remember reading about this in any generics book :P. Anyway, if you got this far, hope it was an informative read.

As often happens during quiet periods, one has time to consider future directions as well as past decisions. In Agile Software-speak, a retrospective (aka retro) if you will. My retro this time has been about decisions. Life seems to have impressed upon me the need for correct and careful decisions – taken with mind, heart, and conscience.

Decisions wrongly made have a lasting impact – not days, not months, but years and beyond. Were this limited only on the decision-maker perhaps it would not be so bad, yet decisions more often than not affect at least two people, usually many more in the long term directly and indirectly. If one subscribes to the idea of Systems thinking, one will agree that nothing stands in isolation – everything is connected – context is always there. Only the Divine knows when that profound impact will be erased, and things return to ‘normal’. Perhaps they never will of their own accord (though they say Time heals all, though more accurately the Divine heals all), and making things right will involve the decision-maker to basically live with, learn from, and persist post that decision, hard as it may be. And to those ever affected by any dodgy decisions I’ve made – you have my sincerest apologies.

Ah retros – sometimes they leave me unmotivated. *Stretch*

Finally got around to uploading this. Have not had time to make a proper public repository, doubt I will have time, so as usual, sources and tests are there to light the way!

Many aeons ago I was introduced to icanhascheezburger (aka lolcats) (by ruby2shoes, who commented here). For those of you who have just joined the interwebz (or can be as ignorant as I for non-technical fun stuff), lolcats is a user-contributed compendium of pictures (and videos – thankfully a lot more pictures!) that display the majestic creatures we know as cats in an amusing, majestic light, doing what they do best – sneer at humans (or hoominz in lolspeak) and dogs :P. Fun stuff!

Anyway, I have decided to bookmark my favourite entries – been doing so intermittently, if you’re feeling particularly bored, visit my lolcats tagged items.

Enjoy! 😛

Recently, I’ve been messing around with a fair bit of Groovy, a little bit of Scala, and a background-favourite (whatever that means), Python.

All 3 languages have functional traits, one functional idea is reduction where a collection of items is operated upon and finally reduced (hence the name) into a single value. From a practical viewpoint, this could be an overall analysis derived for all items in that collection – a sales percentage, a sum, or some other statistic. I am not a functional programming guru, so apologies for the rudimentary description. I was curious to see how each language handles it, and how I might write an implementation of reduce().

In particular I came across Scala’s List.foldLeft(). It also has a corresponding foldRight (and both functions have shorter operator notations :/ and :\ — which look like emoticons as I type this). Right and left determine where in the list it starts converging/reducing. Left starts from the start of the list (if you imagine the list horizontally rather than vertically, with the first/top most item on the left), while right starts at the bottom/end of the list. Depending on values in the list, and/or operations performed on them, the traversal order could obviously impact the result. Thus we note that fold-left and fold-right are basically types of reduce.

On to some code. I’ll keep it simple, albeit a little boring and predictable, the reduction will yield a sum of all elements in the list (yawn…). We’ll see some interesting properties of this simplicity however, and why it matters. I’ll start off with using the stock API for each language, and then roll my own. In all cases, essentially the following happens:

• Decide on a collection of items (usually repeatably ordered!) to reduce
• Apply the fold-left/reduce call which takes in an initial value to be used as we wish, in our case it will be a total result, initialised to zero
• The fold-left/reduce call also takes a closure which is called for each item in the collection. The closure must return/yield a single value each time it is called (i.e. for each item in the collection), and takes 2 parameters, the running total and the current item being iterated over in the collection. I say ‘running total’ for our example, but more generally: for the first item in the collection, it is passed in our initial value, for subsequent items it is passed in the last ‘reduced’ value, i.e. the value that it yielded in the previous iteration.
• A value is finally yielded and returned to the caller after the last item in the collection has been visited. In our case, the total.

Scala:

Groovy:

Python:

A Few Notes on Syntax (skip this section as needed):

For the Scala and Groovy versions, note the syntactic sugar, both inject() and foldLeft() are functions that take 2 parameters, the initial value and a closure. It’s just that the closure can be defined as if it is ‘attached’ or ‘hooked to’ to the function rather than passed in, rather nice. With Groovy, the closure arg has to be the last one to allow this syntax (otherwise you can pass it in ‘foo(“bar”, { /*closure */ }, “meow”)’ like a regular parameter. In Scala, it depends on how the closure parameter is defined – in the case of foldLeft it is in its own parameter list, and so is not part of the initial set of args. I’m still a Scala n00b however, so I’ll stop there!

The Python case looks a little funnier, I am using the lambda form to create a new anonymous function, I could have also defined a function in the scope, and passed its name in as the first argument. This would be needed if I had something more involved in the function which the lambda form could not accomodate or accomodated hell-ishly (its body has to be a single expression only, no statements). Python doesn’t support more complicated anonymous functions as a language construct (there are code-level hacks though).

Implementing fold-left:

Now let’s try re-implementing fold-left using Python for clarity. Python has the idea of ‘sequences’ – positionally-ordered collections (from Learning Python 3E) – lists, strings, and tuples. However I am not sure why there’s no specific ‘sequence’ type, because this would have allowed setting a foldLeft/reduce call on this supertype leading to a more OO feel where you could do sequence.foldLeft(…). Instead the approach is much more procedural as you saw above. I’ll stick to the procedural approach for my implementation so arbitrary sequences can be passed in generically. I have not had a look at the source code for foldLeft in the languages above, I shall soon, however here’s my go at it:

There are 2 versions of the fold-left functions above, foldLeft() and foldLeftMutable(). The latter holds mutable state, albeit localised to the function (the localvar reduced), so probably no big deal (considered a non-functional implementation though?). Both functions have O(N) complexity1. I initially thought I had something exponential for the recursive version, but then realised that I was returning at each iteration, phew! Of course, O(N) also assumes that reducefunc here is O(1)! foldLeft() though holds zero mutable state even within the function. The sequence is sliced resulting in a new sequence each time before the recursive call. This is probably overkill, resulting in new objects each time – but kinda cool anyway from an immutability viewpoint. Needless to say that immutability is based on the assumption that items in the sequence are also immutable, or if mutable, are not being messed around with by the passed in reducefunc argument (in this case adderfunc). But as far as the direct objects that foldLeft() deals with – the sequence, initval, and reducefunc – it in no way changes them.

foldLeft() is, however, I think tail-recursive (another thing I need to read up on!) so it could just be converted to a plain iterative version by the bytecode compiler which would result in something similar to foldLeftMutable(), any specific comments on this would be highly appreciated. Anyway, bed time.

Footnotes:

1 I just realised that slicing the list to produce a new list is likely to be O(N) rather than a constant time operation, which would invalidate my claim that the recursive version is also O(N), grrrr. Now I really am off to sleep.