If your build breaks with a PLY "invalid syntax" error on "dictionary"...

... make sure there aren't files called xpidllex.py and xpidlyacc.py in $topsrcdir/xpcom/idl-parser.

Removing them, and whatever .pyc files are in there, and then doing a clobber build should fix things up.

Paper voting is broken

An interesting link popped up on Hacker News today: the Wombat voting system. It's part of a long line of electronic voting systems (including Helios, created by Ben Adida, now at Mozilla) that aim to use cryptography to ensure the privacy and integrity of votes.

Of course, Hacker News, being the contrarian, negative community that it is, immediately shot it down by claiming that "we don't need computers in voting", that such systems attempt to "fix a problem which don't exist", and that such systems alienate "common people without IT education".

It's sad to see people -- on Hacker News of all places -- being Luddites.

Paper voting is fundamentally broken, and will continue to be as the world's population increases. The reason's simple: it doesn't scale. The last Indian general election had over 417 million people casting votes. 417 million. Imagine the sheer amount of time and resources it would take to count 417 million votes, and the possibility of error that might happen with improperly marked ballots, etc.

Fortunately, Indian elections haven't had paper voting for a while. They've instead had standalone voting machines that keep a tally of votes for each candidate and reveal them on counting day. However, the election commission of India expects citizens to trust these machines on their word, and it's been shown that these machines are actually quite vulnerable to fraud.

So, yes, the problem exists, and yes, we need computers to solve it. I'm glad to see brilliant minds hard at work on solutions. Democracy's far too important to let voting systems not be end-to-end auditable by anyone with the requisite knowledge.

One last note: do people feel alienated when they check their email, type in their credit card number on a shopping site, or operate their bank accounts over the Internet without knowing all the mathematics and engineering making sure no one else is reading their data? The way crypto, and scientific knowledge in general, has always worked is that you either (a) have domain knowledge that lets you verify what is being said, or (b) trust others who do.

Dissent

Over the last two days, I've read a number of blog posts I disagreed with. A couple of them allowed me to comment, so I did so.

On one of them, my comments are still up.

On the other, which adopted a roughly antipodal view, my comments were summarily deleted and I was told I was "derailing and silencing" the conversation by accusing the author of being "overemotional", "oversensitive" and "taking things too personally".

Before today, if you'd asked me which post that would have happened with, I'd have picked the first without a second thought.

Guess I have a lot to learn.

Dr. Seuss and the halting problem

The unsolvability of the halting problem is a well-known fundamental result which says that it's impossible to write an algorithm that determines if an arbitrary program halts given some input. It also implies a lot of other things -- including, for example, that there's no general way to determine whether a particular variable in a program has a particular value at a point, and famously, that every consistent formal system powerful enough to do arithmetic in will have unprovable statements.

I'm not going to talk much about it, though -- instead I'm going to direct you to this extraordinary proof, written in verse, in the style of Dr. Seuss. It's called Scooping the Loop Snooper, and it was written by Geoffrey K. Pullum, who you might also know from posts at the Language Log. Wow.

Important upcoming change: starting Gecko 12, pre-Windows 7 SDKs will no longer be supported

tl;dr: if you're on an outdated Windows build configuration, upgrade.

I just checked in a patch to mozilla-inbound to drop support for SDKs prior to the Windows 7 SDK. Depending on when you last updated your build configuration, your Mozilla build might break.

Everything's documented on the Windows SDK versions page on MDN; here's a quick summary of what you need to do:

• If you're on Windows 2000: Upgrade to Windows XP, Vista or 7.
• If you're on Windows XP SP1 or below: Update to the newest service pack.
• If you have an older SDK (Vista or 2003): Install the Windows 7 SDK instead. You can either download it separately or use Visual C++ 10 Pro, which comes with it.
• If you use Visual C++ 8 (2005) Express or Visual C++ 7.1 (VS2003): Upgrade to Visual C++ 10 (2010; recommended; pro or express) or Visual C++ 9 with Service Pack 1 (2008; pro or express).

MSVC9+ opt builds currently broken due to a compiler bug

Optimized builds with Microsoft Visual Studio 2008 (VC9) and above are currently broken because of what we believe is a compiler bug. More information and workaround in bug 718541.

C# 5.0 to have fresh bindings per iteration

Straight from Eric Lippert. Great news. Now if only ECMAScript Harmony included a fix for this bug...

More experiences with an Apple notebook

It's now been eight months since I got my first Apple notebook. A few months ago I wrote about my initial opinion, where I was pretty sure it would be my last Apple notebook too.

Since then I've had the chance to use it in a variety of situations. Spoiler: none of what I've seen has improved my opinion of it one bit.

1. The decision to make the outer body out of aluminium is literally shocking. If the notebook isn't plugged in to a grounded socket (for instance, if I'm using the plug that comes with the power brick BY DEFAULT), I'm liable to get electric shocks if I touch the casing. I received a couple of shocks, a mild one and a jolting one, before I realized what was happening. Electrical common sense is that if the outer surface is electrically conducting, it MUST be grounded properly. Having an ungrounded plug by default, or even having one in the first place, is inexcusable. (Update: I've had several people complain to me about this, and one person also complain about his plastic macbook's screws shocking him several times. I'm clearly not the only one with this issue.)
2. The Wi-Fi reception is the worst I've ever seen in a laptop, and only slightly better than the reception my Nexus S with its puny little antenna gets. Friends tell me it's because the aluminium casing acts as a Faraday cage and attenuates the signal. The "unibody" marketing's clearly far more important to Apple than shipping a working product. (Update: guess who says metal has a "very high" potential to interfere with wireless connections?)
3. The original power adapters were T-shaped. However, presumably because Apple didn't like the look of and subsequently didn't include the strain-relieving flexes found on all other cables, they were easily frayed. To "fix" this, they started using L-shaped adapters. Of course, what it now means is that depending on the way I insert it, either the power cord blocks the Ethernet port or it gets subjected to strain if I tilt the notebook back.
4. There's no VGA, DVI or HDMI port, so I need to carry around a set of three dongles everywhere I go. There's plenty of space on the left side, too, so that's not an excuse.
5. The lack of working sleep is more annoying than I thought it would be. Amazingly, the EFI equivalent to the POST takes almost as long as Windows resuming from hibernation. A few people seem to be working on getting Windows to boot via EFI, and my hopes are mostly pinned on that.

My iPod nano media player, the only other Apple product I own, is actually well-designed (save for the fact that I need to keep the piece of crap called iTunes around on my computer, even though I don't need to use it.) This is not. This stinks of form-over-function failure.

Edit (25/1): Two inline updates.

So, what *is* recursion?

Recursion's one of the cornerstones of computer science. The fundamental thesis of computer science says that recursion and iteration (and the untyped λ-calculus) have the same power. People introduced to programming through imperative languages often find the idea of recursion hard, though there are good arguments that that's really a deficiency in our teaching.

So, what exactly is recursion then? And what, for that matter, is iteration?

Wikipedia defines recursion as "a method where the solution to a problem depends on solutions to smaller instances of the same problem". I haven't had major problems with this definition until recently, when I was reading the wonderful Concepts, Techniques and Models of Computer Programming (CTM), which unsurprisingly defines an iterative computation as "a loop whose stack size is bounded by a constant". The examples that it gives are far more surprising, though. Here's an iterative computation to find the length of a list in Oz, the language CTM uses:

fun {IterLength I Ys}
  case Ys
    of nil then I
    [] _|Yr then {IterLength I+1 Yr}
  end
end

Programs like this wouldn't be called iterative in a language like C at all! They'd instead all be called tail recursive. Oz optimizes tail calls so that they don't cause the stack to blow up.¹

Even more surprisingly, and perhaps a bit confusingly, it then goes ahead and calls iterative computations a special case of recursive computations, rather than something distinct. It then talks about converting recursive computations to iterative ones (using accumulators and the like), which I take to mean converting non-iterative computations to iterative ones.

Granted that these definitions are from a declarative point of view, where all state is immutable and thus for or while loops don't make sense, but does that then mean that recursion and iteration can only be defined with respect to the language you're writing in? I've never been fully convinced by Guido van Rossum's arguments against tall call optimization in Python, but considering that the feature can determine whether a given program is iterative or not, the arguments start making a lot more sense.

And what about tail recursion modulo cons then, as found in languages like Haskell and Oz? Optimizing tail recursion modulo cons allows functions that aren't tail-recursive, but where the only thing left to execute after the call is a data constructor like cons, to avoid blowing up the stack². Consider this definition of the map function:

fun {Map F Xs}
  if Xs==nil then nil
    else {F Xs.1}|{Map F Xs.2}
  end
end

This function is clearly not tail recursive, and if translated directly to a language like Scheme which optimizes tail calls but not tail recursion modulo cons, this function would cause a stack overflow with a large enough list. However, since the only thing left after the recursive call is the cons operation (denoted by |), in Oz this function is iterative by the CTM definition³.

So, then, does it make sense to define iteration as any computation in a given language which only takes O(1) implicit (stack) space when executed, and recursion as any computation in a given language which references itself? This would mean that the two aren't quite the opposites they're often portrayed to be, and that depending on the language, recursion and iteration could either overlap or be distinct.

And does it make sense to make this explicit while teaching kids how to program?

---

¹ Interestingly, Oz doesn't have a separate optimization for tail calls. That tail calls don't cause the stack to blow up follows naturally from the way Oz executes programs, as became clear to me when I wrote a self-interpreter for Oz for a school assignment.

² Again, neither Haskell or Oz have a separate optimization for this. It's a natural, straightforward result of Haskell's laziness and Oz's data-flow variables (everything's a promise in Oz!).

³ Peter Van Roy, one of the authors of CTM and an Oz developer, explains how this happens in Oz.

Why we shouldn't switch to git, part 2

If unnecessarily bad performance in the usual configuration for anyone on Windows Vista or above wasn't bad enough, msysgit also automatically sets up terrible defaults, leaving first-time developers' heads scratching.

Mercurial, of course, does the right thing here and leaves files alone.

Practically every editor on Windows -- Visual Studio, emacs, vim, Sublime Text -- supports LF endings just fine. As far as I know, Notepad's the only one that doesn't. If you're optimizing for Notepad over everything else, something's really gone wrong.