Looking Out To Sea

A couple of days ago I mentioned implementing simulated annealing for my comicbake program so I thought I would take some time to explain what that means and why it’s helpful. I’m sure there are some curious souls out there wondering what it’s all about!

He is seeking it, seeking it, all his thought is bent on it.

Let us start with a discussion of search.

Search is what you do when you don’t know how to get something by straightforward means. The type of search you do depends on what you’re looking for. Sometimes you know the goal but want to know how to get there. How to get from A to B is literally the problem solved by route-finding programs like Google Maps. The other type of search is where you don’t know what the goal is but you know what properties it has. You don’t know what your next chess move might be until you examine the board, but ideally it would involve not losing any pieces, and maybe gaining one of the opponent’s pieces.

Some searches are completely “uninformed” and will examine all possible solutions. This is obviously quite slow, so is avoided in all but the smallest of cases.

A simple improvement is to assume that any small change that improves the current solution can be used as a starting point to hunt for another small change. This is called “hill-climbing”, as we slowly ascend the terrain of the search space towards the highest point. An uninformed search would walk back and forwards across the landscape in a regular pattern as if looking for a contact lens. Hill climbing would never go back down hill, but follow the steepest course up hill.

The Gloaming from Beinn Bheoil.
© Iain Gillespie

The trouble with hill climbing, as any ramblers out there will know, is the minor summits. You get to the top of a small hill which seemed so all-encompassing, and you realise it actually stands in the shadow of a more massive peak. And to get onto that peak, you have to go downhill. Standard hill-climbing search doesn’t know there are other peaks and won’t ever go downhill to find them. It gets stuck in the foothills.

Simulated annealing is one further improvement to standard hill climbing search. It allows us to go down instead of up sometimes, if the direction we have chosen takes us down. We won’t always go downhill, as we want the gradual trend to be upwards, but a small proportion of downhill treks will help us avoid being trapped on the little peaks. To continue with the hill-climbing theme we can decide that the chances of going downhill as well as up should depend on how energetic we feel. Early in the day we may be willing to strike out in search of new peaks, but as the day wears on and the legs begin to tire, the adventurous spirit wanes.

Search with simulated annealing helps to avoid being trapped in locally good areas. The name in fact comes from the process of heating worked metal and cooling it very slowly — the molecules in this case are affected by temperature, allowing them to break out of their warped crystalline structure and slowly form better bonds as the temperature drops.

There were minstrels and mountebanks and harpers and clowns

What does all this have to do with where we started? With comic strips? You can probably see, in some vague way, how the search process might work if we actually wanted to find the tallest point in a range of hills, but how does this translate to the actual problem at hand?

In case there is any confusion, the problem at hand is choosing the best location to place speech bubbles on an individual panel of a comic strip, so that none of the bubbles overlap each other or hide the characters’ faces. Rather than jumping straight in to the solution we’ll work up to it slowly.

It helps to consider the problem in terms of the degrees of freedom we have at any point. How many things can we change at any step of the problem, in order to make the situation better or worse (ie, to ascend or descend our metaphorical hill)? If we were doing an actual hillwalk we could define our location in terms of x and y co-ordinates (such as latitude and longitude), and for every co-ordinate there would be a unique, corresponding height. Think of it as an association from co-ordinate to height:

(x,y) → Height

Here we have two degrees of freedom, as we can change each of the x and y co-ordinates independently to change our height.

In some situations you have more degrees of freedom. If you’re walking around your house looking for mobile phone signal you might also wave the phone in the air, or stand on the kitchen table or anything else if you think it will work. In this case you’re changing x, y and z co-ordinates. The value which changes is signal strength, and you’re trying to find the combination of co-ordinates which maximises signal.

(x,y,z) → Signal

This situation has three variable aspects, but other situations will have more. Every time we increase the number of variables the problem gets harder. Next you might imagine having to solve this problem to get several compatible solutions. If two people want to use their mobile phone at the same time they both can’t stand in the same spot. Now we need two places where the signal is strong! We can increase this to three, four, five…

But let’s pull things back a bit. If there are two mobile phone users in the same general area they both want good signal. We’ll say for the sake of explanation that we have three people waiting for really important calls:

Phone1(x,y,z) → Signal1
Phone2(x,y,z) → Signal2
Phone3(x,y,z) → Signal3

We want to maximise the sum of all the signals, so that everybody gets a good quality connection.

Maximise (Signal1 + Signal2 + Signal3)

To maximise the signal across all the phones we still only have the options of changing x, y or z for each. If we number each co-ordinate of each phone — so that Phone1 is located at point (x1,y1,z1) — we can see that we really need to maximise the following function:

(x1,y1,z1,x2,y2,z2,x3,y3,z3) → Overall Signal

That’s a lot of choices! And the more things there are to change, the harder the problem is and the more likely that we’ll waste time changing things which don’t affect the overall problem.

(The astute might have noticed that if everyone starts off with okay signal, we might be able to give someone really great signal at the cost of bumping someone else into a signal black hole. Overall the sums might not change, or they may prefer the unfair arrangement to the fair-but-mediocre one. We can avoid this by careful planning.)

Johnny Boo, Twinkle Power
© John Cooper

Now back to the problem again. We’ve got a selection of bubbles that all have to occupy unique places on the comic panel. There are a few places which they definitely can’t occupy (the space occupied by characters’ faces) and they also shouldn’t be out of order otherwise the comic won’t make much sense.

This is more or less the same as the mobile phone example without the ability to change z co-ordinate. For simplicity we actually invert the sense of the search — what we’re trying to do is find sea-level rather than the highest peak, though the principle is identical. To do that we invent a set of guidelines, and breaking each guidelines induces a penalty, or “cost”. The search process is trying to find an arrangement which reduces the cost to zero by not breaking any guidelines.

If we’re finding the ideal arrangement of three speech bubbles then this is the function we have to minimise. Notice the similarity to all the others before:

(x1,y1,x2,y2,x3,y3) → Cost

To calculate the cost we add up all the individual penalties which would each contribute to a “bad” solution:

• Overlapping another bubble induces a penalty. There’s an additional penalty for each bubble that overlaps another, which reduces the chances of them all piling up at one spot on the image.
• Overlapping a character’s face induces a penalty.
• Being out of order induces a penalty proportional to how far out of order a bubble is. If the first bubble appears sixth that’s really bad — it’s at totally the wrong side of the image — so we need to ensure that kind of thing doesn’t happen.

With these simple rules we run the computer through the simple procedure of moving the bubbles randomly, assessing their cost and then repeating. They slowly settle on their chosen state and the search process ends.

Along the way we’ve been keeping note of best overall position of each speech bubble. If it’s the current position we leave them there, but if they have been rearranged since then we revert to the overall best formation.

This search procedure is widely used for a lot of difficult problems — problems which would take too long to solve exhaustively. It’s also surprisingly simple to implement the core. The hard part is coming up with suitable cost measures which are quick but effective.

It’s been a busy few days on the code front. After coming to no real conclusions about the best way to lay speech bubbles out on a page deterministically, I’ve decided to explore the issue of search. I’ve knocked up a quick implementation of simulated annealing, which I’m now weaving in to rest of the code.

Like all random search methods, simulated annealing lives or dies on the quality of the heuristics you can provide. Since you don’t generally know the answer when you’re solving the problem you can’t test any intermediate solutions in the obvious manner. You instead have to test properties which you expect the solution to have. In this case, I have to test that, for example, the speech bubbles are laid out sequentially on the page. Any pair of speech bubbles which are out of order will ruin the sense of the comic, so this is fairly important.

There are other measures of goodness (or badness) of a solution, and some may be more effective than others. This has to be offset against the cost of computing the worth of each solution. If it takes 5 minutes to generate one scene it’s no use to me. Most people would rather place bubbles manually than wait this long. So speed is similarly important.

Right now I’m just waiting. I want to use the Mersenne Twister PRNG from Hackage, and it’s just my luck that the Hackage server appears to be down at the moment:

$ cabal install mersenne-random
Resolving dependencies...
Downloading mersenne-random-1.0...
cabal: Error: some packages failed to install:
mersenne-random-1.0 failed while downloading the package.

I’m optimistic about the results from this approach. I’ve been doing some reading on graph visualisation and also map labelling, which both have a lot in common with my problem. Simulated annealing appears to be effective in both instances, so I look forward to seeing what it produces in the end. When I get my shipment of random numbers…

The International Conference on Functional Programming (ICFP) is taking place this week in Edinburgh. A substantial group of attendees are Haskell programmers and researchers, so it seemed a good idea to organise a Hackathon to work on libraries, infrastructure tools and various bits that everybody can use.

Eric Kow was the driving force behind this, and he managed to get us use of the conference facilities on Sunday, while there were a couple of workshops happening elsewhere in the building.

We didn’t have anywhere definite arranged for Saturday, so I went scouting a couple of weeks ago and identified a couple of places that would be suitable. I emailed and phoned Henderson’s and they weren’t horrified by the idea. We spent the day there, making sure to buy enough coffees to keep the management happy. There were 8 or 9 of us at the busiest point and we got some pretty amused/strange looks from other customers: a crowded table of people all with laptops open, ignoring each other…

P1010566
© Brett Holman

In the evening we went out restaurant-hunting, which I don’t recommend in these circumstances — 9 people, Saturday night, Edinburgh festival, centre of town, no booking. I tried calling Calistoga (their number was still in my phone) as they’re both spacious and hidden from the tourists but they couldn’t take us either. We eventually found an Indian restaurant that would take us, so we idled in the pub across the road while they got ready for us.

On Sunday we were using the ICFP conference facilities, deep in the bowels of the Royal College of Physicians on Queen Street. It was a nice room, with little groups of tables, plenty of extension blocks for powering laptops, a flip chart and a projector. We even had wifi, though the networking infrastructure died a few times from heavy use. We were running off a separate system from the rest of the conference centre and their wireless access died, so there was an influx of random conference-goers looking for net access, which brought our wifi to its knees too. I had felt slightly guilty about taking people to a cafe with dodgy wifi the day before, but in fact the conference centre had an even less reliable connection! :-)

My sincere thanks to the staff of Henderson’s for putting up with us, to Graeme Hutton and Philip Wadler for getting us a room in the conference venue on Sunday, to Eric for doing all his organisation and to everybody who actually came along.

I’m putting a call out to everyone that attended to let me know what they did and so on. More updates when I hear back from them.

There’s another post about static typing (amongst other things) just been posted to Reddit.

(Tangent: I’ve just discovered that left- and right-mouse buttons pressed together emulates the awesomely useful middle-mouse button in Gnome, presumably Linux, presumably other Unix variants. Excellent.)

Static typing in programming is a bit like grammar checking in writing. Except better, because grammar checking is a much harder job. Anyway, it stops you making dumb mistakes, but plenty of people object to it because either (a) they don’t make mistakes or (b) they know better than the checker.

I don’t particularly understand the problem many people have with static typing, though I think the problem may be to do with how badly most languages do it. (You can imagine quite going off grammar checkers if you only knew Microsoft Word. But if you had a real live editor to point out your flaws you’d probably appreciate things more. Obviously the comparison is not legitimate but I think you see the gist — if something is done badly it can become more of a hindrance and is better removed altogether.) I have never done anything where static type checking has held me back, but I’m sure such things exist.

One interesting comment to come out of the above discussion regards teaching. Is it better to have a strict language for teaching purposes, or should the novice programmer discover why their malformed program is bad? Despite preferring static typing, I am actually erring towards no static typing for teaching purposes. I think falling off your bike a few times (metaphorically speaking, of course) will go some way to encourage more rigorous thinking, in the way that being told “no! you’re wrong!” before you try won’t. (Actually, I wonder if there is a language that exists which does static typing but will compile all the same. Then you can read any compilation errors and watch your program fail.)

I certainly remember hating the compiler when I was learning Java at university. Hating it. It never seemed obvious or reasonable that the problem was with my code; it was just a capricious bully, that compiler. Maybe if I’d been able to see the disastrous effects of running my ridiculous code I would have learned that the compiler did know what it was doing after all. :-)

I’m just back from the Edinburgh Cafe Sci with Philip Wadler as speaker.

The evening started with Ed giving a welcome to everybody and explaining what the standard procedure is: a short talk, a break for drinks, then some questions.

Then Philip Wadler stood up and introduced himself as working in the field of computer science, a name with only two problems — the emphasis on technology suggested by the word “computer” and the desperate plea for relevance that calling yourself a science seems to imply! He then said that his aim for the evening was to argue that there is depth to computer science that has nothing to do with the job of IT support.

He started with the basics of logic, in the study of rhetoric founded by the ancient Greeks. He asked everyone to do a short experiment — in fact, two different statements of the famous Wason card problem — as a demonstration of the power of logic and also its usefulness in even the simplest setting.

Having demonstrated that logic probably isn’t all that bad after all, he started a brief history of 19th century logic. George Boole invented a calculus of logic, to the delight of Leibniz (who I think was dead by then, but probably felt vindicated all the same). Frege came in later, someone whose name I didn’t catch (Gensen?) and then onto Church and the lambda calculus. Finally, he explained that many of these proofs and reinterpretations were shown to be equivalent.

It’s hard, very hard, to get across the beauty of things like lambda calculus to anyone, never mind the drinking patrons of a cinema bar, especially when you have no overhead projection facilities. I’m impressed Philip Wadler held everyone’s attention for so long, though inevitably there were some points where the focus began to waver. I think he suffered from lack of preparation, to be honest.

After the interval the questions were quite mixed. There were a couple on the competing language paradigms and the apparent lack of inroads that functional languages have had in the Real World™. Some guy (okay, I say “some guy” but it’s the same tedious guy every time) wanted to argue that logic wasn’t universal but I think any evidence he might have had was self-refuting. Gödel was touched on, and the fascinating but subtle topic of incompleteness and inconsistency. He got in a plug for research people are doing at Edinburgh into proof-carrying code. And he also highlighted that Scotland is the home of two important functional languages (or families), ML and Haskell. And maybe I’m not being true to my East coast roots here, but I prefer Haskell. :-)

If you couldn’t make it, or want more Wadler goodness, I recommend this Google Tech Talk on “Faith, Evolution and Programming Languages”.

This is a wee announcement for anyone who wasn’t paying attention earlier. Philip Wadler will be the speaker at this week’s Café Scientifique, so I highly recommend you go.

Those details in full:

• Title: “Proofs are Programs: 19th Century Logic and 21st Century Computing”
• Date: Monday 16th March
• Time: 8.30pm
• Place: Filmhouse cafe bar, Lothian Road

As the 19th century drew to a close, logicians formalized an ideal notion of proof. They were driven by nothing other than an abiding interest in truth, and their proofs were as ethereal as the mind of God. Yet within decades these mathematical abstractions were realized by the hand of man, in the digital stored-program computer. How it came to be recognized that proofs and programs are the same is a story that spans a century, a chase with as many twists and turns as a thriller. At the end of the story is a principle for designing programming languages that will guide computers into the 21st century.

On a related note, one of the Cafe Sci organisers has started a new blog, so go and visit to say hello. Welcome to blogging Ed!

I recently enjoyed reading Oleg Kiselyov’s pair of posts on efficiently building subsets of a particular size. Read part one and part two on Oleg’s site.

(By the way, the very act of looking around his site is like wandering through a junk shop where every item you turn over appears to be some lost treasure. A real joy, with mysteries and delights behind every link.)

Whether you’re interested in efficiently finding subsets of size N or not — and let’s face it, you’re probably not — there’s still something incredibly dramatic about the presentation of the problem and solution. I think there is a certain charm to the writing as well:

This article will show the design of the fastest ever interpreted subsets function. Sorry I’m too excited about this.

A warning of course, that if you’re afraid of parentheses, don’t read any further.

The blind man at the back takes firm hold of the tail and says:

But why do we need to call it an elephant? No-one knows what that is. Everyone knows what a rope is, so we should just call it a rope.

And that is how the elephant came to be labelled a rope in all the guide books.

I’ve seen a lot of references to FingerTrees around but not much explanation of what they are or where they should be used. The common reference is to 2-3 Fingertrees suggested by Ralph Hinze and Ross Paterson in Finger Trees: A Simple General-purpose Data Structure, so that seemed the best place to look.

There is also a working implementation published of 2-3 Fingertrees on Hackage (version 0.0 at time of writing), so between the two I should be able to work out the details for this structure and glean some idea of where to use it.

For the non-programmers, I include a video of Radiohead’s Treefingers, which I was sure was called Fingertrees when I started writing this post. If you search for “radiohead fingertrees” you’ll see I’m not the only one!

Continue Reading »

I have been thinking about a particular problem now for about two years. The problem doesn’t really matter — it’s a computer program that I want to write one day, when I get some time and space to do so.

What does matter is that last week I realised, almost completely out of the blue, that my long-standing problem was very different in nature to what I had assumed. Not only that, but as soon as I realised this the problem became massively more tractable. It was like turning an unknown corner and finding yourself in a familiar neighbourhood: it all just fell into place.

It’s very comforting to know that the fundamental problem I am trying to solve has been solved many times before, and there is a large body of research into the different approaches to take. The surface problem is still interesting, and to the best of my knowledge no-one has done anything similar before. But it’s new in the sense that the latest model of car is new: the problem domain is well mapped out, and all that matters is the details.