C for Coding

Social is a Cancer

2012-07-23T12:01:00.001+08:00

Two events recently have set me off on what could well end up being a rant.

The first is Kara Swisher’s comments (HN submission and my reply). I firmly believe that the collective brain power and money being spent on social (in particular social “games”) is, well, sad.

The second is the Steam Summer Sale, an annual PC (and Mac and even Linux now I guess) game markdown event where one can pick up games as little as 2 years old for the price of iOS games. I’ve recently gotten back into playing PC games as a distraction and have bought a bunch of games in the last week.

Some are old favourites like Civilization 4 (especially with the superb Fall From Heaven 2 fantasy mod) and the excellent Grand Theft Auto series.

What you notice in playing recent releases (up to 2-3 years) versus older games is one big addition: social. Here is a partial list of what I’ve had to do across various titles recently:

Log onto Ubisoft’s much-hated U-play to play Heroes of Might and Magic 6, a franchise I was once very fond of. Demand probably related to Steam was enough to cause intermittent Uplay outages making single player games unplayable. HoMM6 wouldn’t even let me play until I’d logged on to Uplay at least once. Playing it while on Uplay leads to incessant nagging about connecting with friends, sharing my progress and so on;
Playing GTA IV involves logging onto the Rockstar Social Club and then Windows Game Live, two separate registrations. Windows Game Live needed to install an update that it failed to on two successive occasions, It only succeeded at all because I happened to notice a background confirmation box that needed to be OKed;
Diablo 3 of course only works while online;
A friend bought Burnout Paradise on Steam but Steam… ran out of keys. Say what now? How is this not simply a case of Steam being able to generate their own keys? Why is this not a service? and
EA, Origin and Kalypso each had their own “social” centers to log onto before you could play the game.

I refused to buy Anno 2070 because its social platform/DRM also included limited activations based on hardware changes. Screw that, screw them and screw the horse they rode in on.

Compare this to GTA 3, Vice City and San Andreas and Civ4, all of which simply worked. Emancipation.

Now part of this is the game industry’s obsession with piracy. Making life difficult for consumers who are paying for games is the surest way of all to create software pirates because I guarantee you that the pirated versions don’t have these problems.

Who really shares “achievements” (you can’t really call them that) with their friends on 17 different social platforms or shares the news on Facebook or Twitter? Who really wants to? Does this really add anything to the game? Is it in any way, shape or form more likely to sell more copies of the game or keep people playing for longer?

“Social” is a cancer and it has to stop.

More accurately this kneejerk obsession with social has to stop. Not everything is “social” and-this goes beyond games—don’t ruin your customers experience by foisting “social” on them and then nagging them about it when they simply want to play or use your product.

And don’t get me started on “social” games. They’re simply some combination of the idea of self-expression (“look how I arranged my farm!”) and inciting compulsive behaviour that’s really not much different from being addicted to gambling. I’ve seen iPhone apps were people have clearly spent thousands of real world dollars. It’s nothing more than an exercise in who spends the most real world money. There is no challenge or end result.

It’s simply a constant cycle of compulsive behaviour and big data analytics to identify what works best in creating addicting behaviour.

Social is a cancer. It’s killing the PC as a gaming platform. That makes me sad. It needs to be irradiated, poisoned and excised before it kills the start-up scene too. Instagram is worth more than the New York Times? Is greater than the development budget for SpaceX’s orbital launch vehicle? Give me a break.

Stop it. Now.

Interview Programming Problems Done Right

2012-01-06T07:26:00.001+08:00

Introduction

Why 37signals Doesn't Hire Programmers Based on Brainteasers and my comment on HN generated a lot of responses, so much so that I'm writing this post to properly explain the essence of a good (IMHO) interview programming problem.

Pascal's Triangle

Pascal's Triangle is a shortcut for getting coefficients most often used binomial probability. The root element is 1. Every other element is the sum of the one or two above it (diagonally left and diagonally right).

There are several variations of the problem:

Print out the triangle to a specific row;
Return a given row of the triangle;
Return a given element (by row and index) of the triangle.

All of them use the same basic logic. You explain this to the interviewee and ask them to solve it on paper or on a whiteboard.

Recursive Solution

The simplest version is a recursive solution, something like:

#!/usr/bin/python
def value(row, index):
  if index < 0 or index > row:
    return 0
  if index == 0 or index == row:
    return 1
  return value(row-1, index-1) + value(row-1, index)

def row(n):
  return [value(n, x) for x in xrange(0, n+1)]

for i in xrange(10):
  print row(i)

If a candidate can produce this it is at least a working solution even though the performance (for non-trivial n) is prohibitive. Ideally they would be able to point this out (plus the exponential big-O performance).

On my Macbook Pro (2010) this runs for n=20 in about 0.8 seconds.

Memoization

Some candidates will improve this solution by identifying and caching the repeated calculations. Something like this:

import collections

values = collections.defaultdict(dict)

def value(row, index):
  result = values[row].get(index)
  if result is not None:
    return result
  if index < 0 or index > row:
    return 0
  if index == 0 or index == row:
    return 1
  result = value(row-1, index-1) + value(row-1, index)
  values[row][index] = result
  return result

Real time for n=20 is 0.03 seconds. Bonus points if the candidate correctly states this as "memorization" (rather than the more generic "caching").

Iterative Solution

A more common optimization is to use an iterative rather than recursive solution. The simplest version of this is something like:

#!/usr/bin/python
rows = [[1]]

for row in xrange(1, 20):
  values = [1]
  prev = rows[-1]
  for index in xrange(1, row):
    values.append(prev[index-1] + prev[index])
  values.append(1)
  rows.append(values)

for row in rows:
  print row

Performance is similar to the previous one (0.028 seconds). There are lots of subtle variations of this.

Dynamic Programming

The astute candidate will realize that you don't need to store the rows at all. You only ever need the current and the previous rows. This reduces space for O(n²) to O(n).

#!/usr/bin/python
prev = []
for row in xrange(20):
  curr = [1]
  for index in xrange(1, row):
    curr.append(prev[index-1] + prev[index])
  curr.append(1)
  print curr
  prev = curr

0.027 seconds.

Bonus Points

Assuming f(r, i) returns the value for row r and index i, a candidate may well point out that the triangle is symmetrical, specifically that f(r, i) == f(r, r-i), meaning you, at most, only have to calculate half of the triangle. This is particularly relevant if they are asked to return a specific value (ie f(117, 116) == f(117, 1) == 117).

The second optimization one could make is that since f(r, i) == f(r, i-1) + f(r, i) then to calculate f(r, i) you only need to calculate up to the i'th element of each row.

Why is this a good question?

As demonstrated, the code solutions are short. They're longer in, say, C, C++ or Java rather than Python but not that much longer. The point here isn't to get a perfect solution from the interviewee (meaning that deducting points for a missing colon or a typo would be silly). The purpose of the exercise is to demonstrate the they can turn a relatively simple algorithm into code. They have the thought process to do so. In doing so, their familiarity with their chosen language should be obvious.

Also, there are several degrees of solutions. Any solution trumps no solution but the quality of the solution will give you a useful signal (IMHO).

What should a coding test tell you?

A coding test like this is a negative filter. Assuming your chosen problem is sufficiently simple, if an interviewee can't turn it into at least the outline of code in a reasonable length of time then that's a red flag. If they can do it in record time it doesn't mean they're a rock star. You're just trying to weed out candidates who should've already been screened out.

What's a reasonable length of time? IMHO 5 minutes or less is fast (arguably blazing fast). Anything under 10 minutes is fine. If someone is taking more than say 15-20 minutes, that is possibly cause for concern.

Conclusion

The key qualities in a coding test are:

It needs to be relatively simple. If it takes more than about 20-30 lines of Python to solve it's probably too complex;
It needs to be easy to explain. If someone doesn't know what Pascal's Triangle is, that's not a problem. Explain it; and
The goal is to put thought into code. That code doesn't need to be perfect. It just needs to be sufficiently expressive.

Did Michael Arrington Screw Jason Calacanis and the State of California?

2010-10-01T00:47:00.001+08:00

This week lawyer turned blogger Michael Arrington sold the TecnCrunch network of sites to AOL for an undisclosed sum. That sum has been speculated to be between $25 and $40 million.

The timeline of events suggests a not-so-pretty picture to this saga. But first some background.

The Crunchpad

The Crunchpad was a project to create a $200 tablet started by Arrington in 2008. By June 2009 there had been several prototypes by then in partnership with Fusion Garage. In November 2009, the Crunchpad was dead as Fusion Garage had announced they were going it alone. In December 2009, filed a lawsuit against Fusion Garage from which not much was heard until a September 2010 update that included some fairly damning communications from discovery.

I, like many, felt that Arrington has been screwed on this one. It was clearly his idea and Fusion Garage had seemingly seriously misjudged both the market for their “JooJoo” and Arrington’s resolve to see justice done beyond any sense of any possible restitution.

No formal contract seems to exist between the two parties, which struck many as strange given that Arrington is a lawyer. Fusion Garage seems to have relied upon this fact too not fully understanding or appreciating that a partnership can be inferred from one’s actions.

Tech Crunch Conference

In January 2007, Arrington announced the TechCrunch 20 conference as a joint venture between himself and Jason Calacanis, founder of the Silicon Alley Reporter, Weblogs Inc and Mahalo. TC20 (later TC40 and TC50) was a conference for startups held in San Francisco annually that launched some highly successful companies including Mint.com and Yammer.

In May 2010, Arrington and Calacnis parted ways on TC50. Arrington had earlier (March) launched TechCrunch Disrupt, his own conference. Soon after the split, Calacanis went on to launch the Launch Conference.

Covering the Valley… from Seattle?!

TechCrunch is either a blog or a news organization (depending on whom you ask) that covers startups and entrepreneurs, primarily in the internet space. The Mecca for such companies is of course Silicon Valley, although there are nascent startup scenes in Boulder (eg TechStars), New York, Austin, Boston and other places.

On May 3, 2010, Arrington announced a move to Seattle:

My plan is to roughly split my time between Seattle and Silicon Valley … Seattle is sort of like the minor leagues of the startup world, … But to be honest the biggest reason I’ve moved is to simply mix things up in my life. Like many people I tend to get bored if I stay in one place too long – five years is the longest I’ve lived anywhere since high school. It was time for a change.

The Tax Man

California and Washington have one important difference: Washington has no state income tax. California’s marginal income tax rate is 10.3% (over $1 million). Why does this matter? Capital gains, such as the sale of a company, depending on the state are added to gross income.

That could be as much as $4 million!

There are however some problems. From Do you want to avoid California residency?

(1) California residents pays California tax on all their income.

(2) California generally taxes California-source income, …

So, who is a resident? In determining residency, California law provides two presumptions. The first presumption is that a taxpayer who, in the aggregate, spends more than 9 months of a taxable year in California will be presumed to be a California resident. The second presumption is that an individual whose presence in California does not exceed 6 months within a taxable year and who maintains a permanent home outside California is not considered a California resident provided the taxpayer does not engage in any activity or conduct within the State other than as a seasonal visitor, tourist, or guest.

Permanent residence in Washington? Check. Splitting time between Seattle and the Valley? Check.

But there is no hard and fast rule for what qualifies you as a California resident. It is a subjective test based on factors such as the location of your permanent residence, the location of your family, where you are registered to vote, how much time you spent in California and so on.

Now there’s nothing wrong with minimizing one’s tax liability. The late Australian media magnate Kerry Packer went so far as to say to a 1991 government inquiry:

Of course I am minimising my tax. And if anybody in this country doesn't minimise their tax, they want their heads read, because as a government, I can tell you you're not spending it that well that we should be donating extra!

The interesting part is that the move implies intent. If the California FTB (Franchise Tax Board) argues Arrington moved simply to avoid tax on a business that is clearly associated with, was created in and operates within the state of California, then tax is due. One could go so far as to argue the ethics of paying what’s owed.

But if you ignore that argument and instead argue that the May move to Seattle indicated Arrington’s intent to sell to AOL (rather than simply being a happy coincidence that he moved to an income tax free state 4 months before receiving $30 million), it puts subsequent events into a whole different context.

AOL Buys TechCrunch

On 29 September 2010, AOL Bought TechCrunch. No dollar amount for the sale has been disclosed. Rumours of $25 to $40 million abound. My personal opinion is that it was in the region of $30-35 million with a substantial ($10m+) earn out over 3+ years. The basis for this opinion is, in Arrington's own words

So we begin another journey. I fully intend to stay with AOL for a very, very long time. And the entire team has big incentives to stay on board for at least three years.

(emphasis added)

Plus earn-outs on an acquisition are common practice.

Where this gets really interesting is that according to Business Insider, AOL Tried To Buy TechCrunch Twice Before:

During the second run, AOL wanted to buy TechCrunch for something a little under $25 million. TechCrunch, in negotiations led by CEO Heather Harde, wanted closer to $30 million. AOL wouldn't go there because it thought too much of TechCrunch's revenues were from a conference business it didn't entirely own itself.

(emphasis added)

Tim Armstrong has been CEO of AOL since March 12, 2009. With TechCrunch Disrupt launched in March 2010 and Armstrong purportedly having made at least one other run at TechCrunch, it’s plausible that this move had been planned six months ago.

Jason Calacanis

Calacanis is an incendiary figure, deliberately so. As such he has many detractors. He also has a large media exit to AOL (Weblogs Inc) under his belt. When the sale announcement was imminent, Jason Calacanis Shreds Mike Arrington, Calls Him "A Trainwreck," "A Liability," And "A Sociopath":

@arrington told me he wouldn't sell @TechCrunch for <than $40M last year.TC has ~$6m in revenue/~$1.5m in profits (all TC50!)

Rather prophetic. From back in June:

The Timeline

Date	Event
March 12, 2009	Tim Armstrongs becomes CEO of AOL
2009	Armstrong’s first attempt to buy TechCrunch
September 14-15, 2009	TechCrunch50 conference
March 3, 2010	Arrington announces TechCrunch Disrupt
May 3, 2010	Arrington announces move to Seattle
May 12, 2010	Arrington and Calacanis announce end to TechCrunch50 joint venture.
June 17, 2010	Calacanis first (publicly) accuses Arrington of screwing him out of a piece of the pie.
September 28, 1010	AOL acquires TechCrunch

Conclusion

Where once I felt sympathy for Arrington when he was (quite clearly, in my opinion) intentionally deceived by Fusion Garage, the pendulum has swung the other way.

It’s hard to look at that timeline and not see the intent of Arrington splitting with a partner over something that allegedly represents the majority of TechCrunch’s revenue and then going on to launch a similar conference, building on its success.

As divisive as Calacanis can be, it’s hard to argue that he wasn’t a big part of the TC50 conference at all levels: conceiving (jointly or solely) the idea for the conference, filtering and coaching startups, on-stage presentations, choosing the winners and so on.

Compare this to Chris Dixon’s story: How SiteAdvisor Went From Startup Vision To A Career-Making Exit – with Chris Dixon. There are many tales like this where the founders go above and beyond what’s required to look after those who worked so hard for them.

One could go so far as to call Arrington’s actions premeditated, even despicable.

Coin Tosses, Binomials and Dynamic Programming

2010-08-20T03:19:00.001+08:00

Today someone asked about the probability of outcomes in relation to coin tosses on Stackoverflow. It’s an interesting question because it touches on several areas that programmers should know from maths (probability and counting) to dynamic programming.

Dynamic programming is a divide-and-conquer technique that is often overlooked by programmers. It can sometimes be hard to spot situation where it applies but when it does apply it will typically reduce an algorithm from exponential complexity (which is impractical in all but the smallest of cases) to a polynomial solution.

I will explain these concepts in one of the simplest forms: the humble coin toss.

Bernoulli Trials

A Bernoulli trial is an event (or experiment) that randomly has two outcomes. The probability of each outcome is known. The probability of success is p and the probability of failure is 1-p where 0 < p < 1. The outcome of each trial is independent of any other trial.

What constitutes success is arbitrary. For the purposes of this post, success will be defined as a coin coming up heads. To clarify the independence property, the probability of a coin coming up heads does not change regardless of any previous tosses of that (or any other) coin.

Assume a fair coin (p = 0.5). If you want to determine the probability of k successes (heads) from n trials in the general case, it is worth first recognizing that if you make n coin tosses there are 2ⁿ permutations. We are not interesting in permutations however. For n = 2, heads then tails is identical to tails then heads. If we represent 0 as tails and 1 as heads, the outcomes for the first few values of n are:

Number of Coins	Number of Heads
Number of Coins	0	1	2	3	4
1	0	1
2	00	01 10	11
3	000	100 010 010	011 101 110	111
4	0000	1000 0100 0010 0001	0011 0101 0110 1001 1010 1100	0111 1101 1011 1110	1111

If you ignore the actual values and reduce it to the number of permutations:

Number of Coins	Number of Heads					Total
Number of Coins	0	1	2	3	4	Total
1	1	1				2
2	1	2	1			4
3	1	3	3	1		8
4	1	4	6	4	1	16

Divide the number of desired outcomes by the total number of outcomes and you have your probability.

Binomial Distribution

The above number are obviously not random and correspond to the coefficients of a binomial function:

(1 + x)ⁿ

For example:

(1 + x)² = x² + 2x + 1 (1, 2, 1)
(1 + x)³ = x³ + 3x² + 3x + 1 (1, 3, 3, 1)
(1 + x)⁴ = x⁴ + 4x³ + 6x² + 4x + 1 (1, 4, 6, 4, 1)
…

Any of the above coefficients can be found with factorials:

f(n,k) = ⁿC_k = n! / (n-k)!k!

Binomial Probability

Since we can calculate the number of permutations for our desired outcome and we know the total outcomes are 2ⁿ then:

P(n,k) = ⁿC_k x 2^-n

assuming:

P = the probability of k coins coming up heads for n coin tosses
n = number of coin tosses
k = number of desired successes

Unfair Coins

The above is accurate for fair coins but what about unfair coins? Assume that a given coin has a 60% chance of coming up heads. What does that do to our formula? Very little actually. The above formula is simply a special case of a more general formula.

P(n,k,p) = ⁿC_k x p^k x (1-p)^n-k

assuming:

P = the probability of k coins coming up heads for n coin tosses
n = number of coin tosses
k = number of desired successes
p = probability of a coin coming up heads

Plug in p = 0.5 and the formula reduces to the earlier version.

Pascal’s Triangle

Dealing with factorials is cumbersome and impractical for even small values of n (e.g., 1000! has 2,567 digits). Fortunately there is a much faster method of calculating coefficients known as Pascal's triangle.

If you look at the coefficients to the left, you’ll see that any coefficient is the sum of the two coefficients above it (eg 10 = 4 + 6). This leads to the following function:

C(n,k) = 1 when k = 0 or k = n
= C(n-1,k-1) + C(n-1,k) for 1 < k < n

which could lead to the following naive implementation:

public static int coefficient(int n, int k) {
  return k == 0 || k == n ? 1 : coefficient(n - 1, k - 1) + coefficient(n - 1, k);
}

Unfortunately this simple function has terrible performance: O(2ⁿ) to be precise. The reason is simple: it does an awful lot of redundant calculations There are two ways to solve this performance problem:

Memoization

Memoization is an optimization technique that avoids making repeated calls to the same function with the same arguments. This assumes a pure function, meaning any two calls with the same arguments will evaluate to the same result and there are no relevant side effects. One such implementation is:

private static class Pair {
  public final int n;
  public final int k;

  private Pair(int n, int k) {
    this.n = n;
    this.k = k;
  }
  
  @Override
  public int hashCode() {
    return (n + 37881) * (k + 47911);
  }
  
  @Override
  public boolean equals(Object ob) {
    if (!(ob instanceof Pair)) {
      return false;
    }
    Pair p = (Pair)ob;
    return n == p.n && k == p.k;
  }
}

private static final Map<Pair, Integer> CACHE = new HashMap<Pair, Integer>();

public static int coefficient2(int n, int k) {
  if (k == 0 || k == n) {
    return 1;
  } else if (k == 1 || k == n - 1) {
    return n;
  }
  Pair p = new Pair(n, k);
  Integer i = CACHE.get(p);
  if (i == null) {
    i = coefficient2(n - 1, k - 1) + coefficient2(n - 1, k);
    CACHE.put(p, i);
  }
  return i;
}

To compare, calculating C(34,20) took 10.7 seconds on my PC with the first method and 2.4 milliseconds with the second. C(340,200) still only takes a mere 21.1 ms. There probably isn’t enough time left in the universe for the first one to finish that.

The second method uses O(n²) space and O(n²) time.

Introducing Dynamic Programming

The key to understanding dynamic programming and applying it to a problem is identifying a recurrence relation that expresses the solution for a given value n in terms of the solution for a lower value of n. We’ve already identified this.

It is worth noting that the only thing we need to calculate the values for any row of Pascal’s triangles are the values for the previous row. Therefore, we should never need to keep more than one row in memory at a time, which reduces our desired algorithm to O(n) space.

Consider this implementation:

public static int coefficient3(int n, int k) {
  int[] work = new int[n + 1];
  for ( int i = 1; i <=n ; i++ ) {
    for ( int j = i; j >= 0; j-- ) {
      if (j == 0 || j == i) {
        work[j] = 1;
      } else if (j == 1 || j == i - 1) {
        work[j] = i;
      } else {
        work[j] += work[j - 1];
      }
    }
  }
  return work[k];
}

This algorithm simply calculates one row at a time from the first until the required row is found. Only one row (ie work) is ever kept. The inner loop satisfies the boundary conditions (arguably unnecessarily) and no recursion or more complex cache is required.

This algorithm is still O(n²) but is O(n) space and in practice will be faster than the previous version. My example of C(340,200) runs in 1.5 ms compared 21.6 ms.

Different Coins

Up until now it has been assumed that the same coin (or at least an identical coin) is used for every test. In mathematical terms, p is constant. What if it isn’t? Imagine we have two coins, the first has a 70% chance of coming up heads and the second has a 60% chance, what is the probability of getting one heads when tossing the pair of coins?

Our formula clearly breaks down because it has been assumed until now that HT and TH are interchangeably and (more importantly) equally likely. That is no longer the case.

The simplest solution traverses all permutations, finds those that satisfy the condition and works out their cumulative probability. Consider this terrible implementation:

private static final int SLICES = 10;
private static int[] COINS = {7, 6};

private static void runBruteForce(int... coins) {
  long start = System.nanoTime();
  int[] tally = new int[coins.length + 1];
  bruteForce(tally, coins, 0, 0);
  long end = System.nanoTime();
  int total = 0;
  for (int count : tally) {
    total += count;
  }
  for (int i = 0; i < tally.length; i++) {
    System.out.printf("%d : %,.4f%n", i, (double) tally[i] / total);
  }
  System.out.printf("%nBrute force ran for %d COINS in %,.3f ms%n%n",
      coins.length, (end - start) / 1000000d);
}

private static void bruteForce(int[] table, int[] coins, int index, int count) {
  if (index == coins.length) {
    table[count]++;
    return;
  }
  for (int i = 0; i < coins[index]; i++) {
    bruteForce(table, coins, index + 1, count);
  }
  for (int i = coins[index]; i < SLICES; i++) {
    bruteForce(table, coins, index + 1, count + 1);
  }
}

For simplicity, this code is assuming the probability of heads is an integer multiple of 0.1. The result:

0 : 0.4200
1 : 0.4600
2 : 0.1200

Inspection determines this result is correct. Of course, this algorithm is O(10ⁿ) time. It can be improved to avoid some redundant calls but the resulting algorithm is still exponential.

Dynamic Programming: Part Two

The key to dynamic programming is to be able to state the problem with a suitable recurrence relation that expresses the solution in terms of smaller values of the solution.

General Problem: Given C, a series of n coins p₁ to p_n where p_i represents the probability of the i-th coin coming up heads, what is the probability of k heads coming up from tossing all the coins?

The recurrence relation required to solve this problem isn’t necessarily obvious:

P(n,k,C,i) = p_i x P(n-1,k-1,C,i+1) + (1-p_i) x P(n,k,C,i+1)

To put it another way, if you take a subset of the the coins C from p_i to p_n, the probability that there will be k heads in the remaining coins can be expressed this way: if the current coin p_i is heads then the subsequent coins need only have k-1 heads. But if the current coin comes up tails (at a chance of 1-p_i) then the subsequent coins must contains k heads.

You may need to think about that before it sinks in. Once it does sink in it may not be obvious that this helps solve the problem. The key point to remember is that each step of this relation expresses the solution in terms of one less coin and possibly one less value of k. That divide-and-conquer aspect is the key to dynamic programming.

Algorithm Explained

Assume three coins (0.2, 0.3, 0.4 of coming up heads). Consider the simplest case: k = 0. The probability that all three coins are tails is equal to:

P(3,0,C,1) = (1-p₁) x P(3,0,C,2)
= (1-p₁) x (1-p₂) x P(3,0,C,3)
= (1-p₁) x (1-p₂) x (1-p₃)

which is clearly correct. It gets slightly more complicated when k > 0. We need to remember that we now have a table for k = 0. We can construct a table for k = 1 in terms of that table and so on.

P(3,1,C,1) = p₁ x P(3,0,C,2) + (1-p₁) x P(3,1,C,2)
= ...

Once again, if the current coin comes up heads we need k-1 coins from the remaining coins. If it doesn’t, we need k heads from the remaining coins. the above relation is adding those two things together.

In implementation these two cases (k = 0 and k > 0) tend to be treated the same since k = 0 is a special case of k > 0 given the probability of anything where k = –1 is 0.

Expressing this as a table:

	Coins
Number of Heads	0.200	0.300	0.400
	0.000	0.000	0.000	0.000
0	0.336	0.420	0.600	1.000
1	0.452	0.460	0.400	0.000
2	0.188	0.120	0.000	0.000
3	0.024	0.000	0.000	0.000

Remember each cell in the table is a function of the cell to its right and the cell above that one weighted by the probability of that particular coin. The first column represents the probabilities for 0 to 3 heads from the 3 coins.

Most importantly, this algorithm is O(nk) time and O(nk) space.

Implementation

private static void runDynamic() {
  long start = System.nanoTime();
  double[] probs = dynamic(0.2, 0.3, 0.4);
  long end = System.nanoTime();
  int total = 0;
  for (int i = 0; i < probs.length; i++) {
    System.out.printf("%d : %,.4f%n", i, probs[i]);
  }
  System.out.printf("%nDynamic ran for %d coinsin %,.3f ms%n%n",
      coins.length, (end - start) / 1000000d);
}

private static double[] dynamic(double... coins) {
  double[][] table = new double[coins.length + 2][];
  for (int i = 0; i < table.length; i++) {
    table[i] = new double[coins.length + 1];
  }
  table[1][coins.length] = 1.0d; // everything else is 0.0
  for (int i = 0; i <= coins.length; i++) {
    for (int j = coins.length - 1; j >= 0; j--) {
      table[i + 1][j] = coins[j] * table[i][j + 1] +
          (1 - coins[j]) * table[i + 1][j + 1];
    }
  }
  double[] ret = new double[coins.length + 1];
  for (int i = 0; i < ret.length; i++) {
    ret[i] = table[i + 1][0];
  }
  return ret;
}

Output:

0 : 0.3360
1 : 0.4520
2 : 0.1880
3 : 0.0240

Dynamic ran for 3 coins in 0.018 ms

Conclusion

I hope this serves as a useful introduction to dynamic programming. It can be an incredibly powerful and useful technique but can require some practice to identify where and how to apply it.

The last very short code segment does an awful lot. It can handle large numbers of coins, uniform or not, and deliver results in a timely fashion.

Google Wave, Microsoft and Engineers Running the Asylum

2010-08-06T01:57:00.001+08:00

This week marked the official death of Google Wave and Steve Ballmer described the iPad as “just another PC form factor”. These seemingly unrelated events highlight the perils of both driving and not driving a company from an engineering standpoint.

Microsoft, The Meteor is Coming

For those of us who started using computers before the internet, there is a stark difference between now and 10-20 years ago in the perception of Microsoft. In the post-IBM era, Microsoft was the 800 pound gorilla in the room that crushed everything else, even Apple, Wordperfect, Lotus and Borland.

As much as Bill Gates is derided in some quarters he was and is a programmer. It has probably been many years since he wrote a line of code but the fact remains that has has written code and understands the process. He is a technical guy. Case in point: My First BillG Review.

In those days, Microsoft was a lot less bureaucratic. Instead of the 11 or 12 layers of management they have today, I reported to Mike Conte who reported to Chris Graham who reported to Pete Higgins, who reported to Mike Maples, who reported to Bill. About 6 layers from top to bottom. We made fun of companies like General Motors with their eight layers of management or whatever it was.

…

... and THERE WERE NOTES IN ALL THE MARGINS. ON EVERY PAGE OF THE SPEC. HE HAD READ THE WHOLE GODDAMNED THING AND WRITTEN NOTES IN THE MARGINS.

…

Bill Gates was amazingly technical. He understood Variants, and COM objects, and IDispatch and why Automation is different than vtables and why this might lead to dual interfaces. He worried about date functions. He didn't meddle in software if he trusted the people who were working on it, but you couldn't bullshit him for a minute because he was a programmer. A real, actual, programmer.

Watching non-programmers trying to run software companies is like watching someone who doesn't know how to surf trying to surf.

Steve Ballmer is no Bill Gates.

Ballmer might be a whiz at making org charts, discussing corporate strategy, managing a division, making M&A deals or whatever but he’s simply not technical. He was hired as a business manager and that’s what he is.

The problem is that Microsoft, in spite of everything it’s tried, is a software product company. If you don’t understand how software is created you have, in my opinion, no business running the company. It would be like me, as a programmer, running an airline.

Ballmer isn’t unique or even in the minority here. My personal experience has been the majority of places I have worked haven’t understood software development nor been driven by engineering rather than the business side. Far more common is that programmers are treated as an unavoidable cost centre for which the perfect management metric has yet to be found.

The problem here is twofold:

Microsoft customers are enterprises and PC OEMs not end users; and
Singularity of purpose: Microsoft exists to sell Windows licenses.

The first point is highlighted in another of this week’s stories, Inside Microsoft's internal IE8 privacy battles. Basically, advertising interests won out over user experience.

Windows is so ridiculously convoluted because Microsoft can’t say no to companies that want ridiculous customizations. This is why you have a horrific mishmash of policies, registry settings, etc that mean it’s typically uneconomic to figure out what’s wrong (if not virtually impossible). It’s easier to simply wipe it and start again.

In Commandos, Infantry, and Police, Jeff Atwood references Robert X. Cringely’s book Accidental Empires, which can be used to categorize companies. Startups are commandos. They are aggressively seeking to gain something with nothing to lose. Successful startups become infantry since the army is now so large that it requires structure and discipline. Truly large companies become police that are only interested in maintaining the status quo.

Microsoft’s sole purpose now is to protect its cash cow of Windows and Office. It’s leadership is probably terrified that something will kill the golden goose. What you fear you create. To quote Princess Leia:

The more you tighten your grip, Tarkin, the more star systems will slip through your fingers.

So this is why Ballmer describes the iPad as just another PC form factor because Microsoft just wants to sell more Windows licenses. Ballmer lacks the technical foundation to understand exactly why he’s running a dinosaur so doesn’t comprehend that the meteor is coming.

Google, Today’s Mammals Are Tomorrow’s Dinosaurs

Google has a similar problem to Microsoft in that it has a couple of core, hugely successful products (being the combined search and advertising business) and everything else has either failed, been lacklustre or is yet to bear fruit.

Of course there are successful ancillary products like GMail, Google Maps, Google Docs and so on. Many of these are completely dominant in their space but all of them merely enhance the search and advertising business or simply don’t generate a considerable amount of revenue.

To quote Google’s Revenue Breakdown Shows It Controls Even More Advertising Than You’d Think:

Google revenues last year were $23.6 billion, 99 percent of which came from advertising, the company said. Google doesn’t break down which of its services earn what, and it still hasn’t disclosed share breakdowns from content on YouTube or mobile devices.

Now I say this not to liken Google’s non-search forays as failures (as Microsoft’s forays beyond Windows and Office are almost entirely failures). Google has a different business model. Google is all about people using the Web. The more they use the Web, the more money Google makes. All their successful non-search products share this theme: they lower the cost of or increase the amount or effectiveness of using the Web.

Google is an unusual company in many respects. Larry and Sergey completely nailed search and will go down in history as tech pioneers for doing so. They have created a company that is largely engineering-driven, which shares a couple of parallels to the Microsoft of old except that early Microsoft was all about embracing the external developer community.

That can enable the company to focus on products rather than attempting to quantify programmer performance (a far more typical scenario) but it can have a downside too, which is the whole point of this post.

Despite it’s massive engineering talent, there are areas where Google has been unable to make any headway, namely in the much-hyped social space. Google Wave’s demise foreshadows the increasingly likely (re)entry into the social space, popularly referred to as Google Me.

But the engineering way of thinking left unchecked can have some serious downsides. Consider an example.

Sudoku

We programmers think differently to “normal” people. While we share a lot in common with practitioners of other scientific and engineering disciplines I think it’s fair to say that part of the programmer psyche is still unique. Many programmers don’t realize this and it’s hard to explain to “outsiders” but I shall try with an example.

Sudoku is a number-placement puzzle where the player tries to figure out how to place numbers in a partly filled grid such that certain rules are followed regarding the allowable repetition patterns of those numbers. Puzzles vary in difficulty based on how few numbers they reveal. A given puzzle has but one solution.

Many people enjoy this as a pastime. When first faced with Sudoku I like many programmers reacted in a very different way. I learnt the rules, devised a program that solved any given puzzle, satisfied myself it was correct and then forgot about Sudoku having never done one of these puzzles by hand, which basically defeats the whole point.

Non-programmers will probably find this bizarre. Programmers will almost certainly nod understanding. The point here is that programming trains you to find general solutions. So you can solve one Sudoku puzzle but what would be the point? There are billions of others unsolved! In terms of time investment, you’re better off solving all of them at once!

Google Wave

Google Wave was presented with much fanfare and hype at Google IO 2009. Spearheaded by the quite brilliant Rasmussens (who brought us Google Maps), Wave was touted as one communication platform to rule them all.

Wave was designed to be low level such that any messaging paradigm could be implemented in terms of Wave. Wave could handle a version of email, Twitteresque micro-blogging, IM, even bug tracking and so on. All of these things can be implemented on top of Google Wave.

Or at least that was the theory.

See the pattern here? Much like the Sudoku problem, Google was seeking a general solution to a set of problems.

So while this may be a great engineering feat, it ignored a fairly basic problem: what is the use case for Google Wave? Who will use it? Why? for what?

Those questions are perhaps unfair because many startup ventures begin with an idea and very little idea of what the end will look like. Or at least that end will change several times (dare I utter the overused “pivot” buzzword?). So you can argue that you create a platform and wait for others to find a use for it.

Clearly they didn’t.

Perhaps a better approach is to ask: what is the pain point? What problem is Google Wave solving?

The programmer in me understand the desire to create one platform that can do everything. It’s an alluring siren but don’t lose sight of the rocks drawing ever closer.

To quote Joel Spolsky from How Microsoft Lost the API War:

By the way, for those of you who follow the arcane but politically-charged world of blog syndication feed formats, you can see the same thing happening over there. RSS became fragmented with several different versions, inaccurate specs and lots of political fighting, and the attempt to clean everything up by creating yet another format called Atom has resulted in several different versions of RSS plus one version of Atom, inaccurate specs and lots of political fighting. When you try to unify two opposing forces by creating a third alternative, you just end up with three opposing forces. You haven't unified anything and you haven't really fixed anything.

To paraphrase, Wave didn’t unite anything. In fact it did nothing other than create yet another way we could communicate.

As much as people complain about email, everyone understands the model. A user who gets on the internet for the first time quickly understand the concept of sending someone “electronic mail”. It parallels something with which they are familiar from real life.

Apple and the Click Wheel

Whatever the future holds for Apple, it (or perhaps more accurately, Steve Jobs) will be remembered as one of the most influential tech figures of the computing era to date. Apple popularized and revolutionized digital content distribution, has a brand synonymous with mobile digital music playback and singlehandedly restructured the telecommunications industry.

The first iPod had a speaker behind the click wheel. Its only function was to make clicking noises to give to give the user auditory feedback. Such a feature makes absolutely zero engineering sense. Can you see Microsoft doing this? I can’t. I can’t even see Google doing it.

There is no other company that completely “gets it” in terms of consumer user experience. No one is close. And before you decry Apple for its lack of Flash, the walled app garden, lack of “freedom” (whatever that means today), etc… nobody cares. That includes me.

The point here is that Apple isn’t run by engineers. Apple is completely focused on product and user experience. Anything can be sacrificed to that end. If Apple were run like Microsoft, the iPad would be running some variant of MacOS X. But it doesn’t. Why? Because it makes no sense to put a full desktop OS based on a pixel-perfect pointer interface (ie the mouse) onto a low-power touchscreen device. Apple isn’t concerned about selling OS licenses. They’re focused on the product.

Conclusion

I’m not against programmers running companies. Not at all. Google is a great example of what can be achieved when you give talented engineers the freedom to innovate. Microsoft suffers I believe because its leader has no understanding of how software developments works and how programmers think.

But both extremes can have a downside. This week it killed Google Wave. It’s food for thought as Google ramps up it’s next stab at social.

My Google Interview

2010-07-16T12:50:00.001+08:00

In early June I was contacted by a Google recruiter to ask if I was interested in applying for an engineering role at Google. She had found me based on my Stackoverflow profile. The position she was recruiting for was in Mountain View, California.

Reasons Not to Apply

I had never considered applying to Google for several reasons.

The first is that I’m not a US citizen and I don’t have a green card. This means I would need a visa. For most people, this means the employer needs to sponsor you for a H-1B visa, which anyone familiar with them will tell you is a huge pain. Most employers simply aren’t interested or at least that’s my perception. I guess the larger employers will have the scale and in-house counsel to make this viable.

Many US employers don’t actually know that it’s far, far easier to employ Australians than any other nationality. In fact it’s almost as easy as employing Canadians. Much like the TN (NAFTA) visa, Australians have the E-3 visa but most people don’t know this and employers tend to assume you need a H-1B. US Employers take note: the process for employing Australian nationals is easy.

The second reason I never considered applying to Google is perhaps another misperception on my part. My view was that Googlers seem to fit a particular profile. That profile is of being a graduate of a top school (think Stanford, UW or MIT), typically in their mid to late 20s. That’s not to say all fit this profile but your path is certainly a lot easier if this is you. Again, I’m not claiming this is the case but it certainly was my perception.

The third reason is that Google uses C++. They also use Python, Java and JavaScript but C++ is my particular point of contention. It’s been nearly a decade since I’ve used C++ in anger. Personally I consider it a horrible language. I will go so far as to call it an abomination.

Others have argued this far better than I could, most notably Linus Torvalds, addressing it in 2007 and 2010. Suffice it to say I find C to be a far more elegant and easy-to-understand language for low-level programming.

You could argue that Java and Python can be used by many (most?) Googlers and it’s a reasonable position but one that I don’t think is correct based on my limited experience. More on this later.

Reasons to Apply

The timing of being contacted was somewhat strange and somewhat timely.

In April, a story blew up on Hacker News, proggit and elsewhere concerning an employee leaving Mahalo for Yahoo. Jason Calacanis (CEO of Mahalo) said some perhaps rash things, which the employee foolishly posted to his blog (soon thereafter taken down but you can’t put the genie back in the bottle). More here.

Jason tweeted about this. Entrepreneur-turned-VC Mark Suster chimed in, most notably with Never Hire Job Hoppers. Never. They Make Terrible Employees. This predictably caused an uproar in all the usual places.

My view is Mark makes some good points but it’s too hardline. Let me give you some examples of why.

I started out doing contract (short term) work because that’s all I could get. This all began with doing Perl CGI programming for an ISP that I was a telephone support person for and quickly transitioned into doing full-time programming (elsewhere). This was in part due to the fact that I was studying for my undergraduate degree part-time (so didn’t qualify for graduate programs), partly due to my location (most Australian companies are headquartered in Sydney in Melbourne so programming employment opportunities are disproportionately low in population terms in Perth) and partly due to timing (the early to mid-90s were a still a post-recession period).

Little did I know that this would brand me to some extent a contractor for life. In many organization contractors are viewed as some combination of second-class citizen (eg I worked at one place that didn’t give internet access to contractors), necessary evil and disloyal mercenary. Most importantly, they are expendable and first to go in tough times. This last part of it I’m fine with because I viewed it as the ultimate meritocracy: you’d stay employed as long as you were valuable.

In 2001 I moved to London, England and found this anti-contractor sentiment to be even more prevalent, which surprised me no end. So the cycle continued.

Stays at various companies varied from 3 months to 3 years (on two occasions; one ending when the company fired all contractors and half the salaried staff due to financial woes and the other ending when the company was acquired and it became clear the software’s future was limited).

But in this time I’ve been screwed over more times than I can recount.

I’ve had a client threaten to sue and terminate a contract leaving months unpaid simply as a tactic to avoid paying. I’ve been denied payments by a recruitment agent I was entitled to simply because it was too expensive and time consuming (for me) to pursue legal action. I’ve been thrown under the bus in a political move by a manager who had a project going south and was looking for a scapegoat so his boss wouldn’t fire or replace him. I’ve had someone promise to pay only later realizing they were hiding behind an offshore shelter and never had any intention of paying. The list goes on.

All in all I’ve probably lost $50,000 to $100,000 over the years from this kind of thing so when Mark (or anyone) likens this to a lack of loyalty, it’s fair to say it pisses me off.

That’s not to say I’ve never done anything on reflection I probably shouldn’t have but hey we all make mistakes. I’ve never intentionally screwed anyone over this way.

Perhaps the most erudite and eloquent take on this issue came from one of my favourite bloggers, Giles Bowkett, in Job-Hopping:

Sorry, tangent. Point is, a job-hopper is like Larry King. Larry King's about to have his 8th divorce. He has all these women asking him to marry them, he marries them, it doesn't work out, he moves on to the next one. I don't know Larry King and I wish him the best, but to me, it sure looks like every time he gets married, he's settling. If that wasn't the way it was, he would have fought to keep at least oneof those marriages intact. And that's kinda what's going on if you're a job-hopper. It means the companies want you bad, but you could care less about the companies. I hate to side with the VCs here, but if they want you more than you want them, maybe it means you need to aim higher.

I’ve spent too many years writing bullshit business software, wading through pointless process (eg spending a day in meetings to remove a comma; no I’m not kidding) and doing other brain dead nonsense. I’m tired of it. I’ve had enough. I’ve reached the point that I don’t want to do it anymore. It’s time to make a change even though I’m not exactly sure what that change is yet. It’s reached the point where I’d rather work for nothing on something remotely interesting than do this one more day.

So this had been percolating in my brain. To bring this back to Google, that’s why I say the timing was strange. The project I’d been working on (which was turning into another that was running out of money) was on hiatus and I was looking to do something different.

So I said yes I would apply.

Telephone Interviews

Let me first say it was hard to speak to them on the phone. By some quirk of geography, Mountain View, California and Perth, Western Australia and 16 hours apart (Perth is 16 hours ahead), which really limited times when they were at work and I was awake.

The recruiter told me there would be a couple of phone interviews over the next couple of weeks. I had one the next week that went through a couple of questions.

Note: for this and the on-site interviews I’m not going to reveal the exact content. For the on-sites I signed an NDA but more importantly (at least to me) I said I wouldn’t.

All I’ll say is that Google’s position seems to be that they want to assess your knowledge of computer science fundamentals and problem solving ability. If you Google “google interview questions” you’ll find the kind of problem that require some kind of recursive or other divide-and-conquer type technique. This makes sense and this theme gelled with my experience overall.

I got through two questions even though I stumbled somewhat through the second. I was trying to visualize the solution and that was the problem. As soon as I took a piece of paper and drew a diagram the solution was obvious. That’s just me: I like to whiteboard/diagram rather than trying to mentally visualize.

It took until next week to hear back. I’d been expecting a second phone screen. As it turned out they wanted to arrange a series of on-site interviews at their office in Sydney. I took this as a good sign: apparently I didn’t require a second idiot test.

Preparation

My field guide for this was Steve Yegge’s Get that job at Google. It’s good advice, not just for Google but for also being a well-rounded programmer.

Like I said, I’ve spent a lot of time writing bullshit business software. Frankly my day-to-day usage of graphs, dynamic programming and balanced trees is, well, almost nonexistent. So it was time to brush up. And brush up I did.

I did some thinking about Steve’s post being over two years old. The one thing missing from this is language theory (compilers, grammars, lexing/parsing and so on). Since Steve’s post Google has added:

V8: a Javascript engine;
Go: programming language; and
Unladen Swallow: an LLVM port of CPython aimed at hugely speeding it up.

So I concluded language theory is important but luckily I’d been doing that anyway as part of my (sadly stalled) Markdown project.

On-Site Interviews

A couple of weeks later I was flown to Sydney for 4 hours of back-to-back interviews. It’s been some years since I’ve been in Sydney so this was enjoyable anyway.

I am primarily a Java developer, more by circumstance than planning. I transitioned to Java in the late 90s from doing Perl, C and C++. Since then I’ve dabbled in many languages including Javascript, C#, Haskell, Ruby, Python, PHP and others.

The first problem I encountered was that at least two of my interviewers had only passing or no familiarity with Java. This made it particularly difficult as some concepts are unique to one language.

But everyone knew C++. I’ve read about this before. This combined with my own experience now leads me to believe that C++ isn’t optional for any Google applicant. Not because you need to use it to work there. I have no direct experience of this. But because of “interviewer lottery”. Some at Google (it seems) do nothing but C++. You might be interviewed by one of these people.

I had to write several code segments on a whiteboard. This I expected and was fine with. I realize this is necessary (see Why Can't Programmers.. Program? and The Non-Programming Programmer) and have no problem with it but it depends on what kind of problem you ask. Simple is usually best.

Two of the problems I had were extremely finnicky to solve. In one I think the interviewer was understanding and simply wanted to determine if I understand the relevant contract and I could see what the issues were more than coding a completely correct solution (which I appreciated). Another interview got caught short before an efficient solution could be developed and I really don’t think it’s the kind of problem that lends itself to writing a code solution in 40 minute. By this I mean I believe it would be more valuable to speak about the algorithms and problems involved as the code for an efficient solution would be quite complex.

The theme of problem solving and analyzing thought processes remained constant throughout.

For some reason I had expected there would be a lunch break (10-2). There wasn’t. By the end I was mentally exhausted, 3pm (it ran over time) and I hadn’t eaten since the day before. The next day I returned home.

Aftermath

I was told the results would be reviewed and I would hear from them in two weeks.

Two weeks rolled around. A time for a phone call was organized. That phone call was rather short: “strong but not strong enough for this particular position” was the crux of it.

I’d be lying if I said I wasn’t disappointed. I’d actually gone into the whole thing fairly neutral to begin with in that I wasn’t mad keen on working for Google but was open to the possibility. But as time went on and I spoke to a few Googlers, I got more excited about it. I started to hope it would work out.

I actually thought the on-sites went quite well and I did expect it to progress to the next level (whatever that would’ve been I’m not sure) but my hopes were dashed.

The recruiter told me no specific feedback would be given (since I asked on what the weaknesses were). The one outright bizarre thing I was told was I was “too Microsoft-centric” (direct quote). Apart from dabbling in C# I haven’t programmed for Windows since Visual Studio 6 in 2000. It made me wonder if they were looking at the right candidate. And if I’m too Microsoft-centric, what is Jon Skeet?

Feedback

I have obviously been supervised in the workplace, I’ve supervised other developers, I’ve done recruiting for companies and obviously been recruited. An important theme through all of these is the need for feedback. People need to know what they’re doing right and what they’re doing wrong.

In high school in Western Australia we have (had?) a thing called the TEE (Tertiary Entrance Exams). In year 12 (the last year of high school) you have a set of exames. Your coursework for the year and that exam result is added up with equal weighting (so 50-50), massaged through a bewildering array of scaling formulae and comes out as a score that is used for university admission. In Australia we don’t have the same system as the US of application essays, admissions committees looking at your extracurricular interests and so on. It’s all about that number.

Anyway to prepare for our TEE exams in all my subjects we went through old exam papers. For Maths I did the exam papers for the previous ten years. Our teacher would go through the problems and we could see what we did right and what we did wrong. This was incredibly valuable. Exams may test knowledge but taking exams is also a skill. If you’ve seen how to solve 50 problems and gone through the process of doing so you’re much more likely to be able to apply that knowledge to future problems. There are only so many ways you can state an integral calculus problem on an exam paper.

The Soviet Union dominated the chess world for much of the twentieth century. The Russian approach was to teach students Chess through old games.

When I got to university this all changed. You couldn’t keep the exam paper. Previous exam papers were never examined. Your exam was never given back to you so you could see what you got right and what you got wrong. The exam problems were never solved in class so you could see the right and wrong ways to go about it. This was probably so lecturers could reuse papers year after year rather than writing new papers but ultimately I considered it then (and still consider it) a failing.

Recently I did a Masters degree (in quantitative finance) and found it to be even worse: there were deliberate holes in your lecture notes about applying that knowledge to particular problems and you could bet those would be what shows up in the exam.

Why I consider this a failing is that if you’re truly meant to learn something you should concentrate on (and be told) what you don’t know, what you got wrong.

This is what I mean by feedback.

I don’t even know what position I was applying for. I don’t know what the requirements were. I don’t know what my perceived strengths and weaknesses were. So while I enjoyed much of the actual process it did require a significant time investment and the value proposition for me, as a candidate, is very low. I’ve been told that my application may be reevaluated in a year. The recruiter told me they’d like to keep me on file. I don’t know if this means anything but I’m assuming not simply because it’s the kind of “let’s still be friends” lip service companies tend to offer candidates.

One person asked if I would reapply. My inclination at this point is to say “no”. This might still be the disappointment talking (and I am disappointed) but a year is a long time. The timing worked out well this time around but the likelihood of it doing so a year from now are, well, unlikely. Taking a few days off to interview again for a low value proposition from the process may very well be hard to justify. At the risk of tooting my own horn, I tend to be free as I am now by choice rather than circumstance. It’s simply a question of finding something that doesn’t bore me shitless.

Conclusion

This has been a long post (now over 3,000 words), worthy of the best of Steve Yegge in length if not content.

My view of Google has changed. I don’t have the same view of Google being a Mecca for Ivy-shrouded twentysomethings. It does seem like they really are interested in talent in many forms.

But the process does seem to be a lottery to some extent. I don’t know what the selection criteria is but it wouldn’t surprise me if 4 (or even all 5) of your 5 interviewers need to give you a thumbs up for you to go on. This may represent the “anarchic” (even haphazard) culture of Google itself. I really don’t know.

I do get the impression that references from Googlers count for a lot.

I’ve read that Google receives some 1,500 CVs a day and they do on-site interviews for less than 1% of these so perhaps I should be flattered and should just take the experience for what it was. To some extent I do. I’m simply not sure I feel the need to repeat it next year.

Google’s Position on Flash is as Bad as Apple’s

2010-04-29T23:21:00.001+08:00

Steve Jobs has been remarkably talkative of late. Most recently, he posted Thoughts on Flash and before that has randomly (yet tersely) replied to seemingly random emails.

Jobs actually makes some interesting points in this post but there is something hysterically funny about Apple criticizing Flash for not being “open” (as Bart would say, the ironing is delicious) but once you get past that, comments about video decoding in software, battery life, etc all fit in Jobs’ famous unwavering commitment to his product vision. The battery performance of the iPad and Macbooks are almost legendary.

Lack of Flash has become a rallying cry for iphone malcontents and Android proponents of late. Barely a day goes by that Buzz Out Loud, particularly for Molly Wood and Jason Howell. Such people typically praise Google’s openness with its adoption of Flash.

Last month, Google announced a partnership with Adobe, one effect of which is that Flash will be bundled with Chrome (and later Chrome OS).

This got me thinking. I don’t like Flash. I don’t want it in my browser. Flash tends to be abused (by advertisers). Some have used Flash to restore deleted tracking cookies, which is a huge privacy (even security) concern.

I have previously tried to remove Flash from Chrome (my preferred browser). You can remove it but then every page you go to tells you you’re missing necessary plug-ins and asks if you want to install them. Is there an option to disable this message/request? No.

As of Chrome 3 extensions have come to the rescue and Flashblock is a must-have. Still, this solution is not completely satisfactory. Some Web sites will put extra Flash widgets (sometimes as small as a pixel) to defeat Flash blockers. Click on one of these regions/pixels and you’ve just run some Flash you probably didn’t mean to run.

I can understand the criticisms of Apple’s position even though I personally want to see Flash die a horribly fiery death. But Google isn’t giving me a choice either. Instead of allowing me to have Flash if I wish, it’s forcing me to have Flash whether I like it or not (and, trust me, I don’t).

Now that Youtube has HTML5 video, I don’t need Flash for anything. Why won’t Google give me that choice?

How to Resign Gracefully

2010-04-26T09:39:00.001+08:00

An engineer resigned this week from an LA startup. This otherwise insignificant event turned into a big story when that engineer posted the exchange with his boss on his blog. It’s a lesson in human nature and how to comport oneself in a business environment.

Background

The resignation of an engineer from Mahalo and the subsequent email exchange between that engineer and the CEO, high profile Jason Calacanis, became news this week. It all started with this tweet:

Free advice for entitled Gen Y trophy kids: if you spend 12 months at a company over and over you look like a flake.

The “trophy kid” remark refers to a previous statement by Jason about the trend of Gen-Y now getting trophies or awards for participation, basically for just showing up.

This prompted prominent venture capitalist and host of This Week In Venture Capital host Mark Suster tweeted:

.@jason @tonyadam - I never hire job hoppers. Never. They never make good employees. Jason was spot on.

and then posted the somewhat controversial Never Hire Job Hoppers. Never. They Make Terrible Employees, which was later tempered with Job Hoppers Redux: An Employee’s Perspective.

It became clear that this referred to the resignation of one Evan Culver when he posted the email exchange on his blog (now removed). TechCrunch posted the exchange in How Not To Handle A Resignation Gracefully, which has triggered a firestorm of response, much of it directed at Jason and allegedly much of it has been removed by the moderators.

The Facts

Evan’s email says:

This isn’t an easy email to write, but as the subject suggests, this email is to inform you of my resignation from Mahalo effective in 2 weeks.

This email was sent to Jacob Burch (Director of Technology), Jeff Ammons (Developer) and Jason. It appears Jason was out of the office (his reply is from his Blackberry) and it’s alleged in the TechCrunch comments that Evan resigned to the CTO (Mark Jeffrey).

California is an at-will employment state so barring any relevant contractual terms, no notice was required to quit and no reason is required to fire someone (barring legal issues such as discrimination).

Evan’s email was polite but otherwise perfunctory.

Jason addresses this issue in This Week In Startups #49 saying that he liked the guy, two weeks prior he had been promoted into a management position.

That being said, let me give you some advice.

Showing Up Is Not Enough

It’s about what you do, what you’re achieved. Nobody cares if you simply showed up. This is the tragedy of the modern education system in that it rewards participation not winning. Whether it be children, employees or whatever you are doing them a huge disservice and creating an entitlement culture.

You Will Get Yelled At

A lot of comments on TechCrunch revolved around being treated badly. If you’re lucky you have a boss that’s passionate about what they’re doing. If so, such bosses will get heated and yell because they care.

Getting treated badly is actually having a boss who is completely indifferent. At that point you’re simply a square on an org chart and a line item on a budget, utterly expendable and replaceable.

This shouldn’t be taken as carte blanche for employee abuse but nor should isolated incidents of being yelled at be taken for abuse.

Man Up (In Person)

Apologists will argue that in the age of modern communication, it’s OK to resign by email. Let me be absolutely clear: it absolutely is not.

You walk into your boss’s office and say “I’m not happy because of …” or “I’ve been offered this opportunity to do …” or whatever the case is. Give your boss a chance to respond. This isn’t about making a play for more money. It’s about respect. Even if you have no intention of staying, just by giving your boss a chance to respond and to do in person, you’ve shown that person the respect they probably deserve.

They’re not in the office? You wait a few days until they are. They new job can’t way? Bullshit. Or, if true, it’s a good sign that it’s an organization you don’t want to work for because they don’t care about you.

Most of all, be honest. If it’s more money you want or need, say so. If you simply don’t like it where you are or you think it’s a mistake, say so.

A Startup is not a Large Company

The vast majority of startups are small. That means that each person is much more valuable and much harder to replace. What’s more, most employees will have some kind of equity stake in the company. Contrast this to a large company where you tend to be a small cog in a very large machine and infinitely replaceable. You can’t compare the two experiences.

Chris Dixon posted Twelve months notice:

Generally speaking, there are two approaches to relating to other people in the business world. The first approach is transactional and legalistic: work is primarily an exchange of labor for money, and agreements are made via contracts. Enforcement is provided by organizations, especially the legal system. The second approach relies on trust, verbal agreements, reputation and norms, and looks to the community to provide enforcement when necessary.

In the startup world, the latter approach dominates…

For this reason, if you are an employee working at a startup where the managers are honest, inclusive and fair, you should disregard everything you’ve learned about proper behavior from people outside of the startup world.

So ignore any comments about the “at-will” issue. It’s irrelevant.

Never Ever Embarrass Your Boss

This is Evan’s biggest faux pas: posting the email exchange on his blog. Note the self satisfied:

I should note, that instead of responding, he instead removed my email account. Real pro of him. Good thing I forwarded it to myself first :P

Make no mistake: this is deplorable behaviour. Had it remained private, which it should’ve, Jason may have calmed down and mellowed about the situation over time. As it stands, he would rightfully be incensed because this has become a news story.

Worse for Evan: any future employer will find this story on a Google search and it makes him look really bad.

Barred From The Office

When someone resigns or is fired it is not uncommon to pay them for their notice period and send them home immediately. Frankly I wish more companies would do this.

Employees that are fired—especially programmers and other IT people—can be a security risk as they can do a lot of damage. That rarely happens but it is an issue. What’s more common is soon-to-be former employees can be disruptive and drain the morale of the team that’s staying. It’s often better to simply tie things off cleanly.

In TWIST #49, Jason also mentioned the salient point that Yahoo (the company Evan is apparently joining) is a competing company to Mahalo. They’re both search companies with Q&A platforms.

Some tried to turn this into an issue about unlawfully withholding belongings. I can guarantee you that if there was anything urgent there (eg prescription medication) that he would’ve gotten that ASAP. Otherwise his stuff would be put in a box and either couriered or delivered to the lobby for his collection in a timely manner.

An employer is well within their rights to bar you from the premises.

A Final Point About Human Nature

There is a key observation you can make from the comments on this about human nature: the majority of people will start with a conclusion and then look for facts to support that conclusion.

A vocal minority really doesn’t like Jason. So what? How is that relevant? You don’t like Mahalo either? How is that relevant? It isn’t. This story for many has simply become another opportunity to bash Jason and grind whatever axe it is you feel the need to grind.

Conclusion

This story that never should’ve been a story is a good opportunity to learn a few lessons about conducting oneself in a professional manner.

The American’s Guide to the Australian Internet Filter

2010-04-13T09:53:00.001+08:00

Australia has been in the tech news for all the wrong reasons in the last year: for trying to impose the kind of internet filter used more commonly by dictatorships and communist countries (eg China). Yet this coverage seems to miss the reasons for this so, speaking as an Australian, I will explain.

The Boring Stuff First (yes, it’s relevant!)

Australia’s political system is a mixture of the British Westminster system and the American system. Similar to the United States, Australia has a dual-sovereignty federal system. There are six states and two territories.

The House of Representatives is analogous to Congress. There are 150 seats (or electorates) much like congressional districts. Whichever part has the most seats in the House of Representatives forms government. The leader of that party becomes the Prime Minister, the head of government. In certain cases where no party can form a majority (which can happen with minority parts and independent members) a minority government can form but this isn’t terribly common and tends to be unstable.

The Senate is representation for the states. Each state gets 12 senators and each territory 2, for a total of 76.

The nominal head of state is the Governor General. Officially he or she is the representative of the British monarch. Constitutionally, the Governor-General has several powers but the role is largely ceremonial yet the Governor General can (and has) sacked the government and dissolved Parliament (see the 1975 dismissal of Gough Whitlam). The Prime Minister nominates the Governor General. The British monarch basically rubberstamps that choice.

All 150 seats in the House are contested every election, which occurs approximately every three years. I say “approximately” because whereas the United States has constitutionally mandated election dates, the Prime Minister can ask the Governor General to dissolve Parliament and call an election at any time. It is simply required to happen at least every three years. Snap elections when the government is enjoying a surge in popularity to increase the majority in the House are not uncommon.

The United States and most other countries use a voting system commonly referred to as First Past the Post. If a candidate secures a simple majority, they win. Where this doesn’t happen, often there is a runoff election between the top two candidates.

Australia uses a preferential voting system. You can say on your ballot that your preferences are:

John Smith (Greens)
Mary Miler (ALP)
Gary Mason (Liberal)

What this means is that if your first preference fails to get a simple majority there is an elimination system in place. The candidate with the least first preferences is eliminated. All votes for that candidate go to second preference of each voter and so on until someone has a majority. It’s a remarkably elegant system that means a vote for a minor party is not a wasted vote as it is in the US.

The Senate is a little different. Half the Senate seats are contested each election. In most cases this means six seats in each state. The same preferential system is used but instead of securing a majority a candidate merely needs roughly 14% of the distributed preferences to secure a seat. This means minor parties are represented much more in the Senate.

As in the US, a bill has to be passed by both houses of parliament to become law. There is no powerful executive branch however. Nor is there is a Senate filibuster mechanism.

It’s the Politics, Stupid

Federal Government is currently held by the Australian Labor Party (ALP), which philosophically is most like the Democrats in the United States.

The Republican equivalent is made up of two parties: the Liberal Party and the National Party, which together form what is most often referred to as the Coalition. The National Party hold rural seats (that the Liberal Party does not contest) and is focused on issues that affect “the bush”.

The biggest minor party is the Greens, who are focused on environmental issues.

The Government by definition holds a majority of the House of Representatives so typically it isn’t an issue to pass bills through the HoR yet it can and does happen that members from one party or another cross the floor to vote with the other side allowing the opposition party to pass bills or the government to fail to pass bills.

The Senate has to pass the same bill and here’s where it gets interesting. It is highly unusual for one party to hold a Senate majority because only ~14% of the preferential vote is required to get a Senate seat. Yet this did happen for the previous Coalition government. The current makeup is:

Party	Seats
ALP	32
Coalition	37
Greens	5
Independent (no party)	1
Family First	1

In recent years the Senate has held a disproportionate amount of power because the independents and minor parties have held the balance of power.

Assuming the Greens vote with the ALP, which is most often but not always the case, the votes are split 37-37 with 38 required to pass a bill. That means the government needs to attract Nick Xenophon (independent) and Steve Fielding (Family First) to pass bills in a strict party line vote, which happens a lot.

Family First is a relatively new political force in Australia. Their politics are as the name suggests. The Coalition tends to be sensitive to some of the same issues.

This results in a virtual quid pro quo where those holding the balance of power will vote with the Government in exchange for the Government passing legislation friendly to their pet issues. Child safety on the internet and pornography are high on that list.

The previous Coalition of John Howard had a similar phase when Brian Harradine and Mal Colston held the balance of power.

So first and foremost it’s a numbers game.

The Politicians’ Syllogism

ZDNet covered this in Internet filter according to Yes Minister. Politicians—including our so-called Minister for Broadband, Communications and the Digital Economy, Stephen Conroy—don’t understand the internet. The logic goes something like this:

The internet contains bad things;
A filter can stop bad things;
Therefore we must filter the internet.

I am not kidding. This is the logic.

Conclusion

Coverage on the Web typically comprehends the second point: that politicians generally don’t understand the internet. That explains why a handful want this but it ignores the larger issue that numbers in the Senate is what’s driving this forwards.

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.