'Talisman' and Programming Language Semantics

On Friday night I got together with some of my old old buddies, guys I first met in high school, plus my brother, for a game of Talisman. Not a game of great intellectual challenge, but tons of fun. Having the gang back together for the first time in about 11 years made it so much better.

It's interesting to think about how one would implement Talisman in software. The issue is that Talisman revolves around cards --- "adventure cards", "spells", and "characters" --- many of which modify game rules in some way. (Many other games also have this form, of course.) For example, a card might say "adds 2 to your strength in combat with dragons", or "magic objects have no effect against the owner of this object", or "you may roll twice when moving and choose the larger value". Of course if you know the complete set of cards ahead of time, you can have every step of the game check for all cards which may be in effect. But this is not really a faithful encoding of the game. A faithful encoding would give the source code the same modular structure that the game has. In particular you would have a small core corresponding to the core rules, and one module for each card which fully describes the effects of that card.

The natural thing to do is then to identify a set of "extension points" where cards may modify game behaviour, each with a defined interface, and have each card "plug in" to one or more extension points. This works well for many kinds of applications, but unfortunately it doesn't work well here because again it is not very faithful to the structure of the original game. The real game does not define such extension points; instead almost everything is implicitly extensible. We take it for granted that the English text of the rules can be later modified by the text on cards and we don't have to say anything about the possibility beforehand.

Can we have a programming language that supports this sort of implicit extensibility? I think it would be very useful, not just for these sorts of games but also in other situations. One question is whether the problem is "AI-complete" --- that is, whether you need human-level language processing and general-purpose intelligence to resolve ambiguities and contradictions, the sort of intelligence that would probably let you pass a Turing test. I don't think you do, but the only way to be sure is to demonstrate a non-AI-complete solution. I think you could design a language and toolchain so that at least at program composition time, when all the extensions are known, all ambiguities and contradictions are automatically and precisely identified.

Another question is whether a language with implicit extensibility already exists. As far as I know the only languages that come close are those that expose the program's code to the program reflectively, allowing modification. I think some LISP interpreters allow that, and some languages with "eval" can be thought of as supporting it. But self-code-surgery seems like an incredibly crude and not very expressive way to address this problem.

I first considered this problem over ten years ago, it was even in my .project file back then. Now I wish I'd done my thesis on it. It's a bit off the wall but it would have been more fun and maybe had a lot more impact than the fairly pedestrian work I ended up doing.

I Have A Dream

We're seeing some amazing advances in neuroscience. Today people are taking the first steps towards mental input-output --- such as reading basic thoughts, mental control of joysticks, and stimulation of vision centers. Where could this lead?

Wouldn't it be amazing to have a surgically implanted computer capable of directly receiving thoughts and inducing sensory stimulation? Think of the applications!

• Do away with the whole messy voice, keyboard, mouse etc
  
• Work at full efficiency in any environment doing any activity
  
• Differential GPS capability makes being lost an anachronism
  
• Cellphones become telepathy
  
• High-fidelity virtual experiences of all kinds (nudge nudge, wink wink)
  
• Hook into sensor and actuator networks make your devices direct extensions of yourself: your house, your car, your pet robotic dog, all at your direct mental command at any range, and all acting as additional senses
  

But it doesn't stop there. Choose to share your experiences with others in real time. Experience group consciousness. Weave together many experiences of the same event into an incredibly detailed whole.

There are some risks. For protection, all this has to be optional. But who could shut themselves off from this for long? It's all humanity's dreams rolled into one. (Well, most of them.)

Now imagine that stolen nukes go off in New York, London, Beijing and Bangalore. Tens of millions are dead, hundreds of millions more at risk, and the world teeters close to an all-out nuclear exchange. World leaders are told it is possible to create a virus that will cover the world in hours and provide temporary access to the minds of the implanted, maximising the chance of detecting terrorists --- even disabling any who are already implanted --- and pulling the world back from the brink. It's the only ray of hope, and the plan is executed successfully.

After the immediate threat has passed, citizens are given the option of withdrawing from the emergency cooperative. Such objectors are a potential security threat, and become the focus of the rest of the network. They are, in fact, disconnected from the system lest they interfere with it. It's not a popular option, taken up only by a few eccentrics --- almost no-one who has adjusted to the extraordinary lifestyle of the implanted can bring themselves to withdraw.

Over time, it is judged prudent for the security of the system --- and therefore humanity --- for all implanted minds to be nudged towards approval of the system, to avoid those rare cases where there are doubts. Likewise, they are encouraged to have their children implanted at a young age. Other mental traits that cause social friction are removed ... or if they cannot be removed, their exercise is immediately detected and countered within the mind of the perpetrator. The only remaining external threat comes from the dwindling communities of unimplanted, who are therefore relocated to zones where they cannot endanger themselves or others.

Now unrestricted thought belongs only to the men and women at the root of the system, who control its software and thereby shepherd humanity. What happens to them? Do they automate their oversight and relinquish their power, joining the blissful masses? Do they turn to some new and terrible direction? Or do they err, and all succumb to some terrible catastrophe?

I admit to being paranoid --- but to my knowledge, nothing here is technically improbable. We desperately need a new Orwell for the twenty-first century, someone to terrorise us with plausible visions so we know to flee from the hint of them.

Avalon Lockdown

"If someone wanted to build an implementation of the WS- protocols that could talk to Indigo, they can use the public specs to build their own implementation. If however, someone wanted to clone Avalon or Indigo from top to bottom (that is, from APIs down to protocols) they'll probably want to approach Microsoft about licensing," a Microsoft spokeswoman told The Register.

So if you're a developer planning to base products on Avalon or Indigo, be aware that you're locking yourself to run on Microsoft platforms only, forever.

display:inline and tables

We have run into a problem. Some important Web sites have HTML like this:

<div>Hello <table style="display:inline">...</table> Kitty</div>

The intent seems to be to create an inline table. Unfortunately
the CSS spec currently says otherwise:

• "display:inline" turns the table element into a regular inline element, not a table at all.
  
• The presence of table rows and columns causes an anonymous table box to be created to wrap them. This happens to be in roughly the same place as the original table element.
  
• The spec is quite clear that this anonymous table box has "display:table". (It says "a box corresponding to a 'table' element will be generated between P and T", and the default style sheet is clearly "table { display: table }".)
  
• This is a block-level box inside an inline box, which causes complicated splitting to happen. But the important thing is that this table box will be on its own line, not inline.
  

Currently, in Gecko we have a bug which effectively causes the anonymous table to be treated as an inline-table, usually (but not always!). Because we don't really support inline-table, it probably doesn't work the way an inline-table should.

What should we do? There are a few possibilities:

1. Fix our code so that the anonymous table is a block-level table, according to spec. Then get everyone who relies on our behaviour to fix their sites --- soon, before Firefox 1.1 is released. One big problem here is that because we don't support inline-table or inline-block, there may be no way to work around the removal of this feature/bug.
   
2. Get the spec changed so that when the parent box is an inline box, the anonymous table is made an inline-table. Then change our code to support inline-table as best we can before release.
   
3. Leave the spec as is, but implement inline-table so people can get the old behaviour.
   

I'm leaning towards the second option, but any feedback would be helpful.

Around The World In 22 Days

Well, I'm back! It was quite a journey: Auckland - Singapore - Amsterdam - Frankfurt - Stuttgart - Frankfurt - N�rnberg - Frankfurt - London - New York - Boston - San Francisco - Auckland. More than 52 hours in the air, more than six hours on buses and trains (not counting intra-city travel), four hours of driving, two conferences, two company offices, one wedding, lots and lots of fun.

My favourite city was N�rnberg ... it has beautiful old city walls and other buildings. Amsterdam is nice too. Honestly though, I did not feel tempted to live in any of the cities I visited, over Auckland. I suspect if I get to have more time in London it will come to rival New York in my overall affection as a city to visit.

I was glad to enjoy reunions with some of my most important friends, especially as one of them got married. Unfortunately weddings always make me maudlin, especially when my wife isn't around to lean on for emotional support. I suspect it's because I'm incredibly self-centered and subconsciously begrudge the newlyweds the near-monopoly on attention they rightfully receive. Fortunately that's a minor blip and the wedding was undoubtedly the highlight of my trip.

I flew from Auckland to Europe via Asia for the first time. Now that I've flown both directions around the world, I think it's safe to say God has blessed me with unusual aptitude for air travel. With every journey, on arrival I stay up all day without napping and go to sleep in the evening, then I sleep well and wake up completely adjusted to local time. Concomitantly, I also have the ability to sit in an economy class seat uninterrupted for 14 hours without feeling uncomfortable or even needing to use the toilet. I'll sleep for four or five hours if I need to. I may be heading for deep vein thrombosis, but for now I feel extremely fortunate. Perhaps New Zealanders are evolving adaptations to long-distance air travel.

Graphics Thoughts

At GUADEC last week I gave a demo of my now-sorta-famous rotating HTML implementation. Since it's a GNOME conference I thought I should get GTK+ themes working in cairo. Here are the results.

You can see that bilinear scaling makes the Google logo look good even when we've zoomed in, and in general things look really good now that the GTK+ theme is being rendered. Pay particular attention to the rotated, scaled GTK-themed scrollbar and buttons ... and keep in mind that they still work!

Now the bad news: this required a grotesque and very slow hack. We can't paint a GTK widget theme directly into a cairo context because GTK themes can only paint into GDK rendering contexts (fair enough). My approach is to paint the GTK theme into an offscreen pixmap and then copy that pixmap to the cairo context. That's kinda slow but the real problem is that many GTK widget themes are partially or completely transparent. For example the button theme in this example paints only the slightly darker shadow along the bottom edge of the button. So just rendering into a pixmap and copying that doesn't work because we don't know the alpha values of the pixels, and there is currently no way to reliably create X pixmaps that will capture alpha values. So we resort to our old trick of rendering into two pixmaps: one with a white background and one with a black background. Then with some algebra we can recover the alpha values of the pixels, create a new cairo image surface with the correct pixel colors and alphas, and draw that into the cairo rendering context. Naturally this is really slow, partly because we have to draw the theme of each widget twice, and partly because we have to then ship the pixel data for both pixmaps back from the X server to the client, do significant per-pixel computation, and then ship the results back to the X server. Ugh!

I hope that things change in GTK or Xgl so that we can avoid all this, but I suspect that similar issues will bite us on other platforms. In the meantime, I'm going to look at caching the RGBA rendering of widgets so that we we render the same widget type in the same state with the same size as one we previously rendered, we can just pull the RGBA data out of the cache and blast it to the screen.

An Unexpected Journey

My visits to Stuttgart and Nuremberg went according to plan. I particularly enjoyed Nuremberg --- a wonderful city. But then things took a turn...

Saturday, June 4

I showed up at Nuremberg airport with plenty of time to spare. Everything was fine until the Lufthansa checkin agent said the dreaded words "do you have a visa?" I said I didn't need one ... She said (drum roll) "your passport is not machine readable, you do need one". Then I found out that you can't get a visa waiver without a machine readable passport and mine (issued in 2002 in Washington DC) wasn't. Until June 25 there is a one-time exemption, but it's only for people who haven't visited the United States in the last year, and of course I have, although using an H-1 visa. The rules in this case weren't clear so the checkin agent went to her supervisor, but the verdict was final and grim: no flight to Boston for me.

I briefly had a "what on earth do I do now" moment, followed by somewhat more time praying. Then I had to sit down and think for a while. Three options came to mind: get a visa, get a new passport, or fly straight back to New Zealand. So I called Janet to get the phone number for the New Zealand embassy in Berlin, and called their emergency line for advice. A visa would take ten days so that was out of the question. She quoted me three days for a new passport from London.

At this point I thought that flying directly home would save time, money and hassle since I have no critical need to be in Boston (although I'd be very disappointed to miss my friend's wedding). The Lufthansa ticketing agent had more bad news for me: a new ticket to get back to New Zealand would cost 1700 euros, with no refund on my round-the-world ticket. They wouldn't let me continue on my round-the-world ticket because it turns out Star Alliance has no connections across the Pacific that do not go through the United States (Los Angeles or San Francisco). We looked for routes through Canada, Mexico and even Argentina to no avail. Apparently you can't even change planes in the USA without passing through immigration ... that surprises me but I've never tried it, and they were adamant.

The remaining option was to get a new passport. I called back to the Berlin embassy hotline, who told me I'd better go to London in person and gave me the emergency number there. Loneon told me I could get it done in one hour if I showed up in person, even on Sunday morning. So I decided to give it a go and asked Lufthansa to reroute me to London today and on to Boston tomorrow evening (Sunday). New snag: Star Alliance doesn't fly London to Boston. Fine, I asked them to send me to New York where I can catch the train to Boston. Another snag: the new itinerary appears to exceed the maximum mileage for a round the-world ticket. But after much calculation, apparently it's just under the limit. Phew!

So the current plan is to fly to London today, arriving 3:55pm local time. I can check into an airport hotel and relax a bit, hopefully get online. I'll have to cancel planned meetings with friends in Boston on Saturday night and in New York on Sunday, which is sad, but we'll survive it. On Sunday morning I need to find the New Zealand embassy and get my new passport issued. Then I fly out of London at 6pm, arriving New York 8:35pm ... where I need to find somewhere to stay until I catch an early train from New York City to Boston on Monday morning. If all goes according to plan the net impact will be that I have a less fun weekend than planned and arrive a couple of hours late for work on Monday and a few hundred euros out of pocket... but of course nothing is guaranteed :-).

I'm pleased to report that the New Zealand embassy staff and the Lufthansa agents have been extremely helpful and professional throughout. I'm less pleased with my travel agent, who should have at least mentioned the machine readability issue. In the end, however, the fault is mine.

Update! Sunday, June 5

I made it to London last night, stayed at an exorbitant hotel overnight and took the tube to Picadilly Circus this morning to get my new passport. It only took twenty minutes ... now I'm online at a Starbucks near Charing Cross Station. I should have no trouble making my flight to New York and I may even try to get an earlier flight. London is amazing and I wish I had more time here ... maybe a few months to visit all the museums, monuments, and buildings. I can really feel the weight of its long history, the impact of having been the capital of a great empire.

Update! Monday, June 6

I stayed the night with my friend in Tribeca (thanks mate!) and I should be on my way and in Boston by around mid-day.

Update! Monday afternoon, June 6

I finally made it to Boston, checked into my hotel and arrived at the office. Woohoo!