Stack nomenclature

What’s wrong with the names ‘top’ and ‘bottom’ for the two ends of a stack?

Big-O proofs

Is there any benefit to be gained from learning to write big-O proofs in your analysis of algorithms class?

The stack of iterators pattern

A design pattern for implementing depth-first search in Python using a stack of iterators instead of recursion.

Visual C/C++ incremental linker bug

The Microsoft Visual C/C++ incremental linker sometimes fails to update the executable with the updated object code.

Exact cover III

Using gadgets to translate combinatorial problems into exact cover instances, and how to avoid the gadgets using multiset covers.

Round trip

How I combined a parser and a serializer to achieve an elaborate no-op.

Plan to throw one away

How I had to write a JavaScript engine in two weeks.

Exact cover II

Solving and setting Sudoku problems in Python using an exact cover solver.

Exact cover I

Solving the exact cover problem in Python using ‘Algorithm X’.

A performance regression

A debugging story.

Emacs/Perforce integration: a retrospective

A look back at the first couple of years of maintaining the Emacs/Perforce integration.

The ping that wouldn’t die

A debugging story.

Completion colours

“At this point, if you are used to the way strings work in most programming languages, you ought to be asking yourself, how does this work?

Completion annotations

“Interactive completion works poorly in the case of changelists and jobs, because all you get when you type TAB is a list of opaque identifiers that give you no help in choosing the item you want.”

Five whys

“When confronted with a problem, have you ever stopped and asked why five times? It is difficult to do even though it sounds easy.”

The Bug

“It is stressful to know that something is wrong in your code, but not to know what it is or how to find it, and to have it hanging over your head day after day as you fail to make progress towards solving it. This nightmare scenario is the driver behind Ellen Ullman’s 2003 novel The Bug.”

Software inspection and the Heartbleed bug

Systematic use of software inspection could have fixed the Heartbleed bug without having to find it first.

Password purgatory

I’m seeing what it’s like to try to follow “best practices” for password management, but I find myself wondering if these practices are really suitable for human beings?

Drawing square triangulations

Drawing the triangulations of an oriented n×n square using only lines joining the 4n integer points around the edge of the square.

Shrinking SVG

Generating smaller Scalable Vector Graphics (SVG) from Python.

Scalable vector triangulations

Generating Scalable Vector Graphics (SVG) from Python.

Square triangulations

Computing the number of ways to triangulate an oriented n×n square using only lines joining the 4n integer points around the edge of the square.

User options considered harmful

The desire to add a user option often indicates that you have skimped on a important piece of usability work and are trying to put off doing it.

Software archaeology and technical debt

It doesn’t take long to reach a ‘mature programming environment’ in which complexity is overwhelming and change is expensive and error-prone. We’re all programmer–archaeologists now.

The tabular method

Dynamic programming is an important technique for writing combinatorial algorithms. But the name sucks!

Circular logic

Truth tables, graph colourings and a surprising sequence in Project Euler problem 209.

Language-oriented programming

“Languages are not just for describing algorithms to computers: they are for communication with other people.”

Emacs/Perforce integration: back from the dead

I’ve forked the abandoned Emacs/Perforce integration, and started fixing it. In particular, it no longer hangs Emacs when it can’t connect to the Perforce server.

Bogus foreign keys in Django

Handling bogus foreign keys in legacy databases in the Django web development framework.

The last lousy bug

A debugging war story: “Bug 142 was especially mysterious because it happened after the program quit running…”

Method combinations in Python

Using Python’s class introspection to implement a non-standard method combination.

Python has no precedence grammar

A surprising fact about Python: it cannot be expressed by an operator precedence grammar.

Theo Jansen’s Strandbeest

Theo Jansen is a Dutch artist who, for the last couple of decades, has been building increasingly elaborate kinetic sculptures that he calls strandbeesten (beach-animals).

Turning circles

Using vector geometry to compute a turning circle. Plus a Javascript/canvas demo.

iOS location tracking

The hidden location-tracking feature in iOS 4, with some maps to illustrate the accuracy of the recording.

Encapsulation is not always right

In object-oriented programming, encapsulation is sometimes a bad idea, and motion planning and collision are areas where this is particularly likely to be the case.

Using the Autodesk FBX Python module on 64-bit Macs

A bug report (mostly so that other people who encounter the problem can search for and find the workaround).

Indentation advice

Supposing, just supposing, that you actually wanted to make your dots line up vertically in Emacs, how would you go about it?

History of level 24

A finished game, with smooth gameplay and polished graphics, gives little evidence of the many twists and turns along the path of development. Here, in twenty-four screenshots of level 24, I show some of the trials, mistakes, and modest triumphs from the development of Floe.

Using html5lib to resolve relative URLs

Python code for translating relative URLs in HTML source into absolute URLs suitable for syndication.

Emacs 23

Emacs 23.1 was released on 2009-07-29. In this review, I describe some interesting and useful features of this release, and give some historical background to multilingual support in Emacs.

Colliding balls

Several approaches to implementing a system of colliding balls, ranging from quick-and-rough to painstaking-and-slow.

Validating XHTML

A program to allow you to run your XHTML document through the W3C validator and step through the errors and warnings conveniently in Emacs, and a brief discussion of why someone might want to do this.

Apple Mail crash: “bad external relocation length”

A serious crash in the Apple Mail application, with some analysis and a possible remedy. “It’s a bit worrying that the entire world can make my mail application crash just by sending me some junk mail.

User interface asynchrony

Implementing a match-making user interface for an ad-hoc wireless networked video game shows us that a user interface needs to be able to run asynchronously with respect to the implementation.

Fourteen years of e-mail

Counting and graphing e-mails. With a digression on non-standards-conformant mail user agents and how to use Perl to parse their non-conformant Date headers.

How deep is your build pipeline?

Discussion of video game build pipelines and the development difficulties that they entail.

Constant, qualified, and less attemptable

The const type qualifier in the C programming language, and the consequent impossibility of implementing some common operations in a type-safe way.

Make my day

The trouble with the build tool make is that because it uses file modification dates to determine whether a dependency has changed, it often rebuilds targets unnecessarily.

Multi-way mortgage calculator

There are many thousands of mortgage calculators on the web that compute the monthly payments based on the capital sum, interest rate, and duration. But this one lets you compute any of these four values based on the other three.

Smallest possible transparent PNG

A detailed look at the encoding of bitmap images in the PNG file format, leading up to the discovery of the smallest possible transparent PNG, only 67 bytes long.

Smart quotes in Emacs 22

Smart quotes mode, a minor mode for Emacs 22 that makes it convenient to type ‘smart’ “quotes”.

Zendoku puzzle generation

The technical challenges involved in implementing a sudoku puzzle generation algorithm on a handheld video game console, and how the developers at Zoonami solved them in the production of Zendoku for the Nintendo DS and Sony PSP.

The Python Challenge

The Python Challenge is a website of puzzles compiled by Nadav Samet. The puzzles are a mixture of riddles, codes, and programming challenges, with the Python language being a recommended tool. Here are some of my notes and solutions.

Relational macros

A C programming language technique for embedding relations (tables of data) into programs in a way which is easy to check, safe to update, and requires no tools other than the C preprocessor.

PSP loading times

Why video games on the Sony PlayStation Portable take so long to load, and what game developers can do to reduce loading times.


It’s common and convenient to represent relational databases in the form of spreadsheets, especially using Microsoft Excel. But it’s surpisingly hard to carry out relatively simple database operations on such spreadsheets. This article explains how to implement simple selects and joins as Excel formulae.

Type inference for Python

A sketch of a type system for the typeless programming language Python. The system would allow a limited form of type inference that would detect some type errors at compile time.

The errors of Christminster

A study of the errors found and fixed during the development, testing and release history of the adventure Christminster, together with a suggested categorization of defects in adventure games.

Statement coverage for Python

A tool to support statement coverage testing for Python. It accumulates coverage data over many runs, generates coverage reports, and annotates Python source showing which statements have been covered.

Statement coverage for Python: design and analysis

Lists the requirements for a statement coverage tool for Python, describes some issues in design and implementation, and compares with other statement coverage implementations.

Can we ship yet? Using Perforce fixes to measure product quality

How to use Perforce to efficiently measure the quality of a product in a software development environment where there are many branches, customers, and product versions. Presented at the Perforce User Conference 2001.