C for Coding

Stackoverflow: Joel and Jeff want VC Money? Say What?

2010-02-16T11:45:00.001+08:00

The big news today is that Stackoverflow—started by Joel Spolsky and Jeff Atwood as a programming Q&A site almost 18 months ago—is now looking for VC money. This is huge and deeply worrying. And it raises a whole raft of questions.

Vertical Growth

Stackoverflow has grown to be probably the largest programming Q&A site on the internet in its short life, supplanting the “evil hyphen site”, to be just outside the top 1000 sites having over 4.5 million visitors a month. While it continues to grow, there’s only so big it can get because there are only so many programmers.

Joel says:

In 18 months we’ve accomplish that: we’ve got 6 million unique visitors every month.

Note: this figure includes Superuser (1M) and Serverfault (730K).

The issue of course is how to turn this traffic into revenue sufficient to cover the site’s running costs, development of the site and profit for its owners. Programmers are a hard group to monetize and you can see Joel and Jeff struggle with this when it comes the usual method: advertising. See Responsible Advertising: Feed a Programmer, Our Amazon Advertising Experiment and Summary of Amazon Remnant Ad Experiment.

Horizontal Growth

It’s natural for companies that exhaust opportunities in their home markets to look at other markets that are related somehow, fuelled by (sometimes justified) paranoia that if they stop growing they’ll die or simply the need for incessant growth.

Look at where Microsoft's profits come from and you’ll see their core business is Windows and Office. Forays into gaming, music, online services, mobile communication, etc have varied from being lacklustre to haemorrhaging money pits.

Google’s core business is search and advertising.

It takes a rare combination of talent, timing and luck to successfully branch into new areas as Apple did with online music, portable music players and the iPhone.

Joel gave a Google Tech Talk about Stackoverflow last May that’s instructive. A key point is that all software is social and that a given platform that works in one community that’s dropped into another may simply not work.

Programmers respond to the Q&A format of Stackoverflow because a programmer is predisposed to formulating questions, answering them and categorizing (tagging) them. What’s more, the subject matter is sufficiently objective for there to be right and wrong answers most of the time.

To put it another way: programmers talking about programming are self-organizing.

Some miss the point completely and criticize the format for making discussion hard, which misses the point entirely.

Sister Sites

Joel and Jeff’s first attempts at horizontal market growth are the sister sites: Serverfault (for sysadmins) and Superuser (for general computer questions), which Jeff calls the League of Justice. There are also loose affiliations with How-to Geek and Doctype (from the guys behind Litmus).

While a million (ish) uniques per month is nothing to sneeze at it’s clear that these sites haven’t grown like Stackoverflow has. See superuser.com and serverfault.com (this one has started to pick up recently).

Stack Exchange

Fog Creek has adapted the Stackoverflow code to create a hosted white label Q&A solution. For roughly $129/month you can have your own Q&A site to discuss everything from parenting issues to World of Warcraft (no joke).

Such sites rely on communities and building communities takes time. Stackoverflow succeeded in part because it leveraged the existing audiences of Joel and Jeff.

Careers

This is perhaps the more controversial move and something I covered in Joel Inc., Stackoverflow Careers and Jumping Sharks and Hard Numbers on Stackoverflow Careers. It’s something the pair have pushed repeatedly, going so far as heartfelt testimonials.

This one differs from the others in that the revenue model isn’t based on advertising: it’s based on the high cost of recruitment and the unique tie-in with Stackoverflow. My opinion is there simply aren’t enough active Stackoverflow users for this to be a real money spinner but time will tell.

Self-Funding and Control

Self-funding has huge advantages for any venture. If it’s possible it keeps control in the hands of the founders. Investors have their own agenda—being a return on that investment—which doesn’t necessarily coincide with the best long-term interests of the venture.

Some argue Transmeta was derailed by being forced to make a premature product launch.

When you own your own venture you can do whatever you want. Well, you can’t break the law but other than that, there’s not a lot you can’t do.

As soon as you have investors that changes. Investors have rights. Their money comes with conditions like how you can spend the company’s money, reporting requirements and so on.

It gets even worse when you’re a public company and worse again when you’re a publicly listed company.

Debt and Equity

There are two basic sources of funding for a venture: debt and equity.

Debt is borrowing money that you agree to repay the lender, typically at a fixed or floating rate over a given period of time. In the corporate world, there are many sources of debt: bank bills, overdrafts, commercial paper, bonds, swaps, traditional loans (secured and unsecured) and so forth. Many of these you have to be sufficiently large to have access to (eg corporate bonds are an option for the Toyotas of the world).

Equity is ownership of the company. Depending on your jurisdiction there are many forms of equity: ordinary shareholders, preferential shareholders and so on. They have different rights and a different pecking order for being repaid if the company is ever wound up (and typically the debt-holders will be ahead of all of them).

In between there are countless variations (eg convertible notes are a debt instrument that can be converted to equity in certain circumstances).

Companies generally strive for a healthy mix of debt and equity funding options.

The fallacy that many tech companies succumb to is that venture capitalists are their only source of funding. What’s more, VC funding is about the most expensive source of funding. A bank, being your typical source for a loan, will look at your plan and make a decision on your ability to repay the loan. Not your revenue but your income (being revenue minus expenses), both current and projected.

VCs typically look for blue-sky potential, often in ventures that don’t even generate revenue now or in the foreseeable future. Still any business plan will need to answer the questions of “when” and “how” the investors will get a return.

What Does Stackoverflow Want?

This move is surprising consider Joel wrote Fixing Venture Capital and Strategy Letter I: Ben and Jerry's vs. Amazon. Joel is somewhat vague on their motivations, saying only:

Now we’re biting off the bigger goal of changing the wayeveryone gets answers to their questions on the Internet, and that’s something we can’t do alone.

The infrastructure (hardware and bandwidth) is cheap (almost free) for Q&A. Stackoverflow.com seems to run on three Web servers based on Stack Overflow Architecture (a little outdated but those Web servers are low RAM and single CPU, which means dirt cheap) and Stack Overflow Network Configuration.

It’s fair to say that hardware is ludicrously cheap. Plentyoffish uses less than 10 servers for over a billion monthly page views.

Is it development? Is there some grand Q&A idea that’s going to take 50 man-years of development time to implement? Jeff has repeatedly said that apart from tweaking around the edges, Stackoverflow as a technology platform is basically “done”.

Is it to broaden the scope of Stackoverflow? What about a Wikipedia-like platform? What about the Wikipedia content? Is there any money in that?

Why Venture Capital?

This points to something ridiculously large scale otherwise:

Why wouldn’t a bank fund it (based on existing income)?
Why wouldn’t Fog Creek fund it?

The last is worth mulling over. Fog Creek has ~34 employees. Joel once said for every $10,000/month Fog Creek made he hired a programmer. Fog Creek is a private company so it’s profits aren’t published but it would seem reasonable to assume that their revenue is in the order of $4-10 million per annum.

he business itself could benefit from the publicity of getting an investment from someone who is thought of as being a savvy investor.

The investor will add substantial value to the business in advice, connections, and introductions.

But he also says:

The founders are not in it for their own personal aggrandizement and are happy to give up some control to make the business more successful.

Interesting. Could it be as simple as wanting to cash out?

I suspect (3) and (4) are more what it’s about but without knowing what they want to do it’s largely impossible to figure out the why.

Conclusion

It’s hard not to be concerned by this. The evil hyphen site became evil when they tried to take what was free content and and monetize it using a subscription model. I don’t believe this is a likely outcome here but when you give up control, it’s a question of what your investors believe is the path to profitability that matters.

Many businesses fail because they try to apply something that worked one place to another area where it simply doesn’t work. I would hate to see this happen to Stackoverflow as I’m personally a big fan of the site.

There’s something to be said for leaving something that works well enough alone and turning your attention to building something else. Not everyone can or should be Microsoft or Google. Trying to be is typically a surefire way of converting success into failure.

Update: I misspoke regarding the Stackoverflow Web server configuration. Fixed.

Markdown, Inline Parsing and Badly Formed HTML

2010-02-11T17:04:00.001+08:00

I haven’t had much time to work on my Markdown parser lately (sadly) but I thought it was worth posting an update on where I’m at. I have been digging deep into the dark depths of inline parsing. I have previously discussed the two modes of parsing Markdown, which I call block and inline.

But the block parsing is done (well, I have to go back and tweak one thing) so I’m onto the murky world of inline Markdown parsing.

Parsing Block Markup

Various Markdown implementations allow you to create markup blocks. There are usually quite strict requirements about how you can write these blocks. For example, you might need to put the start and end tags on separate lines such as:

<ul>
  <li>one</li>
  <li>two</li>
  <li>three</li>
</ul>

I have a much more forgiving approach to this such that this “Markdown”:

This is a paragraph with a <ul><li>nested</li></li>block</li> with
some <hr>random<h2>other tags</h2> in it

and convert it to:

<p>This is a paragraph</p>

<ul>
  <li>nested</li>
  <li>block</li>
</ul>

<p>with some</p>

<hr>

<p>random</p>

<h2>other tags</h2>

<p>in it</p>

This part already works.

But it gets better. It will also take that some input stream and convert it to:

This is a paragraph

- nested
- block

with some

------

random

## other tags ##

in it

So to be clear: this will convert acceptable markup to markdown and filter out unacceptable markup (like script tags).

This will include parsing links and images into Markdown references.

Parsing Inline Markup

This is what I’m working on now. I’m still looking for a good generic way of doing this that correctly captures tag hierarchies (eg list items must be children to unordered and ordered lists). What I’m probably going to do is release a messy version of the code (being the current version) then go back and revisit it once I have a working implementation.

This is a good general principle: it’s far easier to fix something that’s complete and working than it is to constantly strive for perfection in incomplete code (basically artists ship).

One thing I’m debating is whether I require tags to be balanced. That means whether I accept this:

<b>this is<i>a</b> test</i>

Ideally I’d like to not accept this. XML/XHTML requires balanced tags but HTML either doesn’t or even if it does, most browsers are quite forgiving of this. XML treats markup essentially as a document tree whereas the HTML view is more like tags are, in certain circumstances, switches to turn behaviour on or off.

Markdown Formatting

I went into this problem thinking I could construct a document tree out of

***this is a* test**

into

document
+- bold
   +- italic
   |  +- text: this is a 
   +- text: test

but that idea quickly falls down when you consider that this is valid Markdown:

**this is *a** test*

which basically parses to:

BOLD_ON
TEXT("this is ")
ITALIC_ON
TEXT("a")
BOLD_OFF
TEXT(" test")
ITALIC_OFF

Almost any Markdown parser will generate HTML from this that looks like this:

<strong>this is <em>a</strong> test</em>

That’s unfortunate because I like the document tree. But sadly the matching problem still remains because if a special sequence doesn’t have a matching close it is put into the document as a literal sequence.

This leads to some fairly pathological corner cases like:

*this [link* google][1]

  [1]: http://google.com

which will translate to

<em>this <a href="http://google.com">link</em> google</a>

and browsers will tend to break that link into two parts (where you can click on “link” or “google”).

But work progresses.

Conclusion

Even with a lot of the Markdown spec being parsed my transformation times on basic documents (eg a couple of lists, a block quote and some paragraphs) is still under 60 microseconds (roughly) and that’s with some messy array manipulation and temporary object creation that I plan to revisit and clean up.

At this stage I’m hoping to have some committed and available for comment within two weeks. It won’t be pretty but my goal is to get feedback earlier rather than later.

Standing on the Outside

2010-02-05T05:32:00.001+08:00

This week I read Life outside .NET, or “How to check out your neighbours”. I really like posts like this. They’re instructive about the culture of a particular community.

For over a decade I’ve been a Java developer (since JDK 1.0.2). Like most Java developers I have a love-hate relationship with the language, the libraries and Sun. Java didn’t invent the virtual machine but it certainly popularized it. 5-10 years ago (in particular) Java was a hotbed for the development of many technologies, concepts and frameworks.

As the author notes, MVC and DI (dependency injection) are simply assumed in Javaland. It’s true. Good luck finding a non-MVC Web framework in Java out of the dozens that exist.

My experience and exposure with .Net is at best peripheral. ASP.NET always struck me as somewhat primitive in the sense that it’s what would’ve happened had JSP been taken to the nth-degree instead of being supplanted by Struts and all that came after. That’s not to say ASP.NET is bad or doesn’t do it’s job but to a Java developer it seems somehow crude.

Beyond the boring and irrelevant comparisons of Java vs. .Net performance, the more interesting comparison is as a proxy for decentralized vs. centralized platform progression.

The Microsoft Way definitely has its advantages. Where once Redmond was playing catch-up on Java (technically speaking), Sun’s inability to lead (and no clue where they were going if they could) has left Java largely stagnant. Java 7 is due at the end of the year but has been delayed years. Thankfully it’s now getting closures if for no other reason than we can all stop bitching about it (frankly, I think some form of function pointers or delegates in “C#-speke” will be sufficient for 99% of use cases).

It can be useful not to have a diaspora of Web development frameworks (even at the cost of innovation). Takes a Struts developer and put them on a Wicket or Tapestry project and their experience won’t be especially applicable.

It will certainly be interesting to see if Oracle can provide more leadership than Sun. Oracle was always heavily invested in Java so I’m hoping Java isn’t simply collateral damage to Larry’s acquisition of Sun’s server business. Bizarrely Oracle seems committed to JavaFX of all things.

For those of you unfamiliar with it, JavaFX is Sun’s “me too” Flash alternative and a prime example of Sun’s boondoggles of recent years.

I for one welcome our new insect overlords. I’d like to remind them that as a trusted blogger, I can be helpful in rounding up others to toil in their underground sugar caves.

Markdown, Block Parsing and the Road to Hell

2010-02-02T12:53:00.000+08:00

I thought it times to update my status on this particular undertaking, which so far has ended up being far more massive than originally envisioned.

The overall design of the Markdown parser is that there are two parsers… kinda. There is a parser to break your document into blocks and another to interpret the inline content within those blocks. As soon as I made this realization, everything just got a whole lot easier.

I use this this term (and “inline”) because those are the terms HTML uses (“block elements” and “inline elements”). Of course HTML also gets more complex (eg “replaced” vs “non-replaced” elements and inline-block, floats, etc) but fundamentally you can think of a Markdown document—or any hypertext document—as consisting of block and inline elements.

Markdown parsers will often talk about “blocks” and “spans” instead.

Block Parsing

The first level of parsing of Markdown is into blocks.

Such a document can be viewed as a tree. The root node is the document. Every node below that is either a block or an inline node. The tree can be arbitrarily deep and there are certain rules about relationships in that tree. For instance:

Block nodes are only ever children of other block nodes (counting the root Document node as a block node);
Paragraphs can only contain inline elements;
List items must be children of lists;
and so on.

The goal of any parser is take an input and build a valid syntax tree based on the rules defined.

This part of the problem for what I’m writing is now done. This includes code blocks, paragraphs, block quotes, ordered and unordered lists, headers and horizontal rules. Tables I plan to return to later.

List Parsing

Today I came across Three Markdown Gotchas, which I hadn’t seen before but it opened my eyes to one particular area of difficulty I had: list processing. Go to StackOverflow, ask a question and type in:

- one
 - two
  - three
   - four

and you probably won’t get you what you expect. You get this:

<ul>
  <li>one
    <ul>
      <li>two</li>
      <li>two</li>
      <li>two</li>
    </ul>
  </li>
</ul>

Let me give you some background: Markdown has the concept of indents. Based on a predefined tab width (typically 4), a single tab or 4 spaces represents one indent. That’s important because code lines are preceded by one indent. A non-indent space is sometimes ignored at the beginning of a line, for example at the start of a paragraph line or the continuation of an existing one.

The original Markdown “spec” says that nesting list items is done by preceding the line with one more indent than the previous line. In vanilla Markdown the above sequence would come out as:

<ul>
  <li>one</li>
  <li>two</li>
  <li>two</li>
  <li>two</li>
</ul>

because none of the lines has a leading indent. That’s logical and consistent. Jeff’s point is basically that even one space should indicate intent and be interpreted as nesting. Sounds reasonable right? Maybe. The problem is that it leads to unintended complexity.

Go back to the above example and put one, two then three spaces in front of the first list item. Watch the preview pane to see how the list changes. The implied nesting changes all over the place? Logical? I think not.

But it gets worse.

- one

 two
 - three

 four

comes out as

<ul>
  <li>
    <p>one</p>
    <p>two</p>
    <ul>
      <li>three</li>
    </ul>
    <p>four</p>
  </li>
</ul>

Okay… bear in mind that there are spaces before two and four so that you continue the list item. Otherwise they would be interpreted as separate paragraphs. But what if you want four to continue the nested list item three? How much indentation do you need? It turns out that the magical number is anything from 5 to 11.

But it gets worse. Put one space before one and suddenly one and three are the same list so four is now indented so far that it becomes a code block run-on from three. Add a second space to the front of one and for some reason it returns to the original nesting even though one is now indented more than three. Huh?

I’ll leave an examination of the MarkdownSharp source code as to the reasons for this as an exercise for the reader. Suffice it to say that it all stems from the motivation that one (more) space indicating nesting being somehow more intuitive.

The Road to Hell

The road to hell is paved with good intentions. It’s one of my favourite sayings. We programmers as a whole are unreasonable people. Through a combination of hubris, stubbornness and even laziness we have a tendency to throw out what’s been done before or simply make breaking changes because we prefer it, we think others will prefer it, we don’t appreciate that someone else may have to deal with the consequences or simply out of ignorance as to what led to the original changes.

We all do this, myself included. It’s worst when it not only manifests itself in company culture but it’s enshrined. Take Microsoft as a prime example. Internet Explorer has “Favourites”. What the hell are favourites? Well, they’re bookmarks. But IE can’t call them that because Netscape called them that first and Microsoft wanted to differentiated themselves and their products. This is of course led to many conversations I know I had at the time that went something like this:

New user: What’s a favourite?
Me: It’s a bookmark.

I couldn’t help but laugh out loud when I first read C# and saw all the things copied from Java had been renamed, sometimes with significantly worse names. Java’s final as C#’s sealed springs to mind. You can just tell that there were people dedicated to the task of finding names to Java concepts and keywords. It’s just sad.

Hyperbolae aside, I digress.

The point of all this is that:

Often things that came before you were done for a reason, whether or not you’re aware of it and whether or not you agree with it if you are;
Breaking changes have a high price so much so that the cure is often far worse than the disease and your delicate sensibilities be damned. Internal consistency and syntactic purity is overrated. Interestingly those overly encumbered with such sensibilities seem to have a disproportionate tendency to become Python programmers.

List Sanity

For this reason my parser has returned to what is probably the original implementation. That is:

A leading non-indent space is ignored before list items. That is, it implies no meaning and is discarded so there is no difference between 0 and 2 leading spaces before a list item;
Up to one leading indent (meaning one tab or 0 to 4 spaces) is consumed from each subsequent line until a new list items is hit or a line with no leading spaces is met. The subsequent list item will be a part of the same list. Text with no leading spaces will end the list and form a new paragraph; and
All lines that continue the list item are combined (with their leading tab or 0 to 4 spaces consumed) and they form a new block context. Meaning they are then parsed as if they were a separate input, meaning it can contain new lists, block quotes, code segments and so on.

(3) provides a lot of consistency. it means that if you have a list item followed by a line with two indents that second line will be a code block (one indent marking a continued list item, the second will be interpreted as a code block within the list item block context).

To me this is supremely more logical—and easier to implement—but I guess if you’re really attached to nesting list items with a single space and figuring out that 5 to 11 spaces is the magical number of spaces to continue a nested list item then you’ll hate it. Too bad.

The nested block context from (3) has one exception. If the nested block context would result in a single paragraph then that paragraph is unwrapped to being inline content of the list item. This has one important effect, which some may consider a breaking change. Namely this Markdown:

- one
- two
- three

and

- one

- two

- three

will both be interpreted as being:

<ul>
  <li>one</li>
  <li>two</li>
  <li>three</li>
</ul>

whereas MarkdownSharp will interpret the latter as:

<ul>
  <li><p>one</p></li>
  <li><p>two</p></li>
  <li><p>three</p></li>
</ul>

which is something I've previously documented and disagreed with.

But this could be interpreted as a breaking change so I will probably add a special case for just this scenario as an option

Conclusion

The block parsing portion is done. The code is ugly and needs to be refactored (again) but it works. I still have an issue with too many temporary objects being created (mainly because it simplified some code) and I’ll need to go back and eliminate that.

What’s been interesting is that I’ve now rewritten the block parsing at least four times before it felt right. John Carmack once said he needs to write something five or six times before he gets it right. I agree with his sentiment. It takes that long to truly understand the domain, in my opinion.

The inline parsing has been a completely different set of problems. I will have a follow-up post on that soon.

Java IDEs: the Blue Heeler, the Dachshund and the Labradoodle

2010-01-28T23:48:00.001+08:00

I’ve had a frustrating week. I’m on a mission to find out why a piece of code I wrote had a “blowout” in execution time (“blowout” here means 60 microseconds instead of 15 in sustained usage just to keep things in perspective). I suspect it’s to do with temporary objects either auto-boxing/unboxing and/or temporary arrays.

Java, in my opinion, has the best IDEs of any language or platform bar none. Say what you want about the language but the IDEs are, on the whole, first rate. That doesn’t mean there aren’t bumps along the road however.

For the purposes of this completely biased rant I shall liken them to dog breeds.

Blue Heeler

The Blue Heeler is one kind of Australian cattle dog. It’s used on sheep farms and cattle stations to round up livestock. It’s not the prettiest of breeds.

So you won’t see these as family pets or in trendy dog parks or in your neighbourhood. But they’re smart, obedient, protective and hard-working. If you’re herding cattle? You won’t see much else. The Blue Heeler is a working dog and a victory for utilitarianism.

IntelliJ IDEA is the Blue Heeler of the Java IDE world.

Ever hear anyone rave about Resharper when talking about Visual Studio? Or even go so far as to say that Resharper is what makes Visual Studio good? Well, Resharper is adding the functionality to Visual Studio that IntelliJ has for Java.

Yet all is not perfect in IntelliJ-land. The biggest problem is plugins. You certainly don’t have the range that, say, Eclipse does. But nor do you have the “plugin hell” woes so often associated with Eclipse either. Open source frameworks will tend to release plugins for Eclipse and its up to third parties to make IntelliJ versions, which doesn’t always happen.

On the bright side, you don’t actually need that many plugins because nearly everything you need is done out of the box anyway.

What makes it worse is that Jetbrains keeps breaking all the plugins. IntelliJ 9 is relatively new but it once again broke all the plugins. I’ve lost count of the number of times a major version has done this. Seriously, can’t you guys make the plug-in architecture remotely backwards compatible? Is that breaking change you’re making really necessary? Really?

The Jetty plugin still doesn’t work, which is a reasonably big deal. Worse, i can’t find a profiler that works in IntelliJ to save my life, except possibly JProfiler but who can justify $499 for a fixed single license of a profiler? Especially considering the same thing for the whole rest of the IDE is $249 (if you don’t want to use the free version.

Dachshund

The Dachshund is a strange and impractical dog. Just look at it and you can tell it’s no product of evolution. Not without man’s intervention anyway.

Yet people like them. Families own them. They are however stubborn and hard to train and they have their fair share of health problems (including spinal problems unsurprisingly).

Eclipse is the Dachshund of the Java IDE world.

If IntelliJ has not enough plugins then arguably Eclipse has too many. Hell, this goes so far as having two Subversion plugins. A former colleague, who was an avid Eclipse fan, could never get either one to work. Sometimes they lied about checking stuff in (big problem) or just conflicted with other stuff.

Every time I try and use Eclipse for something I’m struck with an overwhelming sense of how awkward and unintuitive it is. Take Maven projects as one example. In IntelliJ or Netbeans you just open one up and it just works. Googling doesn’t really help either. The first link is seemingly out of date and it doesn’t get much better.

Now I realize this is a whole Coke vs Pepsi thing. Many people are no doubt experts in Eclipse. They’re used to the “Eclipse Way” so it all makes sense (which strikes me as a form of Stockholm Syndrome but I digress…). Hell, they may even like the whole perspectives thing, which I’ve always hated.

But if you tell me you’ve never had problems with Eclipse plugins you’re lying.

Labradoodle

The Labradoodle is a strange and relatively new dog breed. Whereas programmers with too much free time come out with bizarre ways of calculating Pi and other such boondoggles, dog breeders with idle hands decide to answer a question that has plagued civilization since Aristotle’s time:

What happens when you cross a Labrador Retriever with a poodle?

Baseless hyperbolae aside, I’m sure there was a reason. I just don’t know what it was.

But what resulted is a friendly, energetic and not-too-bright breed that families tend to like.

Well Netbeans is the Labradoodle of the Java IDE world.

Netbeans does some things very well, particularly Swing development (which admittedly in today’s Web-focused world is a lot like being the best manufacturer of horse bridles and saddles).

Netbeans also faces an uncertain future with Oracle’s acquisition of Sun.

Netbeans at least immediately understand my Maven project. It couldn’t find classes with main() methods that were under the test directory (IntelliJ could) but it otherwise all just worked.

So it was looking good to finally get a profiler running… until I came across a bug. There is at least one open bug against Netbeans that raises an issue against Windows 7. My dev machine is a Windows 7 64 bit machine. Months after Windows 7’s release—nearly a year after the beta version—to still have permission problems is simply unacceptable. Yet that’s what happens when I try and use the profiler.

Conclusion

All this and I still have no profile of my code!

Please don’t waste my time and yours by commenting or sending me a message saying I’m wrong about <insert favourite IDE here>. You’re missing the point of a rant (in that largely there isn’t one).

Markdown and an Introduction to Parsing Expression Grammars (PEG)

2010-01-24T13:34:00.001+08:00

Writing an ANTLR LL(*) grammar for Markdown has been the itch I just can’t scratch this month. I keep going back to it as I have a new idea about how to approach the problem or how to solve a previous problem I’ve had. Each time I get further but I still keep hitting a wall.

It’s a shame really because ANTLRWorks is an excellent tool and ANTLR is an extremely mature product. The rewriting rules and tree grammars are extremely elegant.

Over the couple of weeks I’ve been investigating PEGs (“Parsing Expression Grammars”). I highly recommend Parsing Expression Grammars: A Recognition-Based Syntactic Foundation by Bryan Ford. PEGs are relatively new (Ford’s paper was published in 2004) whereas parsing CFGs (“Context Free Grammars”) with LL, LR and LALR parsers has a history going back decades.

Traditional Parsers

Parsing of computer and natural languages (by computers) has it’s roots in Noam Chomsky’s work on generative grammars, particularly the Chomsky hierarchy and the work of Donald Knuth (On the Translation of Languages from Left to Right [1965]) and Frank DeRemer (Practical Translators for LR(k) Languages [1969]).

To understand Parsing Expression Grammars let me first explain the basic workings of a traditional parsers. The first step is lexical analysis that turns an input stream into a series of tokens. The parser will then apply various rules to these tokens. There are varying techniques for dealing with ambiguities and recursive rules.

As Terence Parr (the creator of ANTLR) puts it in his (excellent) The Definitive ANTLR Reference: Building Domain-Specific Languages:

Unfortunately, ANTLR cannot generate a top-down recognizer for every grammar—LL recognizers restrict the class of acceptable grammars somewhat. For example, ANTLR cannot accept left-recursive grammars such as the following (see Section 11.5, Left-Recursive Grammars, on page 274):
/** An expression is defined to be an expression followed by '++' */
expr : expr '++'
     ;
ANTLR translates this grammar to a recursive method called expr() that immediately invokes itself:
void expr() {
  expr();
  match("++");
}

This is something that LALR parsers handle better.

The Lexical Analysis Problem

But the big problem as far as Markdown is concerned is that tokens are not context-free. Take a natural definition for lists:

listItem    : ORDERED inline NEWLINE
            | UNORDERED inline NEWLINE
            ;

ORDERED     : DIGIT+ '.' (' ' | '\t')+ ;
UNORDERED   : ('*' | '-' | '+') (' ' | '\t')+ ;
inline      : (~ NEWLINE)+ ;
NEWLINE     : '\r' '\n'? : '\n' ;

and this Markdown:

1. one
2. two
3. three

will be converted into this lexical stream:

ORDERED inline("one") NEWLINE
ORDERED inline("two") NEWLINE
ORDERED inline("three") NEWLINE

and then this AST ("Absract Syntax Tree") will result:

document
+- listItem
|  +- ORDERED
|  +- inline ("one")
|  +- NEWLINE
+- listItem
|  +- ORDERED
|  +- inline ("two")
|  +- NEWLINE
+- listItem
   +- ORDERED
   +- inline ("three")
   +- NEWLINE

Looks good, right? Wrong. It quickly falls down when the Markdown becomes pathological:

1. 1. one
2. two
3. three

because the input stream is:

ORDERED ORDERED inline("one") NEWLINE
ORDERED inline("two") NEWLINE
ORDERED inline("three") NEWLINE

assuming you can resolve the ambiguity regarding inline being able to technically match "1." (which you can.... kinda).

The above will not be recognized because there is no rule that handles a pair of ORDERED tokens. Really what you want to do is not create an ORDERED token after you’ve already started a list item but at this point you no longer have a context-free grammar.

ANTLR’s semantic and syntactic predicates make an admirable effort of dealing with these kinds of ambiguities and context sensitivities but ultimately it’s just not designed for this kind of grammar.

Enter PEG

PEG parsers take a different approach in two important ways:

PEGs are not ambiguous. Choices in the above can lead to ambiguities. ANTLR resolves many of these by using predicates, which are a way of saying “if it looks like a duck then it’s a duck otherwise it’s something else”. PEGs use a prioritized choice operator, which basically try the choices in order until it finds one that matches. By definition this is unambiguous because the input stream will either be recognized or it won’t; and
PEGs better handle non-CFGs by trying to recognize tokens as part of processing a rule rather than recognizing tokens and then applying rules to them.

Prioritized Choice

So in PEG terms, Markdown becomes easier to describe:

Document <- Line*
Line     <- Heading / ListItem / Inline / Empty
Heading  <= '#'+ WS+ Inline
ListItem <- (DIGIT+ '.' / '*' / '-' / '+') WS+ Inline
Inline   <- (!NEWLINE .)+ NEWLINE

DIGIT    <- [0-9]
WS       <- ' ' | '\t'
NEWLINE  <- '\r\n' / '\r' / '\n'

This is of course partial and a simplification but the important thing here is that prioritized choice resolves what otherwise will be ambiguous. This is the “else” clause I’ve been looking for.

Context-Sensitive Tokenization

Markdown has lots of these issues. For example ‘###’ might indicate a header but only if that line itself isn’t a header (by the next line consisting of all equals signs or hyphens). ANTLR allows you to handle some of these situations by doing something like:

HEADER : {getCharPositionInLine()==0]?=> ‘#’+ WS+ ;

but what about this Markdown?

> # quoted heading
> some text

It’s entirely possible I’m missing some key part of the puzzle here but I’m not hopeful.

Ford illustrates this problem:

...PEGs also create new possibilities for language syntax design. Consider for example a well-known problem with C++ syntax involving nested template type expressions:
vector<vector<float> > MyMatrix;
The space between the two right angle brackets is required because the C++ scanner is oblivious to the language’s hierarchical syntax, and would otherwise interpret the >> incorrectly as a right shift operator. In a language described by a unified PEG, however, it is easy to define the language to permit a >> sequence to be interpreted as either one token or two depending on its context:
TemplType <- PrimType (LANGLE TemplType RANGLE)?
ShiftExpr <- PrimExpr (ShiftOper PrimExpr)*
ShiftOper <- LSHIFT / RSHIFT
LANGLE    <- ’<’ Spacing
RANGLE    <- ’>’ Spacing
LSHIFT    <- ’<<’ Spacing
RSHIFT    <- ’>>’ Spacing

(emphasis added)

Conclusion

This isn’t a new problem and I’m the first to approach the issue of Markdown parsing with a PEG grammar. peg-markdown is an implementation of Markdown in C using a PEG parser.

My own effort is going forward despite this implementation existing for several reasons:

I plan on having implementations in several languages;
I intend to implement various Markdown and Wiki extensions and flavours; and
Because I’m getting a kick out of it.

I learnt compiler theory in university but it was all quite theoretical with simple yet interesting examples. The practical application to a real-world problem is quite something else. Plus PEG is only 6 or so years old so is new to me.

It is my belief that PEGs are a far more natural and robust means of parsing any form of Markdown, Wiki syntax, BBcode or other forum format.

And that’s the direction I’m heading.

Markdown Headings, Grief and Unknown Elements to the Rescue

2010-01-17T11:49:00.002+08:00

Well it’s not a day to be outside (unless you’re at the beach). It’s 41 degrees and that’s metric (none of this Imperial rubbish that only the US uses). That’s 106F in the old scale.

So I’m tackling the problem of Markdown headings in my parser.

Heading 1
=========

Heading 2
---------

# Heading 1
## Heading 2
### Heading 3

Horizontal rules:

-------
*******
_______

This is really annoying for two reasons:

Ambiguous syntax: a line of hyphens could be a horizontal rule or indicate a heading depending on the context (and again we return to the point of Markdown being context-snesitive); and
From an LL-persepctive this is left-recursive and requires LL(*) (arbitrary lookahead) in a normal grammar.

Let me explain.

A subset of the grammar for Markdown might look something like this (in ANTLR-like syntax):

document  : block* ;
block     : paragraph | heading | heading1 | heading2 | codeblock ;
paragraph : inline+ END_BLOCK ;
heading   : '#'+ inline NEWLINE ;
heading1  : inline+ NEWLINE '='+ (NEWLINE | END_BLOCK) ;
heading2  : inline| NEWLINE '-'+ (NEWLINE | END_BLOCK) ;
inline    : '*' inline+ '*'
          | '`' inline+ '`'
          | ...
          | OTHER+
OTHER     : '.' ;
END_BLOCK : '\n' '\n'+ | EOF ;

Try and plug something like that into ANTLR and it will complain all over the place.

Firstly it’s ambiguous. An input sequence like “*123*” matches two of the inline alternatives. I’m led to believe that PEG parsers can deal with this by simply trying rules in the order they appear. That would fit a lot better to this situation. ANTLR can (messily) handle it with syntactic predicates.

The other problem is the grammar is left-recursive, most notably with the inline rule.

Yet another problem is that this requires arbitrary lookahead (again, something ANTLR can do with its LL(*) algorithm) because the token that delineates the heading rules is right at the end of a cyclic rule.

It's even worse once you start factoring in paragraphs and lists.

All of this leads to a whole bunch of headaches but I thought about this long and hard (going so far as to wake up in a sweat after a lexical analysis nightmare) and came up with a much more elegant (imho) solution

Consider a lexical stream that looks like this:

WORD("Heading") WHITE_SPACE(" ") WORD("1") ...

What's next is important because the parser doesn't yet know if this is a paragraph or a heading. But here is where I was trying to be too clever for my own good by determining the block quote in the lexer. After all, it would make the parsing step easier if I could just use a stack to push/pop block elements already knowing what they are.

Instead I decided to treat a stream of inline elements as an Unknown element and I could just determine the type as a parsing action rather than a lexcial rule. So the grammar simplifies somewhat to:

document  : block* ;
block     : codeblock | unknown ;
codeblock : ('    ' .* NEWLINE)+ ;
unknown   : inline* END_BLOCK ;

Again, order of rules is useful here, meaning if it looks like a code block it is a code block, otherwise it’s an unknown block. A syntactic predicate could handle this or you could make an indent at the start of a line an INDENT token, which wouldn’t fit into the inline rule. This makes the grammar unambiguous but still requires arbitrary lookahead. It’s easier to simply make a decision based on the first token and avoid any backtracking whatsoever.

So if the parsing actions come across the right token sequence within the unknown block it changes that block to a heading, otherwise when that block ends it simply defaults to being a paragraph.

Think of unknown elements as being the stem cells of Markdown lexical analysis.

Anyway that was my revelation for the week. I still need to finish my list handling, inline styling and links, which is still more than I’d like but it’s getting there.

Markdown Musings on Unintended Consequences

2010-01-14T23:24:00.002+08:00

It may seem lately that Markdown is my white whale to which I respond thusly… call me Ahab.

One of the problems with implementing something like this is that no one can quite agree on what exactly constitutes Markdown. It gets worse when you consider Wiki syntaxes. What’s stunning is that someone (CosmoCode) has gone so far as to create a matrix comparing them all.

If you peruse the unit tests you find things like:

Asterisks tight:

* asterisk 1
* asterisk 2
* asterisk 3


Asterisks loose:

* asterisk 1

* asterisk 2

* asterisk 3

is converted to:

<p>Asterisks tight:</p>

<ul>
<li>asterisk 1</li>
<li>asterisk 2</li>
<li>asterisk 3</li>
</ul>

<p>Asterisks loose:</p>

<ul>
<li><p>asterisk 1</p></li>
<li><p>asterisk 2</p></li>
<li><p>asterisk 3</p></li>
</ul>

Now having gone through the code I can see why this is: two newlines is typically used as a block delimiter, between paragraphs, code blocks and so forth. But I have to wonder three things:

Is this planned behaviour or simply the result of splitting the file into blocks using two or more newlines as a delimeter?
Is this behaviour desirable?
Is this behaviour reasonable?

Of course there is a case for paragraphs being nested in list items, namely that you have two or more paragraphs or other nested block content within list items. This is certainly something you can do—and will do—in HTML but I’m not so convinced that a newlines wrapping list content in a paragraph is anything other than an unintended consequence.

Of course there is no grammar or spec for Markdown so it’s something you can argue til the cows come home. You can also change it and still call what you do “Markdown”. It’s why there are so many Wiki syntaxes.

There are other issues. For example, should you be able to start or end bold or italic styling in the middle of a word? I believe Github has taken the approach that underscores for italics can’t start or end intra-word, sensibly (as this is a common occurrence in source code).

Lastly, Markdown preserves HTML. It’s my opinion that it should be replaced with Markdown where possible. What should you do with this:

<blockquote>
  <ul id="list">
    <li>one</li>
    <li>two</li>
    <li>three</li>
  </ul>
</blockquote>

In my opinion, it would make sense to convert this to:

> 1. one
> 2. two
> 3. three

Of course you lose information in doing this (namely the id attribute) but you have to decide: are you using Markdown or HTML?

Opinions will of course vary.

Weighty issues indeed! But this is what I’m struggling with as I’m working on my list parsing while trying to prevent my lexer from becoming a pushdown automaton.

More Details on JMD Markdown Parsing

2010-01-13T23:03:00.003+08:00

I’ve reached an important milestone tonight. As previously mentioned I’m working on a non-regex Markdown library for Java (and other languages to follow).

The goals of this project are:

To be feature complete for standard Markdown as well as the StackOverflow/Github extensions;
To add table support;
To support various Wiki markdown flavours; and
To convert from Markdown to HTML and from HTML to Markdown.

There looks like being four steps in this process.

The first step I’ve called lexical analysis but it’s part scanning and part parsing mainly because to do it at this stage is convenient and saves me a lot of grief later. The end result of this step is a list of Tokens, which is highly memory efficient. The Token object only requires 4 integers each and for a source file 10K in size you’ll probably end up with between 2,000 and 5,000 tokens.

The second step, which I’m not convinced will remain, is a rewrite step. There are a couple of awkward cases I don’t want to handle in the third step so I filter the list of tokens at this point.

The last step is to take the list of tokens and to generate a Document. A Document is basically an Abstract Syntax Tree and looks a lot like a DOM.

The last step is to use the Visitor pattern to render an HTML document.

Tonight I have working code that does all four steps. It is still very much feature incomplete. Lots of inline styling doesn’t work. Neither do reference images, reference links nor any kind of list. Still it is correctly handling nested block quotes, implicit paragraphs and paragraph breaks and indented code blocks.

As of right now it is converting (the Code_blocks unit test from MarkdownSharp):

 code block on the first line
 
Regular text.

    code block indented by spaces

Regular text.

 the lines in this block  
 all contain trailing spaces  

Regular Text.

 code block on the last line

into this:

<pre><code>code block on the first line
</code></pre>

<p>Regular text.</p>

<pre><code>code block indented by spaces
</code></pre>

<p>Regular text.</p>

<pre><code>the lines in this block  
all contain trailing spaces  
</code></pre>

<p>Regular Text.</p>

<pre><code>code block on the last line</code></pre>

in 5 microseconds.

Let me repeat that: it looped through that conversion one million times in under 5 seconds… in pure Java! To compare, my regex solution is doing this in 600-700 microseconds (that’s based on the 1.006 MarkdownSharp code; 1.009 has improved block handling, which should make a difference).

Now you might look at that document and say it’s not that complicated (and you’d be right) but all the infrastructure is there. I know how I’m going to implement the rest and I can’t imagine anything (other than auto-linking) significantly affecting performance. What’s more even if it was 100 times slower I’d still be happy. I’m working on a worst case of it being 10 times slower when feature complete.

So far I haven’t used a single regular expression and don’t think I’ll need to apart from maybe link validation. I’ll document more about the design in future posts (after the code is released probably) to explain many optimizations you can make to this process as well as the overall parsing strategy. So far there has been almost zero need for lookahead and backtracking, which is generally what kills your performance (without complicated techniques like memoization).

Stay tuned…

JMD, Markdown and a Brief Overview of Parsing and Compilers

2010-01-11T07:19:00.003+08:00

Like most comp sci students, I did a course on compilers in university. I also did some parsing and syntax trees in a data structures course. At the time I wrote a couple of parsers, including one for simplifying boolean expressions (de Morgen’s laws, a AND true = a, etc) and another for evaluating arithmetic expressions.

So I’ve been familiar with the basics and the theory of compiler design but I was by no means an expert.

Recently, I launched JMD, a Java implementation of MarkdownSharp, itself a C# port and extension of the original Perl Markdown scripts. Like the original it relies heavily on regular expressions.

I like the idea of e and improving Markdown but I’m no fan of using complicated regular expressions for that purpose. The current version is a milestone. It passes the unit tests and allows me to better build the replacement, which will be written more in the traditional compiler/translator sense.

Finite State Machines

A finite state machine (“FSM”) defines two things: a finite number of states and transitions between them. This abstract machines models behaviour of some kind.

Often—but not always—such machines have a start state and one or more end states. FSMs are typically used for games, input processing and many other things.

One important characteristic of such machines is that they typically have no memory. They merely know the current state and what transitions there are.

Typically in computer science we’re more concerned with a special class of FSMs called deterministic finite state machines (“DFSM”) or deterministic finite automata (“DFAs”). The key difference is that transitions are deterministic, meaning there is only one transition between two states with a given input symbol.

Another characteristic of finite state machines is whether they are cyclic or acyclic. If there exists a state such that a transition can be taken and it is possible to return to that same state the FSM is cyclic, otherwise it is acyclic. By definition, cyclic FSMs are capable of processing an infinite space of inputs. Acyclic FSMs are not.

Regular Expressions

The most familiar DFA for most programmers will probably be regular expressions. a regular expression (“regex”) is a shorthand way of building a DFA to process text input by specifying the optionality, cardinality, capturing and ordering of character sequences. Typically programs will determine if a given input matches a specified regex or whether or not that regex can be found anywhere in the input and possibly capture key parts of that input.

Undoubtedly regexes are useful but they tend to be overused. Consider them a shining example of how once you have a hammer everything starts to look like a nail. In particular programmers will often try to use them to parse HTML or XML documents, which tends to be a pet peeve of Stackoverflow answeres such as myself.

The reason they are a poor choice is that HTML is not a regular language. What that means is that it is not possible to parse and validate HTML with a DFA. That’s because things like proper nesting of tags, ordering of opening and closing tags, etc require the machine to have some kind of memory, which DFAs don’t have.

You see that in regex-based Markdown parsers where limitations are imposed to make it possible to parse Markdown, such as introducing a nesting depth limit to certain block level elements.

To give you an example: if you’re looking for links, will “<a[ >]” find them? Most of the time? Yes. But not all the time. Consider the case of such expressions appearing in attributes, XML CDATA blocks, inside XML, CSS or Javascript comments, inside Javascript strings, etc. Regexes can’t detect these kinds of corner cases. It simply isn’t capable. Not reliably at least.

As it turns out a fairly simple change greatly enhances the power of DFAs.

Pushdown Automata

Pushdown Automata (“PDAs”) make the simple change of adding a stack (hence “pushdown”), giving the machine a memory (of sorts) beyond the current state. To clarify, the machine can both inspect and manipulate the stack both in deciding what transition to take and what to do with the stack.

This allows PDAs to process a much broader set of languages. A language that can be processed by a PDA is called a context-free language (“CFL”), which is a superset of all regular languages.

If a PDA is deterministic (much like FSMs vs DFAs) then it is called a deterministic pushdown automaton (“DPDA”). Any languages that can be parsed by DPDAs are called deterministic context-free languages (“DFCLs”), which are a subset of CFLs.

Going back to regular expressions and HTML/XML parsing: with the addition of this stack, suddenly your parsing becomes much more reliable. You can stop looking for anchors when you enter a Javascript block or a comment and so on.

Many programming languages are CFLs but certainly not all.

Context-Sensitive Languages

The next broader class of languages are called context-sensitive languages. CFLs are a subset of context-sensitive languages. C++ is the traditional poster-child for hard-to-parse languages. It’s grammar is also context-sensitive. Take the following expression:

A a = B();

Is that a method call or object construction? You can’t tell without looking up B in the symbol table.

Ruby and some other programming languages are context-sensitive. HTML/XML is also in this category and so is Markdown. For example:

> Block quote <p
> >

Is the second > on the second line the start of a nested block quote or the closing part of the paragraph tag at the end of the first line?

Not only is this context-sensitive it’s also ambiguous. Technically we call this a non-determinism.

Once again returning to parsing a document for anchors, context-sensitivity bridges the remaining gap. Cases like being inside a comment or not represent the kind of context-sensitivity that is unmanageable for regular languages.

Grammars, Lexers and Parsers

A formal grammar (or just “grammar” for short) is a set of rules that describe a sequence of tokens. A token sequence is often called a sentence. The set of all sentences described by a given grammar is the language for that grammar. Note: a context-free language is described by a context-free grammar (“CFG”), etc.

Compilers, interpreters and translators are typically written in at least two parts (that are of interest to us): a lexer and a parser. Simple grammars may be implemented where the lexer and parser are combined. More complicated grammars may have many parsing steps.

A lexer or lexical analyzer or scanner or recognizer reads a set of input tokens—most often a character stream—and converts them into lexemes or tokens. For example, a lexer for arithmetic expressions may convert:

4+5*7

into

NUMBER(4) OP(+) NUMBER(5) OP(*) NUMBER(7)

A parser is a program that interprets a stream of lexemes by a set of rules. Those rules are defined in terms of lexems and/or other rules, or even the same rule (although anything other than tail-recursion in grammar rules tends to be problematic and is usually factored out either manually because the parser won’t accept it or automatically).

This distinction is somewhat artificial and a little blurred. ANTLR maeks the definition that lexer rules are terminating rules and parser rules are non-terminating. “Terminating” means the rules is not defined in terms of any other rules and as such can at best resolve to a lexeme.

Types of Parsers

At the top level there are two main types of parsers.

The first category are LL-parsers. Here each L stands for “left to right”. Basically this means the parser is top-down. The parser attempts to match the input to a rule and in doing so will attempt to match input tokens to lexemes. The other L means the input tokens are matched left-to-right too (ie from hte beginning).

LL parsers vary in their degree of lookahead. The simplest LL parsers are LL(1), meaning they lookahead one token. An LL parser cannot choose between:

r : A B
  | A C
  ;

An LL(2) parser however can. LL parsers with a finite amount of lookahead are also called LL(k) parsers. Arbitrary lookahead LL parsers are called LL(*) parsers.

The other main category is LR parsers. The input tokens are still read from the beginning but instead of trying to match rules, the parser will look at the input and try to construct tokens. From those tokens it will then look for rules and match the input that way.

The most important subset of LR parsers are LALR parsers. Frankly it’s been too many years for me to remember the difference between LR and LALR parsers.

There are various strengths and weaknesses of each approach, which is beyond the scope of this post. Generally though, LL parsers are easier to understand but LR parsers are more often used by compiler compilers. A compiler compiler is a tool that takes a formal grammar and creates a compiler, parser, interpreter or translator.

Another class of parsers is parsing expression grammars (“PEGs”). I know far less about these. They’re fairly new but at least one Markdown parser, Lunamark, has been written with a PEG parser.

ANTLR

Apparently Joel and Jeff discussed this issue in this week's Stackoverflow podcast. They ruminated that it would have been better had Markdown been written using a formal grammar and a tool such as bison. I agree and they provide a pretty good example of how horrifying regex parsing of non-regular languages can be.

My own journey towards a non-regex solution first took me to ANTLR (“ANother Tool for Language Recognition”), which has a good GUI for debugging parsers. ANTLR is an LL(*) parser with some extensions. One of these is syntactic predicates. Syntactic predicates increase the recognition power of LL parsers by resolving some ambiguities that LL parsers otherwise can’t handle.

For example, consider the following Markdown:

> This is a *test of
> blockquoting*,
> emphasis and
> http://www.google.com
> (autolinking)
A paragraph.

When I was playing around with ANTLR this was problematic to parse. The natural way is to remove the blockquoting and then parse the remaining text, probably recursively.

One “problem” with LL parses is that they attempt to match all the rule alternatives so if you wanted to write the above as:

document : (para | quote)* ;
para     : ((~ '\n') '\n')+ ;
quote    : ('> ' (~ '\n')*)+ ;

you’ve actually created an ambiguous grammar because the para rule can match quote lines can be matched by the para rule. Syntactic predicates seek to resolve this kind of ambiguity by saying things like “if it looks like a block quote then it’s a block quote” when choosing between possible alternatives.

Another problem I ran into was how to deal with things like auto-linking URLs?

Throw in limited XML/HTML parsing and it just became a hair-pulling exercise. Basically it just seemed to be the wrong tool for this particular job. Now that doesn’t mean it can’t be done. Someone more skilled than I with it no doubt could get it done. I could see the path forward and it wasn’t pretty however.

It’s a shame really because I like ANTLR. Terence Parr, the author of ANTLR and all-round language tool rock star, has written an excellent book The Definitive ANTLR Reference: Building Domain-Specific Languages and I can’t recommend this enough.

The Future of JMD

One commentor asked:

How is it better/different than MarkdownJ?

It’s a good question. The answer is that JMD will use a true parser rather than a hash of regexes to parse and process Markdown. It’ll also do a lot more than this but more on this later when its closer to fruition.

The ANTLR exercise wasn’t a complete waste. I had a choice to see if LALR parsing would offer a better alternative. The ANTLR experiment did solidify in my mind how I would go about parsing Markdown.

I’m convinced that a hand-coded parser is not only possible but it’s relatively straightforward.

Preliminary results look extremely promising. It’s not feature-complete yet and I won’t release it until it passes a significant portion of the unit tests inherited from MarkdownSharp.

Initial results indicate it will be 50-100x faster than a regex solution. The lexical analysis so far is being done in a single pass using virtually no memory and is taking between 10 and 20 microseconds to tokenize a document about the size of one of the unit tests.

Conclusion

I hope this post has been useful in three respects:

To give a brief overview of the field of compiler compilers;
To explain my thought process behind how to take JMD forward; and
Why I’m doing what I’m doing.

Watch this space.

Announcing JMD: Java MarkDown (port of MarkdownSharp)

2010-01-04T19:39:00.003+08:00

By a strange coincidence when I was looking for text editing options for another project, the Stackoverflow guys released MarkdownSharp last week, being a C# port and extension to what was originally written in Perl.

A couple of days later I have JMD (Java MarkDown) with the same extensions and unit tests. At this stage—and certainly while the code stabilizes and work progresses in passing all the tests—it is an almost line-for-line translation of the C# source as this makes it easier to apply patches. This isn’t the Java Way, in particular Java favours a more DI-centric approach typified by Spring rather than static configuration.

Ugliness and architectural issues aside, it will do for now. You can:

Download it from the Downloads page; or
Retrieve it from Github at git://github.com/cletus/jmd.git.

It is built with Maven and should build out of the box (assuming correctly configured Maven). Running on my machine:

Intel Q9450 CPU (2.66GHz);
8GB DDR2 RAM;
Windows 7 Ultimate 64; and
Intel X25-M G2 80GB SSD.

The results are:

JMD test run

1   Amps_and_angle_encoding                                 OK
2   Auto_links                                              OK
3   Backslash_escapes                                       OK
4   Blockquotes_with_code_blocks                            OK
5   Code_Blocks                                             OK
6   Code_Spans                                              OK
7   Hard_wrapped_paragraphs_with_list_like_lines            OK
8   Horizontal_rules                                        OK
9   Images                                                  OK
10  Inline_HTML_Advanced                                    Mismatch
11  Inline_HTML_comments                                    OK
12  Inline_HTML_Simple                                      OK
13  Links_inline_style                                      OK
14  Links_reference_style                                   OK
15  Links_shortcut_references                               OK
16  Literal_quotes_in_titles                                OK
17  Markdown_Documentation_Basics                           OK
18  Markdown_Documentation_Syntax                           OK
19  Nested_blockquotes                                      OK
20  Ordered_and_unordered_lists                             Mismatch
21  Strong_and_em_together                                  OK
22  Tabs                                                    OK
23  Tidyness                                                OK^

Tests      : 23
OK         : 21 (^ 1 whitespace differences)
Mismatch   : 2

input string length: 475
4000 iterations in 6.301 seconds (1.575 ms per iteration)
input string length: 2356
1000 iterations in 6.390 seconds (6.390 ms per iteration)
input string length: 27737
100 iterations in 10.503 seconds (105.031 ms per iteration)
input string length: 11075
1 iteration in 0.037 seconds
input string length: 88607
1 iteration in 0.518 seconds
input string length: 354431
1 iteration in 4.992 seconds

To compare, on the same machine, these are the MarkdownSharp results in Visual Studio 2008:

MarkdownSharp v1.006 test run on \mdtest-1.1

001 Amps_and_angle_encoding                                OK
002 Auto_links                                             OK
003 Backslash_escapes                                      OK^
004 Blockquotes_with_code_blocks                           OK
005 Code_Blocks                                            OK
006 Code_Spans                                             OK
007 Hard_wrapped_paragraphs_with_list_like_lines           OK
008 Horizontal_rules                                       OK
009 Images                                                 OK
010 Inline_HTML_Advanced                                   Mismatch
011 Inline_HTML_comments                                   OK
012 Inline_HTML_Simple                                     OK
013 Links_inline_style                                     OK
014 Links_reference_style                                  OK
015 Links_shortcut_references                              OK
016 Literal_quotes_in_titles                               OK
017 Markdown_Documentation_Basics                          OK
018 Markdown_Documentation_Syntax                          OK
019 Nested_blockquotes                                     OK
020 Ordered_and_unordered_lists                            Mismatch
021 Strong_and_em_together                                 OK
022 Tabs                                                   OK
023 Tidyness                                               OK^

Tests        : 23
OK           : 21 (^ 2 whitespace differences)
Mismatch     : 2

MarkdownSharp v1.006 test run on \test-input

001 markdown-readme                                        OK
002 reality-check                                          OK

Tests        : 2
OK           : 2
Mismatch     : 0


MarkdownSharp v1.006 benchmark, takes 10 ~ 30 seconds...

input string length: 475
4000 iterations in 3827 ms (0.95675 ms per iteration)
input string length: 2356
1000 iterations in 4205 ms (4.205 ms per iteration)
input string length: 27737
100 iterations in 4736 ms (47.36 ms per iteration)
input string length: 11075
1 iteration in 23 ms
input string length: 88607
1 iteration in 191 ms
input string length: 354431
1 iteration in 1025 ms

So Java is roughly half the speed of C# in this regard, which is more difference than I’d expect for what is essentially the same code. At this preliminary stage I can only attribute this to the .Net Regex libraries being better.

JMD is released under the same permissive MIT license as MarkdownSharp. Please feel free to use it, let me know what you think or to contribute.

Java: Why-oh-why still no multi-line strings?

2010-01-02T07:50:00.001+08:00

Over the last year or two I’ve been doing a lot of PHP (which I really like).One of the things I use a lot is heredoc syntax eg:

$query = <<<END
SELECT *
FROM tablename
WHERE condition1 = $field
AND condition2 = 345
END;

This is much more convenient than, say:

String query =
  "SELECT * " + // MUST remember to put a space here!
  "FROM tablename " +
  "WHERE condition1 = " + field + " " + 
  "AND condition2 = 345";

I’ve been doing quite a bit of Java recently and it’s really starting to bug me. I don't understand why pretty much every other imperative language invented in the last 15 years can have some form of multi-line string syntax but Java still doesn’t.

Java 6 was released over three years ago. Java 7—thanks largely to the unexpected (yet welcome) inclusion of closures—isn’t due for nearly another year. Four years between releases.

Surely Java could have gotten something in that time. Even if it’s the rather ugly (imho) triple-quote syntax of Scala/Groovy it’d be better than nothing.

Anyway, I just needed to get that out.

Happy New Year for 2010.

Mutability, Arrays and the Cost of Temporary Objects in Java

2009-12-29T21:13:00.001+08:00

In his 2001 must-read book, Effective Java, Joshua Bloch said in one item “Favor immutability”. Java theory and practice: To mutate or not to mutate? provides an excellent overview of what this means and why it matters. It states:

An immutable object is one whose externally visible state cannot change after it is instantiated.

A Brief Overview of Immutability

Let’s say you want to create a class to model arbitrary precision rational numbers (ie fractions). A mutable version might start out:

public class BigRational {
  private BigInteger numerator = BigInteger.ZERO;
  private BigInteger denominator = BigInteger.ONE;

  // constructors and so on

  public BigRational add(BigRational other) {
    if (numerator.signum() == 0) {
      numerator = other.numerator;
      denominator = other.denominator;
    } else if (other.numerator.signum() == 0) {
      // no action required
    } else if (denominator.equals(other.denominator)) {
      numerator = numerator.add(other.numerator);
    } else {
      // this could be optimized for greatest common divisor
      numerator = numerator.multiply(other.denominator).add(other.numerator.multiply(denominator));
      denominator = denominator.multiply(other.denominator);
    }
    return this;
  }

  // etc
}

This is how many classes naively start. The problem comes when this class is used as a data member or a parameter. Consider this class:

public class MyClass {
  private BigRational data = new BigRational();

  public BigRational getData() {
    return data;
  }
}

Doing this will modify the internal state of the class:

MyClass mc = new MyClass();
BigRational rational = mc.getData();
rational.multiply(rational);

Obviously this behaviour isn’t desirable, which leads to the practice of defensive copying, a practice familiar to any C programmer. Each time this getter is called a temporary copy is created so the internal state of the class isn’t violated.

One of the biggest early errors in Java’s design was that the Date class is mutable. This means that any API that uses dates either has to use a non-standard date class or defensively copy date instances. Oddly, Java got String, BigInteger and BigDecimal all right as they’re all immutable. Even stranger, the later Calendar class (introduced in JDK 1.1) was also made mutable.

An immutable version would look something like:

public class BigRational {
  private final BigInteger numerator;
  private final BigInteger denominator;

  public BigRational() {
    this(BigInteger.ZERO);
  }

  public BigRational(BigInteger integer) {
    this(integer, BigInteger.ONE);
  }

  public BigRational(BigInteger numerator, BigInteger denominator) {
    if (denominator.signum() == 0) {
      throw new IllegalArgumentException("denominator cannot be zero");
    }
    if (numerator.signum() == 0) {
      this.numerator = BigInteger.ZERO;
      this.denominator = BigInteger.ONE;
    } else {
      this.numerator = numerator;
      this.denominator = denominator;
    }
  }

  public BigRational multiply(BigRational other) {
    if (numerator.signum() == 0 || other.numerator.signum() == 0) {
      return new BigRational(BigInteger.ZERO);
    } else if (denominator.equals(other.denominator)) {
      return new BigRational(numerator.add(other.numerator), denominator);
    } else {
      return new BigRational(numerator.multiply(other.denominator).add(other.numerator.multiply(denominator)), enominator.multiply(other.denominator));
    }
  }

  // etc
}

Arrays are Mutable

The big problem with all this is that Java arrays are mutable. So for example:

public void doStuff(String args[]) {
  args[0] = "Hello world";
}

...

String arr[] = new String[] { "one", "two", "three" };
doStuff(arr);
System.out.println(arr[0]); // Hello world

This is one big reason why you should use Lists instead of arrays in almost all circumstances where you have a choice. Lists can be made immutable:

List<String> list = new ArrayList<String>();
list.add("one");
list.add("two");
list.add("three");
final List<String> immutableList = Collections.unmodifiableList(list);

On a side note, this rather verbose syntax gets a little easier in Java 7 with collection literals, for example:

List<String> list = ["one", "two", "three"];
final List<String> immutableList = Collections.unmodifiableList(list);

Enum Values

Java 5 introduced typesafe enums, largely based on Joshua Bloch’s proposal (that used classes). The unofficial versions had lots of potential issues (eg having to implement readResolve() to cater to serialization creating new instances). In my opinion, Java’s enums are one of (increasingly few) significantly better language constructs in Java compared to, say, C# as Java’s enums aren’t just thinly wrapped integers (as they are in C/C++/.Net) and can also have behaviour.

Java enums have a static method called values() which returns an array of all instances of that enum. After the lessons of the Date class, this particular decision was nothing short of shocking. A List would have been a far more sensible choice. Internally this means the array of instances must be defensively copied each time it is called forcing you to write code like this repeatedly:

public enum Season {
  SPRING, SUMMER, AUTUMN, WINTER;

  private static final List<Season> VALUES =
    Collections.unmodifiableList(
      new ArrayList<Season>(Arrays.asList(values())));

  public static List<Season> getValues() { return VALUES; }
}

Is This Really Necessary?

There is nothing inherently wrong with temporary objects. It’s a question of degree. So creating several hundred (or thousand) temporary objects isn’t any big deal. At some point there is such a thing as too many.

I will demonstrate two things here:

The cost of temporary arrays; and
The correct way to generate random enums.

This post was prompted by Java: Pick a random value from an enum? where the poster created a Random on every iteration. Some years ago this was bad because Randoms were seeded with the current time (in milliseconds or even seconds) so you wouldn’t get a particularly random distribution if called in a short space of time and it’s worth answering the question of fairness.

This enum will be used:

public enum Season {
  SPRING, SUMMER, AUTUMN, WINTER;

  private static final List<Season> VALUES1 =
      Collections.unmodifiableList(
          new ArrayList<Season>(Arrays.asList(values())));
  private static final Season[] VALUES2 = values();
  private static final int SIZE = VALUES2.length;
  
  private static final Random RANDOM = new Random();

  public static Season random1() {
    return values()[new Random().nextInt(SIZE)];
  }

  public static Season random2() {
    return values()[RANDOM.nextInt(SIZE)];
  }

  public static Season random3() {
    return VALUES1.get(new Random().nextInt(SIZE));
  }

  public static Season random4() {
    return VALUES1.get(RANDOM.nextInt(SIZE));
  }

  public static Season random5() {
    return VALUES2[new Random().nextInt(SIZE)];
  }

  public static Season random6() {
    return VALUES2[RANDOM.nextInt(SIZE)];
  }
}

with the following test harness:

public class Temporary {
  private static final int COUNT = 30000000;

  public static void main(String args[]) {
    ScheduledExecutorService executor = Executors.newSingleThreadScheduledExecutor();
    MemoryMonitor monitor = new MemoryMonitor();
    executor.scheduleAtFixedRate(monitor, 0, 10, TimeUnit.MILLISECONDS);
    int[] tally = new int[4];
    long baseline = usedMemory();
    long start = System.nanoTime();
    for (int i=0; i<COUNT; i++) {
      tally[Season.random1().ordinal()]++;
    }
    long end = System.nanoTime();
    executor.shutdown();
    try {
      executor.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);
    } catch (InterruptedException e) {
      throw new RuntimeException(e);
    }
    long memoryUsed = monitor.peak() - baseline;
    for (Season season : Season.values()) {
      System.out.printf("%s: %,d%n", season, tally[season.ordinal()]);
    }
    System.out.printf("%nCompleted %,d iterations in %,.3f seconds using %,d bytes%n",
        COUNT, ((end - start) / 1000000) / 1000.0d, memoryUsed
    );
  }

  private static long usedMemory() {
    Runtime runtime = Runtime.getRuntime();
    return runtime.totalMemory() - runtime.freeMemory();
  }

  private static void waitForEnter() {
    try {
      new BufferedReader(new InputStreamReader(System.in)).readLine();
    } catch (IOException e) {
      e.printStackTrace();
    }
  }
}

and

public class MemoryMonitor implements Runnable {
  private final Runtime runtime = Runtime.getRuntime();
  private final List<Long> usage = new ArrayList<Long>();

  @Override
  public void run() {
    usage.add(runtime.totalMemory() - runtime.freeMemory());
  }

  public List<Long> usage() {
    return usage;
  }

  public long peak() {
    return Collections.max(usage);
  }
}

with each method being run in turn.

The Results

Method	Run time (seconds)	Peak Memory Usage (bytes)
random1	9.746	681,288
random2	5.914	665,592
random3	5.123	669,408
random4	1.476	18,376
random5	4.593	661,368
random6	1.056	18,376

From this we can draw several conclusions:

Creating a Random on every invocation is fair (in distribution terms) but has a high cost in temporary objects and CPU time (by a factor of 2-5);
The garbage collector is working as both the arrays and the temporary Random objects contribute to the memory usage but Java is (partially) handling both being created. What this probably means is that both created is triggering a GC;
Using a static copy of the enum values is 2-5x as fast;
A static array copy is about 20-40% quicker than a static List copy; and
The more optimized version uses 30x less memory and runs 10x quicker than the least optimized version.

Conclusion

For significant use of an enum’s values() method, it’s a no brainer: create and use a static copy instead. It’s faster and uses way less memory. On non-trivial applications it will also mean less memory fragmentation and less (possibly expensive) GCs, which is a significant issue with high-usage Web applications.

Hard Numbers on Stackoverflow Careers

2009-12-15T23:21:00.001+08:00

This is a follow-up to Joel Inc., Stackoverflow Careers and Jumping Sharks, posted late last week.

Joel posted Stack Stats this week in which he demonstrates the correlation between Stackoverflow reputation and Careers take-up.

Now the exact meaning of this graph isn’t listed. Is that 30% of users with 50,000 reputation and above have submitted CVs? Let’s assume that it is.

Reputation	Percentage	Users in Range	# of CVs
1,000	8%	3,257	261
2,000	10%	1,196	120
3,000	11%	640	70
4,000	12%	373	45
5,000	13%	244	32
6,000	13.5%	153	21
7,000	14%	112	16
8,000	15%	95	14
9,000	16%	48	8
10,000	17%	220	37
15,000	19.5%	79	15
20,000	22%	58	12
30,000	26%	28	7
50,000	30%	15	5
Total	10.2%	6,518	663

So we have 145 employers (as of 15 Dec 2009) and 663 job seekers of the 6,518 in the sample representing a percentage take-up of 10.2%.

I would guess that the vast majority of those would’ve paid $29 for 3 years so these ~700 uses account for $21,000 revenue over 3 years.

Is this kind of barrier—charging job seekers—really worth that kind of revenue stream?

Of course the hope is both that:

The number of candidates will substantially grow; and
Many (or most) of them will convert to paying $99/year in 3 years.

Three years from now I would consider it optimistic that the users matching the profile might number 40,000 instead of 10 to 25,000. That won’t accurately reflect the natural attrition rate either (there are some users who have already become basically inactive).

Considering that not all users will be looking for work at the same time (assuming Goldman Sachs’ next crackpot house of cards hasn’t come tumbling down yet), it’s hard to imagine the take-up rate being higher than 15-20% and that’s being optimistic.

So if everything goes well 10,000 people are paying $99/year. $1 million a year—basically money for nothing—is nothing to sneeze at. I can’t see it happening however.

Even if it does, it’s questionable whether this is the critical mass required to attract employers. I guess time will tell.

Joel Inc., Stackoverflow Careers and Jumping Sharks

2009-12-10T16:06:00.001+08:00

Joel Spolsky is a legend in the programming world. His blog—Joel on Software—is the most popular and well-known programming blog. In mid-2008, Joel and Jeff Atwood—of Coding Horror fame—launched Stackoverflow, a free site for asking programming questions.

Stackoverflow is clearly a success but the sister sites haven’t fared nearly as well. Recently Jeff and Joel launched Stackoverflow Careers, a site for programmers to find jobs and employers to find programmers.

Stackoverflow Careers may just be a bridge too far.

Let’s Talk About… Joel

Joel on Software was the first blog I ever read. I read it before anyone really knew what a blog was. Controlling Your Environment Makes You Happy was one of those things I read that completely changed my perspective. How Microsoft Lost the API War I consider to be almost prophetic in its predictions regarding the then-Longhorn now-Vista boondoggle and desktop bloodletting by Web applications.

But something isn’t right in the Land of Joel.

In the late 90s during a brief flirtation with strenuous physical activity, I learnt to SCUBA dive. I went to one of these courses that was an evening of instruction of the evils of nitrogen, a weekend in the pool and then a weekend in the ocean. This was a PADI course and is very much the consumer-grade diving education and I state that as a simple observation not a judgement or accusation. At the other end of the spectrum is NAUI.

PADI is all about selling you stuff—gear, courses, whatever. A friend remarked to me that PADI stood for Put Another Dollar In.

NAUI on the other hand is much more highly regarded but less prolific. It is a not-for-profit organisation. Whereas some accuse PADI of dumbing down SCUBA training, nothing of the sort is levelled against NAUI. That same friend said NAUI stands for Not Another Untrained Idiot.

What does this have to do with Joel? Whereas Joel was once the NAUI-like font of wisdom, now it just seems like he’s trying to sell me stuff.

Jumping the Shark

Of course I’m not the first to articulate this.

In recent times Joel has taken quite a bashing, for example Joel Spolsky, Snake-Oil Salesman and Sten Anderson’s I Heart Joel on Software.

Sten’s comments are particularly interesting because what he says is true: all Joel’s endless talk about great programmers is thinly disguised disdain for the 99% of us that didn’t go to MIT, Stanford, UW, Yale, Harvard or UPenn.

Amusingly, Jeff Atwood posted several years ago Has Joel Spolsky Jumped the Shark? going so far as to say:

I reject this new, highly illogical Joel Spolsky. I demand the immediate return of the sage, sane, wise Joel Spolsky of years past. But maybe it's like wishing for a long-running television show to return to its previous glories.

I guess he got over it.

Side note: Jeff was responding to Language Wars (emphasis added by Jeff):

FogBugzis written in Wasabi, a very advanced, functional-programming dialect of Basic with closures and lambdas and Rails-like active records that can be compiled down to VBScript, JavaScript, PHP4 or PHP5. Wasabi is a private, in-house language written by one of our best developers that is optimized specifically for developing FogBugz; the Wasabi compiler itself is written in C#.

I admit it: I love a good rant. And not just ranting for ranting’s sake but a rant with a message, an essential kernel of truth, a pearl of wisdom. It’s hard to forget Zed Shaw’s now-infamous (albeit retracted) Rails is a Ghetto rant of nearly two years ago. Yesterday I read Giles Bowkett’s Blogs are Godless Communist Bullshit. It’s long but entertaining and absolutely worth reading.

But is all this criticism justified?

Firstly, some background.

IT Recruitment

In Europe and Australia programmers (and other IT professionals) are found in three ways:

Direct recruitment by the employer. This usually means big employers who have dedicated HR departments to filter out CVs, book interviews and so on. Such candidates will most likely become salaried employees of the company;
Word of mouth; and
Through recruitment agencies.

In my experience recruitment agents are loathed by IT workers (eg Why is IT recruitment so bad?). Most of the time they’re utterly clueless (I have in all seriousness been asked “I see you have 7 years of Java experience but do you have any J2SE experience?”). Horror stories are legion. IT recruitment in London in particular is a soul-destroying experience.

Recruiters will fill positions on a permanent (salaried) or contract (paid by the hour, day, week or month) basis.

The recruiter will earn a fee that is typically around 10-15% of the candidate’s annual salary upon successfully filling the position. If the employee leaves in the probationary period (typically three months) some or all of that will be refunded.

With contractors the recruiter will typically earn a margin of 10-25% (or even higher) on top of the contractor’s rate either for a fixed term (eg it scales down after a year) or in perpetuity. Expat contractors typically have criminally high margins put on top of what they earn, at least initially.

So recruitment is expensive.

Compare that to placing ads on job boards will typically cost hundreds of dollars (eg jobs.joelonsoftware.com FAQ and Monster Job Posting) and last weeks. One ad can potentially fill multiple positions. Employers will typically keep CVs on file and getting contacted some time after applying is not uncommon. So ads can be effective although there can be a lot of chaff.

IT recruitment is broken so there’s definitely room for a solution.

Stackoverflow Careers

Careers is another site hoping to capitalize on the success of Stackoverflow. Programmers routinely demonstrate the ability to self-organize, which I think explains—at least in part—its success. Computer science is also a centuries-old. Yes I said “centuries old”. So before some reddit lurker points out computers were born in the mid-twentieth century, I suggest you consult the Timeline of computing 2400 BC–1949 and the work of Charles Babbage and others.

The latest money-making venture is Stackoverflow Careers, heavily cross-promoted by Jeff Atwood (Introducing Stack Overflow Careers and Stack Overflow Careers: Amplifying Your Awesome) and Joel (Upgrade your career and Programmer search engine) as well as echoes in the blogosphere.

Despite the success in terms of audience size (Joel in his Google Tech Talk claims a ~30% programmer share, which is huge if true), programmers are a hard bunch to monetize (see Our Amazon Advertising Experiment). Careers is the latest incarnation.

It’s free to have a public CV but having a private CV costs money (allegedly $99/year after 31st December but don’t be surprised if that changes). The private CV is searchable by employers and allows (as Jeff/Joel put it) “deep” integration with Stackoverflow.

The employers are paying too anywhere from $500 for a week to $5,000 for a year (see the FAQ).

Not cheap. So what are we getting for our money?

The Hollywood Analogy

Joel claims:

In Hollywood, studios who need talent browse through portfolios, find two or three possible candidates, and make them great offers. And then they all try to outdo each other providing plush work environments and great benefits.

Make no mistake: you’re being sold something here. The allure of stardom is deliberate bait. Giles succinctly sums this up:

This last part is laugh-out-loud funny. That's not how Hollywood works. I'm an actor, I've been studying acting for years, and I know award-winning actors who still have to go out on auditions like everybody else. You might wonder how a newbie like me, with nothing but Cop #3 in a student film to his credit, can claim to know award-winning, seasoned professionals. It's simple: because they have to go on auditions like everybody else.

I will take one issue with what Giles said:

Robert Downey Jr. had to fight like hell to get the lead role in Iron Man.

Yes, but there’s a reason for that. He had a serious drug problem and any studio is going to balk at betting a billion dollar franchise on a cokehead.

But I digress.

Here’s another difference: actors are basically the most flexible labour market in the world. They go where the work is. The film shoots for 40 weeks in Siberia? Fine, no problem. Actors go where the films are.

Programmers on the other hand are not nearly as flexible. Programmers are regular workers. We have families, friends, mortgages and so on. Sure we might move from St Louis to San Francisco for a job but we also might not. I think it’s safe to say that more often than not, we’re not looking to move across country. Hell, we’ll even turn down a job if it’s in the wrong part of the same city.

Imagine how far you’d get as an actor if you said “I’ve love to work on your TV show but the studio is in Burbank and commute from Radondo Beach is a bitch so i think I’ll pass.” (only knowing LA to change planes I make no apologies for any gross errors in LA geography I may have just made).

So instead of there being a handful of job markets for actors there are probably 100 or more for programmers.

So What’s In It For Me?

From the FAQ:

If you are seeking employment, we do require a modest annual payment to file your CV. Filing your CV makes it eligible to appear in searches by hiring managers via our private search interface. This fee allows us to ensure employers that everyone they find is actively looking for a job.

Isn’t the fact that I’ve filled out a CV and ticked a box that says I’m looking for work sufficient? Apparently not.

Consider Finding Great Developers:

The great software developers, indeed, the best people in every field, are quite simply never on the market.

So the target market seems to be those developers who think they’re great developers but actually aren’t. If they were they wouldn’t be looking. I get it: everyone is better than average.

Giles sums this up:

The number one rule of the con: you can't con an honest man … Try to get something for nothing, just because Joel Spolsky said you could? You're going to get burned.

I should point out that I signed up in the beta. I was under no illusions however (then again, who ever thinks they are?). The chances of an employer looking in my remote backwater are next to nil but I figured at $30, at worst I was out two lunches from Nando's.

And If I’m A Hiring Manager?

Approximately 6,500 Stackoverflow users have 1,000 reputation or more. This is an arbitrary number choice but the point is this: integration with Stackoverflow only adds value if you’ve contributed a sufficiently large number of answers to mine. Go up to 2,000 rep and you’re down to less than 3,200 users. And so on.

Let’s be optimistic and say the potential audience for whom Stackoverflow will add value to their CV is 10,000. A number of these can be eliminated as being students, retired, incapable of working (eg disability or serious prolonged injury) or simply not looking for work.

Joel claims:

But Stack Overflow Careers doesn’t have to be massive. It’s not for the 5.2 million people who visit Stack Overflow; it’s for the top 25,000 developers who participate actively.

Want to know what the 25,000th user looks like?

I mean no disrespect to these people but “participate actively”?

Take careful note of the language too: 25,000 from 5.2 million? Hell, you’re already the top half of one percent! You’re elite, positively l33t! Uh huh.

Crunching the Numbers

There are at least 100 distinct geographical job markets for an employer. If you’re lucky 10% of the pool is accessible to you either by being in the right place or willing to relocate.

Of those 10%, maybe 10% have the right skills. The importance of programming languages is definitely overstated by (typically clueless) HR departments and recruiters. It’s also true that good developers can program in anything (given sufficient time) but not all languages are interchangeable in all situations. I would consider a Java Web developer to be largely interchangeable with an ASP.NET C# Web developer (in that there is sufficient crossover to enable a sufficiently speedy transition) but I wouldn’t hire a Ruby programmer to do C programming for microcontrollers and embedded devices. The transition from unmanaged (eg C/C++) to managed (eg C#/.Net) code can be steep enough.

Of this reduced pool, how many have the right experience? The more experienced you get as a developer, generally the more important domain knowledge becomes. I wouldn’t hire a mobile telephony architect to design a system for market-making options on commodities futures because you’d spend 6 months explaining bid/ask, spreads, what a future is, what an option is, in-the-money, out-the-money, out-the-money, short, long, contango, volatility, Black-Scholes… the list goes on.

Of the remaining few who has the right amount of experience? You wouldn’t hire a fresh college grad to mentor junior developers.

Now you’ve got a short list (“short” being the operative word) consider how many are available?

And you haven’t even interviewed anybody yet!

So if you optimistically assume that 10,000 people sign up for Careers, chances are you’re down to less than five. Of those, how many are seriously looking? They’re paying by the year so why not have your CV out there just in case?

Don’t be fooled, paying to file your CV doesn’t ensure you’re seriously looking. The only thing it ensures is that you’re a revenue stream.

Critical Mass

Matching candidates to employers is low probability. The number who fit the profile is probably 1 in 1,000 or even less.

So of the 10 to 25 thousand relevant potential candidates, some percentage will actually be looking for work. Of that percentage, a smaller percentage will pay to be seen by employers, less than might otherwise be seen if the service was free (for job seekers). I expect that number to be 2,000 or less and that number is, in my opinion, inflated by the cheap beta registration.

So an employer is going to pay big bucks—much more than a typical job ad—to reach a much smaller target audience?

People will pay money if they are getting value for money. Paying $15,000 to a recruiter to find you a programmer is cheap because the recruiter is doing most of the legwork and assuming a large part of the risk (in that they don’t typically get paid if you don’t find someone you like). Job ads are cheap because they may reach tens or even hundreds of thousands of candidates.

It’s like Careers is charging as if it’s already a proven success.

Things like this work on the principle of critical mass. Take eBay. People buy on eBay because there are things to be bought. People sell on eBay because people will buy them. Without either group the site fails. A job board is no different. People go to them because they have jobs they want. Companies advertise on them because they reach the right audience.

So what job board—and let’s be honest; that’s what it is—is going to survive by restricting itself to 10 to 25 thousand candidates globally? Perhaps Jeff and Joel are thinking that it will be so successful that everyone else will just have to sign up anyway.

Good luck with that business strategy.

Is It Legal?

I have to wonder if anyone has bothered to ask this yet. Consider Job seekers are hit by illegal fees. Not just in the United Arab Emirates is it illegal to charge job seekers. Also, How job seekers can best use recruitment agencies (emphasis added):

Recruitment agencies make their money by charging employers a fee for a permanent hire or an hourly or daily margin on a temporary placement. It is illegal to charge job seekers a fee for finding them work.

That’s for Australia. The point here is that Jeff and Joel probably need to be very careful about how they define the Careers site if they don’t want to run afoul of laws set up to protect the unemployed from unscrupulous practices.

Smoke and Mirrors

From the FAQ:

If you are seeking employment, we do require a modest annual payment to file your CV. Filing your CV makes it eligible to appear in searches by hiring managers via our private search interface. This fee allows us to ensure employers that everyone they find is actively looking for a job.

We’re being sold something here.

Also consider Upgrade your career:

Employers can see how good you are at communicating, …

… how well you explain things, …

… how well you understand the tools that you’re using, …

Er… OK.

… and generally, if you’re a great developer or not.

Whoa. Sorry, but the fact that I know how that parsing HTML with regular expressions is retarded, I can explain how to add a jQuery click() handler and that not sanitizing user input to SQL statements is idiotic doesn’t make me a great developer. It means anything from I like teaching to I’m narcissistic enough to like hearing the sound of my own voice (virtually speaking), perhaps both.

And let’s not forget that all of this can be established by simply including a URL to your Stackoverflow profile on your CV.

Conclusion

The numbers just don’t add up on this one. My only question is how long it’ll be before that sinks in and the model changes. With so much free choice, its just not viable to charge job seekers while severely limiting the candidate pool for employers while charging them an arm and a leg for information they can get from a URL.

Google Wave Invites to Give Away

2009-12-09T09:34:00.003+08:00

I've got a dozen or so of these I don't really need. Drop me a line and I'll send you one, first in first served until they run out.

Programming Puzzles, Chess Positions and Huffman Coding

2009-12-07T19:34:00.003+08:00

This week Andrew Rollings asked the question ProgrammerPuzzle: Encoding a chess board state throughout a game on StackOverflow.

Now I’ll admit that I love this kind of question. I’m not really such a big fan of Code Golf as that’s an exercise in writing terse, unreadable code (although some of the solutions have been brilliant). But this Chess problem is the sort of thing that will allow a programmer to demonstrate his or her mental acuity and problem solving ability (or the lack thereof).

The Problem

What is the most space-efficient way you can think of to encode the state of a chess game (or subset thereof)? That is, given a chess board with the pieces arranged legally, encode both this initial state and all subsequent legal moves taken by the players in the game.

This image illustrates the starting Chess position. Chess occurs on an 8x8 board with each player starting with an identical set of 16 pieces consisting of 8 pawns, 2 rooks, 2 knights, 2 bishops, 1 queen and 1 king as illustrated here:

Positions are generally recorded as a letter for the column followed by the number for the row so White’s queen is at d1. Moves are most often stored in algebraic notation, which is unambiguous and generally only specifies the minimal information necessary. Consider this opening:

1. e4 e5
2. Nf3 Nc6
3. …

which translates to:

White moves king’s pawn from e2 to e4 (it is the only piece that can get to e4 hence “e4”);
Black moves the king’s pawn from e7 to e5;
White moves the knight (N) to f3;
Black moves the knight to c6.

The board looks like this:

An important ability for any programmer is to be able to correctly and unambiguously specify the problem.

So what’s missing or ambiguous? A lot as it turns out.

Board State vs Game State

The first thing you need to determine is whether you’re storing the state of a game or the position of pieces on the board. Encoding simply the positions of the pieces is one thing but the problem says “all subsequent legal moves”. The problem also says nothing about knowing the moves up to this point. That’s actually a problem as I’ll explain.

Castling

The game has proceeded as follows:

1. e4 e5
2. Nf3 Nc6
3. Bb5 a6
4. Ba4 Bc5

The board looks as follows:

White has the option of castling. Part of the requirements for this are that the king and the relevant rook can never have moved, so whether the king or either rook of each side has moved will need to be stored. Obviously if they aren’t on their starting positions, they have moved otherwise it needs to be specified.

There are several strategies that can be used for dealing with this problem.

Firstly, we could store an extra 6 bits of information (1 for each rook and knight position) to indicate whether that piece had moved. We could streamline this by only storing a bit for one of these six squares if the right piece happens to be in it. Alternatively we could treat each unmoved piece as another piece type so instead of 6 piece types on each side (pawn, rook, knight, bishop, queen and king) there are 8 (adding unmoved rook and unmoved king).

En Passant

Another peculiar and often-neglected rule in Chess is En Passant.

The game has progressed.

1. e4 e5
2. Nf3 Nc6
3. Bb5 a6
4. Ba4 Bc5
5. O-O b5
6. Bb3 b4
7. c4

Black’s pawn on b4 now has the option of moving his pawn on b4 to c3 taking the White pawn on c4. This only happens on the first opportunity meaning if Black passes on the option now he can’t take it next move. So we need to store this.

If we know the previous move we can definitely answer if En Passant is possible. Alternatively we can store whether each pawn on its 4th rank has just moved there with a double move forward. Or we can look at each possible En Passant position on the board and have a flag to indicate whether its possible or not.

Promotion

It is White’s move. If White moves his pawn on h7 to h8 it can be promoted to any other piece (but not the king). 99% of the time it is promoted to a Queen but sometimes it isn’t, typically because that may force a stalemate when otherwise you’d win. This is written as:

56. h8=Q

This is important in our problem because it means we can’t count on there being a fixed number of pieces on each side. It is entirely possible (but incredibly unlikely) for one side to end up with 9 queens, 10 rooks, 10 bishops or 10 knights if all 8 pawns get promoted.

Stalemate

When in a position from which you cannot win your best tactic is to try for a stalemate. The most likely variant is where you cannot make a legal move (usually because any move when put your king in check). In this case you can claim a draw. This one is easy to cater for.

The second variant is by threefold repetition. If the same board position occurs three times in a game (or will occur a third time on the next move), a draw can be claimed. The positions need not occur in any particular order (meaning it doesn’t have to the same sequence of moves repeated three times). This one greatly complicates the problem because you have to remember every previous board position. If this is a requirement of the problem the only possible solution to the problem is to store every previous move.

Lastly, there is the fifty move rule. A player can claim a draw if no pawn has moved and no piece has been taken in the previous fifty consecutive moves so we would need to store how many moves since a pawn was moved or a piece taken (the latest of the two. This requires 6 bits (0-63).

Whose Turn Is It?

Of course we also need to know whose turn it is and this is a single bit of information.

Two Problems

Because of the stalemate case, the only feasible or sensible way to store the game state is to store all the moves that led to this position. I’ll tackle that one problem. The board state problem will be simplified to this: store the current position of all pieces on the board ignoring castling, en passant, stalemate conditions and whose turn it is.

Piece layout can be broadly handled in one of two ways: by storing the contents of each square or by storing the position of each piece.

Simple Contents

There are six piece types (pawn, rook, knight, bishop, queen and king). Each piece can be White or Black so a square may contain one of 12 possible pieces or it may be empty so there are 13 possibilities. 13 can be stored in 4 bits (0-15) So the simplest solution is to store 4 bits for each square times 64 squares or 256 bits of information.

The advantage of this method is that manipulation is incredibly easy and fast. This could even be extended by adding 3 more possibilities without increasing the storage requirements: a pawn that has moved 2 spaces on the last turn, a king that hasn’t moved and a rook that hasn’t moved, which will cater for a lot of previously mentioned issues.

But we can do better.

Base 13 Encoding

It is often helpful to think of the board position as a very large number. This is often done in computer science. For example, the halting problem treats a computer program (rightly) as a large number.

The first solution treats the position as a 64 digit base 16 number but as demonstrated there is redundancy in this information (being the 3 unused possibilities per “digit”) so we can reduce the number space to 64 base 13 digits. Of course this can’t be done as efficiently as base 16 can but it will save on storage requirements (and minimizing storage space is our goal).

In base 10 the number 234 is equivalent to 2 x 10² + 3 x 10¹ + 4 x 10⁰.

In base 16 the number 0xA50 is equivalent to 10 x 16² + 5 x 16¹ + 0 x 16⁰ = 2640 (decimal).

So we can encode our position as p₀ x 13⁶³ + p₁ x 13⁶² + ... + p₆₃ x 13⁰ where p_i represents the contents of square i.

2²⁵⁶ equals approximately 1.16e77. 13⁶⁴ equals approximately 1.96e71, which requires 237 bits of storage space. That saving of a mere 7.5% comes at a cost of significantly increased manipulation costs.

Variable Base Encoding

In legal boards certain pieces can’t appear in certain squares. For example, pawns cannot occur at in the first or eighth ranks, reducing the possibilities for those squares to 11. That reduces the possible boards to 11¹⁶ x 13⁴⁸ = 1.35e70 (approximately), requiring 233 bits of storage space.

Actually encoding and decoding such values to and from decimal (or binary) is a little more convoluted but it can be done reliably and is left as an exercise to the reader.

Variable Width Alphabets

The previous two methods can both be described as fixed-width alphabetic encoding. Each of the 11, 13 or 16 members of the alphabet is substituted for another value. Each “character” is the same width but the efficiency can be improved when you consider that each character is not equally likely.

Consider Morse code (pictured left). Characters in a message are encoded as a sequence of dashes and dots. Those dashes and dots are transferred over radio (typically) with a pause between them to delimit them.

Notice how the letter E (the most common letter in English) is a single dot, the shortest possible sequence, whereas Z (the least frequent) is two dashes and two beeps.

Such a scheme can significantly reduce the size of an expected message but comes at the cost of increasing the size of a random character sequence.

It should be noted that Morse code has another inbuilt feature: dashes are as long as three dots so the above code is created with this in mind to minimize the use of dashes. Since 1s and 0s (our building blocks) don’t have this problem, it’s not a feature we need to replicate.

Lastly, there are two kinds of rests in Morse code. A short rest (the length of a dot) is used to distinguish between dots and dashes. A longer gap (the length of a dash) is used to delimit characters.

So how does this apply to our problem?

Huffman Coding

There is an algorithm for dealing with variable length codes called Huffman coding. Huffman coding creates a variable length code substitution, typically uses expected frequency of the symbols to assign shorter values to the more common symbols.

In the above tree, the letter E is encoded as 000 (or left-left-left) and S is 1011. It should be clear that this encoding scheme is unambiguous.

This is an important distinction from Morse code. Morse code has the character separator so it can do otherwise ambiguous substitution (eg 4 dots can be H or 2 Is) but we only have 1s and 0s so we choose an unambiguous substitution instead.

Below is a simple implementation:

private static class Node {
  private final Node left;
  private final Node right;
  private final String label;
  private final int weight;

  private Node(String label, int weight) {
    this.left = null;
    this.right = null;
    this.label = label;
    this.weight = weight;
  }

  public Node(Node left, Node right) {
    this.left = left;
    this.right = right;
    label = "";
    weight = left.weight + right.weight;
  }

  public boolean isLeaf() {
    return left == null && right == null;
  }

  public Node getLeft() {
    return left;
  }

  public Node getRight() {
    return right;
  }

  public String getLabel() {
    return label;
  }

  public int getWeight() {
    return weight;
  }
}

private static class WeightComparator implements Comparator<Node> {
  @Override
  public int compare(Node o1, Node o2) {
    if (o1.getWeight() == o2.getWeight()) {
      return 0;
    } else {
      return o1.getWeight() < o2.getWeight() ? -1 : 1;
    }
  }
}

private static class PathComparator implements Comparator<String> {
  @Override
  public int compare(String o1, String o2) {
    if (o1 == null) {
      return o2 == null ? 0 : -1;
    } else if (o2 == null) {
      return 1;
    } else {
      int length1 = o1.length();
      int length2 = o2.length();
      if (length1 == length2) {
        return o1.compareTo(o2);
      } else {
        return length1 < length2 ? -1 : 1;
      }
    }
  }
}

private final static List<String> COLOURS;
private final static Map<String, Integer> WEIGHTS;

static {
  List<String> list = new ArrayList<String>();
  list.add("White");
  list.add("Black");
  COLOURS = Collections.unmodifiableList(list);
  Map<String, Integer> map = new HashMap<String, Integer>();
  for (String colour : COLOURS) {
    map.put(colour + " " + "King", 1);
    map.put(colour + " " + "Queen", 1);
    map.put(colour + " " + "Rook", 2);
    map.put(colour + " " + "Knight", 2);
    map.put(colour + " " + "Bishop", 2);
    map.put(colour + " " + "Pawn", 8);
  }
  map.put("Empty", 32);
  WEIGHTS = Collections.unmodifiableMap(map);
}

public static void main(String args[]) {
  PriorityQueue<Node> queue = new PriorityQueue<Node>(WEIGHTS.size(), new WeightComparator());
  for (Map.Entry<String, Integer> entry : WEIGHTS.entrySet()) {
    queue.add(new Node(entry.getKey(), entry.getValue()));
  }
  while (queue.size() > 1) {
    Node first = queue.poll();
    Node second = queue.poll();
    queue.add(new Node(first, second));
  }
  Map<String, Node> nodes = new TreeMap<String, Node>(new PathComparator());
  addLeaves(nodes, queue.peek(), "");
  for (Map.Entry<String, Node> entry : nodes.entrySet()) {
    System.out.printf("%s %s%n", entry.getKey(), entry.getValue().getLabel());
  }
}

public static void addLeaves(Map<String, Node> nodes, Node node, String prefix) {
  if (node != null) {
    addLeaves(nodes, node.getLeft(), prefix + "0");
    addLeaves(nodes, node.getRight(), prefix + "1");
    if (node.isLeaf()) {
      nodes.put(prefix, node);
    }
  }
}

One possible output is:

	White	Black
Empty	0
Pawn	110	100
Rook	11111	11110
Knight	10110	10101
Bishop	10100	11100
Queen	111010	111011
King	101110	101111

For a starting position this equates to 32 x 1 + 16 x 3 + 12 x 5 + 4 x 6 = 164 bits.

State Difference

Another possible approach is to combine the very first approach with Huffman coding. This is based on the assumption that most expected Chess boards (rather than randomly generated ones) are more likely than not to, at least in part, resemble a starting position.

So what you do is XOR the 256 bit current board position with a 256 bit starting position and then encode that (using Huffman coding or, say, some method of run length encoding). Obviously this will be very efficient to start with (64 0s probably corresponding to 64 bits) but increase in storage required as the game progresses.

Piece Position

As mentioned, another way of attacking this problem is to instead store the position of each piece a player has. This works particularly well with endgame positions where most squares will be empty (but in the Huffman coding approach empty squares only use 1 bit anyway).

Each side will have a king and 0-15 other pieces. Because of promotion the exact make up of those pieces can vary enough that you can’t assume the numbers based on the starting positions are maxima.

The logical way to divide this up is store a Position consisting of two Sides (White and Black). Each Side has:

A king: 6 bits for the location;
Has pawns: 1 (yes), 0 (no);
If yes, number of pawns: 3 bits (0-7+1 = 1-8);
If yes, the location of each pawn is encoded: 45 bits (see below);
Number of non-pawns: 4 bits (0-15);
For each piece: type (2 bits for queen, rook, knight, bishop) and location (6 bits)

As for the pawn location, the pawns can only be on 48 possible squares (not 64 like the others). As such, it is better not to waste the extra 16 values that using 6 bits per pawn would use. So if you have 8 pawns there are 48⁸ possibilities, equalling 28,179,280,429,056. You need 45 bits to encode that many values.

That’s 105 bits per side or 210 bits total. The starting position is the worst case for this method however and it will get substantially better as you remove pieces.

It should be pointed out that there are less than 48⁸ possibilities because the pawns can’t all be in the same square The first has 48 possibilities, the second 47 and so on. 48 x 47 x … x 41 = 1.52e13 = 44 bits storage.

You can further improve this by eliminating the squares that are occupied by other pieces (including the other side) so you could first place the white non-pawns then the black non-pawns, then the white pawns and lastly the black pawns. On a starting position this reduces the storage requirements to 44 bits for White and 42 bits for Black.

Combined Approaches

Another possible optimization is that each of these approaches has its strength and weaknesses. You could, say, pick the best 4 and then encode a scheme selector in the first two bits and then the scheme-specific storage after that.

With the overhead that small, this will by far be the best approach.

Game State

I return to the problem of storing a game rather than a position. Because of the threefold repetition we have to store the list of moves that have occurred to this point.

Annotations

One thing you have to determine is are you simply storing a list of moves or are you annotating the game? Chess games are often annotated, for example:

17. Bb5!! Nc4?

White’s move is marked by two exclamation points as brilliant whereas Black’s is viewed as a mistake. See Chess punctuation.

Additionally you could also need to store free text as the moves are described.

I am assuming that the moves are sufficient so there will be no annotations.

Algebraic Notation

We could simply store the the text of the move here (“e4”, “Bxb5”, etc). Including a terminating byte you’re looking at about 6 bytes (48 bits) per move (worst case). That’s not particularly efficient.

The second thing to try is to store the starting location (6 bits) and end location (6 bits) so 12 bits per move. That is significantly better.

Alternatively we can determine all the legal moves from the current position in a predictable and deterministic way and state which we’ve chosen. This then goes back to the variable base encoding mentioned above. White and Black have 14 possible moves each on their first move, more on the second and so on.

Conclusion

There is no absolutely right answer to this question. There are many possible approaches of which the above are just a few.

What I like about this and similar problems is that it demands abilities important to any programmer like considering the usage pattern, accurately determining requirements and thinking about corner cases.

Chess positions taken as screenshots from Chess Position Trainer.

Reviewing Project Lombok or the Right Way to Write a Library

2009-11-24T23:00:00.001+08:00

You could consider this a parody of my own Spring Batch or How Not to Design an API. Credit where credit is due however and this brings me to Project Lombok.

What is Project Lombok?

Every Java developer knows that Java involves writing a lot of boilerplate code. Create a value object (or “data transfer object”) and you might have a behaviour-less class with a dozen properties. Those twelve statements are the only important thing in the class. After that you create a hundred lines of getters, setters (if not immutable), an equals/hashCode and a toString method, possibly all IDE generated.

This is an error-prone process, even when generated by an IDE. An IDE won’t typically tell you if, say, you add another data member and don’t regenerate your equals and hashCode methods.

Project Lombok seeks to greatly reduce the need for such boilerplate by using annotations to automatically generate it so you don’t have to. This fits in well with my own philosophy:

Lines of Code Are The Enemy

This is not a new or revolutionary idea. Decades ago it was noted that the number of lines of code was an important metric for both programmer productivity and expected bugs, meaning that whether you were dealing with assembly language or Erlang the metrics were roughly the same. This in part explains the steady move towards higher level languages as the more you can get done in one line of code the better.

Bugs per lines of code addresses this point, referencing Code Complete and other sources.

This is why I think things like first-class properties and closures are advantages in the .Net world (over Java): because they can do the same thing with less code, even if you can do the same thing with IDE-generated getters and setters and anonymous inner classes (respectively).

What Can Project Lombok Do?

Project Lombok has seven annotations for minimizing boilerplate code.

@Getter / @Setter

Never write public int getFoo() {return foo;} again.
@ToString
No need to start a debugger to see your fields: Just let lombok generate a
toString for you!
@EqualsAndHashCode
Equality made easy: Generates hashCode and equals implementations
from the fields of your object.
@Data
All together now: A shortcut for @ToString, @EqualsAndHashCode,
@Getter on all fields, and @Setter on all non-final fields. You even get
a free constructor to initialize your final fields!
@Cleanup
Automatic resource management: Call your close() methods safely with
no hassle.
@Synchronized
synchronized done right: Don't expose your locks.
@SneakyThrows
To boldly throw checked exceptions where no one has thrown them before!

The effect can be dramatic. From @Data you can replace this:

import java.util.Arrays;

public class DataExample {
    private final String name;
    private int age;
    private double score;
    private String[] tags;

    public DataExample(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    void setAge(int age) {
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    public void setScore(double score) {
        this.score = score;
    }

    public double getScore() {
        return score;
    }

    public String[] getTags() {
        return tags;
    }

    public void setTags(String[] tags) {
        this.tags = tags;
    }

    @Override
    public String toString() {
        return "DataExample(" + name + ", " + age + ", " + score + ", " + Arrays.deepToString(tags) + ")";
    }

    @Override
    public boolean equals(Object o) {
        if (o == this) return true;
        if (o == null) return false;
        if (o.getClass() != this.getClass()) return false;
        DataExample other = (DataExample) o;
        if (name == null ? other.name != null : !name.equals(other.name)) return false;
        if (age != other.age) return false;
        if (Double.compare(score, other.score) != 0) return false;
        if (!Arrays.deepEquals(tags, other.tags)) return false;
        return true;
    }

    @Override
    public int hashCode() {
        final int PRIME = 31;
        int result = 1;
        final long temp1 = Double.doubleToLongBits(score);
        result = (result * PRIME) + (name == null ? 0 : name.hashCode());
        result = (result * PRIME) + age;
        result = (result * PRIME) + (int) (temp1 ^ (temp1 >>> 32));
        result = (result * PRIME) + Arrays.deepHashCode(tags);
        return result;
    }

    public static class Exercise {
        private final String name;
        private final T value;

        private Exercise(String name, T value) {
            this.name = name;
            this.value = value;
        }

        public static  Exercise of(String name, T value) {
            return new Exercise(name, value);
        }

        public String getName() {
            return name;
        }

        public T getValue() {
            return value;
        }

        @Override
        public String toString() {
            return "Exercise(name=" + name + ", value=" + value + ")";
        }

        @Override
        public boolean equals(Object o) {
            if (o == this) return true;
            if (o == null) return false;
            if (o.getClass() != this.getClass()) return false;
            Exercise<?> other = (Exercise<?>) o;
            if (name == null ? other.name != null : !name.equals(other.name)) return false;
            if (value == null ? other.value != null : !value.equals(other.value)) return false;
            return true;
        }

        @Override
        public int hashCode() {
            final int PRIME = 31;
            int result = 1;
            result = (result * PRIME) + (name == null ? 0 : name.hashCode());
            result = (result * PRIME) + (value == null ? 0 : value.hashCode());
            return result;
        }
    }
}

with

import lombok.AccessLevel;
import lombok.Setter;
import lombok.Data;
import lombok.ToString;

@Data
public class DataExample {
    private final String name;
    @Setter(AccessLevel.PACKAGE)
    private int age;
    private double score;
    private String[] tags;

    @ToString(includeFieldNames = true)
    @Data(staticConstructor = "of")
    public static class Exercise {
        private final String name;
        private final T value;
    }
}

With Annotations? How?

Most developers experience with annotations involves:

Putting @Override in overriden methods;
Using @SuppressWarnings, often to disable an IDE warning about casting generic collections; and
Using API specific annotations in JPA< J2EE, Spring, etc (eg @Resource, @Transactional).

Far fewer developers have ever written an annotation. If you haven’t it’s worth having a read of Sun's Annotation Tutorial. Annotations can be used to basically generate code at compile-time. That’s how Project Lombok works.

Is This Kosher?

There is some debate about this. A certain school of thought believes that code should still compile and possibly even work without the source annotations present. Alternatively, the belief is that annotations shouldn’t be used as a substitute for language features.

Java 7 had debate over many new features, some changing the language. One is first-class properties, to avoid the boilerplate of getters and setters or provide them in a far terser manner, much like C#/.Net does. First-class properties didn’t make it into Java 7. Project Lombok gives a viable alternative.

Possibly more controversial is that you can use @SneakyThrows to throw checked exceptions without declaring them. This stokes the debate that is old as Java itself: are checekd exceptions a mistake? I view them as a failed experiment in software engineering.

So Project Lombok is somewhat controversial (some have even gone so far as to call it a “hack”) so perhaps the best thing to come out of it is the debate about Java and its future. Up until a couple of years ago Java was a hotbed for debate about software design and an incubator for new technologies, methodologies and architectures. Java (though the Spring framework) popularized dependency injection and inversion of control as well as the use of MVC in Web frameworks.

But after Java 5 Sun seems to have lost its way. It lost such luminaries as Joshua Bloch (to Google). Java 5 itself was a huge change and debate still rages about the complexity of Java generics and the wisdom of type erasure. So much so that closures for Java 7 were declined (but out of nowhere, it was announced closures are now coming to Java 7).

Microsoft has demonstrated leadership for pushing the .Net platform forwards to the point that Java is now playing catch-up (which wasn’t the case prior to .Net 3.0/3.5) whereas Java 7 was mired in debate and lacked leadership and vision from Sun about where to go next, complicated by grand misadventures like the stillborn JavaFX.

But anyway, perhaps all this debate will help reinvigorate a Java development community that seems to have given up.

What has Project Lombok Done Right?

Firstly, using Lombok with Maven is easy. I can’t emphasize enough how useful that is. There’s nothing more frustrating than digging around to find the right artifact(s) and/or repositories to get a particular library to work in Maven. Usually it’s not hard but sometimes it is. I have better things to do than try and figure out what someone should just mention in their project’s documentation.

Also the documentation isn’t super-extensive (as, say, Spring’s typically is) but it sure beats some others (eg typical Apache projects). At least there are examples of all the annotations.

Another thing I really like about it is that it generates toString(), hashCode() and equals() methods automatically but unlike some Apache Commons libraries, it doesn’t do it via reflection at run-time.

Lastly, Project Lombok is released under the highly permissive MIT license.

What Could Project Lombok Do Better?

Currently, Project Lombok only integrates (well) with Eclipse. Netbeans and IntelliJ users are out in the cold and support for those two IDEs seems anywhere from far off to never going to happen. I’m a huge fan of IntelliJ and frankly I wouldn’t use any other IDE given the choice. People tend to feel pretty strongly about their IDEs so currently Project Lombok’s lack of IntelliJ support is (unfortunately) a deal breaker.

I’ve had a bit of a look at the IntelliJ plug-in architecture. You can create plug-ins for new languages so all that’s really required is modification to the existing code for Java, assuming it is done with the same mechanism (which is a big and possibly incorrect assumption).

It seems like a serious limitation of IntelliJ’s internal compiler that it can’t handle compile-time annotations like this in a general sense. Surely one compile-time annotation is lie any other, right?

What Features Could Be Added?

Others have taken to this idea, despite the controversy. One such extension is Morbok, which uses the same idea to get rid of the boilerplate of creating loggers in classes.

It’s worth noting that @Cleanup should become obsolete with Java 7 (a year or more from now) with the advent of ARM (“Automatic Resource Management”). Again, this mimics another .Net feature, where such tedious try-catch-finally blocks are abbreviated using using() { … } blocks for anything that implements the IDisposable interface.

One limitation I noticed was that you can’t use @Data on enums. It would be useful to have an enum-specific version of this. One problem that Lombok could solve is the boilerplate around the use of values(). Enum.values() returns an array of the values. Because arrays aren’t immutable this needs to be copied each time you call it. This makes codes like this inefficient:

public enum Gender {
  MALE("M", "male"), FEMALE("F", "female");

  private final static Map LOOKUP;

  static {
    Map map = new HashMap();
    for (Gender gender : values()) {
      map.put(gender.code, gender);
    }
    LOOKUP = Collections.unmodifiableMap(map);
  }

  public static Gender find(String code) {
    return LOOKUP.get(code);
  }

  private final String code;
  private final String description;

  private Gender(String code, String description) {
    this.code = code;
    this.description = description;
  }

  public String getCode() { return code; }
  public String getDescription() { return description; }
}

That could easily be reduced to a couple of Lombok-style annotations. For example:

@Enum
@Finder
public enum Gender {
  MALE("M", "male"), FEMALE("F", "female");

  @Code
  private final String code;
  private final String description;

  private Gender(String code, String description) {
    this.code = code;
    this.description = description;
  }
}

Conclusion

I’m a big fan of Project Lombok. It’s my kind of library: lightweight, practical and doesn’t get in your face, in exactly the way that many Java Web frameworks aren’t. For example, Seam uses a flawed idea (component-oriented JSF) to solve a problem I don’t have. And for those of you that don’t think JSF is a failed experiment, it’s been about to take off for 7+ years now. At some point you just have to accept that it’s not going to work.

I personally come down on the side of the fence that accepts the utility of using annotations as a substitute for language features, especially considering how Java has stalled in that department in recent years (and Java 7 is delayed now til the end of 2010).

If you happen to be an Eclipse user, you’re in luck. Give it a try. If you’re not, well it’s a choice between those red lines under your seemingly non-existent methods and not using Lombok. But hope springs eternal for future IDE support.

Lost in Translation or Why GWT Isn’t the Future of Web Development

2009-10-29T02:03:00.001+08:00

I recently read Is GWT the future of web development? The post postulates that GWT (“Google Web Toolkit”) is the future because it introduces type safety, leverages the existing base of Java programmers and it has some widgets.

Google has recently put their considerable weight behind it, most notably with Google Wave. I’m naturally hesitant to bet against Google or Lars Rasmussen but the fact is that’s what I’m doing.

On Type Safety and Static Typing

In the 90s type-safety and static typing ruled almost unchallenged, first with C then C++ and Java (yes I realize Pascal, Algol-68 and a plethora of other languages came beforehand). Perl was the calling card of smug, bearded Unix systems administrators.

Performance and the challenges of increasing complexity with relatively low-powered hardware (certainly by today’s standards) were the impetus behind this movement. The idea that variables didn’t need to be declared or that the type could morph as required were tantamount to the sky falling.

Between Javascript, PHP, Python, Perl, Ruby and other languages over the last decade (and yes some have a history going far earlier than that) have clearly demonstrated that indeed the sky hasn’t fallen with loose and dynamic typing.

On Leveraging Java Programmers

This sounds good in theory but let me put it to you another way: if you were to write textbooks in German would you write them in German or write them in English and have a tool convert them to German?

Anyone who has studied or knows a second language knows that some things just don’t translate. The same applies to programming languages. Javascript has lots of features that Java doesn’t: first class functions, closures, extension methods, a vastly different “this” context, anonymous objects, dynamic typing and so on.

The problems you face when writing a “cross-compiler” are:

The weaknesses and limitations of the end result are the combined weaknesses of both languages (or “A union B” in a maths context where A and B are the two languages);
The strengths of the end result are the common strengths (“A intersect B”) of the two languages;
The idioms are different; and
Abstractions are leaky. Jeff Atwood characterized this as All Abstractions Are Failed Abstractions.

This is the same basic problem with ORMs like Hibernate: Object-relational impedance mismatch. Every now and again you end up spending half a day figuring the correct combination of properties, annotations, XML and VM parameters to have a query generate the right two lines of SQL that’ll actually be performant.

Another problem is that GWT fools naive Java developers into thinking they don’t need to learn Javascript.

My position can be summed up as: GWT treats Javascript as a bug that needs to be solved.

On Widgets and Maturity

I’ve programmed with GWT. The widget selection is woeful. The standard GWT widgets look awful, even amateurish. There are some third-party options but ExtGWT is a shockingly bad library. SmartGWT looks like a better alternative (and is actually a community effort rather than a split GPL/commercial mish-mash from someone who simply doesn’t understand Java Generics). There aren’t many other choices.

Javascript has many choices: YUI, ExtJS (completely different beast to ExtGWT), Dojo, jQuery UI, SmartClient and others. Not only is there substantially more choice but the choices are substantially more mature.

Development Speed is King

Java Web apps can take minutes to build and deploy. Within certain restrictions you can hot-deploy classes and JSPs. One of the wonderful things about PHP and Javascript development is that the build and deploy step is typically replaced by saving the file you’re working on and clicking reload on your browser.

GWT compiles are brutal, so much so that significant effort has gone into improving the experience with GWT 1.6+ and 2.0. Draft compiles, parallel compilation, optimized vs unoptimized Javascript and selected targeted browsers in development. These all can help but these are in part counteracted by increasing compile times with each version.

Also compiles are only required when you change your service interfaces. Pure client-side changes can be tested by refreshing the hosted browser (or a real browser in GWT 2.0+). Serverside changes that don’t alter the interface don’t technically require a GWT recompile but this can be problematic to implement (in either Ant or Maven).

Why are long compile times a problem?

Or from The Joel Test: 12 Steps to Better Code:

We all know that knowledge workers work best by getting into "flow", also known as being "in the zone", where they are fully concentrated on their work and fully tuned out of their environment. They lose track of time and produce great stuff through absolute concentration. This is when they get all of their productive work done. Writers, programmers, scientists, and even basketball players will tell you about being in the zone.

The trouble is, getting into "the zone" is not easy. When you try to measure it, it looks like it takes an average of 15 minutes to start working at maximum productivity.

The other trouble is that it's so easy to get knocked out of the zone. Noise, phone calls, going out for lunch, having to drive 5 minutes to Starbucks for coffee, and interruptions by coworkers -- especiallyinterruptions by coworkers -- all knock you out of the zone.

Even a one minute compile can knock you out of the zone. Even Jeff Atwood—still desperately clinging to his irrational hatred of PHP like an indentity asserting life preserver—has seen the light and is a self-proclaimed Scripter at Heart.

Not Every Application is GMail

I think of a Web application as something like GMail. It is typically a single page (or close to it) and will often mimic a desktop application. Traditional Web pages may use Javascript varying from none to lots but still rely on a fairly standard HTTP transition between HTML pages.

GWT is a technology targeted at Web applications. Load times are high (because it’s not hard to get to 1MB+ of Javascript) but that’s OK because in your whole session you tend to load only one page once. Web pages are still far more common than that and GWT is not applicable to that kind of problem.

Even if you limit the discussion to Web applications, all but the largest Web applications can be managed with a Javascript library in my experience.

Now for something truly monumental in size I can perhaps see the value in GWT or at least the value of type checking. Still, I’d rather deal with dynamic loading of code in Javascript that I would with GWT 2.0+ code splitting. Compare that to, say, YUI 3 dynamic loading, which leverages terse Javascript syntax and first class functions.

Of Layers and Value Objects

It’s not secret that Java programmers love their layers. No sooner do you have a Presentation Layer, a Controller Layer and a Repository Layer than someone suggest you also need a Database Abstraction Layer, a Service Layer, a Web Services Layer and a Messaging Layer.

And of course you can’t use the same value object to pass data between them so you end up writing a lot of boilerplate like:

public class TranslationUtils {
  public static CustomerVO translate(Customer customer) {
    CustomerVO ret = new CustomerVO();
    ret.setName(customer.getName());
    ret.setDateOfBirth(customer.getDateOfBirth());
    ...
    return ret;
  }
}

Or you end up using some form of reflection (or even XML) based property copying mechanism.

Apparently this sort of thing is deemed a good idea (or is at least common practice). The problem of course is that if your interfaces mentions that class you’ve created a dependency.

What’s more Java programmers have a predilection with concerning themselves about swapping out layers or putting in alternative implementations that never happen.

I am a firm believer that lines of code are the enemy. You should have as few of them as possible. As a result, it is my considered opinion that you are better off passing one object around that you can dynamically change as needed than writing lots of boilerplate property copying that due to sheer monotony is error-prone and because of subtle differences can’t be solved (at least not completely) with automated tools.

In Javascript of coruse you can just add properties and methods to classes (all instances) or individual instances as you see fit. Since Java doesn’t support that, it creates a problem for GWT: what do you use for your presentation objects? Libraries like ExtGWT have ended up treating everything as Maps (so where is your type safety?) that go through several translations (including to and from JSON).

On Idioms

Managers and recruiters tend to place too much stock in what languages and frameworks you (as the programmer candidate) have used. Good programmers can (and do) pick up new things almost constantly. This applies to languages as well. Basic control structures are the same as are the common operations (at least with two languages within the same family ie imperative, functional, etc).

Idioms are harder. A lot of people from say a Java, C++ or C# background when they go to something like PHP will try and recreate what they did in their “mother tongue”. This is nearly always a mistake.

Object-oriented programming is the most commonly misplaced idiom. PHP is not object-oriented (“object capable” is a more accurate description). Distaste for global is another. Few things are truly global in PHP and serving HTTP requests is quite naturally procedural most of the time. As Joel notes in How Microsoft Lost the API War:

A lot of us thought in the 1990s that the big battle would be between procedural and object oriented programming, and we thought that object oriented programming would provide a big boost in programmer productivity. I thought that, too. Some people still think that. It turns out we were wrong. Object oriented programming is handy dandy, but it's not really the productivity booster that was promised. The real significant productivity advance we've had in programming has been from languages which manage memory for you automatically.

The point is that Java and Javascript have very different idioms. Well-designed Javascript code will do things quite differently to well-designed Java so by definition you’re losing something by converting Java to Javascript: idioms can’t be automagically translated.

Conclusion

Scripting is the future. Long build and deploy steps are anachronistic to both industry trends and maximizing productivity. This trend has been developing for many years.

Where once truly compiled languages (like C/C++ and not Java/C#, which are “compiled” into an intermediate form) accounted for the vast bulk of development, now they the domain of the tools we use (Web browsers, operating systems, databases, Web servers, virtual machines, etc). They have been displaced by the “semi-compiled” managed platforms (Java and .Net primarily). Those too will have their niches but for an increasing amount of programming, they too will be displaced by more script-based approaches.

GWT reminds me of trying to figure out the best way to implement a large-scale, efficient global messaging system using telegrams where everyone else has switched to email.

Microsoft, Marketing Insanity and Windows Piracy

2009-10-22T19:10:00.001+08:00

Thursday marks Microsoft’s release of the Windows 7 operating system. This is an opportune moment to reflect on Microsoft’s marketing strategy because its like they want me to pirate Windows. And I feel the need to rant.

A Brief History of Windows

Windows 3.0 was released in 1990 in an attempt to stave off the successful (but expensive) Macintosh. And it certainly ticked off the boxes (from a marketing perspective at least).

Various incarnations of Windows 3.x followed over the next 2-3 years. Probably the most interesting thing is that Microsoft only stopped selling Windows 3.x licenses in November 2008.

Windows 95 (“Chicago”) in 1995. What some don’t realize is that Windows 95 was in many ways technically superior to MacOS, most notably:

Pre-emptive multitasking rather than cooperative multitasking. Rather than waiting for an application to yield, the operating system could interrupt. Nothing new to UNIX but certainly new to Windows and MacOS;
Virtual address spaces. Macs at the time had to allocate memory slices to programs. Win95 programs could simply ask for more memory. Depending on your hardware, this could be physical RAM or hard disk space. The OS could swap between them while the application was running too. Again, nothing new for UNIX.

The biggest impact of Windows 95 was that it killed off non-Microsoft DOS.

Another notable feature was DirectX, Microsoft’s gaming API. This wasn’t part of the original release. It quickly supplanted OpenGL as a gaming API in the burgeoning world of hardware acceleration to the point that even stalwart advocates like id software are abandoning it but DirectX was a commercial success and the majority player almost a decade earlier.

Separately Windows NT had sprung into existence to break the connection between Windows and the DOS shell. Windows NT 4.0 in 1996 was probably the first version with broad market success, targeted at businesses.

The next notable release was Windows 2000, the successor to the venerable Windows NT 4.0, as it began the convergence of the NT and 9X (including ME) families. This culminated in 2001 with the release of Windows XP.

The Wintel Alliance

The rise of Windows and decline of IBM’s leadership of the PC coincided with marriage of convenience between Microsoft (Windows) and Intel or “Wintel”. This has never been a comfortable arrangement but it is based on a fairly simple principle:

Most people only buy operating systems with new computers.

That conventional wisdom has since been disproven by Apple but more on that later.

The dark side of this marriage is planned obsolescence. Chipsets changing, RAM standards changing, CPU sockets changing and so on. Some of it’s necessary and understandable. Savvy consumers have long figured out that buying high quality (and high cost) components for their PCs for upgrades down the line is a waste of time and money.

The biggest threat to Intel came from the disaster that was (and is) Itanium, AMD cutting them off at the knees with the hugely successful Athlon line of processors, AMD’s x86-64 instruction set putting the final nail in Itanium’s coffin and the disaster that was the Pentium 4. I say “disaster” but it was mixed. The gigahertz marketing campaign against AMD was successful. As a technology it was a disaster.

Why do I say that? Because eventually it was abandoned as Intel returned to the Pentium 3 architecture with what became the hugely successful Pentium M, Core Solo, Core Duo and Core 2 Duo releases.

A New Millenium

For those of us who purchased (and typically built) PCs in the 1990s, it was worth upgrading your PC every year or two. The newer PCs were just that much better. The market while large was much smaller than it is today to the point where Microsoft could count on a rapid turnover in PCs and a low of purchases from first-time PC owners.

As Joel Spolsky noted in How Microsoft Lost the API War:

Microsoft just waited for the next big wave of hardware upgrades and sold Windows, Word and Excel to corporations buying their next round of desktop computers (in some cases their first round). So in many ways Microsoft never needed to learn how to get an installed base to switch from product N to product N+1.

In the last 8-10 years PCs have gotten better but for increasingly more people it’s enough. My father has an old PC cannibalized from parts I bought in 2002. It runs a (modern) browser, Word and Excel and that’s all he needs. There will be absolutely no need to upgrade that PC or purchase a new one until it dies. This is the case for most consumers and businesses.

So rather than buying a new operating system every 2-3 years, the music stopped playing when Windows XP was the OS du jour. Everyone sat down and they haven’t moved since.

Interestingly, Office suffered the same problem at roughly the same time. Office 97 was basically feature complete for 95%+ of all users. Every version since has been an attempt to get businesses to buy it for it’s enterprise tinselware. Sure there have been minor improvements but overall, Office 97 is it.

Fighting Fires

As the scope of Windows has grown over the years, Microsoft has been fighting fires to defend its franchise that include:

Java: “run anywhere” (well, write once, test everywhere) was a threat to the Windows lock-in;
Games: OpenGL also threatened the lock-in since DirectX is Windows-specific;
Developer Tools: once Borland was a major player. Now it’s all about Visual Studio;
The Web: the free Internet Explorer was a desperate attempt to fend off Netscape that was ultimately successful.

The last one is important because even though Microsoft won the battle they lost the war. Microsoft’s hubris, breaking of backwards compatibility, ever-changing platforms and standards and so on probably accelerated the adoption of the Web as a platform for application delivery.

Microsoft was once an innovator trying to get market share. It was then they were at their best. At some point companies become so large that they switch from being innovators to defenders. No longer are they concerned making the best product. They are primarily concerned with defending what they already have.

The Madness Begins

Even before it was released, Vista (or Longhorn as it was called then) had a lot of people concerned. Microsoft had seemingly decided that it was OK to start breaking backwards compatibility.

Faced with people only buying an operating system (meaning a PC) every 5-8 years, what did Microsoft do? They did what most marketing eggheads would do: they raised prices. Instead of getting $100 from a consumer every 2-3 years, let’s charge $250 every 5-8 years including revenue growth to please our shareholders.

Earth to Microsoft: if you charge people more they will buy less.

Segmentation Insanity

A bigger problem was where there were basically two versions of Windows XP (Home and Professional) ignoring the Server version. In classic “how much money do you have?” pricing, there were now four versions:

Home Basic
Home Premium
Business; and
Ultimate

But it gets worse…

Retail, Upgrade or OEM?

Say what now? Try and explain this one to a non-techie. For Windows 7 this is actually worse. For example, Windows 7 Professional Upgrade is more expensive than Windows 7 Professional Retail. What the…?

32 or 64 bits?

Seriously?

This is perhaps the most egregious transgression. Several months ago I had a conversation with a friend who has been using PCs for 15 years and was upgrading his computer about getting the right version of Vista (32 or 64) since he was thinking about getting 4GB or more of RAM. He’s reasonably proficient. Try explaining it to someone who isn’t.

It reminds me of this classic UI blunder:

Why are you asking consumers about questions they don’t understand and don’t care about when choosing which OS to buy? Just sell one version. If an advanced user wishes to install the 64 bit version, let them do so during installation.

Activations and DRM

One of the scourges of the last decade has been the rise of DRM (“digital rights management”). As I previously said, people have an innate sense of fairness. If you tell them they don’t own something like a program, video or song even though they paid for it, they aren’t going to like it.

Even Google got sucked into this sham (probably at the behest of Big Content) and discovered the downside (for them) when they had to refund users when they closed Google Video. Woops.

Vista came with draconian activation limits. Microsoft eventually relented somewhat, particularly with the (pricey) retail version.

Now compare that to a version I can find on The Pirate Bay that simply works and you begin to see that DRM creates pirates.

Windows 7? It Gets Worse

Don’t believe me? Consider this table:

And that’s the simple version of the charge that doesn’t include 32 and 64 bit combinations. The upgrade costs have also changed as you can, say, upgrade from Windows Vista Home Premium to Windows 7 Professional.

But there’s no other choice, right? Wrong.

Timing is Everything

From the mid to late 90s Apple was in the wilderness. Windows had eroded Mac market share to the small single digits. Several attempts were made to turn this around such as Apple’s purchase of Steve Jobs’ NeXT and the Rhapsody OS.

With the return of the king, there were (eventually) two great successes. Firstly, the iPod (and more importantly) iTunes. Secondly, Jobs put the nail in the coffin for PowerPC by switching Apple hardware to Intel’s x86 architecture. Jobs stated that “power efficiency”, which many found laughable given the Pentium 4’s power and heat issues.

Jobs’ timing however was superb (and undoubtedly not luck). Intel’s Centrino platform became all-conquering.

Some Things Are Greater Than Their Sum of Parts

This was a risky move. Differentiation is a key component of Apple’s strategy. If Macs use the same hardware as PCs, why pay extra? Macbook and iMac market share has recovered from around 2% to be almost 10% of US shipments.

Part of Apple’s appeal has always been what I term “countercultural knockback”, meaning there are a certain group of people who will attach themselves to something—sometimes fanatically—in part because it isn't popular. Another part of it is that Apple aims itself at the top end of the market quite deliberately. But a huge part that’s often overlooked by detractors is that the whole package is attractive.

Apple didn’t invent the concept of a sleek laptop, or a digital music player or a phone with Internet capability. They just did it better than anyone else.

One Size Fits All

Consumers don’t like being forced to make choices they don’t care about or don’t understand. Two years ago, Steve Jobs famously fun of Vista segmentation during his WWDC keynote.

Don’t Make Me Think

So I’m looking to buy a copy of Windows 7. I initially started on the Home Premium version. A friend pointed out to me that the XP Compatibility Mode—something I'm not certain I won't need—is only in the Professional and Ultimate versions.

Microsoft’s policy on OEM versions takes some figuring out. As it turns out it all comes down to the motherboard. Change your motherboard and you need a new OEM version. This may or may not be enforced. I’ve been using Windows XP for over 7 years. I’ve had 3 motherboards in the last 2 years so I want the retail version instead.

Well that’s going to cost $449 for the Professional version. Oddly, the Ultimate version is only $20 more. Was there really need to differentiate between these two versions for $20? Why not just have one version that covers both?

That’s a lot of money to pay for an operating system. Times have changed. No longer does a PC cost $3,000. You can buy a quad core box with 4GB of RAM for as little as $500. And I need to pay almost 100% of the hardware costs for Windows? Seriously? What does it do that XP doesn’t? Not a lot (that I care about anyway).

Are you kidding me?

Fear, Uncertainty, Doubt

FUD has been a hallmark of tech marketing. Microsoft is no exception. Just last month, Microsoft announced no TCP/IP patch for Windows XP, claiming the code was too old. Bullshit. It’s marketing strategy to convince us we need to upgrade.

They tried it with Vista too. The long-awaited DirectX 10 update was Vista only. Microsoft marketing was to suggest you might not be able to run the latest games if you have Vista instead of XP (when most hardcore gamers were sticking with XP for performance reasons).

Microsoft has been using FUD against Linux for years. There’s something amusing (even ironic) about them using FUD on one of their own products.

Lipstick on a Pig

What is Windows 7, really? I’ll give Microsoft props for one thing: the Windows 7 marketing is a success. A lot of people are excited about it. I used the RC version for a few months and it’s not bad. The NTFS support is noticeably faster and I didn’t get those stupid “Preparing to delete” boxes when I deleted a directory tree. I must admit I also like to find programs by the Start Menu speed search.

Could these features have been added on an XP base? Absolutely.

Vista has a service pack already. As far as I’m concerned Windows 7 is just Vista Service Pack 2. How really is it different to Vista? The UAC security is slightly less annoying but it’s basically the same. Maybe wireless is a bit better but these are all incremental changes.

The 90s were a pioneering period for personal computing where they went from niche to mainstream. Operating systems and applications are both mature now. Even Linus Torvalds has recognized this:

APC: When do you expect to see a kernel version 3.0? What will be the major changes or differences from the 2.6 series?

LT: We really don't expect to need to go to a 3.0.x version at all: we've been very good at introducing even pretty big new features without impacting the code-base in a disruptive manner, and without breaking any old functionality.

That, together with the aforementioned lack of a marketing department that says "You have to increase the version number to show how good you are!" just means that we tend to just improve everything we can, but you're not likely to see a big "Get the new-and-improved version 3!" campaign.

Basically there (probably) won’t be a Linux 3.0. There’s no need. Microsoft needs to recognize that need isn’t a factor for consumers. Whatever they have, it’s enough.

Old Versions Cost You Money

Anyone who has written software for a living knows this to be true: supporting old versions of your software costs you money. You want your customers to be on the latest version.

Here Apple is clearly more successful at getting their users to upgrade, in part helped by the low (US$29) cost. You can even buy 5 licenses for home for US$49. Each release seems to get bigger.

Cost is clearly a factor here. Detractors would argue Apple is charging for service packs. Maybe so. But it’s clear consumers prefer to pay less money more often.

Ship Early, Ship Often

The other way you cost yourself money is increasing the time between releases. Costs scale exponentially rather than linearly. If takes you four years to ship a product it will probably cost you twice what it does to ship two products at two year intervals.

Long releases tend to be over-ambitious releases. What’s more, there is a huge likelihood that market conditions have changed by the time you release that you’re spending a lot of effort changing an unshipped product before it even gets out the door. There is no better example than the Duke Nukem Forever debacle.

And of course complexity is the enemy. The growth in Windows lines of code shows no signs of abating.

The Business Market

This is both Microsoft’s biggest source of revenue (for both Windows and Office licenses) and its biggest thorn in the side. It’s also a problem Apple does not have.

Most companies buy PCs for their employees. To help with support costs they come up with a standard installation, called an SOE (“standard operating environment”). This version will then come on a CD that’ll install everything. It’s expensive to change and roll out. Most companies will have a Windows 2000 or XP based SOE.

A ten year old PC running Win2K and Office 97 still does its required job. This isn’t just being cheap. Why would you roll out new hardware that from a functionality perspective does the same thing? There’s no business case for it. What do you think a hospital will choose between new PCs of dubious utility and a $3 million MRI that’ll save some lives?

So it’s understandable but these people are the bane for Web developers as they’re responsible for the dogged ~10% market share for Internet Explorer 6 too.

So How Does Microsoft Sell Operating Systems?

Good question, one for which Microsoft has no answer. It probably doesn’t help that the man at the helm (Steve Ballmer) isn’t a programmer. He’s not even a techie. He’s a business guy who thinks in terms of marketing, business strategy and gap analysis. At least Bill Gates was a programmer. Bill Gates’ Microsoft was an innovator no matter what else you could say about it or him.

I have to agree with Jeff Atwood on this one. Microsoft is getting pricing wrong. Prices need to be low enough that it ceases to be a major purchase.

Microsoft Just Doesn’t “Get” Marketing

What can I say? Windows 7 Launch Parties? Microsoft retail stores (hint: Apple had compelling consumer products rather than “me too!” wannabe products before they opened stores)? Vista ads with Jerry Senfeld? I’m shaking my head.

So Which Windows 7 to Buy?

Non-coincidentally, Apple just cut the prices of Macbook Pros and released a new “low” cost white Macbook. In Australia this was at least in part due to the appreciation of the Australian dollar in recent months. A Macbook Pro 13 is now only a few hundred dollars more expensive thn a (plastic) Dell Studio XPS 13.

I’m not a .Net developer so I’m not tied to Windows. My favourite IDEs come from Jetbrains (Intellij IDEA and increasingly Web IDE) and they run on Windows, Macs and Linux.

Windows virtualization and emulation (eg WINE) are getting sufficiently good that you can run Office 2007 under Ubuntu.

I need to install Cygwin to get a workable command line on Windows anyway. It also makes Git work easier.

As a developer I’m finding the Macbook an increasingly attractive option. I only have three criticisms and concerns:

Apple reversed themselves on adopting ZFS as a replacement to (what Linus Torvalds described as "scary") HFS+ filesystem;
Apple’s bizarre stance on delaying Java releases to integrate their look and feel. Java 6 for the Mac was almost a year late; and
I’ll have to buy another copy of Civilization 4.

Linux is of course an option but I’ve been there and done that. Fact is, both Windows and MacOS are slicker than Gnome or KDE.

Conclusion

Microsoft reminds me of an ageing housewife revelling in her high school glory days whose greatest achievement is that she still fits into her cheerleader outfit. Sure you were the popular girl once but that was 20 years ago. Times have changed.

It isn’t 1995 anymore. Next Christmas most people will be fine with a $200-300 netbook. Why would such people buy that price again for an operating system (ever)? Getting existing users to upgrade is (or should be) a key strategy for Microsoft but like any incumbent, business weenies are now running the asylum and they’re more concerned about having room for revenue growth than in actually selling products people want to buy.

Bring it on Apple!

Stackoverflow, Advertising and the Ethics of a Free Lunch

2009-10-01T23:25:00.001+08:00

If the Internet has taught us nothing else, it has taught us that:

Advertising pays for otherwise free services;
People don’t like advertising; and
Advertising works.

These conflicting forces always cause consternation and Stackoverflow is by no means immune.

Stackoverflow is Free

One of the most important features of Stackoverflow is that it is free to browse, ask and answer questions. People like free. It’s one reason I believe that Stackoverflow has been so well-received by programmers as a whole. Of course it has it’s detractors (most of whom seem to lurk on reddit) but as Bjarne Stroustrup says:

There are only two kinds of languages: the ones people complain about and the ones nobody uses.

The lesson being that anything—not just programming languages—that’s popular will attract countercultural malcontents keen to assert their non-mainstream identities.

Stackoverflow Costs Money

While the content is community driven (and thus free), the site is not. It takes money for hosting, hardware, software development, administration, support issues (separate to community moderators) and so on. No one would argue with that. Yet there appears to be a disconnect between the fact that something costs money and the activities required to earn that money. Either that or people mentally file that away as Somebody Else’s Problem.

So how does a “free” service pay for itself?

Micro-Transactions Don’t Work

An excellent resource on this is Fame vs Fortune: Micropayments and Free Content:

This strategy doesn't work, because the act of buying anything, even if the price is very small, creates what Nick Szabo calls mental transaction costs, the energy required to decide whether something is worth buying or not, regardless of price.

Joel Spolsky has also spoken on this subject. In addition to the mental cost of transactions (no matter how small), Joel remarked on how people will do things for free that they will never do if paid (a small amount).

Segmentation Doesn’t Work

Market segmentation is the time-honoured technique of asking people how much money they have when they want to buy something rather than telling them what it costs, meaning what it costs is a function of how much money they have.

Joel speaks about this in-depth in Camels and Rubber Duckies.

Working my way backwards, this business about segmenting? It pisses the heck off of people. People want to feel they're paying a fair price. They don't want to think they're paying extra just because they're not clever enough to find the magic coupon code. The airline industry got really, really good at segmenting and ended up charging literally a different price to every single person on the plane. As a result most people felt they weren't getting the best deal, and they didn't like the airlines.

Perhaps it’s more correct to say segmentation doesn’t work in the long term.

Advertising Works

It’s clear that advertising works as a means of revenue. Why is it clear? If it didn’t, we wouldn’t have it. Of course, that doesn’t mean it works universally. It is obviously possible to lose money on advertising but it’s clearly possible to make money too.

Traditional media typically lied about conversion rates. Conversion rate is the percentage of visitors, users, viewers or listeners who see, hear or read an advert that take some desirable action, which could be simply clicking through or result in an inquiry, a sale or the like. Twenty years ago you’d have radio and TV marketing departments who would work up a model based on conversion rates of up to 25%. They did so because there was no way to refute their claims (other thank taking the plunge and getting disappointed with the result). With the internet such things are precisely measurable. Because the cost of distribution is so low, the conversion rates of 1 in 1000 (or less) are fine.

The other proof that advertising. Possibly 95% of email is spam, if not more. Clearly the conversion rate is non-zero otherwise they wouldn’t do it so that one guy in 10,000 who can’t find porn on the Internet (somehow) or thinks a plastic bottle of oregano will really extend his… well, you know… he is responsible for spam eclipsing legitimate email by a factor of 20-to-1.

Registration to Read Annoys People

The Evil Hyphen Site (ie Experts Exchange; deliberately no link) exemplifies this point. You can read content for free on that site if you either know where to look for free registration (deliberately not obvious) or you get to the site from Google (even though it says “register to see the answer” the answer is at the bottom of the page; try it).

This annoys people and is part of the reason that site has (justifiably) earnt so much hate.

Sometimes this registration is simply offensive, like why do I need to provide you with my date of birth and home address to read your forum post? Of course one has to wonder about what the less scrupulous operators are doing with such private information but even if you’re reputable, you don’t need it so why are you asking?

I can’t speak for anyone else, but as far as that sort of invasive information gathering goes, my name is Jimmy Hoffa, I’m 93 and I live in Afghanistan. I also run a banking company with a million employees and have an annual income of $10,000.

Stackoverflow doesn’t even require you to register to ask questions.

Alienate Your Community and You Have No Site

In this era of social sites (including crowd-sourced sites like Stackoverflow), community matters. A given solution can succeed and fail on the strength of it’s community. The same solution in different communities may succeed in one and fail in another by virtue of the different communities.

On a site like Stackoverflow the most important people are the ones who answer questions. This is a somewhat controversial opinion. The editors will disagree (or at least have a higher opinion of their worth). Don’t get me wrong: editing has value but no one celebrates the guy who edited The Great Gatsby, they celebrate F. Scott Fitzgerald.

Such communities over time can become insular (arguably incestuous). The poster child for this are Wikipedia editors, who went so far as to have a secret McCarthy-esque black list of "problem" users.

Lose your community and you lose your site. The Evil Hyphen Site has already done that.

Stackoverflow and Advertising

Originally Stackoverflow was quite light on for advertising, limited to a (mostly textual) right sidebar. The site started out looking much like this:

Now if you have less than 200 reputation it looks like this:

Interestingly, it only seems to look like this in Internet Explorer, even when I delete all my cookies. Firefox and Chrome (cookies deleted) still look like the original.

The difference? The right sidebar is “higher contrast” and there is an ad banner at the top of the question (and another further down). The top ads I believe were once text only, which is far less invasive. But Jeff has stated there won’t be any Flash or animated ads.

The latest controversy concerns the “offensive” advertising indicated to the left. Along with the "offensive" Adobe icons.

Call me crazy but I actually like these Adobe symbols on anything Flash/Flex related. It makes them easier to spot and I think it adds value. Spotting an Adobe icon is easier than finding the exact text that you’re after.

if you do find all questions tagged with one of these sponsored tags, you get this:

Is this too much? In my opinion? No. Others (naturally) disagree. Some to the point that they’ve written a script to remove such sponsored content.

Such activities, if done by a sufficiently large percentage of the userbase, undermine that site’s ability to generate revenue that pays for the site existing.

“But I Don’t Click on Ads Anyway!”

The first obvious rationalization is that basically ads don’t affect you. Bullshit. Ads do two things: they attempt to entice the user to take particular action, clicking through, buying something and so on. They also simply raise awareness of a brand, product or service. This is all about mind share. This one is subtle and hard to measure but if you see an ad or a logo often enough you’ll subconsciously recognize it.

“It’s Like Fast Forwarding Through Commercials”

No it isn’t. This defence was used in the ReplayTV lawsuit:

Yet, what the advertisers who are supporting TV are paying for is the potential that you might watch television ads. They know you might channel surf, get up and fart, go grab a smoke, or whatever. The challenge to the advertising agencies is to make commercials that you like to watch, that you want to watch. By editing out the commercials entirely, a priori, the networks can claim that ReplayTV in effect creates a derivative work that deprives them of the possibility that you might actually watch the ads. It is that possibility that generates the value of their ad space, and if something like ReplayTV were widely used, those numbers would drop, big time.

The other way to look at this is that if no one saw the ads, no sponsor would pay for them. If half the audience skipped the ads, it would be worth half as much to the sponsor and so on.

“It’s Already Loaded!”

Irrelevant. Something that’s loaded but never seen is of no value to an advertiser. Also, revenue from advertising can come from simply placing the ad, clicking through the ad or some combination of the two.

Adam Bellaire claims:

I don't think the SO guys are going to "not get paid" by a user script removing images and content after it's already loaded. Nobody can tell who or how many people are using this thing.

It could be argued that Adam believes advertisers are that clueless but it would be the height of naiveté. It’s far more likely that this is simply rationalisation.

“I Should Be Able to Opt Out.”

Adam once again pontificates:

…this is a completely opt-in script!

So what? Does it magically cost nothing to provide the service for you specifically? I must’ve missed the “This packet is intended for Adam” bit in the TCP/IP packet structure so the telcos know not to charge for it. I’ve got a good mind to write to W. Richard Stevens so he can issue an emergency addendum to his book.

“But This is ME!”

All of this comes down to what I call the BITM (“But this is ME!”) syndrome, closely related to NIMBY (“Not In My Backyard”). Examples include “I realize there is a speed limit… but this is ME!”, “I realize that I should stop at this almost red light… but this is ME!” and so on. Once again with Adam:

Or do you mean to say that as long as some people see the sponsored ads, then it's okay? Because I agree with that,

To put it another way: I understand someone needs to pay for this, I just don’t see why it should be me.

Alex Papadimoulis succinctly rebuts this:

Ad blockers are like the fat bastards at the grocery store who take handful after handful of free samples. If everyone [Ed] did it, the system would collapse and everyone would lose out. We know it, they know it, and we all just roll our eyes as they stuff their face with cut-up hot dogs and go "whhaaaat?". When they try to justify it ("it doesn't say only one, not my fault they give it away!"), it just makes 'em look worse. As I always say, at least have the decency to admit you're a bastard

The Innate Sense of Fairness

People have an innate sense of fairness to the point it can be manipulated or predicted with neurochemistry. This can work for companies if they treat their users fairly or against them if they don’t.

EA released Spore with a nauseating and invasive DRM system that limited it to three activations (later changed to five). Microsoft tried the same thing with limited activations of OEM Vista. People naturally believe that if they buy something they should be able to reinstall it as many times as they want.

A lawyer may argue that you haven’t bought the software, you’ve bought a license to use it in a limited way. But we’re not talking what’s legal here. We’re talking what’s fair.

It’s this sense of fairness that will cause people to reject the underhanded tactics of the Evil Hyphen Site to get you to subscribe or pirate some piece of software they’ve bought that has run out of activations (or simply installs a rootkit allowing your system to be hacked). So I guarantee you that if the Jeff and Joel go too far with advertising the userbase will react. But we’re not there yet. Nowhere near it.

There’s No Such Thing as a Free Lunch

Sites cost money to develop, maintain and host. They have a right to earn revenue to cover their costs and make a return on the investment they’ve made (and risked). So what’s fair?

My personal opinion is that icons on tags are OK, sponsored links at the top are OK (if you have a problem with that I guess you don’t use Google or pretty much any other search engine) and the side bar is OK. I find the graphical ads littered throughout the question a bit much but then again I have more than 200 reputation so don’t see them.

For what it’s worth I think I’ve even clicked on a couple (Telerik and SpreadsheetGear spring to mind) of the many thousands I’ve no doubt seen but, as mentioned, such a low conversion rate is to be expected.

The euphemism “opt out” in this context is akin to “it’s OK to steal from the supermarket as long as no one else does it”. If you want good services like Stackoverflow to exist then on principle alone you should be supporting them.

Writing scripts to block ads is just selfish. What’s more if the ads offend you that much it suggests a certain irresponsibility, thoughtlessness, touchiness and intolerance that doesn’t speak well of your character.

Seriously, get a clue.

Anyone Interested in a PHP Fluent Interface for Generating HTML?

2009-09-17T00:31:00.001+08:00

For the past few days I’ve been toying with a set of classes in PHP that is basically a fluent interface for generating HTML. A basic usage example is:

echo p(b('This'), ' is a ', i('test'))->addClass('foo')->html();

or alternatively:

echo new Paragraph(
       new Bold('This'),
       ' is a ',
       new Italic('test'))->addClass('foo')->html();

echo new Paragraph()->append(new Bold('This'))
                    ->append(' is a ')
                    ->append(new Italic('test')
                    ->addClass('foo')
                    ->html();

which outputs

<p class="foo"><b>This</b> is a <i>test</i></p>

My goals in doing this were to:

Create a terse fluent interface for gnerating HTML;
Create valid HTML. This code currently implements the HTML 4.01 Transitional standard so it'll generate an error if you try and append a <p> element to an <object> element, for example;
Correctly handle HTML escaping implicitly; and
Provide a level of jQuery like manipulation functionality.

I did this largely to see how it would turn out. Basically for my own curiosity. I don't even know if I'll be using this with what I'm working on but just in case I have to ask: is this something others might be interested in?

I haven't seen anything like it but that doesn't mean it hasn't already been done. If there is interest in it, even if its just idle curiosity, I'll clean it up and open source it.

PHP Smarty Tutorial: Caching and Versioning Static Content

2009-09-16T21:47:00.001+08:00

I am a nascent advocate of using Smarty as a view templating engine in PHP. Some—including myself until recently—might ask “Why use a templating engine for PHP, which is a templating engine?” In this post I hope to give you one example of how Smarty can clean up code in a useful way.

Static Content

Static content refers to primarily images, Cascading Style Sheets (“CSS”) and JavaScript files but can also include such things as videos, audio clips and so on. All of this tends to be labelled “static content” as it is largely unchanging (as opposed to Web pages, which are largely dynamic).

Static content can include things like static HTML files but in practice other methods tend to be more common for caching HTML content.

Caching

Static content can be cached in two places: on the client and on the server.

Caching on the server isn’t typically an issue with truly static content. It’s more an issue with cached content that is generated in some way, such as the dynamically generated Javascript files from Supercharging Javascript in PHP. Serverside caching is not the focus of this post.

Client caching involves telling the browser to keep a copy of certain content and not request it from the server. There are several variations upon this theme:

Caching for a fixed period of time. For example, setting the HTTP Expires header in the future;
Allowing the browser to ask if the content has changed. For example, use of ETags in HTTP/1.1; and
Some combination of the two.

The one we’ll focus on is (1). It is a simple scheme but you must balance setting the Expires header sufficiently far in the future versus making spurious requests to the server when the content hasn’t changed.

Versioning

As a solution to the far futures Expires header problem of content that changes, a common scheme used by modern Websites is to use some form of versioning. What this means is this: the Expires header is set in the far future (one or more years). When the content changes a new URL is generated. This forces the browser to reload the content.

In my previous articles I used URLs like this:

http://example.com/images/logo.1233454569.png

The disadvantage of this is that it requires URL rewriting to work. I have since settled on a simpler scheme: putting the file’s last modified time as the query string. This means a URL like this:

http://example.com/images/logo.png?1233454569

No URL rewriting required and it should work out of the box with Web servers.

Static Content Domain

Another optimization that is encouraged is to split your publicly available static content onto a separate domain. The reason is that you could minimize traffic and overhead by the client not sending unnecessary cookies.

Image Dimensions

Lastly, images in particular can be optimized by specifying their height and width in the HTML. This can speed up how fast the browser renders the page and whether or not there are possibly unsightly visual artefacts as the page loads, such as content jittering or shifting position while it is loading.

Directory Structure

This example will assuming the following directory structure:

/var/www                    Top-level on host
+- /site                    Document root of dynamic domain
+- /static                  Document root of static domain
   +- /images               Images subdirectory
+- /lib                     Third-party code
   +- /Smarty-2.6.26        Smarty install files
+- /include                 PHP files not served by the Web server and thus not under the document root
   +- Mysmarty.class.php    Custom Smarty template generation. See Smarty installation notes.
   +- /templates            Smarty templates
   +- /templates_c          Compiled Smarty templates
   +- /cache                Cached Smarty content
   +- /config               Smarty config files
   +- /plugins              Smarty plugins

Your structure may of course vary. I will say I prefer to put nothing under the document root that isn’t the endpoint of an HTTP request.

The Apache, IIS, nginx or other config to set the far future Expires header is assumed.

Mysmarty.class.php

A common technique with Smarty is to create a custom subclass of Smarty that sets all the correct configuration. This looks something like this:

<?php
define('BASE_DIR',      '/var/www/');
define('LIB_DIR',       BASE_DIR . 'lib/');
define('INCLUDE_DIR',   BASE_DIR . 'include/');

// separate static site
define('STATIC_URL',    'http://mystatic.com/');
define('STATIC_DIR',    BASE_DIR . 'static/');

// use the following if everything is on one site
//define('STATIC_URL',    '/');
//define('STATIC_DIR',    BASE_DIR . 'site/');

// Smarty directories
define('TEMPLATES_DIR', INCLUDE_DIR . 'templates/');
define('CONFIG_DIR',    INCLUDE_DIR . 'config/');
define('COMPILE_DIR',   INCLUDE_DIR . 'templates_c/');
define('CACHE_DIR',     INCLUDE_DIR . 'cache/');
define('PLUGINS_DIR',   INCLUDE_DIR . 'plugins/');

// static content
define('IMAGES_DIR',    STATIC_DIR . 'images/');

// URLs
define('IMAGES_URL',    STATIC_URL . 'images/');

require '../lib/Smarty-2.6.26/libs/Smarty.class.php';

class MySmarty extends Smarty {
  function MySmarty() {
    $this->Smarty();

    $this->template_dir = TEMPLATES_DIR;
    $this->compile_dir  = COMPILE_DIR;
    $this->config_dir   = CONFIG_DIR;
    $this->cache_dir    = CACHE_DIR;
    $this->plugins_dir  = PLUGINS_DIR;
  }
}
?>

Hopefully you should be able to adapt the above to whatever directory structure you use.

Smarty Image Plugin

To demonstrate this, I’ll use just one example: images. You can however easily apply this to other forms of static content.

Assume the following code exists and is accessible to the plugin:

<?php
$standard_attributes = array('class', 'dir', 'id', 'lang', 'style', 'title');

function standard_attributes(array $attributes) {
  global $standard_attributes;
  $ret = '';
  foreach ($standard_attributes as $attr) {
    if (isset($attributes[$attr])) {
      $ret .= attribute($attr, $attributes[$attr]);
    }
  }
  return $ret;
}

function attribute($name, $value) {
  return ' ' . $name . '"' . htmlspecialchars($value) . '"';
}

function build_image($params, &$smarty) {
  $src = $params['src'];
  if (!isset($src)) {
    return "[No src to image]";
  }
  $file = IMAGES_DIR . $src;
  $mtime = filemtime($file);
  if ($mtime === false) {
    return "[Image '$src' not found]";
  }
  $height = $params['height'];
  if (!isset($height)) {
    $size = getimagesize($file);
    $height = $size[1];
  }
  $width = $params['width'];
  if (!isset($width)) {
    if (!isset($size)) {
      $size = getimagesize($file);
    }
    $width = $size[0];
  }
  $alt = htmlspecialchars($params['alt']);
  $attribs = standard_attributes($params);
  $url = IMAGES_URL . htmlspecialchars($src);
  return <<<END
<img alt="$alt" src="$url?$mtime" width="$width" height="$height" $attribs>
END;
}
?>

It makes sense to put the above into Mysmarty.class.php or at least include/require it there.

In the Smarty plugins directory, you need to create a file called function.image.php.

<?php
function smarty_function_image($params, &$smarty) {
  return build_image($params, &$smarty);
}
?>

You may well ask "why not put the code in the plugin directly instead of calling a function?" and you'd be right except for one thing: I will reuse it for another plugin but more on that later.

This plugin does several things:

It verifies that the specified image actually exists in the expected location;
It gets the last modified time (mtime) of the image file;
It prepends the correct URI to the image name including the static domain if there is one;
The plugin user can specify as many or as few attributes of the image tag as they wish. This version is written to handle most that you would expect to encounter and is easily extensible to include others;
It uses the GD library to get the height and width of the image, if required. It is only required if the user does not specify both. The user-supplied values are used in preference.

That’s a lot. In a template it is nothing more than:

{image src="logo.gif"}
{image src="top.png" height="100" width="300" alt="Some alt text"}
etc

You can of course do that in standard PHP. I've previously created functions like auto_version() just for this purpose but it's nowhere near as readable and maintainable. The pure PHP version would have to pass in an array of parameters like so:

<?php echo auto_version(array('src' => 'logo.gif', 'height' => '100', 'width' => '200', 'alt' => 'Some alt test'); ?>

But it gets even better.

Compiler Plugins

The astute reader will point out the inefficiency of this: every page request will access the image file once or twice. Firstly to get the mtime. Secondly to get the height and width (if not specified by the user). What’s more the second operation is arguably more expensive since it necessitates reading in the image file and processing it.

The plugin we just created is, in Smarty terms, a template function. The function is called with every view of the template. An alternative is to use a compiler function.

The basic lifecycle of a template is:

If the template file is newer than the compiled template or there is no compiled template, compile it;
Templates are compiled into PHP files that are put in the ‘compile_dir’ directory (typically ‘templates_c’);
Caching and other config can change this.

A template function is called on each execution. A compiler function is only called when the template is compiled into PHP.

You might say that for many of your images they change very infrequently. As such the overhead of reading the dimensions and the last modified time is overkill. This is a good candidate for a compiler function. These values will only be calculated once.

The downside is that if the image does change you will need to regenerate the compiled templates. This is easily done by simply deleting the relevant contents of the compile directory.

Static Image Plugin

We will create another version of our plugin that will be executed at template compile time. We will call this one ‘static_image’. If it had the same name ('”image”) as the template function, the compiler function would take precedence (ie the other would not be called).

There are several differences with template functions:

The file is named compiler.static_image.php;
The function is named smarty_compiler_static_image();
The raw argument (eg ‘src=”logo.png height=”100”’) is passed as a string to the plugin instead of an array of key-value pairs; and
A compiler function generates PHP statements instead of HTML markup.

Bearing all this in mind, we need two functions: one to parse the raw text argument and another to generate the PHP statements. Also, the build_image() function needs to handle a string parameter.

_parse_attrs($tag_attrs);
  $ret = array();
  foreach ($args as $k => $v) {
    $ret[$k] = $smarty->_dequote($v);
  }
  return $ret;
}

function php_echo(string $text) {
  return 'echo "' . addslashes($text) . "\";";
}

function build_image($params, &$smarty) {
  if (!is_array($params)) {
    $params = build_params($params);
  }
  $src = $params['src'];
  if (!isset($src)) {
    return "[No src to image]";
  }
  $file = IMAGES_DIR . $src;
  $mtime = filemtime($file);
  if ($mtime === false) {
    return "[Image '$src' not found]";
  }
  $height = $params['height'];
  if (!isset($height)) {
    $size = getimagesize($file);
    $height = $size[1];
  }
  $width = $params['width'];
  if (!isset($width)) {
    if (!isset($size)) {
      $size = getimagesize($file);
    }
    $width = $size[0];
  }
  $alt = htmlspecialchars($params['alt']);
  $attribs = standard_attributes($params);
  $url = IMAGES_URL . htmlspecialchars($src);
  return <<<END
<img alt="$alt" src="$url?$mtime" width="$width" height="$height" $attribs>
END;
}
?>

With these changes and additions, the compiler template becomes:

<?php
function smarty_compiler_static_image($tag_attrs, &$smarty) {
  return php_echo(build_image($tag_attrs, &$smarty));
}
?>

Using it is as simple as:

{static_image src="logo.png"}

This is something not easily done in pure PHP.

Conclusion

This is but scratching the surface of what Smarty is capable of but I hope it provides a useful demonstration of what makes Amsarty so good.

What’s more this functionality comes at very low cost since Smarty is simply compiled into straight PHP. Barring the initial compile, the only cost on a per-request basis is one to see if the template has changed (and thus needs a recompile). In production environments this check can even be disabled for further performance.

Windows Git Tutorial: Cygwin, SSH and Projectlocker

2009-09-08T23:40:00.001+08:00

Recently I’ve switched from using Subversion to using Git for version control on personal projects. Now as much as Windows annoys me—and believe it me when I say it does annoy me—I still prefer to use it as a development environment (for PHP or Java) over Ubuntu (which I used for that sort of thing for a year or two). There is a better selection of tools. The UI is better. And to top it off, Civilization 4 is easier to run on Windows.

Why Git?

There are quite a few comparisons between Subversion and Git out there. Ultimately they’re just different philosophies and approaches. For me it came down to:

I like the Git philosophy of being able to distribute patches without creating history on your central repository. At work, doing a code review usually entails doing a checkin (and yes I know you can create svn diffs);
Git allows you to push your changes to several repositories. This is great for redundancy. I’m paranoid about losing source code. Anyone who writes software should be paranoid about becoming the next Avsim;
You can use Git for deployment to your hosting provider; and
All the cool kids are doing it. :-)

That being said, Git does have some downsides:

Subversion has better tooling and IDE integration;
Getting Git to work right on Windows is a hair-pulling experience (which is the point of this post);
With Subversion you are the user that’s set up for you in the repository. In Git, you are who you say you are, which takes a bit of getting used to;
Obviously multiple repositories is by its nature more complicated than a single central repository; and
Subversion deals with binary files better and easier than Git does.

One piece of advice I’ll give you is this: If your Windows username has a space in it, change it. I was bashing my head against a brick wall for awhile before I figured out that my Git commands were failing to remotely authenticate because the Python script didn’t handle the case where the username contained a space as best as I could tell.

Why Cygwin?

The nicest environment to have is one where you don’t have to type in your password every time you want to do a pull or push to a remote repository. Good security suggests you should do such things over SSH.

I wasted a lot of time with firstly the bundled git-bash and then with PuTTY. I had problems with git-bash like when doing a git push over ssh it would inexplicably hang. It also seemed to be leaking file descriptors or something because it reached a point where it wouldn’t connect to anything, not even things I’d successfully connected to.

PuTTY I usually use under sufferance. It does the job but I find myself just wanting a good command line (rather than say plink.exe and a command prompt).

Do yourself a favour and use Cygwin from Day One.

I’m currently using Cygwin 1.7.0 even though it’s in beta. When you install it, you have to select the packages you want. SSH (openssh) is not installed by default so select that under Net or search for it and select it.

One of the (many) nice things about Cygwin is that it creates a virtual filesystem for you where you can mount different directories at different points using the mount command. For example:

mount c:/xampp/htdocs /www

creates a convenient spot for your deployment directory.

If you’re not familiar with a Unix/Linux shell like bash and the typical Unix/Linux commands, do yourself a favour and get comfortable with them.

Why Projectlocker?

One of the things I wanted was a remote backup for my source code that is separate to my hosting account. Some may consider this overly paranoid. I think it’s good practice to have a local repository, your production code deployed on your hosting provider and a remote backup of your development work since that won’t necessarily be pushed to the hosting provider.

I compared several private hosting alternatives including the ever-popular Github, Unfuddle and Projectlocker. Their free version for me had the best features:

Both Subversion and Git;
Multiple active projects;
Unlimited repositories;
RAID storage and nightly backups;
500MB storage; AND
SSL encryption.

These services all differ in what products they integrate (eg Wikis, bug/issue tracking, project management and so on) so you really need to do your own research to find what’s right for you.

The one downside of Projectlocker is their website is rather primitive and at times slow to respond (with certain pages). But once you’re set up you should have almost no need to go to it again.

Setting up SSH

Using public key encryption is far more convenient than being asked for your password every time you want to access the remote repository.

First, create a public key if you don’t have one already:

username@hostname:~$ ssh-keygen
Generating public/private rsa key pair.
Enter file in which to save the key (/home/username/.ssh/id_rsa):
Created directory '/home/username/.ssh'.
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /home/username/.ssh/id_rsa.
Your public key has been saved in /home/username/.ssh/id_rsa.pub.
The key fingerprint is:
63:17:a4:06:78:34:9d:4f:2d:4c:7f:8f:84:5a:4b:c4 username@hostname
username@hostname:~$ cat ~/.ssh/id_rsa.pub
ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAQEArGyNxx5nct8vic01GxKPybSxL6ZNBMcOrtwo0dMSU0qN9l4pxAuX0jjJe4Pl/I121NztTDdiIntOTaYiQQXTQ2NP8MD5X1oyr7svs8Rm50zpQwOQ3rt4MvwgotZZjMoETT39fA3soRoQLQS5LzD0W7cvVdSoTGYcL+lfv2f0xQdS+CgCrRTeiwn7KYgD6arZLo6B1wVPCAmaiyo1Hetu1q7UIzh4dCACUy4BymlLAxon0NRWAhEADKltZqMitnPgDqtRXyMLUzEn6AvIotRprK7LoPzvLqz2MgBfzTne13Dz8LFOPhbM2n7cSf/OEUt+TtKZqvIoUb79smKDsf2aXw== username@hostname

Next, go to the Projectlocker Portal, login and if you haven’t done so already, create a Git repository. Your Git URL will be under “User Home” on the left hand menu. Also on the left-hand menu is “Manage Public Keys”. Click “New Key” and enter:

Save that and assuming everything has been done correctly you should be able to go to your local machine and type:

username@host:~$ ssh git-CompanyName@freeN.projectlocker.com
PTY allocation request failed on channel 0
ERROR:gitosis.serve.main:Need SSH_ORIGINAL_COMMAND in environment.
Connection to freeN.projectlocker.com closed.

You don't have shell access but as long as you don't get prompted for your password, it should all be working correctly. You can get more detailed information with:

username@host:~$ ssh -v git-CompanyName@freeN.projectlocker.com

or even more verbose:

username@host:~$ ssh -vv git-CompanyName@freeN.projectlocker.com

Local Git Repository

There are multiple ways of doing this. You can create a local repository and push it to Projectlocker or you can simply clone it, which is what I’ll do:

username@hostname:~$ git config --global user.name "Your Name"
username@hostname:~$ git config --global user.email "youremail@example.com"
username@hostname:~$ git clone git-CompanyName@freeN.projectlocker.com:project.git
Initialized empty Git repository in /home/username/project/.git/
remote: Counting objects: 118, done.
remote: Compressing objects: 100% (96/96), done.
remote: Total 118 (delta 15), reused 111 (delta 15)
Receiving objects: 100% (118/118), 184.08 KiB | 69 KiB/s, done.
Resolving deltas: 100% (15/15), done.

Your output may look different as I'm cloning a populated repository in this case. The first two statements are telling Git who you are. Any commits will be identified by that name and user and this includes pushes to remote repositories. This is what I mean by Subversoin users needing to get used to this. Rather than being who the remote server authorizes you as, you are who you say you are.

An alternative way to set this up is:

username@hostname:~/work$ git init
Initialized empty Git repository in /home/username/work/.git/
username@hostname:~/work$ git remote add project git-CompanyName@freeN.projectlocker.com:project.git
username@hostname:~/work$ git pull project master
remote: Counting objects: 126, done.
remote: Compressing objects: 100% (102/102), done.
remote: Total 126 (delta 17), reused 111 (delta 15)
Receiving objects: 100% (126/126), 184.87 KiB | 78 KiB/s, done.
Resolving deltas: 100% (17/17), done.
From git-CompanyName@freeN.projectlocker.com:project
 * branch            master     -> FETCH_HEAD

Now try the following test:

hostname@hostname:~/project$ cat > test.txt
This is a test
^D
hostname@hostname:~/project$ git add test.txt
hostname@hostname:~/project$ git remote
origin
hostname@hostname:~/project$ git commit -m "adding test file"
[master 4811b38] adding test file
 1 files changed, 1 insertions(+), 0 deletions(-)
 create mode 100644 test.txt
hostname@hostname:~/project$ git push origin master
Counting objects: 4, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (2/2), done.
Writing objects: 100% (3/3), 282 bytes, done.
Total 3 (delta 1), reused 0 (delta 0)
To git-CompanyName@freeN.projectlocker.com:project.git
   a6a6bf9..4811b38  master -> master
hostname@hostname:~/project$ git rm test.txt
rm 'test.txt'
hostname@hostname:~/project$ git commit -m "getting rid of test"
[master 172d57d] getting rid of test
 1 files changed, 0 insertions(+), 1 deletions(-)
 delete mode 100644 test.txt
hostname@hostname:~/project$ git push origin master
Counting objects: 3, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (2/2), done.
Writing objects: 100% (2/2), 243 bytes, done.
Total 2 (delta 1), reused 0 (delta 0)
To git-CompanyName@freeN.projectlocker.com:project.git
   3edc309..bccaeeb  master -> master

Here we’ve simply added a test file, committed it, pushed the whole master branch back to Projectlocker and then removed it. The "git remote" class lists our remote repositories

Remote Deployment

To do this cleanly, you require SSH shell access to your hosting provider or remote server. Rather than I write this out myself, I shall point you to excellent Using Git to manage a web site as to how to set this up.

Conclusion

I hope you’ve found this guide useful. It can be a daunting task to figure out exactly where to start and how to begin with a new tool like Git, particularly because there are so many ways you can use it. I truly hope this saves you some grief in getting it set up and working on Windows.

PHP and Smarty: What IDE?

2009-09-04T16:06:00.001+08:00

This week I’ve decided to use Smarty for a personal project. I’ve previously been leery of using a template engine with PHP because PHP is a template engine. You can embed code in what are otherwise HTML documents.

Why Smarty?

But this week I’ve come around to the Smarty way of thinking for several reasons.

It has excellent documentation. Every function is documented (as far as I can tell) and there are sections on relevant advanced topics. As regular readers will know, I have been critical of projects lacking documentation;
It’s compiled to PHP anyway so apart from an initial “compile”, there is performance cost for using it.
It simplifies a lot of common task like odd-even table row styling, rendering combo boxes with a particular item selected, etc;
There are extensive variable modifiers;
There is very little magic going on. By “magic” I basically mean auto-loading and other things that introduce code you don’t necessarily expect. Smarty is very straightforward and is obviously designed for high-performance use, which I really appreciate;
Smarty is extensible with it’s plugin architecture and input and output filters.

Ok, so decision made: use Smarty. Now what?

Where are the Tools?

I still haven’t found a PHP IDE that I’m comfortable with. In part, this is probably due to using Intellij IDEA, which as far as I’m concerned is by far the best Java IDE out there. So much so that many Visual Studio users consider Resharper a “must have” extension for .Net development. Resharper and Intellij are both by Jetbrains. Resharper adds a lot of the refactoring tools that Intellij has to Visual Studio.

So what am I looking for?

Syntax highlighting;
Code completion;
Being able to navigate to and from templates, plugins, etc; and
Some form of validation (eg plugin file naming).

The code completion and syntax highlighting should, at a minimum, apply to PHP, HTML, Javascript and CSS. Ideally it would also include good jQuery support but that’s just a nice-to-have.

This isn’t an exhaustive review of these tools, merely an overview based on a fairly narrow set of requirements.

Eclipse PDT

I have never quite grokked the Eclipse way of thinking. The whole perspectives thing where your whole IDE changes when you are, say, debugging never sat right with me. To each their own I guess. You also have the well-known malaise known as Eclipse plugin hell.

Still, I’ve tried it a couple of times and it’s OK but it doesn’t understand Smarty templates. There is a project to add Smarty support to Eclipse but it seems to be abandoned or dead and doesn’t seem to work with Eclipse 3.5.

Netbeans

For PHP I’ve used Netbeans far more than Eclipse. I can’t give you a concrete reason for this other than to say that I just found it less bloated and more straightforward. But unfortunately there is no Smarty support and it appears there are no plans to add it.

Komodo Edit

I only tried the free version (Komodo IDE is commercial) but it has no Smarty support. I’ve read some people rave about this tool. Personally I found it uninspiring.

PhpEd

There are lot of things I like about PhpEd but it is commercial. It has one glaring problem though: You can’t change the font size menus and other UI components. You can change the editing pane but the rest is derived from the OS DPI settings. Apparently this is because of the framework PhpEd is written in from what I could gather from the forums. Still, that’s a problem. There’s a huge difference between a 24” 1920x1200 display and a 15” laptop display that’s also 1920x1200. Changing the DPI setting in the OS is fraught with problems so changing it is not always a viable option.

That being said, I am generally most impressed with this IDE out of all the others. The price (US$210) is that high but it can be a lot for a personal project considering how much you can get for free elsewhere.

One thing I don’t like is that you have to buy a Windows or a Linux version. Why? Compare this to Intellij. You simply buy a license and you can use it on Windows, Mac or Linux. Why should it matter if I want to change my OS? It’s also a greatly different version (3.3.3 on Linux, 5.8 on Windows). Is there a difference? Is Linux lagging behind?

PhpEd does understand Smarty templates though so it has to get a big plus for that.

CodeLobster PHP

I’ve been testing Code Lobster for a few days. It’s an interesting product. What I like about it:

It’s lightweight at under 10 megs in size;
The UI is modern-looking and snappy;
It has support for Smarty, Joomla, Wordpress, CodeIgniter, Drupal and jQuery;
It is quite cheap and you only pay for those plugins you use, basically.

That being said, I did come up with a few things that need some more work.

No “live” search. I’ve been spoilt by Intellij on this one. This is where the cursor moves as you type so you can stop typing as soon as you get to where you want. I consider this a “must have” feature of any editor. The venerable search box needs to be retired;
The search/replace functionality was a bit awkward in how it searches multiple files. It doesn’t list all the matches that you can just click on. Searching a subfolder is awkward;
Making changes to the filesystem externally requires a manual ‘Reload Project’. Something like Netbeans or Intellij will just find changed files quickly;
There doesn’t seem to be a way of moving files around within the IDE;
Some of the auto-formatting takes a bit of getting used to. For example, you type an opening brace and it advances automatically to the next line and indents. That’s not bad. You just need to get used to it.

I can’t say this is an exhaustive list and I’m not saying it’s a bad product. Overall I like it. It’s just a bit rough around the edges.

Web IDE

In the last month, Jetbrains has announced the development of Web IDE in standard and PHP editions. You can download an Early Access Preview release and try it out. To me this is the Great White Hope of the PHP IDE market because I have such enormous respect for Intellij’s code editor, which to me is the most important part of any IDE.

I’ve had a brief look at the PHP support and it still seems like there is a long way to go but I’ll certainly keep an eye on it. Based on Jetbrain’s track record, I have a lot of hope for this one but as Eclipse has shown, making a good Java IDE is different to making a good PHP IDE and as soon as you try to do everything you end up being good at nothing. I usually describe this condition as “doing everything badly”.

Also, it seems Jetbrains will be rolling this functionality into the fully-featured Intellij IDEA 9 (Maia) release so if you happen to get that version anyway (which I will) you’ll get it for “free”.

The good thing about Intellij is that it’s equally usable on Mac, Linux and Windows and you can use your license for any of those. It’s out of the box functionality comes with Subversion integration and pretty much everything you need out of the box. For me, this sure beats the plugin hell of Eclipse like figuring out which Subversion plugin to use (Subclipse or Subversive).

It’s the Little Things

There are plenty of people who happily develop using a text editor such as Textmate, Notepad++, Vim or Emacs. You can but there’s nothing like an IDE that supports left-clicking on a class to open the other class. Or an IDE that understands what framework you use (eg understanding Spring is particularly useful for a Java IDE).

Several of the programs I looked at did things like have code completion for HTML, CSS and Javascript to the point that you could click Ctrl+space and get a list of values for a CSS property. All of those things are useful.

One of the things that really impresses me about Intellij is the little ways the editing makes your life easier. This can be as simple as you type “mysql_query(“ and it inserts a closing parenthesis for you. Lots of programs do that but in Intellij if you then type a closing parenthesis, it moves you cursor after the automatic one. No spurious parenthesis is added and I don’t have to navigate over the automatic one with cursor keys or mouse. This speeds up how fast you can type and helps not break your flow.

That may seem like a small thing but there are literally hundreds of things like that in Intellij to the point that I now look for them in anything else I use, for better or for worse.

Conclusion

I guess the downside of using a dynamic language like PHP is that it’s harder to do anything like validation and navigation.

For my money, at this point in time, I would have to say that PhpEd is the best of the bunch if Smarty is important to you but keep an eye on Web IDE/Intellij IDEA when the next version is released by the end of the year (Q4 2009).