Numbers Games

There is an Australian Federal Election due in a few weeks, and for those of you unfamiliar with political system of Teh Best Country In Teh World Ever, the skinny is that the focus is on the House of Representatives, which has one hundred and fifty something electorates, each electing one member. The party who wins majority of those electorates generally claims government, regardless of who wins the overall “popular vote”. There is no separate presidential election, even though practically speaking, the modern game is dominated by “presidential” leaders.

Now, here’s a little game-theory contrivance that shows that raw number-of-seats aren’t the only story – small numerical changes can have big practical consequences, and big numerical changes can have small practical consequences. I forget where I originally read it (searching the web for [25 26] is most unhelpful), but here it goes.

Suppose you have a parliament of 100 seats (or call them 100 senators, if that makes you feel better) and that you need 51 to pass legislation. There are four political parties (called A, B, C, and D), and party discipline is very tight – all members vote as a block with their party colleagues. Naturally, your party is the A team.

If each party controls 25 seats, then obviously each party is equally powerful. Now suppose there is an election and only three seats change hands, so that the A/B/C/D split is now 23/26/26/26.

A relatively small change, in terms of numbers, but you (and the rest of the A team) are now useless. You can’t make up the 51 with one other party, any other two parties could make the 51 without you, and if you joined a coalition of three (or more) parties, they could just ditch you (and then wouldn’t have to make any concessions to keep you on-side) and keep their 51-ness. Your negotiation power is zero.

Now suppose, more realistically, that there are two dominant political parties, say B and C, and you (A) and D are minor parties, say a split of 3/48/48/1. This is a drastic fall in your number of seats, but in terms of on-paper (i.e. modulo things like ideology, mandates, and reality in general) negotiating power, you are now as powerful as B or C, and more powerful as D (since D is as irrelevant as A was in the 23/26/26/26 example). Out of A, B, and C, a coalition of any two can form the 51, and hence all three are equally powerful (assuming iron-clad party discipline).

Of course, this is all contrived, e.g. I don’t see the Liberals teaming up with the Greens (a minor party) to trump Labor in the forthcoming parliament, but it’s an interesting example (IMHO) anyway.

As an aside, for those of you Aussies not living in marginal electorates and feeling neglected from the barrels of pork raining down in those areas, I’ve previously blogged a wacky idea for dismantling the notion of electorates altogether, but in light of this example, the lack of a party to enforce party discipline would instead accentuate this sort of volatile coalition-forming and post-electoral opportunistic negotiation. Hmm…

What does this blog post mean? I have no idea. Then again, I woke up this morning from dreaming all my teeth crumbled and fell out, and I have no idea what that means either. Except that I should probably floss more often. Hey, while I’m there, I should probably backup my disks too…

When a Switch is On, It’s On

I’ve just rolled version 0.6 of Superswitcher – a compelling replacement for Alt-Tab.

You can find the download links (source tarball, or Ubuntu .deb packages) off the project homepage. Tijl Van den Broeck has kindly put together an amd64.deb, for those who swing that way. I haven’t tried it myself, but I’m sure that it’s absolutely frabjous.

The key change since 0.5 is the ever-so-subtle but “forehead slapping, why didn’t I think of that” handy feature of not crashing immediately on Ubuntu Gutsy 7.10. There was an libwnck API/ABI change (in the active_window_changed signal handler), as unstable libraries sometimes do, somewhere on the journey from Feisty 7.04.  This API/ABI change broke 0.5-era superswitcher binaries, but as far as I can tell, it’s all peachy again with the latest and greatest.

There’s also window previews (a.k.a. thumbnailing), but this is highly experimental – they’ll need to invent letters that come before alpha to describe this one. I’ve seen a thumbnail-enabled Superswitcher crash whilst playing with Compiz, but I haven’t been able to reproduce this reliably.

Even without blingy thumbnails, Superswitcher and Compiz haven’t really played nicely together in the past. Prior to Gutsy, I haven’t actually used Compiz as my day-to-day window manager, since I’m a grumpy old bastard who thinks, “Ugh, hard-to-read text” when presented with a semi-transparent window. But with Compiz now part of the Ubuntu out-of-the-box experience, Superswitcher’s compatibility will probably see some attention soon. You’ll read about it here first. Unless, of course, you send me a patch instead. Yes, you.

Where’s My Rocket-Powered Themes?

Recently, there was some gtk+webkit goodness posted on Planet GNOME [1], [2], and it seems quite an easy (open source) project to check out and get your head around, given its size. There’s been some recent activity with the GTK-specific code to draw e.g. buttons and checkboxes that look like the GTK theme. I thought I’d start with the simple task of fixing up the radio buttons to actually look like radio buttons, and for the push-buttons to react to mouse-overs and mouse-presses, and not have the bounding box filled in with the default GTK background color (as I’ve helpfully called out with my hot pink arrow on the 8x blow-up below).


The hover / pressed stuff is pretty straightforward, it looks like this

GtkStateType state_type = isHovered(o)

But to avoid the background-box being filled in, spot the hack in the following code:

bool RenderThemeGdk::paintButton(RenderObject* o, const RenderObject::PaintInfo& i, const IntRect& rect)
  GtkWidget *button = gtkButton();
  button->allocation.x = -2;  // HACK
  GtkStateType state_type = isHovered(o)
  gtk_paint_box(button->style, i.context->gdkDrawable(),
    state_type, GTK_SHADOW_OUT,
    NULL, button, "button",
    rect.x(), rect.y(), rect.width(), rect.height());
  return false;

Yes, I explicitly set button->allocation.x to be -2 instead of the default -1. Is that fragile and will that probably break something inexplicably in the future? Probably yes. Why does that have any effect? Well, if you look at clearlooks_style_draw_box in the Clearlooks engine code, it says this:

/* Fix some firefox crap. */
if (GE_IS_BUTTON (widget) && GE_IS_FIXED (widget->parent) && widget->allocation.x == -1 &&  widget->allocation.y == -1)
  gtk_style_apply_default_background (...);

Indeed, it looks like GTK theme engines are a tangle of special cases [3][4]. So, dearest lazyweb of benevolent GTK theme gurus, if I were to do this properly, what would be the ‘correct’ way to do this?

Oh, and with painting the radio buttons, I seem to be setting shadow_type = GTK_SHADOW_IN to mean ‘checked’. Again, I have no idea whether this is a coincidental hack or if this is the right way to do it.

Dang it, isn’t it supposed to be the future? Where’s my jetpackTiger Stripes?

P1mp My Switcher

Thanks to John Stowers’ link drop (and his offhand remark that someone could "use this as the basis for window previews in libwnck") and a rainy Sunday, I’ve now added some XComposite / XRender blingfactor to SuperSwitcher (yeah, SS first, maybe libwnck later, once I actually understand how all this X voodoo works). In a word, thumbnails:


Compare that to the version 0.1 screenshot:

It’s (more than) a little buggy at the moment (e.g. it doesn’t show minimized windows’ contents, or those from different workspaces, and it doesn’t speak XDamage events), but if you want to play with it, the code has just hit the SVN repo.

If you don’t recognize the video playing in MPlayer, then get your eyes onto some sweet, sweet Chaser.

Shimmy to the Left, Shim-my to the Right

Since Carlos recently talked about animation (and usability) in GTK+, I suppose that I should dig up and share my old mock-up for animating Back and Forward (or just following links) in the browser. Cute and/or usable, no?

The animated GIF is a little stuttery, since the screen capture (Byzanz, IIRC??) also wanted a fair piece of the CPU (which is probably just due to all the extra X server work). It looked a lot better on my computer (without the screen-cap also running), since it’s a lot smoother, but the GIF should convey what I’m trying to do.

Update (2007-06-07): Baseless allegation about Byzanz’s design removed. Apologies, Benjamin.

Hello, World

I mean, g’day Planet.

Hi. I’m Nigel Tao. You might know me from such GNOMEly things as:

I would like to echo Prashanth Mohan’s recommendation of Rob Pike’s Newsqueak talk (and the elegance of the Sieve of Eratosthenes program). Also, there are many more Google Tech Talks, where all sorts of interesting (and not so interesting) technical people drop by Google HQ and, uh, talk. For example, Aza Raskin of Humanized gave one recently titled Away with Applications: The Death of the Desktop demonstrating Enso (which I’ve previously mentioned).

Warning: this paragraph of interest to programming language buffs only :-). In Newsqueak, variable declaration looks like i: int (compared to C’s int i), and assignment is the bog-standard (although mathematically lax) i = i + 1. One cute little syntactical feature is that you can combine declaration and assignment to write i := 42 to (loosely speaking) be a short-hand equivalent to i: typeof(42); i = 42, sort of like how i += 1 is short-hand for i = i + 1. It looks like Pascal’s old-school assignment operator, but it is in fact two separate operators, and you can even put whitespace in between to get i: =42.

Finally (in the small print section), these posts are entirely my own personal opinions and do not necessarily represent the views of my employer, blah blah blah, yadda yadda yadda.

Shameless Plug (of a Memory Leak)

Superswitcher version 0.5 is out.

  • Plugged a memory leak. Previously, we were not destroying cairo contexts.
  • First draft of a D-Bus interface.
  • New add and remove workspace buttons.
  • Respects #define MAX_REASONABLE_WORKSPACES 36 as per metacity.
  • –trigger-on-caps-lock split into –also-trigger… and –only-trigger…

The memory leak turned out to be that I wrote gdk_cairo_create without having a corresponding cairo_destroy. You’d think compilers these days should be able to pick up an error like that. C++ has ‘smart pointers’ and destructors, but hot damn is it ugly. Garbage collected languages take away the problem of explicit memory management, but can be sluggish (yeah, yeah, it’s debatable), which might be quite important if you’re on limited resources.

I like C. I get it, and as far as software goes, it’s small and simple enough that I think I get all of it. I can read C, and I can understand what’s happening. Compare this to C++, where overloading and operators and multiple inheritance and references instead of pointers means that when you get an obscure bug, it hurts. Even when you have a simple bug, the compiler error messages are horrendous to get your head around. Apparently there’s a new C++ standard (“C++0x”, due Real Not-Soon Now) brewing that will ‘fix’ some of these problems, but I expect it to suck because they’re adding more things rather than taking stuff out. To mix metaphors, you can’t polish a backwards compatibility crutch.

Java and Python are (relatively) easy to write in, but for serious stuff, you have to “learn the architecture of the machine”, so says Samba guru Jeremy Allison. You gotta understand pointers, and that something is slow because you’re copying lots of char arrays in a dumb way. Having read what I just wrote, I am turning into such an old fart, but then again, I’m like 48 in computer years.

What I really want is a programming language that reads like Python and runs like C. That should be its mission statement: reads like Python, runs like C. Maybe I should enrol in a research degree, spend a few years inventing Yet Another Best Programming Language Ever, and whinge that nobody uses it even though it is the Best Programming Language Ever. If I do, you’ll surely hear about it. In the meantime, enjoy a less leaky window switcher.

Closing thought: what’s the biggest memory leak anyone’s ever seen? This fuzzy screenshot shows Firefox clocking over 1.5GB…


To be precise, I’m on the Slashdot, which means I now have +1 Nerd Cred. Admittedly, it popped up on Easter Friday, which would probably be in the top 3 slowest news days of the year. And you have to dive in to the numerous links (no, not from a comment, from the actual ‘article’) to find my name in one tiny corner. And the blog post it linked to is over two weeks old. And it’s not as outrageously remarkable as Bonsai Kittens. But I’m there, dammit.

The blog post it linked to is from my work blog, which is more product announcy than personal diary-y, but, yeah, for the last few months I (with help from my colleagues, especially David) have been working on getting GeoRSS and KML to show on Google Maps and also through the Google Maps API.

There were a lot more linkbacks to that post than I was expecting, and it was a little odd, when just surfing around, to follow the trail from Jeremy Zawodny’s linkblog (one of my occasional internet timewasters) to Sam Ruby’s Which Way Is Up, which opens with, whoa, my name. It also made the O’Reilly Radar.

Which Way Is Up also mentions that GeoRSS isn’t officially standardized – it’s a partially undefined specification, with respect to boring details like what’s the XML namespace, are lat/lng co-ordinates separated by commas or whitespace, blah blah blah. That’s not to say that KML is perfect either – a personal boring detail peeve is how it’s sometimes child elements rather than attributes: <LineStyle> <width> 3 </width> </LineStyle> rather than <LineStyle width=”3″/>. But really, that’s a boring detail I ought to save until around the 50 hour mark when we’re stuck in a borked elevator together and have totally run out of other conversation.

Backtracking a bit, the thing with GeoRSS being somewhat loose means that the example that I chose to demonstrate GeoRSS-on-Maps could be held up as exemplary, or “officially blessed by Google”, even though it’s imperfect wrt this loose standard, or so the discussion went at Which Way Is Up. But really, it was just an arbitrary decision by me made in like 3 seconds when I needed a reasonable looking GeoRSS example and SlashGeo was the first one I saw on my Tomboy note full of these things. It made me wonder (briefly) about what other standards have been ensconced somewhat accidentally…

Sigi Says That I Should Blog More Often

Sometimes happiness is simply a new pair of shoelaces.

Does He Say "Math" or "Maths"?

I was going to stick an Update on my previous post (on Terry in the New York Times) but it’s sort of evolved into a full post. It turns out that my 大哥 has a shiny new WordPress. For example in his response to the NYT story, there’s a discussion about math education, and Terry says

“For instance, while teaching undergraduate linear algebra here in the U.S., I’ve found that students respond well to the story of how two Stanford graduate students in mathematics and computer science managed to exploit the theory of singular value decompositions of large sparse matrices to create a rather well-known multi-billion dollar web search company 🙂 .”

For the non (linear algebraists) amongst us (not to be confused with the (non-linear) algebraists), he’s talking about PageRank and the Google. I’d also add computer graphics and games as another reason for the kids to wanna learn linear algebra. I can hardly remember what dull rag my MATH1001 professor waved to try and motivate us, but it was, by definition, forgettable.

He also has a rather interesting riff (this time for armchair physicists) on Lara Croft as an analogy for Quantum Mechanics. I always thought that her body defied the classical laws of physics. 🙂