Recently, Daniel, Ted, Andy and James all point to a post by Tom Lord over on the arch-users mailing list.

Tom's comments are made in the context of Red Hat's agreement to distribute Sun's JVM as part of their "Enterprise Linux" offering, a story that (although I regularly program in Java and I'm writing this post on Red Hat box) quite frankly I haven't been following at all. Much of what is interesting about Tom's comments may be a function of reading them outside of this context.

I find this a striking post, among other reasons, because it raises several distinct responses from me:

1. What are we building?

Tom suggests:

There has been a sort of tension in the commercial free operating system world:

(a) Are we building a free alternative to proprietary software?

or

(b) Are we building a commodity, $0-price OS component to lower the cost of proprietary applications?

For my part, this is a false dichotomy. In my open source efforts I'm not trying to do either of these, but rather to simply build something useful. Whether this something is an alternative or adjunct to proprietary software is incidental at best. For that matter, whether this something is truly innovative or just a more useful variation of a component that already exists isn't terribly significant either (although the utility of copying something that's already readily available is limited of course).

I wonder if this a symptomatic of differing perspectives between the BSD-style and GPL-style camps of open source development.

2. How do we build it?

Tom writes:

If the goal is (a), then we need an architect. We need to come up with an inexpensive-to-develop architecture that, nevertheless, contains viable solutions for the needs of our markets.

If the goal is (b), then we need an anti-architect. We need to come up with impossibly-expensive-to-fully-develop clone projects of proprietary software to draw off the energy of volunteer contributors who might otherwise undermine the value of the proprietary applications we expect to drive revenues for our distro.

Here option B is obviously a straw-man, so of course I'll follow option A. But while I agree we need "an inexpensive-to-develop architecture", and the word "architect" appears in my job title, I'll suggest a evolutionary approach is the best way to get there. Inexpensive-to-develop systems of any interesting size, let alone federations of such systems, are rarely "architected" in a traditional sense. What we need is an environment where diverse ideas are allowed to compete, cooperate and breed.

3. How hard is a Java implementation, really?

Running throughout Tom's post is the notion that a reasonably complete Java environment is simply too complicated to implement in an open source fashion:

For example, under (a), we would probably have to admit that trying to clone all the Java libraries _and_ build a competitive Java implementation is too expensive a course of action. While we might be perfectly happy to ship a low-end, incomplete implementation to help the low-end of the market, in the long run, we'd want to look for a more clever solution: something that can compete with Java and Java libraries on functionality, but that is cheaper to build in the first place (and cheaper and more effective to apply, of course).

[...]

[Y]ou can also make things expensive to develop by structuring them as an object oriented framework that you then spend zillions on filling out with subclasses, or by making really hard components (like finely tuned JIT compilers and garbage collectors) critical to implementations.

[...]

Some architectures, such as the Java environments and the view-tree/component-based GUI frameworks, are ideal for large proprietary software companies with large command-and-control armies of developers and QA practitioners. Those architectures are a terrible fit for the loose confederation of generally underresourced developers in the free and open source software world.

Putting aside questions of productivity and effectiveness, and the "enterprise" libraries for the moment, how hard is the core Java environment to implement, really? More difficult than a Lisp implementation, for example, but I suspect it's not substantially more difficult to implement than, say, a C implementation, and probably on par with something like Ruby.

4. Where are the alternative Java implementations then?

Well, there are several actually, although relatively few complete or robust ones. Why? Perhaps one compelling reason is that proprietary yet free (as in beer) Java runtime environments are readily available for most platforms.

Besides, who really wants another Java platform anyway...

5. "Yep, time to stop copying"

Like Daniel and Ted, I find the general call for innovation dead on:

For a long time, the right strategy for GNU was to build a basic unix replacement differentiated primarily by licensing. [...]

Well, that part's done and the strategy won.

[...]

If the goal is still "(a) build a free alternative to proprietary software", then a new strategy is called for: competition on software architecture, not just licensing.

Here Tom and I are in violent agreement. If I were building an open source compiler and/or language-platform, I'd certainly think twice about doing it on Sun's plantation--not because it's too hard; in part (as before) because the utility of copying something that's already readily available is limited; but mostly because I think you could construct more useful environments.

It's worth applying this, independently, to the "enterprise libraries" I set aside earlier. Are J2EE implementations like Apache Geronimo or JBoss building something "useful" or a "$0-price OS component to lower the cost of proprietary applications"? From my perspective, I've found some pieces of the J2EE suite to be quite useful, and others seem to fit Tom's "proprietary vendor" strategy.

6. Except when it isn't

It's interesting to observe how quickly the arch-users thread evolves from "we need a new architecture" to "we need a Lisp platform". (It's doubly interesting to note how often that seems to be the case.) And perhaps that really is what we need. But there's a big difference between "time to stop copying" and "time to stop copying Java".

(Actually, although I think one could do much better than to copy Java, you could also do much worse. It would be naive to think that Java's success is purely coincidental or purely the result of marketing muscle. They must be doing something right.)

More generally, it would be naive to think that what we need is innovation for innovation's sake, and I think deciding we need to resurrect a 40 year old platform is evidence of this fact.

7. What are we building, revisited.

Tom writes:

Nowadays, the proprietary competition is about databases, and productivity apps, and browsers, and middleware layers. The software we're competing against is not like unix: it isn't simple; it wasn't built by a small number of people; it's a moving target. It isn't a tractable project to clone this proprietary software under different licensing.

This point is puzzling. Certainly we don't mean to assert that it is impossible to successfully build open source databases, web browsers, or middleware servers, do we? Do we assert it is a bad idea to do so?

While I certainly think we should look for innovative ways to solve the sorts of problems these projects do, it would be a mistake to believe that the existing approaches don't offer something of value simply because they have strong proprietary implementations as well--just as it would have been a mistake for the GNU project to reject a pipe-and-filter architecture simply because a strong implementation was once controlled by Bell Labs. I don't think it is tractable to create a wholly new software paradigm--one that doesn't contain variations of n-tier, database and web technologies--out of thin air. We need new ideas, but we need old ones too.

[Via Jay Fienberg's iCite.net]

Don't ask yourself what the world needs. Ask yourself what makes you come alive, and go do that, because what the world needs is people who have come alive.

An anonymous quote cited by Condredge Dole on Ward's Wiki.

What fun! Dave's latest Kata is a little math problem, and it features everyone's second favorite example of recursion.

Think of binary numbers: sequences of 0's and 1's. How many n-digit binary numbers are there that don't have two adjacent 1 bits? For example, for three-digit numbers, five of the possible eight combinations meet the criteria: 000, 001, 010, 011, 100, 101, 110, 111. What is the number for sequences of length 4, 5, 10, n?

Flexing the "proofs" part of my brain for the first time in long while, I think I've got both the solution and a proof for this. I've developed this solution independently, so there are probably more elegant proofs available.

Spoiler Warning: If you'd like to work this Kata yourself, beware, spoilers follow. I'll leave some blank space first.

 ... 

spoilers follow

 ... 

Definitions and Notation

First, let's define some terms.

Let S_n be the set of binary sequences of length n. Note that |S_n| = 2ⁿ.

Let F_n be the set of sequences of binary sequences of length n that do not contain two consecutive 1 bits. The Kata asks us to determine |F_n|. I'll call that f(n).

By inspection, it's easy to work out the first few values of f(n). Note that when n=0, we can count the empty sequence.

To make the proof a little bit easier, I'll introduce some additional notation.

Let concat(a,b) be a function that maps a pair of sequences to a new sequence by prefixing the first to the second. For example, concat(1,0) = 10 and concat(10,1101) = 101101.

Let CONCAT(a,B) be function that maps a sequence and a set of sequences to a new set of sequences obtained by prefixing the sequence a to each sequence in the set B. In other words, CONCAT(s,T) := { concat(s,t) : t in T }.

The Theorem

If you're familiar with it, it is easy to recognize f(n) to be the Fibonacci Sequence, at least for small values of n. So here it is in theorem form: If f(n) is the number of binary sequences of length n that do not contain two consecutive 1 bits, then:

f(0) = 1
f(1) = 2
f(n) = f(n-1) + f(n-2) for all n > 1

The Proof

That f(0) = 1 and f(1) = 2 can be readily seen by inspection. We'll only need to demonstrate the part of the theorem that applies to n >= 2.

Note that the set S_n can be seen as the union of two disjoint sets derived from S_n-1, those that start with a 0 and those that start with a 1:

Sn = CONCAT(0,Sn-1) union CONCAT(1,Sn-1)

Similarly, CONCAT(1,S_n-1) can be seen as the union of two disjoint sets derived from S_n-2, those that start with 11 and those that start with 10:

CONCAT(1,Sn-1) = CONCAT(11,Sn-2) union CONCAT(10,Sn-2)

Hence S_n can be seen as the union of three disjoint sets:

Sn = CONCAT(0,Sn-1) union CONCAT(11,Sn-2) union CONCAT(10,Sn-2)

For convenience, let's name each of those three sets:

Let A = CONCAT(0,Sn-1) 
Let B = CONCAT(11,Sn-2)
Let C = CONCAT(10,Sn-2)
Sn = A union B union C

Since the sets A, B and C represent a proper partitioning of S_n, we can determine F_n by determining the sequences that meet the conditions in each of the sets independently.

How many sequences in A are in F_n? The answer must be f(n-1), since prefixing a 0 bit won't change whether or not a sequence contains two consecutive 1 bits.

How many sequences in B are in F_n? The answer must be 0, since our prefix alone already rules out all of those sequences.

How many sequences in C are in F_n? The answer must be f(n-2), since prefixing 10 won't change whether or not a sequence contains two consecutive 1 bits.

Hence:

Fn = CONCAT(0,Fn-1) union CONCAT(10,Fn-2)

and

f(n) = |Fn|
     = |CONCAT(0,Fn-1)| + |CONCAT(10,Fn-2)|
     = f(n-1) + f(n-2)

Q.E.D.

Comments

For some reason, I had initially thought I'd be clever and reverse the problem. Why count the number of sequences that don't meet some condition, but instead count those that do? This yields the sequence 0, 0, 1, 3, 8, 19, .... Other that starting with the Fibonacci-like 0, 0, it didn't seem recognizable at all to me. (More generally, this sequence is 2ⁿ - fibonacci(n).)

Via Wired, David Byrne on PowerPoint:

Having never used the program before, I found it limiting, inflexible, and biased, like most software. On top of that, PowerPoint makes hilariously bad-looking visuals. But that's a small price to pay for ease and utility. We live in a world where convenience beats quality every time. It was, for my purposes, perfect.

I began to see PowerPoint as a metaprogram, one that organizes and presents stuff created in other applications. Initially, I made presentations about presentations; they were almost completely without content. The content, I learned, was in the medium itself. I discovered that I could attach my photographs, short videos, scanned images, and music. What's more, the application can be made to run by itself -no one even needs to be at the podium. How fantastic!

Although I began by making fun of the medium, I soon realized I could actually create things that were beautiful. I could bend the program to my own whim and use it as an artistic agent. The pieces became like short films: Some were sweet, some were scary, and some were mysterioso. I discovered that even without text, I could make works that were "about" something, something beyond themselves, and that they could even have emotional resonance. What had I stumbled upon? Surely some techie or computer artist was already using this dumb program as an artistic medium. I couldn't really have this territory all to myself -or could I?

At my day job, we develop what seems to be a wide variety of systems: several subscription based web sites, a suite of desktop applications, an e-commerce system for selling both subscriptions and physical products, and various financial, administrative, content management, editorial and reporting systems for supporting them. We've been developing most of those systems under a locally adapted form of XP for about three years now.

For a lot of what we do an agile process works well. We're often making "small" modifications to a running (production) system, so a process that allows the customer to say "here's a set of changes, implement and deploy them in the next couple of weeks" fits our needs rather well. Even the least imaginative customer is typically able to break down large changes into an incremental series of small ones, and is often happy to see the intermediate steps in a running (although not always production) system.

Allow me to call this approach "adaptive" planning. (I don't think I'm the first to do so.) An interesting feature, perhaps the defining feature, of this adaptive approach is that customer is often defining new requirements as we're implementing the old ones, so that we're not always exactly sure where we're going when we start. It's sort of like a hill climbing approach: we take a few steps in what seems to be the right direction and then reevaluate. Our plan adapts to changing business requirements and generally doesn't try to look very far ahead in any detail.

It doesn't take a lot of insight to see that an adaptive approach is well suited to what might be called "product" as opposed to "project" management. If one conceives of the system as long-lived, constantly improving entity, it's easier to be comfortable with an iterative development process. No one can really foresee where the system is going to end up anyway, so the urge to ask "when is it going to be done?" is lessened.

On the other hand, there are times when the customer wants, or at least thinks he wants, a more predictive planning process: "Here's a large set of requirements, when are they going to be met?" This question is important because the answer will often drive business deals, strategic planning, and revenue projections. Depending upon the time sensitivity of the opportunity, the answer may determine whether the project is worth initiating at all.

Frankly, I don't think our process is very good at answering this sort of question. In practice, the way we approach such a question is quite similar to most "traditional" methodologies: we'll collect coarse grained requirements and prepare coarse grained estimates for them. This process is often time consuming--the customer team will spend weeks struggling to define and communicate a "base" set of requirements for estimation purposes. The result is often unsatisfactory--poorly understood and poorly articulated requirements lead to poor estimates.

One solution is to somehow dissuade the customer from believing that he needs detailed planning or long term predictions. Sometimes it really is a distinction without a difference--we're going to do the work anyway, so knowing precisely what features make it into the version 1.0 release or precisely when this release will occur are details that can be determined later. Most projects end with some negotiation of scope and schedule anyway. The trouble is, sometimes accurate predictions really do matter.

Another solution is to accept the limitations of this predictive approach--we don't really know how long it will take to complete the project, or what "complete" really means in the first place, so the best we can do is take an educated guess and know that the margin of error (and therefore the risk) is high. True as it may be, this answer is unsatisfactory at best, and unacceptable at worst. The fact that traditional planning approaches don't fare much better is little consolation.

We've been through this "predictive" planning exercise perhaps four times in the past three years, and have found it to be successful, but only moderately so. Increasingly I am beginning to believe that the adaptive process may be a more effective way of arriving at accurate predictions anyway. Through a lack of information, insight, or political capital, I've never seen it played this way, but I'm beginning to think this is the right approach:

Rather than spending a couple of weeks (or more) trying to determine a rough but "complete" estimate for the total cost of the project, spend that time developing an implementation of some of the base features (call it a "spike solution" or prototype if that helps, but it's really neither of those things). The requirements will certainly be incomplete, maybe even wrong. The implementation is likely to be wrong too, or will be when the requirements are better understood. I think that that may not matter.

Part of what leads me to this conclusion is that this is what we really do anyway. Although the thought is "let's not go down this road until we're sure that's what we want to do", in practice what we'll struggle to determine what the "total cost" of the project is going to be until it becomes clear that if we don't initiate the development soon, we won't be able to hit the requisite dates anyway. We may only be 60% sure that the project is worth pursuing, but the schedule eventually makes the decision for us. Indeed, this is how we first adopted an XP practice: as a way out of the "analysis paralysis" threatening a major product initiative.

(This last-minute adaptive approach is expensive in at least a couple of ways. Firstly, by the time a deadline is looming, we no longer have the luxury of slowly ramping up size the development team, we need to throw all our developers at the system immediately. This is a chaotic way of doing green-field development. Secondly, when we follow this approach, it's rarely the most important features we attack first, it's the ones that are easiest to define.)

I think this "just get started" approach may bring several benefits over a predict-then-implement one. Having a working system, however rudimentary...

• makes the total cost estimate more accurate simply by virtue of having some of the requirements already implemented. We don't need to guess what those will cost--they're already done.

• makes the development team more confident about their ability to address the remaining requirements.

• makes the development team better able to predict what's going to be tricky and what isn't. We have some measure of the team's velocity when working on the system in question. As a result, estimates should be more accurate.

• provides the customer team with a reference point to work from. Rather than saying "here's what the final system will look like", they can be begin to express requirements as "here's how I want to you change the existing system."

• may give the customer team enough confidence in the development team's ability to deliver the end product to follow an iterative/evolutionary approach. Once it's clear that we can deliver something by the deadline, it may be less important precisely what that something is.

Of course, the customer team can in parallel continue to define and refine the requirements and seek a "total cost" estimate, but at least for these first few iterations, we don't need to worry too much about the total scope of the project

There is some risk here, namely that after a couple of weeks of development it becomes clear that this is not a project worth pursuing and hence the development effort in those first few weeks is wasted. I can't imagine that this cost is significantly greater than the cost of the predictive analysis, but for better or worse in my environment there is a general impression that development resources are precious and hence need to be conserved--it's better to waste "analysis" time than "development" time. Overcoming this impression may be the key to selling this approach.

Looking over what I've written here, it looks like I'm describing a straight-forward XP process, and perhaps I am. In some ways, the distinction may be in the reasons for the adaptive approach. In our typical agile project, we sell the just-in-time requirements definition process as a way to get development moving while the business is still working out requirements. When predictive questions are asked, the business often believes that the requirements are already defined (although in practice they're often not as well defined as the customer may believe), only the technical cost needs to be determined. In this case the iterative development cycle may be more valuable to the technical team than to the business.

It may be interesting to explore how to use an adaptive planning process to answer predictive planning questions.

I'll come right out and admit it: commons-logging, at least in its initial form, was my fault, though probably not mine alone.

Back in 2001 I did a fair bit of work refactoring and debugging commons-httpclient. As part of that effort, I replaced a custom setDebug()/System.out.println based logging system with log4j. I did this for several reasons but all of them come down to the fact that a fully-fledged logging system is often quite useful. In fact, that debugging effort probably wouldn't have happened without it.

This change turned out to be controversial, and a runtime dependency upon log4j was in fact vetoed. After an enormous amount of discussion, not all of it pretty, a compromise was finally agreed to. This compromise basically said (a) use a thin wrapper around either log4j or the System.out logging initially implemented and (b) allow the user to specify whether to use log4j or System.out.println based upon a method call (inversion-of-control style I guess) or an external property. I did the first implementation of this. It was later suggested, probably reasonably so, that this "log wrapping" package be extracted from httpclient for use in similar circumstances. In a more robust or complicated form (depending upon your perspective) this eventually became commons-logging.

For all its warts, this brief history of Commons Logging shows the "bazaar-style" of open source development working as it should: the operative word here being "compromise".

Personally, I don't believe it to be especially important that Jakarta Commons committers be able to express their creativity by the selection of logging frameworks. I'd have been happy simply using log4j, and I think Ceki's work with the "light" log4j-ME would have been sufficient to address most of the technical concerns raised. Yet others disagree, and I'll respect that position. Certainly respect for that position has encouraged advocates of alternative logging implementations to participate more fully in Jakarta Commons.

That said, I think Hani and Glen miss the point entirely. The purpose of Commons Logging is not to isolate your code from changes in the underlying logging framework. (That's certainly easy enough to do on your own, and not really worth doing in the first place given the ease of switching from one logging framework to another.) The purpose of Commons Logging is not to somehow be more useful than actual logging frameworks by being more general. The purpose of Commons Logging is not to somehow take the logging world by storm. In fact, there are very limited circumstances in which Commons Logging is useful. If you're building a stand-alone application, don't use commons-logging. If you're building an application server, don't use commons-logging. If you're building a moderately large framework, don't use commons-logging. If however, like the Jakarta Commons project, you're building a tiny little component that you intend for other developers to embed in their applications and frameworks, and you believe that logging information might be useful to those clients, and you can't be sure what logging framework they're going to want to use, then commons-logging might be useful to you.

On a slightly unrelated note, I think that Hani's post fails to adequately explain how the problems caused by trying to integrate systems that use incompatible versions of the same component are unique to Commons Logging. If you want a discussion of the technical issues with Commons Logging, which are quite genuine, there are much better analyses available.

I have to give a product demo this morning. Although I hope I don't need to use it today, I'm reminded of a little joke I used to tell back in my consulting days to keep the customer occupied when a problem forced me to do an unexpected restart, reboot or reinstall in the midst of a demonstration:

A chemist, a physicist and a computer scientist were traveling in a car when the engine suddenly puttered out and they were forced to pull over to the side of the road.

"We must be out of fuel", the chemist said, "but I just saw a gas station. I'll walk back and pick some up."

"No, no", said the physicist, "that clearly sounded like a mechanical problem. Let me pop the hood and take a look."

"Wait!", said the computer scientist. "I have an idea. Let's all get out of the car . . . and then get back in."

• Radio now supports TrackBack. See TrackBack for Radio for details, but the gist of it is this: (a) enable TrackBack through your TrackBack preferences page then (b) invoke the <%trackbackLink%> macro somewhere within your item template.
• As you can see, I've got trackback links turned on in this blog now. I've also added direct (non-JavaScript) links to my comments and trackback pages. I did this by adding <%radio.weblog.getCommentLink(<%itemNum%>, adrblog)%> and <%radio.weblog.getTrackbackLink(<%itemNum%>, adrblog)%> calls to my item template.
• I've finally figured out where many of the built-in Radio macros are stored. From the Radio application, go to Window:Radio.Root:system:verbs:radio:weblog. The system/verbs tree has a number of nifty macros, including radio.weblog.getUrl, which generates the absolute URL of your Radio homepage. This is the answer to a question I had previously asked.
• Another pair of interesting macros I discovered there are radio.macros.previousDayLink and radio.macros.nextDayLink, which should generate day-to-day links in your archive pages. I've got this set up in my archives now, but there seem to be minor problems here and there. For example, the previous day link from Wednesday, 16 July 2003 goes to Monday, 14 July 2003, skipping over the post on Tuesday, 15 July 2003.

When I get a chance, I'll type these up for my Radio Tidbits page.

PS: I'd love it if someone could point me to a definitive reference to Radio's scripting language.

Recently I've read a number of comments (some old and some new) that take issue with the use of XML for one purpose or another (in the above examples, Ant and Jelly scripts, respectively). In fact, it seems all the cool kids are XML detractors these days, although the coolness may have peaked a few months ago, when even Tim Bray was admitting that XML may not be as nifty as first thought.

Now, I'll certainly admit that XML has its drawbacks. Is it overly verbose? Often. An equivalent s-expression syntax would be more concise and (for Lisp developers at least) more useful. Is it hard to read? At times. It's certainly better suited for documents where the ratio of text to tags is high. Is XML often used for developer convenience at the expense of user convenience? Is there information that has no business being in an XML format, but that developers or vendors insist on making XML anyway? Yes, yes, of course.

(On a related note, if "executable XML" is such a bad idea, how does one explain the longevity of Lisp?)

Despite these limitations, there is some value in selecting XML over, say (as Andy Hunt suggested for Ant) some arbitrary context-free grammar.

Part of this value is the ease with which a developer can drop in an XML parser, but that's only an indirect source of value. Part of this value is the comfort that users familiar with popular SGML applications (read "HTML") have with the angle bracket notation, but that may only explain the quick adoption.

The real value of XML is in the tool chain.

Suppose Ant had been based upon some custom, non-XML grammar. What would we lose?

Well for one, nearly every programmer's editor has a syntax coloring, well-formedness-checking mode for XML (certainly emacs and vi, or at least vim, and nearly anything that calls itself an IDE). Moreover, many editors support DTD or Schema validation as well, perhaps even tag and attribute completion. Using an XML format means a host of editors can handle Ant scripts smartly. The same would probably not have been true, at least initially, with some arbitrary grammar.

How does this come about? Well in part because XML is a popular format, but also because of the ease with which a developer can drop in an XML parser and other libraries.

For another advantage, consider the plethora of XML-based or XML-extending specifications. Many commentators have looked at that dense diagram and scoffed: not everything is well suited for an XML representation. Yet few would deny that at least some of those technologies do something truly useful.

Similarly, consider the number of tools, libraries and technologies that implement those specifications or provide other XML utilities. Want a pretty printer? There's a tool for that (indeed you're probably using one right now). Want an API for processing arbitrary XML? There's several, in nearly any language you can name. Want portable validation? Want to combine dialects? Want to translate one schema to another? Want simple macro support? Want to embed or link sub-documents? Want to generate hyperlinked documentation for a script or it's syntax? There's a tool for that too.

Sometimes it's sufficient to be adequate and popular, when that means a strong tool chain comes along for the ride. Sometimes worse really is better, or at least good enough.

Matt Quail writes "We have just released (beta) an Eclipse plugin and a NetBeans plugin for Clover, allowing you to instrument your code and view coverage results all from with the those Java IDEs."

Haven't tried it yet, but the screenshots look like exactly what I was hoping for. Sweet.