Dynamic Source Maps

I’ve been looking at source maps recently. The reason for this is that I want to be able to pass some code through a pipeline of transformations, but still maintain sourcemaps so that you get the nice debugging behaviour.

The specification for source maps talks about VLQ as if it’s a well known thing, and perhaps it is – apparently it’s part of the MIDI spec and the wikipedia page is entirely focussed on that implementation. I finally found a bit more detail from Peter van der Zee on exactly how it works and was able to create my own decoder.

As part of that, I got into a discussion about whether it was possible to use dynamically generated source maps. The result of my investigation is on github here.

Dancing-links: What Programming Is

Most people have no idea what ‘being a programmer’ is about. A common response when saying what you do is ‘oh, I couldn’t do that, staring at a screen all day’.

In the hope of communicating better, I’ve been trying out a few different responses. One I tried recently is “I solve abstract problems through the manipulation of symbols”. By itself it doesn’t actually help all that much but it does open up a whole realm of possible conversations that would normally be shut down by ‘oh I couldn’t do that, staring at a screen all day’.

What do I mean by abstract problem? Well, the sudoku in the paper on friday is a concrete problem. An abstract problem would be solving every sudoku. Solving the friday sudoku gives you the solution and some limited insight into how you got there. Solving the abstract sudoku problem gives you every solution for any sudoku you come across in the future, and an insight into what kind of thing sudoku actually is, what solutions are, and often what sorts of things are going on in the human brain, and what sorts of things would go on in the human brain if its ability to keep track of things without getting bored wasn’t hopelessly stunted.

Every time you tried to solve a sudoku and found yourself jotting little notes to help you keep track of more information than could reasonably be kept in your head you were reaching for solutions that were beyond what is practical in a normal human brain. If you ever started reading about ‘techniques’ or trying to work out all the different ways you can make progress on a sudoku, you were thinking about the abstract problem.

Solving the problem teaches you the solution. Solving the abstract problem teaches you about yourself and the nature of the world.

What does the solution to the abstract problem look like? The solution to the abstract problem has to be able to generate a solution to any of the concrete problems, so rather than a filled in grid, the solution to the abstract problem is a process that given a puzzle grid will generate the filled in grid. Both the concrete problem and the concrete solution can easily be printed in a newspaper but the abstract solution is a process which could be represented in many different ways none of which look anything like a sudoku grid, just as a recipe for cupcakes doesn’t look anything like an actual cupcake.

cat sleeping when it should be doing sudoku because this *is* the internet after all
A cat is not a good abstract solution to the problem of sudoku.

Still, while the abstract solution may be a process, we need a way to communicate it to other people, so we describe the process in words. As you come up with more and more abstract solutions, you discover that a lot of the parts of the process can be broken down into small steps that are used in all sorts of different abstract solutions. Amazingly, these steps are simple enough that they can all be done by machine, so you can build a machine that takes a description of an abstract solution and makes that process easily repeatable (which is in fact what a computer is).

One of the interesting things that comes out of finding the abstract solutions to problems instead of the concrete solution is that sometimes you find that the exact same abstract solution can be used to solve apparently different problems. Often this involves converting between different representations of the problem. For example, there’s no difference between a sudoku puzzle where the symbols you use are the numbers 1 to 9 or the same puzzle using the letters A to I. You can rotate a sudoku puzzle or flip it upside down, but it’s still essentially the same problem. Once you start thinking like this, you can make surprising discoveries, like the fact that tiling shapes into a chessboard can be solved with exactly the same abstract solution as sudoku.

For a time, it was hoped that perhaps all problems in the universe could ultimately be solved by one single master abstract solution, which would contain the answer to everything. Starting perhaps with logic and maths puzzles, and then ultimately, as we find better descriptions for the universe moving on to problems of physics, chemistry, biology and psychology. The german mathematician David Hilbert in the early nineteen hundreds was particularly associated with the first part of this task. The dream of being able to do this with everything looks pretty unlikely now that Gödel proved that any system that includes simple mathematics can represent problems for which it is unable to represent solutions, but there are many interesting stories in the history of logic puzzles, going back at least to Archimedes who proposed a maths puzzle about the ‘cattle of the sun’ which when solved gives an answer of more cows than could possibly fit in the visible universe.

In computing we call the process that is an abstract solution an algorithm after the Persian mathematician Muḥammad ibn Mūsā al-Khwārizmī from the 9th century House of Wisdom in Baghdad. One of the abstract solutions for solving sudoku (and n-queens, and shape tiling…..) is called Algorithm X, and an efficient way of keeping track of all the moving parts was named ‘dancing links’ by computing legend Donald Knuth (currently working for Google).

For fun, I’ve implemented dancing links here where you can see it solve sudoku and shape tiling (at the bottom of the page). It’s also a project that I created using particular tools and services; javascript, jasmine, node.js, heroku, jsdoc, cloud9, git, github and I will write a more technical blog about my experiences with those soon.

Game In A Day Challenge

Looking through my ‘project ideas’ page, I see that many of them rather ambitious – plans that would really require a minimum of a year of full time effort before seeing anything. They’re all really good ideas, but the chance of me actually doing any of them short of winning large amounts of money in a lottery is fairly slim.

I’ve been reading The Lean Startup recently, and one of the things that struck me is the importance of getting things in front of people quickly. It argues this from the importance of learning and appropriately acting in an uncertain environment, but perhaps even more important is in terms of your own motivation and focus.

So I set myself a challenge. Could I create a game and put it on the android market in less than a day?

You can see the answer here or if you don’t have an android phone here.

It’s designed to be played on a tablet, and you drag your green circle around while at the same time shooting at the yellow circles. It’s pretty simple, but reasonably fun.

I certainly learnt a lot, and one of the best things that came out of it was that it inspired me to spend a week learning and writing other things that came from it. I think that perhaps the biggest benefit setting myself a ‘1 day’ challenge is the effect it has on larger projects too.

Firefox 3.1b1pre (includes tracemonkey) vs Google Chrome

The one that’s faster on everything except date, regex and some string is google chrome.
Test was sunspider-0.9. Of course, this is a firefox nightly build, so it may well improve, but then so may Chrome.

My Mistake. Actually the figures below are with jit not enabled. I enabled it and tried to rerun the test. It was looking as if it would be even faster than Chrome, but then half way through it crashed the entire browser. Oh well.

Rant On A Related Note: does saying 1.49x as fast make any sense? Fastness isn’t a measure unless you mean velocity, which doesn’t have an obvious meaning in this case, since there is no reliable measure of the ground to be covered. The measure that makes sense is how long something takes, so 2x slower makes sense – it takes twice the time. Saying 2x faster implies that there is some measure of fastness that has increased. It seems to me that logically, fastness is a measure of the time it didn’t take, not 1 over the time it did take. Of course, the time it didn’t take is so large as to be unusable as a way of thinking, so maybe we could stick with things like “took half the time”, or maybe even “half as slow”, rather than these imaginary “fastness” measures.

TEST                   COMPARISON            FROM                 TO             DETAILS


** TOTAL **:           1.49x as fast     7574.0ms +/- 5.2%   5081.8ms +/- 7.2%     significant


  3d:                  2.47x as fast      917.8ms +/- 6.4%    371.4ms +/- 7.3%     significant
    cube:              3.26x as fast      319.2ms +/- 9.1%     97.8ms +/- 17.3%     significant
    morph:             1.75x as fast      266.2ms +/- 1.3%    151.8ms +/- 9.7%     significant
    raytrace:          2.73x as fast      332.4ms +/- 8.4%    121.8ms +/- 21.2%     significant

  access:              4.31x as fast     1148.2ms +/- 5.4%    266.6ms +/- 14.8%     significant
    binary-trees:      8.38x as fast      145.8ms +/- 23.3%     17.4ms +/- 10.8%     significant
    fannkuch:          5.87x as fast      517.4ms +/- 3.9%     88.2ms +/- 17.2%     significant
    nbody:             3.36x as fast      349.2ms +/- 4.0%    103.8ms +/- 22.3%     significant
    nsieve:            2.37x as fast      135.8ms +/- 11.5%     57.2ms +/- 14.3%     significant

  bitops:              4.65x as fast      887.4ms +/- 2.1%    191.0ms +/- 10.4%     significant
    3bit-bits-in-byte: 13.1x as fast      193.8ms +/- 6.1%     14.8ms +/- 11.0%     significant
    bits-in-byte:      6.09x as fast      201.0ms +/- 4.1%     33.0ms +/- 9.6%     significant
    bitwise-and:       3.52x as fast      198.8ms +/- 5.6%     56.4ms +/- 17.7%     significant
    nsieve-bits:       3.38x as fast      293.8ms +/- 5.9%     86.8ms +/- 13.1%     significant

  controlflow:         11.3x as fast      113.0ms +/- 4.2%     10.0ms +/- 0.0%     significant
    recursive:         11.3x as fast      113.0ms +/- 4.2%     10.0ms +/- 0.0%     significant

  crypto:              3.00x as fast      537.2ms +/- 7.1%    179.0ms +/- 18.4%     significant
    aes:               2.95x as fast      193.4ms +/- 6.1%     65.6ms +/- 27.4%     significant
    md5:               2.91x as fast      172.4ms +/- 15.9%     59.2ms +/- 19.3%     significant
    sha1:              3.16x as fast      171.4ms +/- 7.0%     54.2ms +/- 18.1%     significant

  date:                *1.39x as slow*    632.4ms +/- 6.2%    880.2ms +/- 8.0%     significant
    format-tofte:      *1.42x as slow*    373.2ms +/- 5.1%    529.4ms +/- 5.8%     significant
    format-xparb:      *1.35x as slow*    259.2ms +/- 8.7%    350.8ms +/- 12.6%     significant

  math:                2.69x as fast      931.0ms +/- 7.1%    345.8ms +/- 11.3%     significant
    cordic:            2.19x as fast      417.6ms +/- 5.9%    190.8ms +/- 16.9%     significant
    partial-sums:      2.81x as fast      328.0ms +/- 15.4%    116.8ms +/- 18.0%     significant
    spectral-norm:     4.85x as fast      185.4ms +/- 7.8%     38.2ms +/- 7.4%     significant

  regexp:              *1.90x as slow*    618.8ms +/- 15.4%   1177.0ms +/- 6.2%     significant
    dna:               *1.90x as slow*    618.8ms +/- 15.4%   1177.0ms +/- 6.2%     significant

  string:              1.08x as fast     1788.2ms +/- 4.2%   1660.8ms +/- 8.0%     significant
    base64:            *1.21x as slow*    161.6ms +/- 7.9%    195.0ms +/- 13.2%     significant
    fasta:             2.08x as fast      363.0ms +/- 7.3%    174.6ms +/- 11.5%     significant
    tagcloud:          *1.39x as slow*    331.8ms +/- 1.7%    460.2ms +/- 9.4%     significant
    unpack-code:       1.20x as fast      702.2ms +/- 5.4%    584.4ms +/- 12.2%     significant
    validate-input:    ??                 229.6ms +/- 9.7%    246.6ms +/- 10.2%     not conclusive: might be *1.07x as slow*

Hurricane, Charity and the New Bronze Age

In this age of war and terrorism, torture, mistrust, wiretapping and the institutionalisation of conspiracy, it can be difficult to believe in anything except the inevitability that the machinery of government will divide, turn brother against brother and nation against nation. From the schoolyard to the boardroom, the impulse to distrust and despise the Other is a familiar and comfortable garment that never stays in the wardrobe long.

Though the polity are not foreign to fear as foreign policy, it is not the only thread running through our experience of international affairs. When hurricane strikes Burma, leaving thousands dead, the whole human race recognises the disaster, and the whole human race joins together to help the stranger from an incomprehensible culture and distant land. To give up some of your own comfort for your family is normal, even expected. To help a neighbour in trouble, it’s normative, to help those from your own country unknown to you is praiseworthy, but to help those on the other side of the world can only mean a recognition of the humanity, value and similarity of those our political machineries are devised to keep us separate from, to teach us how different they are.

And though this empathy is not universal, it gives me hope. No international cooperation in war is like the cooperation in aid, spreading so wide, taking in such diverse people, creating new links directly between individuals.

The hope is not just for the people suffering disaster, it is a hope for the future of the human race.

4000 years ago, the bronze age changed the face of humanity. It brought tools so far beyond the best that stone could produce that it created the possibility for empires, for organisation and life that looked beyond the local.

But it is a simple fact that inspires me most about Bronze. Its ingredients, tin and copper are almost never found together in nature. Stone, wood and bone, the raw materials for the tools in common use before the dawn of the bronze age were picked up and scavenged from the local environment of the individual. Cooperation was helpful, but not necessary. But no one man can mine both the copper and the tin he needs to cast a simple bronze blade. For the bronze age to come about, there had to be trade and sharing of knowledge between diverse and separated cultures. The key innovation was not the bronze itself, it was the social organisation that made bronze possible, indeed inevitable. Without the Neolithic social network of links between people spreading beyond the horizons of any one of them, there could have been no bronze, and no bronze age.

I hope that the forces that limit our empathy, our horizons will not remain strong for long, that the impulse to link will beat the impulse to fear. When our horizons grow, so grows our potential. And who knows what technology can emerge and is now emerging from a world where individuals link across boundaries of race and wealth and age and geography. Technologies that can define an age.

I’m a stone age trader, hoping for the next bronze age.

Recent notable HARDtalks

Dissident writer Liao Yiwu spent four years in jail after writing an epic poem about the Tiananmen Square massacre. In a rare interview, Liao talks to Stephen Sackur. on iplayer, the interview webpage

When the pictures of torture of Iraqi prisoners by American soldiers at Abu Ghraib prison flashed around the world in April 2004 most people were shocked. But the images were eerily familiar to Professor Philip Zimbardo, as they were very reminiscent of those he himself had taken during the famous Stanford Prison Experiment, which he devised in 1971. Stephen Sackur talks to him about the parallels and the lessons we should learn. on bbc programmes (I have this one recorded, let me know if you want to borrow it).

Res Judicata

John Reynolds stood in the lobby of his office block staring up at the sheets of rain that had just unfolded themselves all over his unremarkable town. He’d just finished an unremarkable day of giving advice to customers of his employer. After a moment, he exchanged nods with the security guard, zipped up his unremarkable coat and stepped out into the downpour.

Stooping along the slick pavement, his head into the wind, he would barely have registered that there was a man in the long dark coat and pulled down hat in his way but for the two words said to him as he moved to go past.

“Mr Reynolds”

Nobody had said those two words to him for more than six years. He stopped short, standing straight, the rain forgotten.

The first thing his brain reached for was the simple lie; “That’s not my name”, but as he became aware again of the rain dripping from his nose and running in rivulets down his coat he realised the futility of denying with his mouth what he had already confirmed with his actions. He felt once more the vague sense of danger he had managed to forget as the years had passed.

“Are you with the police?” he asked.

The man paused, then nodded. “Let’s talk somewhere drier”, he said, and gestured towards a nearby car.

John started to back away. If they knew where he worked, they probably knew where he lived. What was left for him now? “I’m afraid I’m going to have to see some identification” he said.

It was at that point that he stumbled backwards into another man who’d stepped out from behind the car.
“Careful sir”, he said, hand resting firmly on Johns shoulder. With quick efficiency John was guided into the back seat of the car, where he made a dejected puddle in the upholstery.


An hour later the car pulled up outside a miserable concrete construction. The rain had slowed to a drizzle and John had collected himself enough to realise that he was falling apart. Not just emotionally. Over the years, he had come to believe in the new identity he’d forged; now he was losing that, he wasn’t really sure who he was. What did he have left? He knew he was angry though. And scared too.

The two men in the front of the car hadn’t said much to him the whole journey. He’d been trying to guess who they might be working for, but since the building they’d pulled up to was obviously government owned, he was assuming it was something to do with the witness protection program. That didn’t explain their tactics though.

They bundled him through the door quickly, but he was quick enough to read the lettering in black stencilled onto the reinforced glass. “Department of Decided Matters”.

“You’ll be wanting to talk to your lawyer I suppose”, said the man who’d first approached him.

“Do I need to?”.

“Well, you’re under arrest, and will be deported tonight”


“You have a court appointed lawyer, upstairs, first door on the right.”

The stairs were narrow, steep and the plastic underfoot felt cheap. John pushed his way into the cluttered office, and sat down in what was obviously the designated clients seat. His court appointed lawyer was nowhere to be seen. He drummed on the desk to pass the time.

It was then he noticed the newspaper. It was sitting on the top of a stack of papers on the desk as if someone had been reading it before he came in. The date was from six years ago, shortly after he’d been put in the witness protection program. He’d blundered innocently into working for an organised crime syndicate, and had gone to the police as soon as he realised. There were still those who wanted him dead.

The newspaper was one he’d read at the time. Shortly into his new life and new identity, he’d read about the horrific murder of Senator Jackson and the trial of John Reynolds, his killer. Was it just coincidence that the man had had the same name as him? He’d looked very familiar in the photos, grainy though they were. He’d assumed that it had been a clever trick by the witness protection agency to make it look as if he was out of the picture while he got on with his life. He hadn’t followed the case that closely, prefering to concentrate on what was new in his life.