Sleep

I've had it explained, with diagrams and everything, but my dear brain has no truck with the concept. Thus it is that I'm wide awake at 0300 with programming problems vying for mindspace. Technically, one programming problem and one programming language.

The problem is one of memory management. My employer's language of choice, IDL, is great if what you want to do is prototype some procedural code with the backing of some convenient built-in libraries for DICOM, XML and lots of maths gubbins. It's (fairly) cross platform too which is nice in a mixed Windows/OS X/Linux environment. Pity I'm developing applications that have to behave like proper applications. You know the ones: functionally complete and correct, easy to use, robust (in the face of some of the users' idiosyncracies), pretty and as short a bug list as possible.

So happens that IDL supports objects as well as procedural code. Hurrah! Because of this, I can bring lots of OOP goodness to bear on my applications! On second thoughts, perhaps that should read: "Despite this, I can..." IDL is weakly and dynamically typed which means the "compiler" is little more than a glorified syntax checker and everything fails at runtime. Lots of folks like that sort of language, I'm just not one of them, especially when it comes to anything more than trivial applications. IDL also has no concept of private, protected or public access modifiers for classes. No C/C++'s #define nor Java's public static final class members for constants. No standard library for fundamental data structures like lists, maps, red-black trees. I've written the libraries or worked around most other "features" but there's one that's recently risen up to bite me. Again.

No garbage collector.

There is, sort of. As long as you aren't using objects. I use objects as a matter of course because it's the only way to get a measure of type safety in IDL. So that left me with implementing reference counting. It's worked extremely well for the last five years or so, everything deriving from a single base class implementing addRef() and destroy() to change the ref count and which finally calls its own destructor when the ref count hits zero.

There were a few wrinkles with things like ensuring correct destruction of objects that were both observed and observer in the Observer pattern but nothing serious. As long as I avoided one construct, that is: a tree where, as well as the parent holding references to its children, the children each hold references to the parent. This mutual holding of references ensures that, without special handling, at no time can the reference count of parent or child reach zero and so the tree can never be destroyed.

This is the nub of the problem, I cannot see how to avoid needing this construct. I need to be able to hold a reference to one node and navigate the whole tree, ancestors and children, from that one node. I have to find a way to both ensure that the tree is destroyed when no longer needed, but not until exactly none of the nodes of the tree are referenced by any object outside the tree itself. The only solution I've come up with so far is to do a brute force search of the tree for a node who has a ref count that exceeds (parent + number of children). Obviously this has worst-case performance of O(n) where n is the number of nodes in the tree. Inelegant and inefficient :( Sadly, it's the only solution my nocturnal brain can come up with. Hopefully tomorrow I'll get it implemented correctly so at least I'll actually have a working solution. If the real world performance is unacceptable then I foresee painful optimisation.

The other thing fighting for thinking power is Haskell. I've never used functional programming before but I read that it is to object-oriented design what object-oriented design is to structured procedural coding. Clearly the thing to do is learn it and find out... You've got to wonder about a language where you can write a quicksort in one or two lines of code and a power of 2 FFT and inverseFFT in less than 50 lines including comments, right? Cue lots of time awake while I try to assimilate lots of new and alien concepts :/ How functional programming and my comfortable world of imperative Java/IDL relate in another post.