Beware of the Train

Today's hack is up. It's to the flashlight app again; now the UI stays in portrait orientation no matter how you rotate the phone. This prevents the pause/resume/create cycle that was killing my Activity and causing the light to go out. Most of yesterday's code is no longer needed and has been taken out again, but that's a good thing, right? :-)

Sideload the app (if you care - HTC Sense has such a thing built-in) from here.

Anyway, the way you do this is by adding the attribute android:screenOrientation="portrait" to the activity element in your manifest. This tip came from this StackOverflow post: I tried the more complicated "add a configChanges attribute and override onConfigurationChanged" approach described there, but that resulted in the LED wedging in whatever state it was in when you rotated the phone and not accepting any further changes. God knows what was going on there.

By the way, does anyone use git add -p much? I tried the "edit this hunk" feature a couple of times, but it told me that it my patch wouldn't apply cleanly, and then rejected the whole thing. Also, I'm having trouble uploading files to GitHub's "download" section.

Edit: and I've had a documentation patch accepted into Idris. Go me!

I badly need some better strategies for making sense of large, twisty, underdocumented codebases.

My current "strategy" is

• grep for interesting words or phrases
• find relevant-looking functions
• look for their call-sites
• look up definitions of other functions called in those sections of code
• if I don't understand what a variable's for (almost certain) then look for assignments to it
• once I've identified all the bits of code that look relevant, stare at them until my eyes cross
• maybe put in a few printf's, try to make sense of the logs
• enter procrastinatory spiral of despair
• stress about losing job
• make more coffee
• repeat.

What do you do?

A couple of days ago, Chris Yocum asked me to help him out with some OCaml code. He's learning OCaml at the moment, and thought he'd practice it by solving a problem he'd encountered in his research on early Irish law.

In early Irish law, murder was punishable by a fine dependent on the status of the victim. Ten-and-a-half cows per king murdered (no, really!), five for a major nobleman, and so on. At one particular event, we know the total fine levied, but not the number of victims. Chris wanted to find out the range of possibilities. This is an example of the change-making problem: given small change of various denominations, how can you give your customer 73p? I most often encounter this problem with rugby scores: if Wales beat England 67 - 3 (I can dream...), then at seven points for a converted try, five for an unconverted try and three for a penalty, what might have happened?

( Be the change you want to make )

All suggestions for improvement, as ever, gratefully accepted :-)

I recently underwent a major personal technology upgrade.

This was in two parts. The first was to buy a second-hand Kindle 2 which was being offered on a mailing list I read. I've wanted an e-ink device ever since I read about the technology in the blue-skies column of some computing magazine or other, and the legibility hasn't disappointed: reading on a Kindle is a positive pleasure, nothing like the tiring experience of reading a backlit screen. So far, though, I haven't used it as much as I'd thought I would. One of the main things I bought it for was reading scientific papers; while it's possible to read A4 PDFs on it in landscape mode, it requires a lot of scrolling, and referring back to something a page or two ago is a hassle. This wouldn't be a problem for novels, but I've got a lot of treeware novels I feel compelled to read first. Another intended use-case was for travelling (I always take too many, and simultaneously too few, books whenever I go anywhere), but the only trip I've made since buying it was a cycling-and-camping holiday round Orkney: not ideal for sensitive electronics.

I'm experimenting with converting PDFs to .mobi using Calibre: we'll see if that fixes the excess-scrolling problem.

The second part was an upgrade of my phone. Owing to years of inattention and a major Ugh Field, I was paying an embarrassingly high amount for a phone that just did the very basics: calls, texts, er, that's it. It had a camera, but getting photos off the phone was such a hassle that I rarely bothered to take photos. No Internet, no maps, nothing fancy. I didn't much miss mobile Internet at first, but I've been training myself not to wonder, and the lost opportunities to learn were increasingly starting to grate.

So, I reasoned, I could either keep my existing level of functionality and pay a lot less for it, or I could pay a bit less and get a totally bitching-ass phone¹.

Then I got very, very lost trying to find my way to a pub in an unfamiliar part of town without a map, and decided to go for the second option.

So I screwed my courage to the sticking-place, walked into a phone shop, and asked to see their range of Android phones. The Android-versus-iPhone choice was very simple, since I have access to precisely zero devices capable of running iTunes². I didn't even consider a Symbian or Maemo phone, though perhaps I should have. I had a brief look at the HTC Legend and HTC Desire, but fell instantly in love with the Google Nexus One - it's basically the same phone as the HTC Desire, but with (IMHO) a slightly nicer case design and a noise-cancelling second microphone. Slightly less RAM, but then it doesn't have HTC's proprietary Sense UI (which I didn't want), so it gets on fine with less. And so, after a week of hassle with my previous provider to get my number transferred over, that was the phone I took home.

"Phone"'s the wrong word, though: it's really a general-purpose portable communication, computation and sensor platform. Out of the box it was a street map, an email client, a news-and-weather feed, a camera, a calendar, an address book, a web browser and, yes, a phone; within the next few days it became a device for playing text adventure games, a weight-tracker, a compass, a hiking map³, a star chart, a device for recording my hikes and bike rides, a tricorder, an ssh client, a graphing calculator, and a spirit level. Yes, a spirit level. What would Robert Hooke think? Most recently, it's become a handy reference for arguing with climate change deniers, a facility which I have yet to use in anger.

I've also been working through the Android development tutorials, which have really impressed me; so far, it looks like a very sane and well-designed platform, though my little netbook struggles rather with Eclipse.

But I'm surely missing something. A device like this must be capable of things I can't begin to imagine. So, what else could I be making it do? For those of you with smartphones, what useful/surprising/cool apps have you found? Don't hesitate to mention iPhone apps: I can go looking for Android equivalents, or have a bash at writing my own.

There's one thing my phone definitely can't do, though, and that's dissipate wormwood_pearl's envy³ - which was made even worse when we went round to visit friends a week ago and they both pulled out their new HTC Desires. I guess I know what I'm getting her for her birthday...

¹ Or possibly a totally bitching ass-phone.
² And then there's Apple's distinctly unsavoury management of the App Store, my fear of getting caught on Apple's Treadmill of Shiny, and my general preference for open systems over closed ones. Android's less open than it could be, but hell, give it time.
³ And jealousy; she's remarked a few times "I don't mind you spending time with your new girlfriend, but would you mind not stroking her in front of me?" I think she's only half-joking :-(

It occurs to me that not enough people know about TeX's line-breaking algorithm.

Take a paragraph of text; this one, for instance. Form a graph whose vertices are possible line-breaks, and whose edges are the words (and part-words, in the case of hyphenation) between two possible breaks. For instance, if your text is "Fred loves Wilma", then you'd have four vertices: the beginning, the space between "Fred" and "loves", the space between "loves" and "Wilma", and the end. You'd have five edges: "Fred", "Fred loves", "Fred loves Wilma", "loves Wilma" and "Wilma".

Now, here's the clever bit: you decorate each edge with the "badness" associated with fitting those words onto a line, represented as a number between 0 and 10,000. There are various heuristics used to calculate this "badness" score, but basically it comes down to how much you have to squash or stretch the words and the spaces between them, plus extra badness penalties for hyphenation etc.

Finding the optimal set of line breaks is now a simple matter of applying a standard minimum-weight graph-traversal algorithm. Some further cleverness brings the average-case running time for the algorithm down to linear, and the worst-case to O(n²).

Theoretical computer science for the win.

Unfortunately, TeX doesn't apply this algorithm to the problem of breaking paragraphs into pages, for (AIUI) historical reasons: the machines on which TeX was developed didn't have enough memory to hold more than one or two pages in memory at a time, and so had to write out each page as it was created. The page-breaking algorithm is thus local rather than global, and hence sometimes gives strange results. Wikipedia informs me that optimal page-breaking is NP-complete in the presence of diagrams, but in practice we efficiently find good-enough solutions to NP-complete problems every day, so I don't know why they're still using the local algorithm. Hopefully some TeXpert will pop up in the comments and enlighten me :-)

As part of my preparation for the PASTA job interview, I spent some time refreshing my knowledge of basic compiler theory, and learning about some of the bits that I'd never really got my head around. Here, in the hope that someone else will find them useful, are the notes I took about parsing theory. They're loosely based on the Edinburgh lecture course on Compiling Techniques. You'll need to be familiar with the notions of formal language and formal grammar (links go to Sam Hughes' highly approachable introductions to the subjects); you'll also need to vaguely know what a regular expression ("regex") is, and to know that every classical regex (ie, one without backreferences) can be mechanically converted to a Deterministic Finite Automaton (DFA) that accepts exactly the same set of strings. All code is for illustrative purposes only and probably won't even compile.

( Nowe read on... )

Comments? Corrections? Clarifications? Questions? You know what to do.

We've been using git for version control at work for the last couple of months, and I'm really impressed with it. My favourite thing about git is what might be termed its unfuckability: no matter what you do to a repository to fuck it up, it seems, it's always possible to unfuck¹ it, usually simply by keeping calm and reading the error messages. I've managed to lose data with an ill-advised git reset --hard, but that was before I knew about the reflog, and I've always been able to recover "lost" work in every other case. And then there's the rest: cheap local branching², the index, the raw speed, git-bisect, git-gui and gitk (which has rapidly become an indispensable part of my development toolchain)³.

The merge algorithm pretty much Just Works: we get the occasional merge conflict, sure, but (so far) never without good reason. So I was surprised to learn (from Mark Shuttleworth) of a really simple case where git's merge algorithm ( does the Wrong Thing ).

Bazaar obviously gets this right, otherwise Mark Shuttleworth wouldn't have written his post. Commenters there suggest that Darcs gets this right too, but after spending a while looking through the Darcs wiki I discover that I really, really can't be arsed to work out how to do the necessary branching to test it. Hopefully some helpful Darcs user (I know you're still out there...) will be able to post the relevant transcript in a comment. [Edit: I realised belatedly that you don't need branches for this. Transcript here.]

Overall, I don't think this is a show-stopper, or even a reason to seriously think about switching to another DVCS, but it's certainly worth remembering and watching out for.

¹ Why yes, I have been watching the excellent Generation Kill. How did you guess? :-)
² If you're not used to systems in which this is possible, it probably sounds really scary and difficult, and like the kind of thing you'd never need or use. It's not. It's actually really simple and incredibly useful. The article that made it click for me, Jonathan Rockway's Git Merging By Example, is no longer online, but I'm sure there are equally good ones out there. You'll probably find Aaron Crane's "branch name in your shell prompt" utility helpful.
³ Just to clarify: I'm not saying that Your Favourite VCS sucks, or that it's impossible to get these features using it: I'm just saying that git has them, and they're really, really helpful.

It occurred to me recently that programming comes in several flavours, and that how much I enjoy a programming task depends strongly on which flavour predominates. The flavours I've identified so far, in descending order of how much I like them, are the following:

Data munging: You have a large mass of data in some fairly generic form, and must fold, spindle and mutilate it with well-understood tools to extract the information of interest to you. Writing Unix scripts is the classic example, but list manipulation in Haskell or Lisp and array manipulation in J or APL have this flavour too.

Clever algorithms: You have some calculation or task to perform, and brute force has proved inadequate. Now you must apply the Power Of Your Mind to find a cunning and better approach. I haven't actually done very much of this stuff, but I have had to solve a couple of problems of this nature at my current employer, and have another one waiting for me on Monday morning.

Twisty if-statements, all alike: You want to zom all the glaars, but only if (the moon's in (Virgo or Libra), unless of course the Moon's in Libra and Hearts are playing at home), or (the engine-driver's socks are mismatched xor (the year ends in a seven and the month contains an R)). And you meanwhile want to wibble the odd-numbered spoffles if the Moon's in Libra, Hearts are playing at home and (the year ends in a seven or the engine-driver has mismatched socks). The challenge lies in making sure you've identified all the exceptions and special cases, and in actually coding them up correctly. Not remotely elegant, but better than...

Doctor X-style wizardry: Making a system do things that it was never intended to do. If you squint at the problem just right you have all the tools you need to do the job, sort of, but it's at best a witty hack and at worst a horrible bodge, and certainly not something you'd want to put much weight on. All non-trivial TeX programming has this nature. This kind of thing is quite fun when you're doing it as a joke or a proof-of-concept, but it's downright horrible when you need to do it to get something important done. But it's still far more fun than...

API spelunking. You have a candle, a slice of cheese, and a pair of old boots. You need a fork-handle. Is it even possible to construct one out of what you have? Is there a chain of method calls and constructors that will lead you from what you have to what you need? And if you succeed in constructing your fork-handle, is it the fork-handle you need? Or some nearby, but completely inappropriate, fork-handle? This is in some sense dual to data-munging. The worst examples I've encountered have actually not been in relation to documented APIs (though try reading lines out of a zipped text file in Java, if you want to see what I'm talking about), but rather in large crufty systems with complicated and ill-thought out data models. The Law of Demeter addresses this problem, but I have yet to work on a project that sticks to it. I'd settle for some sort of coherence theorem, but that would require coherent API design, which is kind of the problem to begin with...

By popular demand, a picture of Slava Pestov wailing on guitar:



NB: image may not actually depict Slava Pestov.

Previously.

Probably everyone who's spent more than five minutes working with web services and JSON has versions of these utilities. Here are mine.

( jd: JSON pretty-printer/dumper )

( jf: extract fields from (lists of) JSON objects )

I gratefully acknowledge the generosity of my employers (for whom I do not speak...) for allowing me to release these programs despite them being written during work hours. Thanks!