Wednesday, December 28, 2011

The Kiwi Rule

Driving in NZ is pretty sweet, the only thing that catches out new arrivals is the `give way to the right' rule, aka the Kiwi rule. Simply described, if you are turning left, you must give way to anyone turning right. They are actually getting rid of this rule next year, and I expect it to be carnage, but in the mean time, I find the rule really interesting, for a number of vaguely computer science related reasons.

First of all, assuming people do everything right, it shouldn't matter whether you give way to the right or left, as long as there is a protocol, then everything should work out. Which is our first computer science lesson (or rather software engineering) - you have to design for the error cases too...

When it works, the Kiwi rule is good as it improves overall contention at a junction, although it is a little counter-intuitive why. With give way to the left (the UK/Aus convention), you often get queues where someone wants to turn right, but there is a steady stream of cars coming in the opposite direction, either straight on or turning left (I'm assuming its just a turn off a main road). The car turning right has to wait for a gap in the traffic, which may not come for some time. In the give way to the right system, the car only has to wait until someone wants to go left, which occurs more often than a gap (well, a gap will suffice also). You might think this just means you get a queue on the other side of the road, but the car turning left only has to wait for no cars in the opposite direction turning right, which is actually the common case. So, wait times, and thus queues, are reduced. In comp sci terms, you adopt a clever scheduling algorithm to reduce contention.

Of course, there is no free lunch. Contrary to most road rules, signalling is essential to the Kiwi rule functioning. If someone accidently leaves on their left indicator, when they are actually going straight on, they can cause a crash if someone else coming from the opposite direction thinks they can turn right. Likewise, if the car turning right forgets to indicate and the car turning left therefore doesn't give way. So, for the Kiwi rule, signalling changes the semantics of the protocol, and this means incorrect signalling can lead to crashes, kind of like an unsound type system, or possibly a language where the type system affects the semantics.

So, for the sake of safety over speed, it's probably a good thing it is being scrapped; but I will be sad to see it go, it seems to me like a formalisation of politeness in driving, and fits nicely with the NZ attitude to life.

Tuesday, December 20, 2011

Things not to like about NZ

I seem to spend a lot of time telling friends and family how awesome New Zealand is, so this blog post is meant to be a counterpoint, where I vent my spleen about a few of the things that are bad about living in NZ. Don't get me wrong though, the list of things that are good would be way too long for a post, and moving here was one of the better life decisions I've made.

Sandstone (most important) - a nice sandstone bouldering area would be nice. God I miss sandstone.

It's a long way from anywhere - this is the biggie for me, it's a pain to get anywhere, and especially anywhere interesting. Doing the long weekend in Europe or a few weeks in the Middle East or North Africa, etc. would be really nice.

Tea - we pretty much solved this one by bringing over 500 tea bags whenever we go to the UK, but still, what is the point of Kiwi tea, you can barely taste it, more like a cup of hot water that dreams of being tea when it grows up. I tried using two or three tea bags at once, but it's still not right.

Beer - proper beer, not lager (Kiwi lager is excellent, some of the best I've tasted). Why can't you get a proper ale or bitter in this country?

The climbing walls are all crap - why? I don't know, there are some largish ones, but still they don't seem to be able to get it together properly, surely it's not that hard?

Horrific child abuse - not funny this one. Not sure if its because there's no other crime to report, but torturing your children to death seems a little too common.

Stuff is expensive - I know it's a small market and all, but if I can international mail order stuff retail and pay the postage and tax and it's still 30% cheaper than in the shops, then something is wrong.

Muesli - yet to find a brand I like.

Slow and expensive internet - and not having free wireless everywhere like in a proper country.

Public transport - it doesn't go where you want it to go, and it doesn't go there very often. Airports seem to be particularly poorly served.

The pollen - I really suffer with the hayfever, especially in Christchurch.

Pumpkin - I like pumpkin as much as the next man (probably more in fact), but it would be nice to just once find a vegetarian dish in a restaurant that ddoesn't include pumpkin.

Ozone hole - it would be nice to be able to go out in the sun without feeling like you are being x-rayed.

Sunday, December 18, 2011

Compiling Firefox

A few posts back I described my slightly painful experience compiling Cairo. It was thus with some trepidation that I approached compiling Firefox (which includes Cairo), also on Windows. As it turns out it was a breeze, the only slightly tricky bit being finding the executable at the end. Instructions are here, and they are pretty accurate.

Check out Firefox from the repository of you choice using Mercurial.

Download the Mozilla Build Environment.

Run the Build Environment from the Visual Studio command prompt.

Make Firefox ("make -f" in your Firefox source directory).

Wait for some time (I left it running over night, not sure how long it actually took, but at least a few hours).

The executable is in the obj.../dist/bin directory, which is nested inside your Firefox source directory.

Easy-peasy huh? Why couldn't Cairo be that easy?


I've lived in Christchurch for the last year, minus a few months in India and Europe. We picked a pretty bad time to move to Christchurch really, and in a way, the year has been dominated by the earthquakes. Even before the quakes, Chch was not as nice a city as Wellington, so my list here of things I've liked about Chch was always going to be shorter than last year's, but with the quakes closing the city centre for pretty much the whole year, it has been a bit bleak. Anyway, I don't want to dwell on the negatives, so without further ado, here is my list of things I'll miss about Chch.

Castle Hill - Far and away the best bouldering in NZ. Flock Hill is total classic, Quantum Field and Spittle Hill are good when you want something a bit different. I still haven't really got the hang of climbing on limestone, but it's still a lot of fun. And the whole area is amazingly beautiful. Also, Cave Stream on a summers day is lots of fun.

Snowboarding - I started learning this year, and it is so much fun. And there are so many ski-fields around Christchurch, it's amazing, and they're good and not too busy, and some of them even serve good coffee. Oh, and you can get a season pass for all of them for not very much money, how awesome is that?

C4 - Amazing coffee. Really, their flat whites are the best I've tasted, and consistent too, all but one coffee I've had in a year have been perfect, and the one was still above average.

Lyttelton - Before the quake at any rate, Lyttelton was a really nice town, loved the character and the cafes and bars around the main street. I really hope it comes back with the rebuild.

The Bodhi Tree - Burmese restaurant in Ilam, one of the few city centre restaurants that managed to relocate, but a really good one. I'd not had Burmese food before, and I'd been missing out. Some nice wines too.

RDU - Good radio.

Sweet Kitchen - Behind Merivale mall, good (but expensive) cakes,

Bank's Peninsula - Not really in Chch, but close enough, the roads to Diamond Harbour or Akaroa are brilliant for riding a motorbike. And it's very pretty, and Akaroa is a really cool little town. I imagine the peninsula would be a great place to chill out and do nothing for a few days.

So, lets see what Auckland is like...

Saturday, September 24, 2011

Amazon Kindle

I bought a Kindle a few months back and I love it! It is the first gadget that I've truly connected with and I think I would be more upset about losing it than my laptop, But, I am deeply conflicted about the whole ebook thing.

The Kindle is damn fine: the hardware is nearly perfect, of course it could always be smaller, lighter, and have a bigger screen (and I never use the keyboard, so that is dead space to me), and the software is pretty good, although there is room for improvement here (it crashes more often than I'd like, viewing two column PDFs is pretty poor, it takes ages for big files such as audio books to appear, etc.). So, I have no big complaints with the device, and it is extraordinarily convenient. Being able to buy books and read them in seconds is amazing, it's great for travelling with - I recently travelled round India with mine using the Lonely Planet PDFs (pro tip: avoid the LP Kindle editions like the plague) and a whole bunch of books I would not have been able to carry otherwise, and it's a nice reading experience in a way I can't quite put my finger on.

BUT, I'm already fighting the urge to buy paper copies of my ebooks. Having real books is so nice, it's something I grew up with, and having a book case full of good books to browse and just have around is really important to me. There is something aesthetic about all the colourful spines, as well as the ease of browsing and the serendipity factor of some old book jumping out at you for a re-read. I don't see the Kindle coming close at the end of the day, or anyway to get around this fundamental barrier. I am already using the Kindle to read books I don't think I'll want to read again or have around, and saving the good ones for the real thing.

And then there's the cost. On Amazon, Kindle books are only a whisker cheaper than their paper equivalents, which to me means someone is making a big profit over the paper, and I would bet anything you like it's not the author. So I feel like I'm paying a premium for an inferior product. If I lived in the UK, I would probably only use the Kindle for travelling.

However, it's a lot cheaper than buying the book in New Zealand (where books are extortionately expensive) and I don't need to wait for weeks for them to turn up by mail, so here and now, the ebooks have an edge. If you live in NZ, buy a Kindle, you'll save a fortune.

Friday, September 09, 2011


I was never a fan of algorithms as an undergrad. Whether it was the way they were taught or my attitude at the time, I don't know, but I didn't like them. It felt like dull rote learning, un-practical because, you could always look up an algorithm that you needed, right? (In contrast, I always had a soft spot for data structures, for some reason they just seemed so intuitive and stick in my head without me really trying, and there is something creative and almost artistic about some of the fancier ones).

I am currently applying for software development jobs, and I think my knowledge of algorithms is one of my weakest points. Programming is like riding a bike, it seems to just come back, I think I have pretty good 'general knowledge' about computer stuff, and I have a good idea of design things from my teaching, but algorithms are a bit of a gaping hole in my knowledge, and since they are a necessary thing to know for the more interesting jobs, and seem to be the number one thing to ask at interview, I thought I ought to improve...

So, I have been reading a lot and programming a lot of algorithm-type problems (makes a change from compiler things), and I've been really enjoying it. I don't know what's changed, but this time round I'm finding the algorithms stuff really interesting. It's amazing how some of these work, the creativity of some of them is amazing. And tackling algorithm-type problems (see, e.g., Google code jam, topcoder, endless olympiads/programming competitions) is lots of fun. I used to think of these as distractions from 'proper' coding, but it's great to really think about some of these things and often the model answers or commentaries are illuminating.

Anyway, just thought I'd write a little about the fun I'm having...

Monday, June 20, 2011


As a mini-project to get my hand back in with C++ and to learn the Cairo graphics library, I made a Tetris clone. It is surprisingly playable! You can download an executable here and the source code here (bear in mind that the quality of the code is not high, more later), it requires Windows, but not a particularly recent version (probably). I am pleased that it looks and plays so well, and pleasantly surprised how quickly the C stuff came back after a few years away from it. The code itself is bordering on the trivial, but I spent a long time looking up library stuff, so it took longer than expected. Cairo, it turns out, is a nice graphics library to use.

Since this is more of a learning exercise than anything else, the project is far from perfect. Rather than spend lots of time making it so, I thought it would be more beneficial to critique the code:


I am happy with how the game plays and it has all the main features of Tetris. It is deliberately missing quite a lot too: score, high score board, music, sound effects, an intro screen, the 'B' game, and probably a load more I can't remember. I could also spend more time tweaking the piece rotations and the starting positions and other general UI/presentation stuff.

I used the Windows API to make the window and handle input and the game loop/timer. This worked quite well, but has downsides - if the processor gets busy, the game stutters a little, it is not greatly efficient or robust and it is not portable. To make a really professional version, I'd want to use DirectX or something (although, that wouldn't make it very portable) and handle the game/input loop myself. I also cut a lot of corners on the Windows side of things, there is just a basic window, I should make it non-resizeable and tweak a whole load of settings etc., but that was not the focus of the project.


I'm happy with the overall deconstruction into classes. I think most of the concepts are right, and the classes are about the right size. I like the use of the flyweight pattern to represent squares (i.e., the components of a piece in the board). However, there is definitely room for improvement: I would like to split the Piece class into two: one representing an actual piece in the game, and one representing a kind of piece, at the moment the responsibilities of the former are split between the Piece and Board classes. Given the small number of squares on the board, it might be nicer to have an explicit Square class, rather than using the flyweight pattern - this would allow some of the responsibilities of the Piece class to be moved to the Square class (such as colour, and drawing the piece). I like the use of a data file to initialise the pieces and the use of a linked list to store the rotations.

The Piece and Game class are very tightly coupled and this could be improved. In particular there is an implicit requirement on the dynamic interactions of these classes which couples them together. In a way, Game should be a controller class, and Board a view class, but actually Board has (and should have) some controller features. It might be best to split both Board and Game into view and controller components (and perhaps split out a model from Board); some better separation of Board and Game would still be necessary.

The Game object is a state machine, but this is implicit; I should make this explicit.

The drawing code (using Cairo) is scattered throughout the program. It could better be encapsulated in a presentation layer. The Windows code is all in the 'top' file - Tetris.cpp and doesn't pollute the rest of the program, but it should be in a class (or classes) of its own and should be better organised.

I use an array of rows, I think this is the right choice because often I use random access, but when I think about it most access is conceptually sequential - the piece drops one row at a time, I always look at adjacent rows at once (e.g., all rows occupied by the dropping piece, lines are shuffled down by one row at a time, etc.), so maybe it should be a linked list.

Tetris has a tile-based presentation (on the Gameboy, at least, which is the only real version, if you ask me) and I preserve this in my version. But internally there is no explicit tiling (except for the actual board). The drawing code would be cleaner if the tile structure were explicit.


The overall code quality is not high: it could do with some more comments, and some better variable names. More importantly, a lot of the standard C++ defensive programming things are missing - I don't take care of copy and assignment constructors, check for errors allocating memory or doing IO (or anywhere else), there are not as many 'const' or 'explicit' declarations as there should be, etc. There should be more (some!) unit tests. Perhaps I ought to use references some places that I use pointers, but I kind of go for pointers by default.

I could probably make better use of the STL, rather than using so many explicit loops, etc.

There is not much re-use or inheritance going on. This is probably OK, since it is a small program and there are not many overlapping concepts. However, I still should think about how classes might be reused, and add 'virtual' declarations accordingly.

The use of Cairo is inconsistent (especially the use of save/restore) and pretty unsophisticated (but the whole point of this was to learn Cairo, so this is to be expected). I use the Cairo text library which is apparently just a "toy" library, so I should use something heavier-weight, but then it did the job pretty well (I also picked a slightly obscure font, so the text might not look so good on your system).

I could probably store objects that are repeatedly drawn (such as the scoreboard and walls) rather than redrawing them each frame, I didn't work out how to do this in Cairo, though. This is particularly an issue with the text (and using a stringstream just to convert from an int to a char* is overkill, but it used to do more).

Thursday, June 02, 2011

Building Cairo in Windows

Recently, for reasons best left aside for now, I tried (and succeeded) in building the Cairo graphics library in Windows. This is a bit more complicated than it sounds (although not as bad as I expected), so I thought I would document it in case someone else wants to do it too. For the record, I am running Windows 7 (32 bit), I used a combination of Visual Studio 2010 and GCC. You'll need Git installed. I use %zlib% to mean the (top) directory where zlib is installed on my computer, and similarly for the other libraries.

Step 1 - download

You will need the following:

Cairo (git://
Pixman (git://
LibPNG (
Mozilla Build Environment (
ZLib ( (sort of optional)

You will need to clone the first two Git repositories and download and extract the source zip files for the latter two (or three).

Step 2 - ZLib

You can build ZLib if you like. I built it, but got linking errors later on, instead I used the ZLib static library which builds as part of LibPNG (more later). If you want to do it, it's straightforward:

First you need to build the assembly files, run bld_ml32.bat found in %zlib%\contrib\masmx86. You will need to do this from the Visual Studio command prompt, not the usual windows one.

Open %zlib%\contrib\vstudio\vc10\zlibvc.sln in Visual Studio.

Change the configuration to 'Release' and build it. That should be it.

Step 3 - build LibPNG

Open %libpng%\projects\vstudio\zlib.props in a text editor and change the value of '' to %zlib%. (I used the zlib library which I downloaded, there is a ZLib library included with LibPNG and you could probably use this here, somehow). Save and close the file.

Open %libpng%\projects\vstudio\vstudio.sln in Visual Studio. Change the configuration to 'Release Library' and build it.

Step 4 - build Pixman

I couldn't figure out how to build Pixman or Cairo in Visual Studio, I got close with Eclipse, but couldn't quite figure it out using the Eclipse build system. In the end, I resorted to automating the following method using a batch file and a shell script (see below) and launching that when building from Eclipse. I expect I can do the same thing for Cairo, but haven't yet.

You might need to create pixman-version.h from and, I did this manually, but it might get done automatically.

Open %mozbuildenv%/start-msvc10.bat in a text editor and add the following lines:
set LIB="%LIB%;%zlib%\contrib\vstudio\vc10\x86\ZlibStatRelease;%libpng%\projects\vstudio\Release Library;%pixman%\pixman\release"
set INCLUDE="%INCLUDE%;%zlib%;%libpng%;%pixman%\pixman;%cairo%\src;%cairo%\boilerplate"

Note that '%LIB%' and '%INCLUDE%' are literal strings here.

Save the file and close it.

From the command line (Windows or Visual Studio), run %mozbuildenv%/start-msvc10.bat, cd to %pixman%\pixman. Run "make -f Makefile.win32 CFG=release OUT_PATH=%outpath%", where %out path% is the path where you want to output the compiled Pixman library.

That's all you need to do a manual build. To automate it from Eclipse, you will need to create the following batch and shell scripts and run the batch file as the build command in Eclipse. You will also need to set the MINGW_HOME variable in the Eclipse project properties.


@echo off
del %pixman%\pixman\release /Q
%mozbuildenv%\start-msvc10.bat %pixman%/

cd %pixman%/pixman
make -f makefile.win32 CFG=release

Note that the %paths will need to be in Windows format in the first two cases, and *nix format in the latter two. You could do the same for Cairo.

Step 5 - Build Cairo

I needed to apply a couple of patches before I could build Cairo. If you get a more recent version these patches may already have been applied, or be unnecessary. The patches are at and Apply these using Git.

Open %cairo%/build/Makefile.win32.common in a text editor and find the reference to 'zdll.lib' and change it to 'zlib.lib'. If you do not have the zlib, libpng, pixman, and cairo directories nested in the same directory, you will need to change the paths in this file accordingly. Save and close the file.

Copy and rename %libpng%\projects\vstudio\Release Library\libpng15.lib to %libpng%\libpng.lib. Copy %libpng%\projects\vstudio\Release Library\zlib.lib to %zlib%. Alternatively, you could change the paths in Makefile.win32.common, in fact this is a better way of doing it, if you plan to re-build libpng or zlib. Note that I am using the version zlib.lib built by libpng, I could not get Cairo to build using the version built by zlib - I got a bunch of errors linking libpng.

From the command line (Windows or Visual Studio), run %mozbuildenv%/start-msvc10.bat, cd to %cairo%. Run "make -f Makefile.win32 CFG=release OUT_PATH=%outpath%", where %out path% is the path where you want to output the compiled Pixman library. Note that you need to run the makefile in the cairo root, not the src directory.

Tuesday, May 17, 2011


Well, it took longer than expected but N is now open source! You can download it from GitHub at the URL in the previous post. Just a warning that it is buggy as hell and very fragile...

Monday, May 02, 2011

The N PL semantics tool, and other stuff

What have I been up to? I am currently gainfully unemployed. I am climbing a lot and seeing more of NZ. I'm also still working on some acadmic things - I'm continuing to work on a wildcards paper and I'm the PC chair for IWACO 11 which is keeping me busy (by the way I think this year's IWACO will be excellent - we've got a whole bunch of great submissions, thanks to everyone who submitted!).

Most excitingly (for me) I've been working on a tool for PL researchers called N. It is kind of a proof assistant, but also checks formal type systems and outputs them in pretty LaTeX, so takes out a lot of the drudgery of writing formal type systems. It is very much work in progress, but most of the checking and LaTeX output stuff is done (for a fairly small formal lanaguage) and I am working on the proof assistant part. This is novel (and exiciting for me to work on) because it is purely syntactic and high level, as opposed to Coq, Isabelle etc. which are semantic and low level,, they work at the level of logic/maths, whereas N works at the level of PL-style type systems. This means that when N says a proof is done it does not guarantee that the proof is correct. However, writing proofs in N should be orders of magnitude simpler and quicker than using a proper proof assistant. Think of it as a tool for doing hand-written proofs - it does some checking and automates some parts, but does not fully check.

N is written in Python and will be open source very soon (next few days), it will be at Feedback is appreciated!

Thursday, February 24, 2011

IWACO '11 website

Visit for the latest info on this year's IWACO, which should be a good one as we celebrate 20 years of research in the field.

IWACO 2011: Call for Papers

Call For Papers

International Workshop on Aliasing, Confinement and Ownership
in object-oriented programming (IWACO)

Celebrating 20 years of aliasing research

at ECOOP 2011

July 25th, 2011, Lancaster, UK

Call For Papers

2011 is the 20th anniversary of "The Geneva Convention on The Treatment
of Object Aliasing", which started research in aliasing and led to the
development of object-ownership techniques. To celebrate, IWACO 2011
will be a special edition; we are in negotiation to publish a book
(edited by members of the organising committee) containing the best
papers from IWACO '11 and invited papers of a survey or retrospective
nature. In addition to original research papers, we encourage authors to
submit position papers and papers considering future research

The power of objects lies in the flexibility of their interconnection
structure. But this flexibility comes at a cost. Because an object can
be modified via any alias, object-oriented programs are hard to
understand, maintain, and analyse. Aliasing makes objects depend on
their environment in unpredictable ways, breaking the encapsulation
necessary for reliable software components, making it difficult to
reason about and optimise programs, obscuring the flow of information
between objects, and introducing security problems.

Aliasing is a fundamental difficulty, but we accept its presence.
Instead we seek techniques for describing, reasoning about, restricting,
analysing, and preventing the connections between objects and/or the
flow of information between them. Promising approaches to these problems
are based on ownership, confinement, information flow, sharing control,
escape analysis, argument independence, read-only references, effects
systems, and access control mechanisms.

The workshop will generally address the question how to manage
interconnected object structures in the presence of aliasing. In
particular, we will consider the following issues (among others):

* models, type and other formal systems, programming language
mechanisms, analysis and design techniques, patterns and notations for
expressing object ownership, aliasing, confinement, uniqueness, and/or
information flow.

* optimisation techniques, analysis algorithms, libraries, applications,
and novel approaches exploiting object ownership, aliasing, confinement,
uniqueness, and/or information flow.

* empirical studies of programs or experience reports from programming
systems designed with these issues in mind

* novel applications of aliasing management techniques such as ownership
types, ownership domains, confined types, region types, and uniqueness.

We encourage not only submissions presenting original research results,
but also papers that attempt to establish links between different
approaches and/or papers that include survey material. Original research
results should be clearly described, and their usefulness to
practitioners outlined. Paper selection will be based on the quality of
the submitted material.

The workshop will be held as part of the ECOOP'11 conference taking
place in Lancaster, England.

Programme Committee

Nicholas Cameron (chair, Victoria University of Wellington)
Dave Clarke (KU Leuven)
Werner Dietl (University of Washington)
Ioannis Kassios (ETH Zurich)
Doug Lea (State University of New York at Oswego)
James Noble (Victoria University of Wellington)
Matthew Parkinson (Microsoft Research, Cambridge)
Alex Potanin (Victoria University of Wellington)
Tobias Wrigstad (Uppsala University)

Important Dates

15 April, 2011: paper submission deadline
20 May, 2011: author notification
25 May, 2011: full program disseminated
24 June, 2011: papers available
25 July, 2011: workshop takes place


Dave Clarke (KU Leuven)
James Noble (Victoria University of Wellington)
Tobias Wrigstad (Uppsala University)
Peter Muller (ETH Zurich)
Matthew Parkinson (Microsoft Research, Cambridge)


The number of participants is limited to 25. Apart from those with
accepted papers, others may attend by sending an email to Nicholas
Cameron ( indicating what contribution you could
make to the workshop. A small number of places will be reserved for PhD
students and other researchers wishing to begin research in this area.

Selection Process

Both full papers (up to 10 pgs.) and short papers (1-2 pgs.) are
welcome. All submissions will be reviewed by the programme committee.
The accepted papers, after rework by the authors, will be published in
the Workshop Proceedings, which will be distributed at the workshop. All
accepted submissions shall remain available from the workshop web page.

Papers should be submitted via Easychair at

by 15 April, 2011. Submissions should be in English.


Queries may be directed to Nicholas Cameron (

Christchurch Earthquake

For anyone reading who I have not been in contact with - Ru and I are fine and our house has survived pretty much unscathed - we have been very lucky, the damage to the city is incredible. Aftershocks are ongoing, I'm now able to keep sleeping through anything less than about a 4....