Plan to throw one away

When I had interviewed for the job, the interviewer had explained that I was needed to work on their JavaScript engine. The company was a web development tools startup, and they had spotted that it would be a good idea to have JavaScript code running on the server as well as on the client, so that you could share your business logic and validation code between the client-side and server-side parts of your application. There are now lots of products in this space but twenty years ago was probably too soon for this to be a success.

Anyway, the interviewer told me that the JavaScript engine was nearly done, but there were one or two features that were missing, and it was running a bit slowly, so I might have to do a bit of optimization. Sure, I said, that sounded like it would be fun … )


Exact cover

Karp (1972) introduces the name ‘exact cover’ for the following decision problem:

INPUT: Family Sj of subsets of a set ui, i=1,2,…,t

PROPERTY: There is a subfamily ThSj such that the sets Th are disjoint and ∪Th = ∪Sj = ui, i=1,2,…,t

(The problem being to determine, for an arbitrary input, whether it possesses the property.) Karp goes on to prove that this problem is NP-complete, using a reduction from chromatic number, which has a reduction from satisfiability with at most three literals per clause, which in turn has a reduction from satisfiability, which he proves is NP-complete directly.

Instances of this problem often arise in the solution of combinatorial problems … )


Emacs/Perforce integration: a retrospective

I’ve been maintaining the Perforce/Emacs integration for a couple of years now, so it’s time for a retrospective. … Perforce and Emacs are tools that I use all day every day, which means that small inconveniences in the integration stand out to me and I can see clearly cases where I have a frequently performed task that deserves some extra automation or assistance. I’m also in a position to check quickly that my change really fixes the problem. Here are examples of improvements I’ve made based on this approach… )


The ping that wouldn’t die

It was Friday afternoon at the customer site and I had completed my tasks for the week. I had implemented the new feature and its test cases, written a design justifying the implementation, and drafted a section of the user manual explaining how to use it, so now I was looking for something else to do. In any large program, there are always things that need fixing, so I poked about in the depths of the issue tracker to see if there were any interesting problems that could be appropriated from the other developers. The unluckily numbered and long unsolved issue 13 caught my eye… )



Joe sits in the office of his detective agency in Vientiane, drinking and smoking, watching the rain come down, and reading trashy fiction:

The book was a worn paperback with a garish, colourful cover. It showed a multi-story building in the final stages of collapse, a dusty African street, and people running away from the blast. The book was called Assignment: Africa and, in an only slightly smaller subtitle, announced it as the third title in the series Osama Bin-Laden: Vigilante. The unlikely named of the author was Mike Longshott.

A woman comes into in Joe’s office with a job for him:

At last, she said, ‘I want you find him,’ and her fingers caressed the book; he couldn’t put a name to the look she had in her eyes then; he thought she looked lost, and sad, and a little vulnerable.

‘Find who?’

‘Mike Longshott,’ she said.

( What follows is a pastiche of the hard-boiled detective genre... )


The Quantum Thief

Jean le Flambeur, gentleman thief, is sprung from prison by the beautiful Mieli, who persuades him to undertake one last job. Author Hannu Rajaniemi works hard to obscure the familiar outline of this hoariest of heist plots, by layering on the worldbling with a trowel:

The hidden Sobornost tech beneath the Oortian sapphire coral wakes up. The spidership reconfigures itself. The scattered modules pull themselves together along their tethers and fuse together into a tight, hard cone. The q-dot winglets transform from a perfectly reflective material into a diamond-hard firewall. Just in time, before the Archon’s nanomissiles hit.

I do like the experience of being confronted by a complex fictional world and having to make sense of it. ( But I also like to feel that there is in fact some sense to be made, and in this novel I frequently failed to make it. )


Completion colours

In ‘Completion annotations’, I illustrated the interactive completion feature in Emacs with a screenshot showing what happens if you type M-x set-cursor-color RET Dark TAB: you get a *Completions* buffer containing the colour names starting with ‘Dark’. Nick Barnes posted a comment pointing out a potential usability improvement:

It would be nice to have a bit more control still, so that (for instance) when completing on colour names one could see the colours.

To do this, just evaluate the following expression:

(dolist (c (defined-colors)) 
 (put-text-property 0 (length c) 'face `(:foreground ,c) c))

and then run any command that prompts you to pick a colour, for example read-color. 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? )