SOAP on Jetty

A common way for non-Java users to access Mulgara is through the iTQL client jar, using SOAP. This is very bad, as the iTQL jar uses RMI to talk to the server. This is OK if you're in a JVM and accessing the objects directly, since we put a bit of effort into making objects stream intelligently, but if you're going to chunk up the streamed results into XML, then you'll be introducing a whole series of problems. Not to mention that you now move all the data over sockets twice.

Unfortunately, there hasn't been an alternative to this approach before. There are some options with the descriptors interface, but this is designed for providing results for specific queries. Besides that, I hear it's broken at the moment. Trying to run it seemed to bear this out, but at least the SOAP endpoint is there. I believe Brian is looking into this bug at the moment.

The main problem with putting SOAP (or any other kind of access point, such as the RESTful options being considered) on the server is that the iTQL interpreter is supposed to be on the client. If ItqlInterpreter is naively accessed on the server, then some of its internal session data will not be set up correctly.

Fortunately, the main reason the ItqlInterpreter has internal session data is so that it knows which server to send the query to. If I want a non-RMI service on a Mulgara server, then it won't need to work out which server to go to, since it's already there!

However, this isn't a drop in replacement for the RMI service, as I need to find the appropriate references to Sessions and the like. A cursory inspection suggestions I will only need to change a couple of lines, but I want to be sure I get them right, so I'm going through the code line-by-line to make sure I have a correct understanding of all that is going on. It's a little strange, as I know I wrote some of it. There's a sense of familiarity there, and I even remember some things, but in many ways it also looks like completely new code. I'm probably taking longer than I need to in some of these classes, but I'm using the opportunity to get completely familiar with this code again.

One area I need to spend some time in is the Jetty configuration. It looks relatively straightforward, but I wanted to read the documentation for what certain method calls are doing... and that was when I discovered a problem.

The Jetty we are using is version 4.2.19. It turns out that this is ancient. Jetty is now up to version 6.1. This has a few implications.

• No online Javadoc.
• Difficult to track down the cvs revision for sourcecode.
• Not Java 1.5 compiler-compatible (uses enum as a label).
• Only supports Servlets 2.3, not 2.5.
• Only supports JSP 1.2, not 2.1.
• No longer maintained.

I'm sure there's a lot more, but you get the idea.

My initial reaction is to update to the latest Jetty. Unfortunately, I note that a lot of the interfaces have changed, and this will need learning how Jetty needs to be configured. I should also learn how it WAS put together, so I can work out what I'm updating.

The thing that led me here was trying to find out what an HttpContext is exactly, since a group of these gets set in the Jetty server in Mulgara. However, they don't exist anymore, and neither does the the more generic Context class. So I'll have to work out what these things were in order to make sure I can configure the same functionality in Jetty 6.1.

Fortunately, The download site has old versions, including 4.2.27. This should only involve bug fixes from 4.2.19, so the documentation will stay the same.

Frankly, I hate these distractions. The whole way down these side roads you question the value of the effort of learning a new part of the system just so you can replace something that is currently working. There's no denying the value and enjoyment of learning something new, but it really takes the focus off important things.

Zarro Boogs Found

At the start of this week I tried to integrate several patches submitted to Jira. Unfortunately, there were two impediments to this.

The first problem was simply because XML output has now been configured to provide datatypes and language types to any literal that defines them. This makes a lot of sense to me, and I was happy to integrate it. Unfortunately all the scripted tests are looking for exact textual matches on the output, so many of them are suddenly failing. This is trivial but time consuming to fix. As I write this, I'm running tests over my latest attempt to squash all these bugs. I hope I finally got them all.

The other problem seemed to be easier, but was far more insidious.

I was getting an iTQL error that I didn't understand. The stack trace in the log did not take me far enough, so I added in some more logging. The next time through the tests, the section I was analyzing passed, but something else failed.

This went on for a whole night. Every time I thought I was getting closer, the failing code would move. This generally indicates threaded code with a race, but I couldn't imagine where. I finally tracked one instance of the bug down to a transaction exception, which was the point where I decided I needed to talk to Andrae.

String Pool

In the meantime, Andrae had decided to take on the hard task of the fixing a problem that had been reported with the string pool. I had so much on my plate that I wanted to avoid it, though I knew it was a significant issue, and would compromise confidence in the project.

Since I needed Andrae's help I offered some description on the structure of the string pool. However, I quickly realized how lazy I was being, so I decided to look for myself.

Andrae had managed to narrow down the problem to a very specific behavior. This made it much easier for me to think through exactly what was happening, and how the system had to get there.

The problem was due to an entry in the AVLTree, with no corresponding entry in the IntFile. To understand this, I need to explain some of the basics of the string pool.

String Pool

The string pool gets its name from the fact that it used to store strings in it. The strings were either URIs or string literals for RDF. However, it didn't take long before we needed to store other data types as well, starting with doubles, and eventually moving on to the entire set of XSD datatypes. By this point, we had a lot of code using the name "String Pool", and we were all used to referring to it by that name, so we kept calling it that, despite the fact that it holds much more than strings.

The purpose of the string pool is to map these data objects to a unique number representing a node in the RDF graph, which we call a graph node, or gNode. We also need to map from a gNode back to the data, so we know what that node is supposed to be representing.

The string pool is based on two main structures, with each structure providing one of the two mappings we need.

The first is an AVLTree, which is used to sort all entries (of all data types). This is used to look up data (strings, URIs, numbers, dates, etc) to map it back to a gNode (a "long"). It is also used to find ranges of data, such as all URIs beginning with the rdf domain, or all dates in a range. This tree is phased, in that it contains multiple root nodes, with each root corresponding to a phase. Only tree nodes uniquely belonging to the latest phase can be written to. Older phases are for reading data only, and each phase is associated with Answers obtained when that phase was the most recent. (This is why Answers must be closed - we can't mark nodes from an old phase as free until the Answer no longer needs them).

The other structure is called an IntFile. This is an array integers, which we use to hold an array of string pool entries. These entries each contain exactly the same information as the nodes in the AVLTree (laid out in the same way). The entries are indexed in the array by gNode value. Each entry is 72 bytes, so a gNode ID of 100 would correspond to data starting at byte 7200.

Importantly, this array is not phased. Once a gNode gets allocated in a phase, it represents the same data in all phases. The gNode can only be reused after the data has been deleted, AND all phases that have ever referred to that gNode have been closed.

So we have a tree which maps from data to gNode (the "localization" operation), and the array which maps from gNode to data (the "globalization" operation).

Out of Synch

Back to the problem: we have an entry in the tree that is not in the array. Now the methods that put data in the string pool put that information into both structures at the same time. The structure of this information is identical for both structures (the array doesn't have to store the gNode, since the location of the entry gives this). For a gNode to come up as a "blank node" means that the entry in the array is full of zeros, meaning it hasn't been written to.

The problem is trying to work out how the same data can be written into two files, and only show up in one of them.

Data written in a phase tree is really irrelevant until it is committed. Committing means writing the location of the new root to a separate file (called the metaroot file). So if we see data in the tree, then the tree MUST have been correctly committed to disk. The operation of committing means "forcing" all data to disk in a consistent way. We do this by forcing the tree to disk (if this fails partway through, then the old tree data is still valid), and only once this is finished can we save this new root to the metaroot file (making this new root valid in future). If you look at the prepare() method, then you'll see this data being forced to disk, and only then is the metaroot file updated and forced to disk.

So how can this AVL tree get ahead of the array in the IntFile? This could only happen if the IntFile were not forced to disk when the tree was forced to disk. This would mean that while the data was "written" to the array, it would not have arrived on the disk yet, even though it was committed to the tree. This would be bad, as nothing should be "committed" until it is completely consistent on disk.

So the solution was to find if there was any code path where the tree were forced to disk and the array were not. Looking in the string pool, it turns out that the tree is only forced to disk in one place, and the array is never forced to disk! So this must be the source of the problem.

Write behind at the OS level is generally a safe operation, even when a process is killed. However, it is possible to call write() and have things die before the data makes it to disk. (The libc libraries can do write-behind, the OS could die in some way, power gets pulled, etc). So the lack of synchronization is unlikely, but possible. This is why we've never seen it before now.

The solution is simply to ensure that the IntFile is completely written, before any data relying on that file is consistent enough to be committed. This means we just need the single line before updating the metaroot file:

 gNodeToDataFile.force();

Tests

I believe the bug could be reproduced by inserting a large number of unique literals into the store (sufficient to overflow the caches and force the JVM to buffer IO); followed by a commit(); and then kill -9'ing Mulgara immediately the commit returns.

Andrae's suggestion here is an attempt to fill the write-behind buffers, committing the data in an inconsistent state (since there is necessary data in the write-behind buffer), and then killing the write operation before these buffers can reach the disk.

Since we're trying to prevent the IO operations from operating correctly at the libc/OS level, it's not a problem that is suitable for running in JUnit!

So we're confident we've found the problem, but consistently reproducing it is not
trivial. This makes it similarly difficult to properly test that it's fixed.

I'm the one who understood the string pool structure enough to look for this and find it, but I wouldn't have even been looking in the right place had Andrae not taken me there. This story got played out in a similar way again the following day.

Transaction Exceptions

The String Pool bug was a vital one to find and fix, but it was extremely rare, and really hadn't affected us before this first bug report. It is a testament to how rare the bug is that this was our first report of it in the nearly 6 years that it has existed! However, I still had my transaction bug to find, and I was getting this one all the time.

I had managed to create a test case that was guaranteed to fail for me. My code performed a simple query (a duplicate of one that usually failed in our tests), and then iterated through the Answer, printing the results. However, before iterating, I did exactly what ItqlInterpreterBean does, and checked isUnconstrained() first (in which case the return value should be true).

This almost always failed, but I soon discovered that if I did the query (successfully) in the iTQL shell, then it would sometimes let my test code run correctly. My first approach was to see the difference between my code and the iTQL shell, and I finally realized that the shell would always call beforeFirst() on an Answer before check isUnconstrained(). Doing this in my sample code also fixed the problem. But why?

The exception I was getting was always a MulgaraTransactionException. The problem was happening when the transaction manager detected that an operation was being performed by a different thread to the one that had just registered itself for performing the operation. But I didn't know why this was happening.

While discussing what was happening, I started to gain an appreciation for what was happening inside the transaction manager. Andrae and I (mostly Andrae) even managed to spot some minor problems, which we could clean up. If nothing else, it was helping understand this new part of the system.

Transactions are the area Andrae just spent a couple of months working on, so I asked him to look at it. This was when I discovered that Andrae wasn't seeing these problems at all! I'd already established that a thread race was going on, and it seemed that my Core Duo (unfortunately, it's a 32 bit Core 1, and not the 64 bit Core 2) was demonstrating sufficient difference to a single cored machine to demonstrate the bug. So I gave Andrae an account on my machine, and went to bed.

RMI Threads

The next morning Andrae had some news for me. The transaction was being thrown correctly. For some reason an AnswerPage object was accessing an Answer using a different thread to the one that was asking for isUnconstrained() on the same Answer.

I was confused, as I thought that these two read-only operations would be perfectly safe operating in separate threads. Andrae explained that the semantics of an RMI connection like this required that only one thread be accessing the object at a time. Once he told me this, I immediately understood why, but it had never occurred to me before then.

The purpose of an Answer page is to package a page of Answer data, compress it, and send it over RMI to the client, all completely transparently to the client. This saves the client from making an expensive RMI call every time it needs the next row of an Answer. This is only ever performed on large result sets. The problem was that this would result in a pause for the client every time it ran out of the current page, and it needed to wait for the next one. The solution was to get the next AnswerPage in the background. In other words, they were supposed to operate in a separate thread. I have a blog entry on when I wrote this, back in 2004.

In general operation, using an Answer never resulted in two threads trying to access the server at once. The initial call to beforeFirst() would set the paging thread off, and pretty much all other calls would access local data. The only exceptions (like getRowCount()) were never going to be called while in the process of iterating over the Answer. So while I had not been aware of this issue with multi-threading over RMI when I wrote the code, the operation of the class would not have caused a problem anyway.

This all changed a few months after Answer paging was written, when isUnconstrained() was introduced. This indicates a "match" or true value for a query, even when there are no variable values to be returned. So before iterating over a result set, a client should always check for the value of isUnconstrained(). Unfortunately, the first thing a large Answer does after construction is to build start the paging thread. If isUnconstrained() is called immediately after construction of the Answer, then this will conflict on the server.

There are a few things to note here. A small Answer set will never be paged, so this bug will not manifest for Answers of less than 100 lines (or whatever mulgara.rmi.marshallsizelimit is set to by the user). Also, the form of a query will indicate if isUnconstrained() needs to be called, and only short, non-paged Answers will need this method called. Usually, the only method that will ever be called while paging Answers in the background is the next() method. However, ever since isUnconstrained() was introduced, generic code for handling and printing Answers, such as what is found in ItqlInterpreterBean, will always need to call isUnconstrained() no matter the size of the answer set. In fact, this must be the cause of the "Concurrent access exception" errors that have been reported, and I never understood.

Andrae's new transaction code was written specifically to prevent inappropriate access like this. So by throwing this exception it is doing its job perfectly. It's a godo thing he wrote it, or else this bug would have been around for a lot longer!

Once Andrae explained to me that we now had a situation where two threads could try to speak to the server at once, I realized I had to prevent both threads from operating on the server at the same time. The background thread is only ever started synchronously, in response to a call to the constructor, beforeFirst() or next(), and it ends asynchronously. On the other hand, the other methods which use RMI are all started and finished synchronously with respect to the rest of the client system. The way to handle this then is for any potentially conflicting methods to wait until a page returns.

Fortunately, the mechanism for this page return is already in place. The method is called waitForPrefetchThread(). This is the ideal method to use here, since it manages timeouts, throwing an exception if the server takes too long. All we had to do was put this method into the start of every method which makes an RMI call. It only took a few minutes to add the code, and then for the first time in a long time, every test passed!

Like the first one, this bug has been around for a while. It would also have taken much longer to be found if it were just Andrae or just myself working on it. It's a good thing we're both on it at the moment. I'll have to try to make more time available when we can both be online at once.

I hope Andrae is feeling good about these bug fixes, because I sure am!

Dreaming in Code

Time has been too short for me to comment on a couple of articles I've saw last week, so I'll just write something brief.

The first story was Software is Hard, which is an interview with Scott Rosenberg, the author off Dreaming in Code. Some of this story seems so familiar, and yet some of it seems unaware of modern software production techniques. Not that I can blame anyone for this. No technique works in all situations, and few are taught in schools or universities around the world. The most effective become a "fad" for a while, as those whose projects are most suited to them discover these techniques, but the resulting hype sets unrealistic expectations for people with less compatible project requirements.

Of course, the techniques I'm referring to are the various types of Agile programming, such as XP (the one that suffered the most from hype), Scrumm, and my own company's COSM. It is not a part of my duties to work directly with COSM, but I've still spent some time with it, and I agree that it is impressive, for the project planning as much as for the techniques of integrating business component with code components. But Agile is not the only useful technique out there.

Having defended these techniques, I will also say that they are not a panacea. Most people who use them don't really use them. They pick up on some ideas, but for reasons of practicality of preference, they decline to implement the entire paradigm. Another problem is that programmers are often at fault. It's one thing to have a great plan, but it is completely different to follow it. The type of plan you have is also going to suit different programmers differently. Highly skilled and creative programmers may be better with agile techniques, while those who pass a postgraduate course in programming will often be better suited to more structured environments like the waterfall model. (Note: I've never heard of, let alone seen, the waterfall model actually working).

It is this last part about asking talented (or any) coders to conform to management techniques that aligns most with what Scott has to say on the topic. One point of note is that he points out how good programmers enjoy re-inventing the wheel as it may often be faster than learning the intricacies of how "someone else" did it. The problem with this being that the resulting code is not tested as well, and has not been iteratively improved by running in the real world.

While this comment is true, I think Scott is looking at the problem from a traditional "commercial" viewpoint. Many programmers today, especially those in agile environments, will choose to use an open source project which implements some important functionality. The "challenge" that programmers enjoy is then sated by the integration of the many tools and libraries typical of most projects. Have a look at the library directory in Mulgara for a common example. There are 75 separate Jar files in there, all of which are from external projects.

In summary, he's sort of right, but he's also missed the ability of agile programming to work in some places. He has also seemed to have missed open source software, both as a project paradigm, and as a resource that modern programmers are absolutely ready to use.

By the way, I liked the title of the book. In my early days of programming I had several dreams in C: not about C, they were actually in C. The plot was a set of actions which was represented by functions, with people, places and events being structs. I've heard the experience is common.

A Stratified Profession

A different tone was set by Prof. Neil McBride in his article The Death of Computing. He sets a very cynical tone criticizing those still adhering to computationally pure programming techniques, and advocating the pragmatic approach. In particular, Neil talks about an inter-disciplinary approach for computers.

I like the idea of the interdisciplinary approach. After all, computers were always tools which we use to do jobs. They don't exist for their own benefit (though this has almost changed now with the advent of the internet). When I was younger, I noticed that all the successful approaches to computing relied on mixing skills with computers with expertise in engineering, finances, medicine, and so on. This made sense to me then, and it makes more sense now. This is particularly evident in the field of computational biology, where unbelievably complex systems (like genomes) are finally starting to be managed.

I also agree that in the past universities considered the computational purity above all else, and that rigidly sticking to this path is ignoring the pragmatism that the commercial world today wants. However, there seemed to be no acknowledgment of the continued need for the purists as well.

The idea seems to be that where once there were purists, today we need only pragmatists. I disagree with this. I think we need the purists as much as we ever did, but now there are also roles for the pragmatists. Whereas the profession was once restricted to the academic mindset, today we have a stratification, with different people needed at all levels.

We really do need people who don't understand a lot of the underlying system but who are prepared to be the resources needed for large financial institutions to build their enterprise systems. We need the talented developers who can take an idea, and in a few months turn it into a prototype that can set a new standard on the internet. We also need the theoreticians who analyze logic and modeling systems for completeness, or create new mathematical techniques for representing and transforming data.

I agree with the need to take a pragmatic approach. However, it can be taken too far, as is evident in many learning institutions today. Favoring pragmatism over everything else is throwing the baby out with the bathwater.

Interfaces

Interface design appears to fall into two categories.

The first category is where a set of functionality is to be provided, or is available in some way, and the interfaces are then built to provide access to all of this functionality. These designs are typically obtuse, and force a developer to jump through obscure hoops for their own internal gratification. 90% of interfaces fall into this category.

The second category is where the designer thinks about the task to be performed, and then thinks about how the code they would want to write in order to accomplish this task. Subsequent implementation may force some extra requirements into the design, but it is almost always possible to write implementations that largely fit the initial design.

Of course, the first category is built from the bottom up, and the second is top down. Sometimes it is necessary to use the bottom up approach, particularly when providing access to a pre-existing system, but the results are almost never pretty. Unfortunately, given the difficulty of many interfaces available today bottom up design seems to be the norm for designing interfaces. I want to name names here, but with the exception of Microsoft (MFC, or COM+ anyone?) it hardly seems fair to many of those hard working developers out there. (Actually, MFC doesn't seem to be a bottom up design. It's just full of weird inconsistencies where 6 similar-but-slightly different tasks rely on 6 completely unrelated mechanisms).

As an aside, when I say "interface", I'm not referring to Java interface definitions. I'm referring to the more general concept. These can be defined as Java interfaces, C++ headers, IDL files, XML descriptions, IUnknown querying, and more.

RDFS and OWL

Many interfaces I've seen for interacting with RDFS and OWL have had bottom up interfaces, often because they are trying to provide all of the functionality available in these languages. However, the result is usually very messy, and difficult to work with. For many of these interfaces, you really need to know OWL in order to use the interface.

However, the task that most developers what to achieve is often much simpler than anything that would require a complete knowledge of OWL. Typically, a developer will want to define two things: A model, and instance data.

• The model will generally involve a taxonomy of classes, each with their own specific fields. It will describe properties on those fields, such as data types, lists, which ones are key fields, which ones are optional, and so on. It will also describe relationships between the classes, and possibly restrictions on those relationships.
• The instance data will simply be a set of objects which each have a type defined in the model.

To be sure, all OWL interfaces out there allow all of this, but I personally haven't found them easy to use.

It should also be noted that OWL isn't the only way to do this. UML has done all of this for a long time now. This should be no surprise, as almost all features from each language (OWL and UML) can be mapped into a representation in the other. The exceptions are rarely employed and can be worked around (one of these exceptions is n-m associations in UML). However, UML is typically used statically at design time, and not dynamically at runtime. This makes sense, since UML is a closed world model, and a runtime system would need to allow temporarily incomplete systems while instance data was being built. OWL has a natural advantage in this regard.

RDFS/OWL Interfaces

When I needed a modeling interface, I made a conscious decision to avoid all of the OWL constructs, and only pick what I needed. I reasoned that the underlying language already would support any new required constructs, and trust that it would be possible to make sensible additions to the interface if any new requirements came along. My justification here is in my experience with interface changes usually being trivial, but modifying an underlying construct is often difficult or impossible.

Once I made that choice, my next step was to work out just what I wanted to do. The list was short, being comprised of the class definition, and object instantiation described above.

So what is the easiest way to describe each of these things? To me, a class definition is the name of the class, along with any inheritances it may have. It also contains a collection of fields. So a class definition should be a constructor which accepts a name, a list of other class definitions (or their names if I wanted to get into referencing classes before their definitions), and a list of fields. Fields would also require a name, a datatype (object or simple type), and some flags to indicate if they represented required data, a key field, and if they represented a list.

So was this approach useful? Well other than being verbose (having to describe all the fields, and then construct the class definition), it seems easy to use, and has been quite successful in the code we've used it in.

A more interesting question has been object instantiation.

I decided to take a leaf out of Perl here, where objects are just a hashmap, keyed on field name. This works quite well, and described a cheap way for me to get objects up and running. Wrapping the hashmap in a class that is given a copy of the class definition allows the data to be checked for consistency and completeness, and in some cases inferencing can be performed.

My only regret with this approach has been that it is verbose in a similar way to defining classes. The hashmap has to be created and fully populated, with each field taking its own verbose call for insertion. While easy, it isn't the way I would like to create these objects. Using the objects is similarly verbose, with all access going through get and put methods.

Thinking about it, the most obvious thing that I want to do here, is to simply create the object with an inbuilt language constructor. In the case of Java, this means a call to new, with appropriate parameters. This is what UML would have provided, but UML would have been compiled into Java source code before compilation. What I'm looking for here is dynamic creation of the class.

Bytecode Libraries

This is where my interest in bytecode libraries like ASM and BCEL comes in. Using these libraries it is possible to turn a class definition into a Java class, that can be instantiated with a custom class loader.

Make the custom class loader the current class loader, and you could theoretically use the new keyword. However, you'd have to cheat by doing a bait-and-switch, where you let the compiler build against one instance of a class, but have the class loader provide your class instead. OK, so this is an serviceable hack, but it's fun to know it's possible. Accessing fields isn't so easy though, and reflection is the only effective way.

A bigger problem is evolving class definitions over time. I've dynamically built classes in the past, but never tried to update a class after it has already been loaded once. I suppose the simplest way would be for each modification to get a new version ID that becomes a hidden part of the name, but that could lead to problems.

A better language to do this in is Ruby. Ruby already lets you define classes at runtime. More importantly, it lets you update them at runtime as well. I'm still a Ruby beginner, and I know nothing about the VM, so most of my ideas are just that, but it seems like a good idea.

I haven't had the chance to work on any of this modeling code for some months now, but I'm hoping I'll get the chance again soon. Depending on what seems most "natural" at the time, I may get to do some interesting things yet.

I should point out that most of my API is based on RDFS, with just a little OWL (InverseFunctionalProperty, Transitive, cardinality). While this sounds very restrictive, these few constructs provide a great deal of functionality. I'm looking forward to applying a few more.

Vista DRM

Windows Vista puts a lot of work into preventing what it considers to be "unauthorized" access to copyrighted material. In an attempt to plug every leak (an impossible task) the DRM system pervades every aspect of the OS, from the kernel upwards.

One disturbing aspect is the constant scanning of the system to determine if there are any fluctuations in voltage, unexpected register content, etc. Over time this totals to significant energy consumption. Also consider that the CPU requirements are significantly higher than would otherwise be expected, meaning that power consumption gets even higher.

We often don't pay attention to how much power extra CPU cycles burn in a PC, but it becomes painfully obvious when traveling with a notebook computer. I once had a PC which made it clear whenever I scrolled text in a web browser, as the fan in the power supply would go up in pitch with the extra load from the CPU. So the power difference of CPU use can be significant, despite it being hidden in amongst the hair dryer and air conditioning in your electricity bill.

If 90% of the new computers in the world (Microsoft's approximate market share) are going to be running Vista, then what will be the extra power consumption? This is a worldwide expansion in energy consumption for the sake of the MPAA.

Time Bugs

A short while ago I received a bug report for Mulgara, where certain Date/Time stamps were being randomly changed. I dreaded to think what this could be, and avoided it in the hope that the reporter (DavidM - but not the DavidM who wrote the storage layer!) or someone actively working in the storage layer (like Andrae) would find the problem.

Another report yesterday made me realize that DavidM didn't know where in the system the problem was to be found. Rather than simply tell him to look at SPObject and SPDateTimeImpl, I decided to have a look myself. After all, I know this area reasonably well.

The latest bug report claims that whenever the following timestamp is entered:
  April 26, 1981, 02:56:00
Then the system always returns:
  April 26, 1981, 03:56:00
(one hour later)

First, I ran the test queries and confirmed that the problem occurs for me too, and that it is definitely the string pool causing the problem. To help me narrow things down more quickly, I copied out some of the relevant code from the string pool so I could play with SPDateTimeImpl in an isolated environment.

I quickly realized that the problem was occurring when a third-party library was parsing XSD dates. So I reported this to the developers list, and stopped looking. There were some alternative library suggestions, and Brian said he would fix it.

Third Party F/OSS

It was still bothering me that this library was failing for us. Given that it was open source software, I decided that I could at least report the problem to the developers. I don't know about taking the time to debug the code, but at least I could give them a heads-up.

(I won't mention the name of the library, because I don't want anyone to think there is anything wrong with their library. Read on.)

So I wrote an example piece of code that parses one of these bad date/times, and sent it to the developers of this library.

A couple of hours later a developer wrote back to tell me that the library works correctly for him, and that the problem may be related to timezone issues. I'm in CST and he is in BST. He gave me a test case, and asked for some details of my system.

So I ran the test, and discovered 2 things. First, the time was still being printed incorrectly, though it worked for him. Second, the tests that he wrote all passed.

Initially I thought that the tests must have been written poorly, but on inspection I discovered that they were perfectly correct. In this case, he was comparing the results of their parsed date/time with a Calendar object from the Sun JDK. Of course, since the printed data was incorrect, I expected it to compare incorrectly to the Calendar object from the Sun JDK. But this wasn't happening.

The next step was to work out why this was happening, so I asked the third-party library to print its internal long value, and compare it to the internal long value from the Calendar. But the Calendar was also giving the wrong value. That's when I realized something was screwy with the JDK, and not the third-party library.

Timeslip

A quick test class shows the problem:

import java.util.Calendar;
public class TimeTest {
  public static void main(String[] args) {
    Calendar cal = Calendar.getInstance();
    cal.clear();
    cal.set(1981, Calendar.APRIL, 26, 2, 56);
    System.out.println("Time @2:56 in millis: " + cal.getTimeInMillis());
    cal.clear();
    cal.set(1981, Calendar.APRIL, 26, 3, 56);
    System.out.println("Time @3:56 in millis: " + cal.getTimeInMillis());
  }
}

If you live in Australia or Great Briton, then this code will work perfectly. For instance, running this is Australia will give you:

Time @2:56 in millis: 357065760000
Time @3:56 in millis: 357069360000

Note that there is a time difference between 2:56 and 3:56 of 3600000 milliseconds.

However, if you happen to live in the Central American timezone, then you will get this:

Time @2:56 in millis: 357123360000
Time @3:56 in millis: 357123360000

Note that these numbers are identical! They both represent 3:56am on that day.

I tried this with Java 1.4, 1.5 and 1.6 on my Mac. I also tried with with Java 1.5 on x86/Linux and Windows. All of these configurations return identical results.

Could Sun have created a problem here? Why does it only affect timezones in the USA?

At this point it was getting late, and I was startled at what I was seeing. Andrae was online, so I showed him. I was too tired to look in the source for java.util.Calendar and java.util.GregorianCalendar, so he offered to look for me. But rather than letting me go to bed, he insisted I should blog about it so that it was written up somewhere.

Fortunately, it takes a little while for me to write a blog entry. This allowed Andrae time to discover what was happening. It comes down to the following:

The Uniform Time Act of 1966 (15 U.S. Code Section 260a) [see law], signed into Public Law 89-387 on April 12, 1966, by President Lyndon Johnson, created Daylight Saving Time to begin on the last Sunday of April and to end on the last Sunday of October. Any State that wanted to be exempt from Daylight Saving Time could do so by passing a state law.

According to comments in java.util.GregorianCalendar, the hour sequence on that night is:

  12 Std -> 1 Std -> 3 Dst -> 4 Dst

This means that there was no such time as 02:56 on that morning. So the Mulgara date/time bug is not a bug at all, but required behavior.

Disambiguation

The Mulgara behavior may be correct from one perspective, but it can still be troublesome. A time like this can be supplied from a non-US source, but it cannot be entered into a US system. This demonstrates that Mulgara date/times do not support timezones, even though they are described in the XSD specification that they implement.

I'm thinking that the default behavior in Mulgara should be to assume the local timezone (as it does now), but to allow for explicit timezones as well. That way any ambiguity can be removed.

Date/times on the input should allow the timezone to be included, as per the spec. I was disappointed to learn that we don't support that at the moment, but it should be easy enough to add the option to the parser.

That leaves the issue of the output. At the moment, it will be converted to the client's local timezone though it will be printed without timezone information. I'd rather not change the default behavior, so I think we should introduce an option of printing the timezone. Strictly speaking, the timezone used won't matter, as the times will be converted according the timezone being used. However, it would still be nice to specify the exact zone to be used. The time is stored relative to UTC, and the conversion to the time in a specific locality is only really relevant when it needs to be presented to a person. This means that we only need to worry about it at the client end. The infrastructure doesn't exist to store a timezone at the server, so it is only really feasible to make the conversion at the client end anyway.

I expect to put in a system property to control the output format in a few days. I have a lot of travel ahead of me tomorrow, so perhaps I'll get the time then.

Object Interfaces

Last year I wrote some code for work for managing objects in Mulgara. It started out as a quick hack, but quickly extended into something properly structured and significant. Unfortunately, most of my hours at work seem to be very inefficient, but I spent many long evenings on it, and got something quite useful going in just 2 weeks.

The idea was to define objects using standard RDFS, and to store instances of those objects all in the same model. This is similar to an object database, or Castor, or even Hibernate, but the object definitions are more malleable, and the instances need not be complete, and can even have fields filled with inferencing.

I thought the result was reasonably compelling, and it enabled someone else to build a nice little Rails application that we used a few times in a demo. Unfortunately, since then we've gone in another direction, essentially orphaning the code.

I'd love to take this code and run with it, but I did write it for work. Even though the majority of the development time was after hours, and the idea was my own, I still spent some work time on it, and it was definitely for a work project. But that's OK. Now I get to implement a Second System. I'll just have to be careful not to overdo it.

Interface Options

One of the biggest problems with objects and object definitions in the previous system was the manual detail needed to build simple things. Every field had to be defined up front, including the name and datatype (including lists). There are also optional attributes such as the field being a key, required, and even transitive. These were encoded using owl:InverseFunctionalProperty, owl:minCardinality and owl:TransitiveProperty, which left the door open to start doing some more interesting things with OWL.

Defining all these fields made for a powerful system, but hardly a friendly one. I'd like to keep an interface like this, but also allow for more natural creation of objects.

The original style of interface was inspired by Perl. In this interface object definitions use a simple map, where each field name is mapped to it's type data (this includes the optional modifiers). I've also added in a couple of methods for finding fields via the properties. The object instances are similar, in that the field names map to the data. It's easy, and it works well, but it involves a lot of messy calls to Map.get() and Map.put().

The first alternative that comes to mind is to build objects by example. By this, I mean to create a Java class definition (sans methods, and with annotations for some more interesting features, like transitivity), and to construct the RDF via reflection. With a system like this, it would be easy to pass any java.lang.Class to create a new definition, or just pass an object and have the object and definition stored at once.

Reading objects back out of the store would take only a little more work. First of all, the name of the object definition can be tested in the class loader. If it exists, then create the object via reflection, and populate it. Otherwise, use ASM (or BCEL, or whatever appeals most to me at the time) to create a new class definition, and hand it off to the class loader to build in the same way as above. I'm still figuring out the bytecode for annotations, but ASM seems to handle them just fine.

(If I wanted to get really fancy, I could even store the methods for a class by storing the AST in RDF. This has been something I've wanted to do for a while, but it really belongs in another project, and including it at this stage really sounds like an example of the second system effect.)

The main problem with this system is that it requires that objects to be stored are already statically defined (you don't want your users to use a bytecode manipulator to dynamically build their classes). That makes the system similar to Hibernate, when it should be much more dynamic.

A simpler alternative might be to allow object definitions with a simple syntax, which I parse as a string. That kind of appeals, since it makes the API easy for the developer, while passing the hard work into the engine, where it belongs.

For the time being, it may be better to stick to the map-style implementation, and add features only once I have it all going again in an open source way.

Pitfalls

Implementing this the first time around showed up some of the difficulties in actually building something like this.

Atomicity

One important problem was a difficulty in querying all the data needed to construct objects in an atomic way. I had hoped that subqueries could solve this, but I didn't find a way through it. If it isn't atomic, then a structure could be inconsistent if someone were modifying the data at the same time.

So far my code has all been "client side", but the requirement of atomicity has me wondering if I need to move to a server side API. I should talk with Andrae about transactions.

Updates

There is also the question of updating the data. This is an important question, while at the same time it is a non-issue for RDF.

RDF asserts simple statements of subject-predicate-object. A statement either exists, or it doesn't. If I have a statement like:
  [ S O P1 ]
and I want to change the predicate so that the statement becomes:
  [ S O P2 ]
then I have not changed this statement at all! Instead I have removed the first statement, and inserted a new one. So RDF only handle assertions and denials, nothing else. Keeps everything simple.

However, any structures built on RDF (such as RDFS) do require the ability to modify them. I suppose that it is possible to naïvley remove the whole structure, and insert a new one, but this is both inefficient, and possibly disastrous for any links to that object. However, keeping track of object deltas is not very easy. I also have concerns (that I haven't addressed yet) of how to ensure any changes are compatible with related structures.

Open World

Another problem is that the real world wants object structures to be in a "closed world" definition. This isn't the time to justify this assertion, but there are a lot of practical reasons for it. To date I've taken a couple of liberties with RDFS, where I've required that fields in an instance must have type definitions in the object definition, but this is not RDF. The closed world is certainly more practical for computer applications, but I'm thinking I should explore an open world interface, while still keeping the API practical.

Datatype Properties

I also ran into an unusual issue with strings.

While I could have used the org.mulgara.query.Query interface (like I know Andrae does) I have chosen to use iTQL instead. There were several reasons, but the most compelling at the time was the need to create the code quickly and to debug easily.

However, I have to say that I hate working with strings. They're messy, prone to typos, and reek like magic numbers. That's a problem with iTQL, where all the queries are constructed from strings. To counteract this effect, I created a series of classes and enumerations which did all the iTQL building for me. The irony was that I ended up with a similar looking interface to using org.mulgara.query.Query directly. I like to think that I gained a few important features though. :-)

One part of the code passes all subjects, predicates and object to a method to get the appropriate iTQL representation. For URIs this is simply the URI wrapped in angle brackets. For blank nodes during insertion, this becomes a variable. And for literals, the data is converted to a string, placed between single quotes, and gets followed by the datatype. It even spots the difference between a URI and a URI Literal.

Reconstructing data from a literal is also straightforward, using an enumeration which maps the XSD datatypes back to the required Java constructor.

The problem is that all strings end up looking like this:
  'A string'^^<http://www.w3.org/2001/XMLSchema#string>

Now strictly speaking, this is right. Unfortunately no one ever writes RDF data that uses typed literals for strings. It appears that untyped literals are always used for strings, and typed literals for anything else. Just to be clear, Mulgara considers a typed string to be distinct from the same value in an untyped string, making strings incompatible between imported RDF and the data I construct.

For the moment I've left the string datatype where I found it, as I haven't tried to integrate data from other sources yet. However, I will probably need to make an exception for strings, where they have the datatype stripped off during a write, and missing datatypes inferred as strings during a read.

This problem did point out that these two types of strings are incompatible in Mulgara. Subsequently I've been wondering for a while whether we need to address this. Maybe I should go and look at some more RDF theory. I suspect that they are intended to be distinct, but I'm not sure I see a practical reason for it.

New API

I've been thinking for a while that Mulgara needs an API at a higher level than RDF. I'm not talking about RDFS or OWL inferencing (which is what I'm usually discussing) but a solid way to manipulate structures at this level of abstraction. I'm even prepared to use a different abstraction to RDFS and OWL, though it makes sense to pursue these ones.

Everything I wrote here is really about object definitions and instances (MOF levels 0 and 1), rather than addressing RDFS or OWL directly. In fact, only a couple of OWL constructs are used, so I can't say that it supports OWL in any meaningful way, only that it uses a subset of OWL to represent some structural information.

I want to pursue this style of API for the time being, since many real applications want to refer directly to objects and their definitions. I think this is a very practical approach, and can even be extended to encompass most (or maybe all) of OWL. But I'm also thinking that I should consider a real honest-to-goodness OWL API as well. Perhaps something that resembles the OWL abstract syntax. After all, there are a lot of people using OWL out there, who may want direct access to OWL structures, but don't want to manipulate RDF (which can be verbose for simple OWL constructs). But before going too far down this road, I should take a closer look at others attempts at an OWL API (such as Sofa, which was integrated into Kowari at one point).

Late

As usual, I've stayed up much too late to write this, leaving no time to proof read. Caveat emptor.

Numbers

Here I was, hoping to get more blogging done on my "working vacation", when I suddenly discover that I'm leaving Australia tomorrow! Oh well, it was nice to get some family time in. We have more planned for today.

I got an email this morning telling me that a link to some code I wrote has gone stale in an old blog entry. Oops.

The code isn't a big deal, but if anyone wants to generate a lot of RDF based on cardinal numbers, then I've put the file up on Mulgara.

See you in the USA.

New Look

I had to change some of the elements on this page (I was still linking to Kowari!), so while I was at it I decided to change the look a little bit.

The color change is mostly because someone anonymous complained about it. I couldn't tell if the complaint was spam, but I figured I was due for a change. The change in width is because the narrow columns have been bugging me for years. Unfortunately, I know next to no CSS, so I fiddled until I liked it a little better. Please let me know if I killed the layout in some horrible manner.

Mulgara Progress

Mulgara is going ahead nicely at the moment, thanks mostly to Andrae. He has implemented some major changes and bug fixes which were sorely needed. My only problem with any of this has been that my main support has been administrative, rather than technical.

Once upon a time I was writing TKS/Kowari/Mulgara code every day. It was very challenging and very satisfying. I also found that the whole process of blogging was useful to help keep my thoughts focussed, and keep other people in touch with what I was up to.

These days I'm involved in a lot of other people's code, and I can't blog about at all. It also keeps me away from coding, which is very frustrating, as I don't get that rush of implementing something cool, and seeing it all the way through to completion. That leaves me to do the interesting work at night, but after a long day at work, and time with family, I don't have the motivation to put in long hours of coding. Of course, two young boys mean that my weekends are packed as well.

Any remaining time does go to Mulgara, but the less frequently I work on it, the more I have to re-learn the context of where I was the "last time I was here". Just yesterday someone sent me an email, where they included a message they received 2 months ago. The email was coherent, and apparently written by someone who really knew the issues. I found myself agreeing with a lot of it and thinking, "this guy knows more than I do". Unfortunately (or fortunately?) I soon realized that the original author was myself.

It can be difficult to make a lot of progress when you have to bring yourself back up to speed every time you look at something.

I'm not sure what to do about this lack of time for non-work activities, but I'll have to resolve it soon. I'm supposed to start back at university shortly, and without any free time available I won't be writing a thesis! That's particularly frustrating, since I've been making all sorts of progress in processing OWL recently.

RLog

So what have I been doing in Mulgara/OWL?

Some time ago I realized that I needed to get an OWL processor out there, even if it were only partly complete. Hey, I can call it OWL-Lite if I want to! The specification explicitly says that there is no list of requirements to fulfill, so I'm covered. Fortunately, there are a lot of simple OWL inferences that I can perform already, courtesy of Raphael Volz. A number of others also come to mind, given some of the operations in iTQL, so this looked like a good first step.

The problem is that most of this work is easy to code using description logic (as Raphael has done in the paper I mentioned), but converting it into the RDF format I've created for the Krule engine is tedious and prone to bugs.

I found myself wishing that someone would write a programs that would parse the description logic, and convert it into Krule syntax. Even better, the dependencies could be automatically generated, based on the the format of the output of one rule, and the input to another. This would avoid many of the bugs I could potentially introduce through manual transposition, and make all future rules MUCH easier to encode.

So I'm motivated by laziness (who wants to manually encode all those OWL/RDFS rules and axioms?), impatience (why should I have to find all those dependencies, when computers are better at that kind of thing?), and hubris (hey, I could write a program to do it for me, and it would be cooler than every other logic interpreter out there because it works on my database).

So it looks like I want to re-write Prolog (yes, I've even looked at an interruption function in the algorithm to permit "cut" operations, à la Prolog). That takes hubris to a whole new level for me. But the funny thing is that it would be so easy. The hard work is in the rule engine, and I've already written that!

The language isn't really Prolog, or even the simpler logic languages, like Datalog. The main difference is in the allowable syntax. For a start, I want to allow domains on the predicates (so I can write owl:sameAs(x,y), for instance). I also want to use lower case letters for variables (instead of the upper case letters required by other logic processors). But in essence it's all the same.

So it's a type of logic, and it's based on RDF. Without anything better, I decided to call it RLog (which I pronounce Arr - Log). Who knows, if I finish it, it might even take off. (OK, OK, I don't have that much hubris).

It's funny that I'm looking to implement this. A couple of years ago I realized that Kowari could form the basis of a Prolog engine, though I knew that there was a lot of coding needed before we could do it. Now I'm on the verge of having written it, and I never really intended that.

Where Am I? How Did I Get Here? And What Am I Doing In This Handbasket?

I started all of this some time ago, but for the reasons I've mentioned above, I still have some way to go.

I started out by encoding my first set of OWL rules in RLog. The language didn't need much definition, just standard predicate logic, along with variables, domained predicates, comments, and so on. So then I converted all the RDFS rules, and added in the OWL rules that I want for the first cut. This showed up some interesting cases that I had to consider.

RLog tricks

The first thing I found was in rule 4b on RDFS. Strictly speaking, it should be:
  rdfs:Resource(u) :- a(x,u).
Meaning that for any triple <x a u> the element labeled "u" is a resource (or rdfs:Resource). That's what the RDF documents say anyway. However, this violates RDF, since u might be a literal. Literals are unable to have types like this, since it requires that they be the subject in a statements, which is illegal in RDF.

The way I've been getting around this in Krule so far has been to use a "type" model in Mulgara. The result removed all resources which were literals (via the "minus" operator). I decided that the best way to achieve this in RLog is with the following:
  rdfs:Resource(u) :- a(x,u), ~rdfs:Literal(u).
So now RLog has negation. Wonder how I'll make that work in the general case?

The next issue is a little trickier. Rule XI (Why Roman numerals? I never worked that out, except that this rule is weird) states that if a predicate URI starts with the RDF domain and an underscore, then it is a ContainerMembershipProperty.
  eg. http://www.w3.org/1999/02/22-rdf-syntax-ns#_1
This isn't quite right, as anything after the underscore is supposed to be a number, but it's not too bad. Sesame seems to get away with this rule.

Since Mulgara is using "magic" predicates for certain operations, it made sense to extend this into RLog:
  rdfs:ContainerMembershipProperty(i) :- i(x,y), mulgaraprefix(i,"&rdf;_").

Fortunately, none of the OWL rules needed anything fancy, though I suspect I may need to when I get deeper into subsumption.

Beaver

I think that I've already discussed the various compiler-compiler options I looked at. To recap, I chose Beaver as an LALR parser, and JFlex as the lexer.

JFlex is under the GPL, which would normally be bad (since Mulgara is OSL), but fortunately they state that any code generated by JFlex can be under any license you like. I don't plan on changing or extending JFlex, so that's fine (I'd be more than happy to contribute back any changes I made).

The incompatibility of the OSL and the GPL means that I can't distribute JFlex to generate the lexing code, but I have two other options. The first is that I just provide the lexing code, and the original .lex file. That would let anyone use the code just fine, since the lexer can just be taken "as is". A developer would only need to download JFlex for themselves if they needed to change the lexing rules.

The other option is to add an Ant task to download JFlex if needed. This seems to be the better, option, but I haven't done it yet.

As far as using Beaver/Flex is concerned, I've finished the parser, and can easily print out the Abstract Syntax Tree (AST). Now I need to write the code that walks over the tree, finds the dependencies, and converts the AST into Krule.

None of it seems to hard, but it's a matter of finding time. Meanwhile, the boys woke up a short time ago, so I'd better go and play "Daddy" for a while...

Patents

Today Slashdot has a story on LSI patenting multiply linked lists. The patent was applied for in 2002 and granted in April this year.

I'm glad to see lots of comments on Slashdot referring to prior art. A decent lawyer could avoid the question of doubly linked lists, so I was pleased to see more complex examples from the 80's and 90's.

I was particularly bothered by this patent due to the fact that I would have inadvertantly violated it several years ago. My blog describes an RDF DB design with takes advantage of multiple links for each node in a list, so that the lists can be traversed in completely different directions. Unfortunately the posts were made in May 2004, which was well after the submission date of the patent (2002). So my work doesn't qualify as prior art.

You'd think that my own work (among others) constitutes the breaking of the "non-obvious" requirement. Apparently not. There must be a whole swathe of the software developers community who may be classified as "brilliant geniuses" by the USPTO, given that we all come up with the same non-obvious idea.

When learning programming, we are all inculcated with standard techniques. We are taught to not reinvent the wheel. Design patterns, algorithms, you name it... the state of the art in programming is to take someone else's system and build on it. Make it something new by connecting old things in new ways, or adding into existing systems. We are NOT taught which techniques to avoid due to patent problems. We are not taught how to search for possible conflicts with existing patents. In fact, the whole point of modern programming is an anathema to what patents try to enforce. So it can be really frustrating to see patents on common ideas. It can be even more frustrating when someone decides to patent something that you've worked with. I guess I should be grateful that I needed a more scalable design than the one described in that blog post.

Mashups

I like seeing the tools we write being used in the real world. After all, what is the point otherwise? We are trying to create something useful, so it has to be applicable to use-cases that people really want. While my own specialty is Mulgara, this is just a tool for the semantic web. So I'm interested to see these use-cases, regardless of the underlying engine.

With this in mind, I enjoyed reading a post from Danny Ayers today. He describes using various data sources to solve a useful real-world query that he got from yet another source, to wit:

"Where can I buy firewood as a function of price and distance from where I am now?"

While I agree with Danny about the ability to put all of this together, I think he is a little optimistic about the effort to do so:

"... all the tech to answer the question on the Web is readily available as almost-commodity tools, not a lot of effort needed."

It would be nice to think that he is right, but I'm skeptical. Maybe I'm overestimating the effort. After all, I'm still a beginner at programming Ruby. :-)

My favorite line was last:

"Why would anyone put such data on the Web? Perhaps they might want to sell their wood."

BTW, of all the words in the US spelling system, the one that bothers me the most is "favorite". It just looks wrong somehow. Why this word bothers me more than "color", "optimize", or "bank check" is something I can't answer. :-)

Lament for Open Source Work

I miss those heady days of working on open source code 90-100% of the time. In those days I could talk about work as much as I wanted, with no ramifications. In fact, discussing my work on Kowari was a good thing.

I initially started blogging about my work simply so others in my team could find out what I was doing. If they didn't have time, then they didn't have to read it, but if they were interested then it was all there for them to read. I quickly found that organizing (there's that American spelling again) my thoughts sufficiently to write about them helped me to keep track of what I was doing, and to plan for up coming work.

Somewhat surprisingly (for me), it didn't take long before people I didn't know started to read my blog as well. This was an interesting experience, and led to some interesting conversations and contacts. Ultimately it helped me get my current job!

Unfortunately, my work now is almost exclusively commercial. That means I can't write about it in public. I've also found that I like blogging too much to write about it privately (even in the local Wiki at my company).

I can still write about Mulgara outside of working hours, but then I run into a new problem. Back in the day, I was able to work on Kowari (now Mulgara) during the day, and blog about it at night. These days I work on "other things" during the day, and at night I can either blog, or I can work on Mulgara. It's hard to find the time to do both. It's a little frustrating.

Actually, most of the technical things I've been writing about have been in the Mulgara Wiki, and not in this blog at all. So at least I've written something, but it's disappointing to think that I've lost most of my audience (small as it was). The emails and comments I received were often insightful, very useful, and quite gratifying.

With all that audience missing, who am I writing for today? Well, mostly myself... just like it was in the beginning. I suppose I'll also be read by those people who forgot I was in their RSS feeds (hello to both of you!). :-)

Recently I've noticed that I miss the process of writing. I guess I'll have a flurry of activity in this blog for a little while, until I get overwhelmed with other things again. Hopefully it will be fun while it lasts!

Functional Programming

Is functional programming the next big thing? A lot of the reading I've done lately would seem to suggest so, but that might just be the nature of what I've been reading, rather than a genuine shift in the IT community.

Of course, I've been hearing about functional programming for years. I've always skirted around it, since it was not taught in my electrical engineering course and I never pursued computer science academically until recently. (Maybe that's another reason I've been hearing about it more?)

My first exposure to this style of programming was when I learnt the C++ Standard Template Library (STL). Of course, it's no where near pure functional programming, but I was amazed at how elegant code could become with the STL. An HP example that I remember seeing demonstrated a simple program which read strings from stdin, sorted them, removed duplicates, and printed the results, all in 2 lines of code. However, if I wanted terse I could just code in Perl. The beauty of this code lay in its simplicity.

Over time I encountered this approach in many different forms, but it wasn't until I watched the lectures of Abelson and Sussman that I got a formal appreciation of it. Now I understand why programmers recommend learning Lisp, simply for the different way that it makes you think.

Recently I've started seeing many programmers whose blogs I follow commenting on functional programming. It has taken a while, given that the approach was first really pushed by Backus way back in 1978.

One of the big advantages of functional programming is the ability to provide a proof. There are mechanisms for proving the correctness of imperative programs, but these are largely impractical on real systems. Functional programs by contrast have the form of a mathematical expression, thereby making proofs easier to derive and verify.

I used to think of proofs as only being of interest to academics, but I've since changed my tune. Everyone in this industry is aware of how buggy software can be, and how often projects fail to meet deadlines due to errors. Unfortunately it is all too common that these problems (among other things) can lead to projects failing altogether. With this in mind, several companies have been successfully programming using tools for converting formal specifications in Z-notation into running code. The reported bug rate is significantly lower, along with extraordinarily high rates of success. I understand that many clients with critical applications (such as military and space deployments) are choosing to only accept code written in this way. It makes sense to me.

The more I learn about this, the more I appreciate Dijkstra point of view, particularly on teaching programming. And I'm not the only one lamenting his lack of influence (I apologise to those non-IEEE members who cannot read that link). I understand the point of view that he was Ivory Tower idealist, but with projects constantly failing in this industry, and our inability to find developers with a proper understanding of programming, then I've come to revise my point of view.

With this in mind, some months ago I started learning Haskell. This language was created for academic purposes, and is considered the only completely functional language. For that reason, it may sound impractical, though Quake Haskell, along with many other projects, provided me with enough encouragement that it really can be used in the real world.

I'm not very productive in Haskell yet (for instance, I can follow monads, but I don't really get them - though I'm still reading). But I've found that it has improved my understanding of certain programming approaches, and made me a much better developer in the languages I am good at.

In the process of learning Haskell, I started to learn more about another functional language called Erlang. This language was developed in the late 80's by Ericsson, partly in response to some of the things I've been talking about here. Ericsson also released a short film, if you're interested in learning more about it. Erlang has a number of similar features to Haskell, including pattern matching, which is phttp://beta.blogger.com/img/gl.link.gifrobably the single most important feature of these languages.

If they're similar, then why would I start learning Erlang when I still haven't mastered Haskell? Well, regardless of the success of Haskell in some of the above projects, there are still barriers to its practicality. The best comparison I've seen so far was by Joel Reymont, when he attempted to build a client application for a poker server. Regardless of his complaints on Haskell, he still finished by saying:
"That said, because it forever twisted my brain into a different shape and I think I’m overall a much better coder now."
This reflects my own experience so far, so I'm continuing to make my way through my Haskell books slowly. It's a shame that it has to be as slow as it is, but work, study and Mulgara leave me limited time. Maybe one day I will get competent enough at Haskell and Erlang that I can move on to OCaml.

It's amazing how all of these things interconnect. I'm also spending time on Description Logic and how to do this in RDF/OWL, so I can create a programming engine in Mulgara. While assertions are different to function calls, there is enough similarity that I wish I could do much of this work in Haskell rather than Java. At least Haskell has taught me many of the techniques I need to make this job easier, and much more likely to be correct.

Morphisms

This won't make sense to most people, but I'm just taking notes for myself so I don't forget...

I notice in the Wikipedia entry on Category Theory the following:

"Relations among morphisms (such as fg = h) are often depicted using commutative diagrams, with "points" (corners) representing objects and "arrows" representing morphisms. The influence of commutative diagrams has been such that "arrow" and morphism are now synonymous."

This reminds me of the (recently neglected) idea of compositional statements in OWL. I require some formalism to make composition a viable suggestion, and this may be a starting point.

The problem with this approach is that predicates can't really be considered to be morphisms, as it is possible to repeat them many times on a given subject. (Does this mean that the predicates can't be morhpisms, or just that they can't be monomorphisms?) Still, I wonder how many category theory ideas are portable into RDF? In a moment of meta-meta insanity, I'm left wondering if there is a morphism from category theory to RDF?

Nothing

I didn't want to embarrass myself in public, so I looked at the whole owl:Thing vs. owl:Nothing again. Something I'd forgotten is that owl:Nothing cannot be instantiated. So it's OK if owl:Nothing seems to be a contradiction (I think), since it is only the instances of a class which create problems, and you can't have an instance of owl:Nothing.

It's after midnight. I'd better get to bed before my head hurts any more.

OWL

I'm finally getting off my rear end and writing some code to do OWL in Mulgara. (I hear the gasps of disbelief from the peanut gallery).

So I needed to start with some OWL axioms. You know, owl:Class is an owl:Class, it's a rdfs:subClass of owl:Class, etc. So I went to a handy little file I have named owl.rdf. Now I distinctly recall that the file was not originally named owl.rdf but I wasn't sure why I'd renamed it. All the same, I've had it for some time, and it looks official, so I decided to work with it.

The easiest way to convert it into Krule axioms was to load this file into Mulgara, and then have an iTQL client build the RDF for me. I had a one line bug (why is it always one line?) which took me a while to track down to a typo in a constructor where I effectively said:

  parameter = this.parameter;

But finally my output was as expected.

At this stage I noticed something odd in the axioms. Out of curiosity I went back to the owl.rdf file and discovered this:

  <Class rdf:ID="Thing">
    <rdfs:label>Thing</rdfs:label>
    <unionOf rdf:parseType="Collection">
      <Class rdf:about="#Nothing"/>
      <Class>
        <complementOf rdf:resource="#Nothing"/>
      </Class>
    </unionOf>
  </Class>

  <Class rdf:ID="Nothing">
    <rdfs:label>Nothing</rdfs:label>
    <complementOf rdf:resource="#Thing"/>
  </Class>

So on one hand it says that owl:Thing is the union of owl:Nothing and everything, and on the other hand, owl:Thing is the complement of owl:Nothing. I can see a rational behind both points of view, but they can't both be true at one. owl:Thing either includes owl:Nothing or it doesn't. (Or am I missing something really big here?)

So where did this file come from? Unfortunately, I picked it up with wget. If I'd used Safari, then it would store the URL in metadata which I could view with mdls. Apple metadata might be a nice patch to work on for wget. Fortunately, when I went to the W3C to search for the file, I suddenly remembered where it came from.

RDF uses Uniform Resource Identifiers (URI) to identify resources. Note that these are Identifiers and not the more familiar Uniform Resource Locators (URL). URLs are a subset of URIs, but their purpose is for location rather than purely identification. A URI may look like a URL, but it may not be specifying the location of anything at all. This is often confusing for first-time users of RDF, who expect that the identifiers they see should be taking them somewhere useful.

Now just because RDF says that you don't need something at the address of a given URI, that doesn't mean you can't put something there. In fact, many people do, including the W3C. For this reason, one day I decided to put the URI for the OWL domain into wget and see if I got anything. The result was this RDF file called owl. Once I remembered that, I also remembered changing the name to the more useable owl.rdf.

So here is this file sitting at the W3C, hiding in plain sight. I find it amusing that it can have such a contradiction in it.

Am I Getting Old?

This story has been written elsewhere, but I have my own contributions to make to it. Hopefully the catharsis will help me sleep better. :-)

I've been helping to interview several programmers recently, and I've really been surprised at the results.

To be clear, I do not have a degree in Computer Science. My first degree was in Computer Engineering. That means that I spent many long hours debugging breadboard with a logic analyzer, and the code I was writing in my final year was usually for device drivers to communicate with the hardware I'd built. That isn't to say that I didn't have subjects in computer science - I did.

I did the basic first year CS course, which taught us about records, how to build linked lists, recursive functions, simple sorting algorithms (bubble sort!), and the other essentials. I did subjects on networking, operating systems, concurrency (anyone care to dine with philosophers?), modular programming, complexity theory, and databases. Funnily enough, in my first database course we were not given access to computers, and never learnt SQL. Instead, Terry Halpin taught us how to model data using a system called NIAM. It seemed very theoretical at the time, but it ended up being a vital foundation for my later work in OWL. I also had Computer Engineering subjects which taught me Assembler (in several flavours) and C, how to use them to talk to hardware and/or the operating system, how to model hardware in software, sockets programming, and so on.

I never covered more advanced data structures or algorithms, but then I never did a degree in CS, did I? My physics degree gave me the opportunity to do a couple of extra subjects in programming, but these were vocational, and hardly worth the effort. Instead, I had to gain an understanding of professional programming in my own time. I had a very good mentor to start with, but his main role was in teaching me how to teach myself. Consequently, I now have a large bookshelf full of books covering topics from MFC and GTK, through to Knuth, Type Theory, and Category Theory. There are still holes in my knowledge, but I've covered a lot, and I'm still progressing. In fact, learning after university has meant that I've learnt better, as I learnt out of genuine interest, and not because some lecturer said I needed to learn something in order to pass an exam. For this reason, I have learnt to have less respect for certified courses, and a greater appreciation for enthusiastic amateurs.

The same willingness to keep learning also applies to most of my friends and colleagues. This is important in our industry, both because the field is too large to know it all, and because the systems and protocols implementing the theory are constantly expanding. Fortunately, we don't need to know it all. The fundamental principles in computer science always hold, and form a solid foundation for all future learning. Once you have these down, then any new language or paradigm can be understood and applied quite rapidly.

So when we interview candidates, I look to make sure that they have a grasp of the fundamentals. Instead I keep discovering people with years of experience in J2EE, who are completely unaware of the underlying principles of computer science. It is almost universal that these people have solid vocational training, but very little ability to work outside of established paradigms.

Why do I consider these things important? Isn't it acceptable to simply work with EJBs, SOAP and JDBC? Why should I expect more?

There are several answers to these questions.

To start with, staying within these narrow APIs has left many of these people unaware of significant APIs in Java proper. Most developers we have met do not even know what file mapping is, yet alone the fact that it is included in the java.nio package. Concurrency is a subject with subtle complexities, yet these developers are often unaware of the attributes which make up a Thread in Java, including the stack that each thread owns. How can they hope to correctly use a ThreadLocal object, or know how to debug a deadlock?

Another problem with vocational training with a narrow focus is that almost all systems have a chance to interact with each other in some way. Not understanding the surrounding systems leads to an inability to solve some problems. I have yet to meet a candidate who understands what significance a 64 bit operating system has for a JVM, when compared to running on a 32 bit system. This is so important that Mulgara has a completely different configuration for file management when operating on 64 bit systems, with vastly different performance. How can programmers working on scalable "Enterprise" applications be effective at their jobs if they can't understand this difference? The level of ignorance is surprising, given the general interest in 64 bit chips and operating systems.

This extends down to simpler issues as well. As with many languages, some understanding of 2's complement binary arithmetic is required for working with all of the numeric types in Java. For instance, for every signed integer type in Java, the abs(MIN_VALUE) is always 1 greater than the MAX_VALUE. Even when shown this fact, the people I've spoken to don't understand the significance of the expression -MIN_VALUE. This could easily cause problems in code that said:

  if (-x > 0) {...}

We also find an amazing ignorance of complexity. How can a programmer write a scalable application if they believe that linear complexity is to be preferred over logarithmic? We even had one person think that polynomial was best!

The next issue is that Java will not be the dominant paradigm for the rest of our careers. Computing moves fast. Java may be around for some time yet (look at C), but something new is guaranteed to usurp it, and it will happen in the next decade (I feel uncomfortable making a statement with a guaranteed timeframe, but I have history on my side). For instance, many clients of mission critical systems are looking to developers using functional languages with the ability to mathematically prove the correctness of a system. I'm only mentioning it briefly, but the importance of functional languages in this respect cannot be underestimated. Proof trees make it possible to prove the correctness of an imperative program, but the results are messier than practical in a commercial environment.

Finally, and this is one of the most important principles, other languages teach programmers to think differently. This allows programmers to write important functionality in Java that would not be possible with standard J2EE practices. Mulgara needed a C programmer like David in order to have data structures on disk which are as efficient as the ones we have. Standard J2EE techniques would not store anything directly to disk, but would use a relational database. Even if a programmer had chosen to write directly to disk, standard serialization techniques would have been used. Instead, Mulgara uses densely packed data structures that serialize and deserialize quickly, and are structured in complex ways that are made cleanly opaque to the calling object oriented code... and it is all done in Java. David's understanding of how operating systems use write-behind algorithms, which hard drive operations are atomic, and how best to interact with the operating system's buffer cache were all vital in Mulgara's performance.

Google needed Lisp programmers to write MapReduce, which is one of the most important and fundamental tools in their system. It was Lisp programmers trying to get some semblance of Lambda Calculus into C++ who introduced the templates, and ultimately the STL. This then led to template classes and functions in Java, again highlighting the need to understand these other systems in order to better program in Java.

If we want to write important code that does anything beyond standard business logic for commercial applications, then we need people who understand computer science, and not people who have received vocational training in the popular language of the day. They need to understand the mathematics behind programming, the pros and cons of both functional and imperative languages, the features of underlying operating systems, along with many other things.

Finally, if they want to be really good, they need a desire to go out and learn some of this stuff for themselves, because no course can teach it all. It's just a shame that they don't seem to teach the basics any more. And it's the fact that I typed that last statement that makes me realise that I'm getting old. :-)

One at a Time

I'd love to be writing more here, but instead I'm putting my Mulgara ideas up on the Mulgara Wiki. Anyone interested should look under Development/Indexes.

I can only really manage the time for writing in one place at a time. Not to say that I'm abandoning this blog, but it is more appropriate to put Mulgara design details on the Wiki.

Mulgara v1.0.0

Mulgara v1.0.0 has been released!

All my spare time has gone into this recently, which should explain the dearth of blogs posts. Now that the first release is out, I should have more time to:

• Write some code.
• Write more blog entries.
• Get OWL working in Mulgara.

I hope that future releases will require less effort, since the project is off the ground, and we've established several procedures for this first release.

Thanks to the people who helped me get it out. In particular:

• Brian, who coded and debugged.
• David, who reviewed everything from legal files through to web pages, and without whom I'd find myself in a world of trouble.
• Thomas, who volunteered out of nowhere to design the web pages for us.

For anyone missing my technical musings on the structure of Mulgara, then have a look at the Mulgara Wiki. I've just started using this area, so others can contribute, and also because it allows me to structure some of the details.