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.

The centre of the universe – 1665

The other opinion – followed by the Pythagoreans, Aristarchus of Samos and others long before Aristotle or Hipparchus or Ptolemy came into this world and returned to center stage by Nicolas Copernicus some one hundred years ago – is still approved by the most excellent mathematicians. It places the sun at the center of the universe as the soul of the world and governor of the universe, from which the earth and all the planets borrow their light. There they believe it to remain stationary, as we can see in the second figure…

Now it is not our intention here to specify which of these opinions is consistent with truth and best befits the natural order of the world. That is a question we must leave to those versed in the science of celestial matters. And for all that the earth, according to the Copernican hypothesis, moves annually around the sun in a circle whose diameter would be two million leagues from Germany, and that the sphere of the fixed stars would be of so vast an extent as to be utterly incommensurate with that of the sky around the earth, there is, nonetheless, no noticeable difference between this theory and the earlier one (according to which the earth is the center of the universe) in respect of the apparent rising and setting of the celestial bodies, the changing duration of days and nights and the other things that follow from this. But since the hypothesis of a fixed earth seems generally more probable and is, besides, easier to understand, this introduction will adhere to it, without for the present considering the other theories.

Introduction to Geography, Joan Blaeu, Atlas Maior, 1665

(by the way, two million leagues is about the 1/75th of the true distance).

Milgram

This is distressing. I had thought that there was a reasonable argument to be made that adults in modern society are a lot more individualistic and skeptical of authority than in the early 1960s. Apparently that was just wishful thinking on my part.

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”

“Deported?”

“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.

My Great Female Age

Most of the time I wander around blissfully unaware of my age, but at this time of year, I tend to get reminded of it. I’m occasionally frustrated when I realise how old I seem to have got without writing a great epic, curing any disease, routing a dragon, rescuing a damsel, or visiting the moon (let alone punching a shark).

One friend was recently reminding me of matters chronological when, to deflect the weight of implied responsibility to do great things, I decided to point out how much older than me she was. Typically she had a response: since women live longer, in male years (like dog years?) she is younger than me.

Obviously at this point, calculations had to be done to determine if she was right. The fruits of my labour are below. Again, typically, she was right.

The life expectancy values are from 2002 for the UK.

code on jsbin