Trackmap.net changelog

Back in 1996 when the web was young I started a website to host my collection of railway track diagrams. It eventually became trackmap.net. It has updated in fits and starts – the last time it did so was in early 2006 – but I still plan to get time to do updates in the future, such as the maps from this summer's Frankfurt trip.

Despite the irregular updates, trackmap.net was probably my main claim to Internet fame, until I wrote xcftools (which, incidentally exists solely because I needed it for producing track maps easier). Up until now, I have updated a static recent changes page whenever I did something – but seriously, nobody is going to look at that very often to see if there's any news, what with the multi-year hiatuses.

But perhaps some readers would find it useful to subscribe to an RSS/Atom feed for updates to trackmap.net and have their feed reader check it quietly for them? That sounds like a plan. So here is what I'll do: Every time I update trackmap.net (or its subsites) in the future, I'll post about it on this very blog, with the label "trackmap.net".

The label search page becomes the new changelog page, and the feed for new updates is here (Atom) or here (RSS). (Note: These feeds will show only posts related to track maps. If you select the Blogger-provided feed link in the navigation bar, you will get my full blog feed where I blather about various other topics at irregular intervals).

Old changes are still at http://dk.trackmap.net/news.

This posting serves to populate the trackmap.dk labels such that the links just given will not be empty.

Java 5.0 type inference is underspecified

Here's a program that will make your brain hurt:

class C<E> { }
class G<X,Y,Z> { }
class P { }
class Q { }

public class Test {
   static void foo(Object o) {
      System.out.print("Object ");
   }
   static <T> void foo(G<? extends T, ? extends T, ? extends T> g) {
      System.out.print("G ");
   }
   static public void main(String[] args) {
      foo(new G<C<? super P>, C<P>, C<Q>>());
      foo(new G<C<? super P>, C<Q>, C<P>>());
      foo(new G<C<P>, C<? super P>, C<Q>>());
      foo(new G<C<Q>, C<? super P>, C<P>>());
      foo(new G<C<P>, C<Q>, C<? super P>>());
      foo(new G<C<Q>, C<P>, C<? super P>>());
      System.out.println();
   }
}

Quick, what does it print? No cheating!

For what it's worth, Sun's reference javac, version 1.5.0₀₇ produces a .class file that prints

G G G G G G 

whereas Eclipse SDK 3.2.1 creates one that prints

Object Object G G Object Object 

Normally this would lead one to point at one of the compilers and shout BUG! – but after several hours of close reading the Java Language Specification I have come to the conclusion that both behaviors adhere to the letter of the specification. In other words, it is entirely up to the whims of the compiler which of the foos gets called in each of the six calls.

This is somewhat remarkable. Sun has otherwise gone to great pains specifying exactly what a Java program is supposed to mean, modulo the a few clearly defined areas where the virtual machine – not the compiler! – is explicitly given discretion. But here is a completely straightforward single-threaded program where (so I assert) the language underspecifies which method is supposed to be called.

Such nondeterminism makes it hard to do static analysis of Java source code. What happens?

Broadly speaking, generics happen. The half of generics that gets all of the press is parameterized types, but the really hairy stuff only begins to happen when we consider parameterized methods, too. The reason for this is the the programmer always needs to write down the type parameter explicitly in order to instantiate a generic type – but the designers of Java's generics decided that explicit type arguments should not be necessary for calling a generic method. It is possible to give type parameters explicitly in the code, but in the common case, the compiler must try to infer appropriate type arguments given the types of the ordinary arguments.

And this is fairly hard. In fact, because subtyping gets into play, it is so hard that the language makes no claim that the compiler can always find appropriate type arguments when you want to call a parameterized method. The language specification itself remarks, in the middle of the 16 pages of extremely technical definition of how the type inference works:

[...] type inference does not affect soundness in any way. If the types inferred are nonsensical, the invocation will yield a type error. The type inference algorithm should be viewed as a heuristic, designed to perfdorm well in practice. If it fails to infer the desired result, explicit type paramneters may be used instead.

Still, however, one would expect the inference to be deterministic such that one would not risk changing the behavior of a program just by recompiling with a new version of the compiler. But perhaps "perfdorm" and "paramneters" is a hint that this section has not received the most thorough of proofreadings before it went to press.

In the example program above, the type inference eventually computes that T should be instantiated to the "least containing invocation" of an unordered set of the three types C<? super P>, C<P>, and C<Q>. I now quote:

[...] lci, the least containing invocation is defined

lci(S) = lci(e₁, ..., e_n) where e_i in S, 1≤i≤n
lci(e₁, ..., e_n) = lci(lci(e₁, e₂), e₃, ..., e_n)
lci(G<X₁, ..., X_n>, G<Y₁, ..., Y_n>) = G<lcta(X₁, Y₁),..., lcta(X_n, Y_n)>

where lcta() is the the least containing type argument function defined (assuming U and V are type expressions) as:

lcta(U, V) = U if U = V, ? extends lub(U, V) otherwise
lcta(U, ? extends V) = ? extends lub(U, V)
lcta(U, ? super V) = ? super glb(U, V)
lcta(? extends U, ? extends V) = ? extends lub(U, V)
lcta(? extends U, ? super V) = U if U = V, ? otherwise
lcta(? super U, ? super V) = ? super glb(U, V)

[The Java Language Specification, third edition, p. 465]. Read the definition of lci carefully. The first line says that we arrange our three types in some unspecified order. The second line says to combine two types at a time using a two-argument version of lci. And the two-argument lci in the third line just distribute lcta over all the type arguments. (We know from earlier in the type inference that all arguments to lci are instances of the same parameterized type).

This would be a nice and standard construction if only lcta (and by extension the two-argument lci) were commutative and associative. It is indeed commutative – it has to be, for the cases given in the definition only make sense if we understand implicitly that we are to take their commutative closure. But it is manifestly not associative. To wit:

(? super P) lcta (P lcta Q) = (? super P) lcta (? extends Object) = ?

whereas

((? super P) lcta P) lcta Q = (? super P) lcta Q = (? super P & Q)

In the former case, the parameterized foo is not applicable to the call with T = C<?>. Therefore, compile-time overload resolution decides on the less specific but viable foo(Object) instead. But when T is C<? super P & Q>, the parameterized call is applicable.

How clever of javac always to choose the evaluation order that reaches the better result! In fact, I suspect it of cheating and using a smarter multi-argument lcta computation for each type-argument position, instead of selecting on a common order of all lci arguments. Extending the example program to test this hypothesis is left an exercise for the reader.

(Also left for the reader is to figure out the exact meaning and properties of ? super P & Q, a possibility not hinted at anywhere in the JLS except for the two occurrences of "? super glb(U,B)" in the definition of lcta).

Does P equal NP? This is not an answer.

A preprint by Sten-Åke Tärnlund, purporting to prove that P≠NP, is making its rounds on the internets. I noticed it through a blog post by Bruce Schneier; he quite sensibly notes that "these sorts of papers make the rounds regularly, and [Schneier's] advice is to not pay attention to any of them."

Still, someone has to try to pick such papers apart, if only to make sure that they are as worthless as statistics suggest. I'll volunteer for this one. (This mini-review was originally intended to be a comment to Schneier's posting, but grew a bit too large for that. Also, I want to use markup that plain-text comments cannot contain).

It is not easy to figure out what the author is getting at, because the paper is pithy to the point of sloppiness. Take, for example:

Definition 8 p(a) for c·|a|^q some c q ∈ N any a ∈ L.

By comparison with other similarly terse definitions, this apparently means

Definition 8. Let p(a) abbreviate c·|a|^q for some c and q in N, and any list a.

But what are the scope of the quantifiers on c and q? Are they constant throughout the paper or can they depend on something? What can they depend on? It makes no sense in context to let them depend on a ... Complexity theory has no lenity for those who fail to be rigorous about order and scope of quantifiers.

Formally, the paper begins to go wrong no later than Definition 13, where T(s,a,u) is defined to mean something that involve the "truth" symbol ⊨ (or |= if your font, like mine, has no native Unicode glyph for this symbol), which is not in the language of B – but in the remainder of the paper T(s,a,u) is treated as if it was a formula of B, and bogosity ensues.

Of course, a formal error does not mean that the idea behind the paper is flawed. But it does not bode well – one would think that an author who is smart enough to solve an open problem as famous and long-standing as this would be more careful. Indeed, a true flaw shows up:

As far as I understand it, the main argument in the paper goes somewhat like this: Assume that you give me a Turing machine that purports to solve SAT (i.e., decide whether a propositional formula is a tautology) in polynomial time. Then I'll try to run a sufficiently large "pigeonhole formula" PF_m through your machine. I already know that this formula is a tautology, but if your machine tells me that in polynomial time, I can extract a short proof of the formula from what the machine does. This contradicts a theorem by Haken which says that proofs (in a certain restricted form) of the pigeonhole formula are always long. Therefore, your machine either does not solve SAT or does not do it in polynomial time.

What first meets the eye here is that the paper appears to redefine SAT. The SAT we all know and love is about propositional formulas (i.e., expressions built from Boolean variables and the Boolean operators not, and, or and so forth). However, PF_m which the paper tries to use the SAT solver on is not propositional. It is defined only informally here, but for it to have any relation to Haken's theorem, it needs to contain non-Boolean variables and equality operators. Those belong to predicate calculus, not propositional logic. However, this is not in itself damning, because satisfiability in the pure first-order theory of equality is easily seen to be in NP. A valid proof that this is outside P would also solve the P=NP question.

Correction (2008-11-09): It turns out that there are indeed purely propositional formalizations of the pigeonhole principle, and the paper must be referring to one of those. I had in mind a formula such as "(a=1 or a=2) and (b=1 or b=2) and (c=1 or c=2) implies a=b or a=c or b=c". What I did not notice (and, in my defence, the paper never writes out an example of its PF_m) was that we can just expand, say, "a=b" to "(a=1 and b=1) or (a=2 and b=2)", in which case we can take things like b=2 as propositional variables.

The true fallacy here, however, is the tacit assumption (partly concealed as Definitions 13 and 14) that if we have a Turing machine that recognizes tautologies, then a short proof that this machine answers yes for a given formula corresponds to a short proof that the formula is indeed a tautology. But this is not necessarily true; it is at least conceivable that there is a fast Turing machine that recognizes tautologies but that we cannot prove that this is what it does. In that case, a trace of the Turing machine's action does not correspond to any proof that the formula is a tautology, much less a short one. And even if the machine provably recognizes tautologies, we cannot necessarily extract a short proof in a particular formalism from a short run of the machine.

There is various additional smoke and mirrors, including the central proposition which is stated thus:

Theorem 1 SAT ∉ P is true in a simply consistent extension B' of theory B.

Does this mean simply that there is some consistent extension of B in which SAT is not in P, or that SAT∉P is true in every consistent extension of B? I cannot tell. In the former case, the proposition says nothing about the standard model for B (i.e. Turing machines modeled with the standard integers, which are not necessarily a model for the extension). In the latter case, why bother speaking about extensions in the first place?

In conclusion, Schneier is right, and this can safely be ignored.

Legal consistency

Some time ago I asserted that American court opinions "are fairly accessible once one learns a few key words and turns of phrase". Suddenly I begin to doubt that.

In EEOC v. Lee's Log Cabin (7th. Cir, 2008-10-06) I read this marvellous piece of logic:

The dissent also asserts that "[i]t is undisputed that at all relevant times, Stewart was not only HIV positive . . . but she also had AIDS. So the allegation in the complaint that Stewart was 'HIV positive' is consistent with the fact that she has AIDS." Dissent, at p. 18. No, it's not, but the opposite is true. That is, an allegation that Stewart has AIDS is consistent with an allegation that she was HIV-positive, but not vice versa. If a person has AIDS she is necessarily HIV-positive; but a person who is HIV-positive does not necessarily have AIDS.

(footnote 3). In the kind of logic I was taught, "consistency" between two propositions means that it is conceivable that both can be true at the same time, or (more syntactically) that assuming both will not let you derive a self-contradiction. This is a symmetric notion. It makes no sense to assert that A is consistent with B yet B is not consistent with A.

I wonder whether there is a particular legal meaning to "consistent" which is different enough from the logical one to make the above quote senseful.

More precise than a million monkeys with typewriters

Ferdinand Foch is remembered for remarking, when the Treaty of Versailles was signed, that it was "not a peace but a 20-year armistice". This was eerily prophetic – he was right to within a handful of months. Foch must have had an unusually precise sense of the forces that make history go.

Or did he? I wonder how many would-be prophets characterized the treaty as an armistice for 10, 15 or 25 years, and were quietly forgotten by history.

It's easy to pick successful prophecies when you're allowed to wait until they come true before you decide which prophecies to point to.

Why copyright is doomed

In the beginning there was no copyright.

Books were written (and music composed) by men of independent means, or by talented men sponsored by princes and nobles, or by scholars or clerics who were fortunate enough to have the power to decide that writing a treatise on this or that just happened to be part of their own duties. Somehow world literature got along.

Then somebody invented the printing press. The press, together with other technological advances during the 1400s, made mass production of printed books a feasible alternative to hand copying of manuscripts. And this changed everything.

First and foremost, printing books is a capital-intensive undertaking. In addition to the cost of the printing press and its various paraphernalia, setting type by hand is slow and costly. It makes sense to analyze the typesetting cost as capital rather than labor, because once the type is set, you can print copies of the book very cheaply. You can make your customers pay quite a bit more than your marginal cost for each item you sell, which will allow you to break even in the end. And the customers are not going to care whether you've broken even or not, so you can still charge the high price after you break even. If there's enough demand for the title, printing books can be quite a profitable business.

Now, printers who choose to print books that turn out to be popular become rich; printers who choose badly do not. If we assume that the popularity of one title over another is due to some special talent or effort expended by its author, it begins to look quite unfair that the printer should become rich because of them and the author get nothing. That is what the first copyright laws set out to remedy, after the changes wrought by Gutenberg had had a few centuries to sink in.

Actually, it was a bit more complex than that. Publishers – who around this time were emerging as a separate trade of funders and distributors of books – also benefited from copyright: Regulation of who could print what reduced the risk that another publisher would start printing the same book, leading to a price war (which would lose money for both printers as the the price per copy dropped towards the marginal production cost). But the moral justification for having a copyright system in the first place was that it let authors get a cut from the profit when the quality of their works became the foundation of somebody else's business.

During those same centuries, medieval religious drama gave way to professional theatre, and instead of semi-improvised lines that changed with time according to audience reactions and the actors' own wit, plays came to have written-down scripts authored by named playwrights. Theatre was now a business, and a company could make a profit with a good performance of a good play – and thanks to the printing press, the playwright need not be affiliated with the theatre company.

In music, partly in response to the demands of theatre, ensembles grew in size and complexity – beyond the point where the performance could be structured by oral agreements and remembered tunes. Music notation expanded to meet the needs of orchestrally scored music. Eventually the public concert where professional orchestras performed for paying audiences was invented. Having a good work by a recognized composer on the billboard certainly helped draw in those paying audiences.

Playwrights and composers must now suffer that not only could publishers make a business of printing their work, companies and orchestras could make a business of performing them. In response, copyright expanded to cover "public performances" in addition to simply the making of physical copies.

As I have insisted above, the moral purpose of copyright was still to save creators from the indignity of seeing somebody else build a profitable business upon their work without getting a share of the success themselves. But as a side benefit, creators who did create successes got an income source and the opportunity to quit their day jobs and create yet more successes. This benefits society as a whole. It was seen as an independent motive for copyright as early as 1787, when the drafters of the American constitution allowed for federal copyright legislation "to promote the Progress of Science and useful Arts".

Sound recordings were invented in the late 1800s and quickly integrated into the basic structure of copyright. They fit well there, because it requires specialized and expensive equipment to manufacture records, and large specific costs to prepare a recording for being mass produced – exactly the qualities that made copyright the right legal tool for printed books centuries earlier. As for books, creators of successful records have been able to quit their day job, sometimes spectacularly so.

Movies also got copyright. Again, production of film prints is a specialized commercial operation, and public performances is usually organized by businesses too. This fits the philosophical framework of copyright fairly well – though in comparison to a novel or a symphony, which are usually the work of an individual genius, creating a movie is quite a team effort. Copyright fairly easily let itself be extended too deal with large team efforts.

In each of these successful cases, copyright has felt like a right and just tool, because the activity being regulated – whether printing a book, performing an opera, stamping a record, or showing a movie – was naturally and necessarily a commercial undertaking. Done by a business. For a profit, which it is only reasonable to share with a creator.

Well, well, well. Guess what is not true anymore?

We see the underlying assumption break down most clearly for recorded music. For at least a decade there has been no practical reason why copies of sound recordings need to be made by a business rather than by private individuals. The technology is cheap and ubiquitous, and the shift in public perception of copyright has been quick and pervasive. Very few people today really feel that it is morally wrong to create an unlicensed copy of a commercially released song they like. Those of us who nevertheless refrain from doing so do it for the warm fuzzy righteous feeling of complying with the law even when the law is unreasonable.

Movies are not far behind music in this development. Many kinds of books still hold out, because people like the feeling of real bound paper books better than reading from a computer screen. But if print-on-demand hardware becomes ubiquitous enough that bound paper books are not made by specialized businesses anymore (or if really acceptable ebook readers emerge), I predict that the respect for copyright of books will go the same way as that for music. And, of course, already some kinds of non-fiction books are dying breeds, being replaced by free internet versions.

Music and movie publishers everywhere know all this, and are understandably all up in arms. Their response so far is threefold:

1. Try to put the genie back into the bottle. Have copying technology outlawed or forcibly crippled. If this prevents amateur artists from creating their own works that may compete with commercial offerings, then so much the better.

   If successful this would lead to a nightmare world, but I don't think our politicians are that stupid. We have Vernor Vinge, Cory Doctorow and the EFF to explain why this shouldn't succeed; overall they do it well enough that I think it won't.

2. Lobby legislatures to introduce ever more draconian laws to enforce copyright. Hope that you can bludgeon people into following rules out of fear that they won't follow out of fairness.

   At best, this is a short-term stopgap. At worst ... well, it doesn't really seem to have the desired effect out in the real world, does it? If anything it seems to reinforce the perception of copyright as an instrument of oppression, rather than a rule that works for the common good.

3. Appeal to everybody's better nature such that we will all begin to think it is wrong to make private copies of music even if no business is involved. This is the "artists deserve compensation" argument, and it is very convincing on its face. It is also, I think, subtly flawed, and the main point of this essay is to explain what is wrong with it.

   The hidden assumption of the argument is that the creator suffers some kind of moral wrong each time someone enjoys his work, and that the purpose of royalties is to compensate him for that wrong. But what is that wrong? It cannot really be the lack of opportunity to capitalize on the copyright, because the whole point of the argument is to motivate copyright in the first place. But stripped of that explanation, the assumption is simply stupid – creators want their work to be enjoyed, and are pleased when people do so. True, they also want to quit their day job, which requires that income can somehow be derived from the work, but it does not follow that this income has to be in the form of per-copy royalties. And wanting the conclusion to be true does not make the argument hang together.

I think all three responses are likely to fail in the end. Copyright is doomed. It may take decades, or even centuries, for it to die out completely, especially because it has been entrenched in international treaties which are very difficult to change. But die out it must, for it cannot persist in a world where copying is no longer expensive and complex.

This state of affairs creates a political obligation to think ahead. We still want want the world of tomorrow to be one where talented creators can quit their day job and create more. The challenge is to think up a system that does this and still respect the technological reality.

It is tempting to take as a starting point that creators should be rewarded in proportion to the enjoyment people derive from their work. But the trouble is that enjoyment is not easily quantified. In a way, the copyright system uses "number of copies" as a proxy for "amount of enjoyment", which works rather poorly. When making and keeping a copy is cheap and easy, people are likely to keep a copy of every work that they don't actively dislike, whether that work is one of sublime genius or merely passable.

There's a movement towards using "number of listenings/readings" as a proxy for amount of joy, such that if you want to read a book again you have to pay anew. This doesn't work well either. Many a time when I sit down to read a book, it proves to cause me no enjoyment at all and I conclude that the book is horrible. And when I reread a book it may not be because I enjoyed it the first time, but because I need to look up a dry fact about it.

I doubt a working calculus of joy can be developed. How about explicit public subsidies to outstanding creators, awarded by expert committee? That is already common in countries with languages that are perceived as too small for a national literature to flourish funded entirely by copyright, such as Danish. But I don't think it is attractive as a general solution; too much power is concentrated in the hands of the committee, and even with the best of intentions the committee cannot possibly have enough information to make a really informed choice.

Despair and accept that day jobs must be had? Most likely, music and literature would continue to exist – the equipment necessary to create either is within the reach of determined hobbyists. Movies wouldn't, however; it is mindbogglingly expensive to create a movie at the technical quality modern audiences expect. Can that be covered by the box office alone? Probably not in the long run, what with the increasing quality of home AV equipment. And a plan that means that movies cannot be made is not politically viable. Exit "despair".

I am left, for the time being, with no good proposed solution. But that does not make the problem go away. It is still there, whether we like it or not, and solving it before the death throes of copyright end should be high on the list for politicians concerned with culture.

Confused? You won't be after this...

A customer needed to read some simple information out of our server software programmatically, and suggested that a "SOAP API" might be a good way to do that. To me fell the task of researching what that might mean.

SOAP is a lightweight protocol intended for exchanging structured information in a decentralized, distributed environment. Why, it says so right in the spec!

I dread to think of a protocol that the W3C would call "heavyweight".

That funny judgement with the tree

I found this judgement through a Groklaw article some time ago. Recently I desired to reread it, but it took me quite a lot of tries to remember sufficiently precise search terms to locate it again. Clearly it has not received enough link love.

It's about a young couple who bought a house and cut down a mulberry tree which leanend over the backyard but actually belonged to their new neighbour. The neighbour sued. Fairly banal case, except that it is presented with hilarious wit.

I give you Thayer v. DeWolf, memorandum order by Magistrate Judge Goodbread, who I think would make a good hacker. Respectfully recommended for your reading pleasure.

Rindler's relativity textbook

An open letter.

Dear Professor Rindler,

I write to thank you for writing Relativity: Special, General and Cosmological. I picked it up by chance at a university bookstore several years ago, and I've found it to be very enlightening and well readable.

I'm what one might call a physics amateur – not quite a physics student, certainly nothing resembling a researcher, but possibly a step up from the "educated layman" level. I like to extend my understanding of modern physics, for my own amusement and a sense of moral duty for a thinking being to at least try to understand the world he finds himself in. Here, by "understanding" I mean something deeper than memorizing some popularizer's free-floating qualitative assertions and analogies. Luckily, as a computer scientist with a B.S. in mathematics, I am no stranger to formulae – a mathematics-free understanding of any area of physics appears to be an oxymoron.

It is not easy to find good literature for a project such as mine. There are, of course, many books that purport to explain modern physics to laymen, but they all studiously avoid presenting any mathematical content of the theories they speak of. (The only exception I have encountered is Roger Penrose's The Emperor's New Mind, which however covers so much ground that its treatment of any particular subject is very brief). Even when they manage correct qualitative descriptions of a theory, they cannot, lacking formulae, convey a good sense of the predictive character of the theory. As for general relativity, popular works tend to stop at the rubber-sheet analogy, usually without even developing it enough to make it clear whether they try to depict spatial curvature or graph gravitational potential.

On the other hand, actual university textbooks tend to be too dry for the amateur. They often dive straight into formalism, with much time spent on methods of concrete calculation and little emphasis on intuition and perspective. The amateur (meaning I) tends to have little patience with problem-solving tricks; he wants to understand the structure of the theory more than he wants to apply it in practice (though, of course, one person's clever computational shortcut can become a basic feature of another's theory – as I understand it to have been the case for quantum electrodynamics). And above all, he needs hints about intuition and perspective. Intuition without mathematics is for cocktail-party philosophers, but mathematics without intuition is for robots. Apparently most textbook authors rely on the instructor for supplying students with the big picture, which is not unreasonable but does not help for self-study.

Your book, however, is a rare gem: A text that both teaches the formalism of the theory and explains what it means intuitively. In reading some of the sections, I have followed the mathematics carefully, checking derivations and doing exercises. This gives me a solid sense of knowing what goes on. In other sections I have skipped most details of the formulae but still got a general picture from the connecting text. This general picture is, in a sense, second-hand knowledge, but feels more secure than that, because the mathematical details are right there should I ever want to check them.

It is very wonderful that the book is capable of being read both ways.

I'm convinced that this book has made me smarter. It has enabled me, in many discussions with fellow amateurs, to correct (I hope!) misconceptions and confusions caused by fuzzy and imprecise popularizations of GR and black holes. I have been recommending it left and right. I'm very happy that it exists, and that I discovered it.

Sincerely yours,

Henning Makholm

* * *

Respectfully recommended for your reading pleasure: Relativity: Special, General and Cosmological by Wolfgang Rindler (Oxford University Press, 2001; 2nd ed. 2006). This book will teach you everything you want to know about special relativity (saw the Lorentz transform in high school and thought it was all there is to it? Think again), general relativity, black holes, as well as a fair overview of cosmology and tensor calculus. The preface promises: "Anyone who knows the calculus up to partial differentiation, ordinary vectors to the point of differentiating them, and the most useful method of approximation, the binomial theorem, should be able to read this book." As far as I can tell, that is what it delivers.

Elections and geography

Some time ago I confessed that I read American court documents for fun. I cited the quality of some judges' writing as a reason for that, but a side benefit is some indirect insights into the half-continent of madness that is the United States of America. And sometimes, by contrast, into little old Denmark too.

Consider this recent case, Gonzalez v. Aurora. Several people from a western suburb of Chicago sued their city council, demanding that its voting districts be revised such that their particular racial group would be likely to get more seats on the council. Plaintiffs lost in the lower (district) court, and now they lost in the appeals court too. The court's opinion does not have the kind of dazzling rhetoric I wrote about earlier. But it made me think, about the differences and similarities between the political system it describes and the one I'm used to.

It probably ought to startle me that this matter is considered something that a court should decide at all, but it doesn't. In USA, it seems, everything is a potential matter for court intervention. Everyone who doesn't live in a cave probably heard about the 2000 presidential election.

What does trouble me a bit is that the plaintiffs' argument seems to assume that the voters in Aurora decide who to vote for using candidates' race as their first and final criterion. Such voter behavior is not unheard-of – in semi-failed post-colonial states suffused with mutual distrust between clans and ethnicities who find themselves sharing political structures by way of historical accident rather than sharing a functional society. But in a modern democracy with everybody integrated in a common economy? I know that when I go to vote, I try to vote for the candidate who shares my political views the most, rather than one who shares my complexion.

It might seem equally troubling that the appeals court willingly accepts this strange theory. But the court did find against the plaintiffs, and it makes for a stronger and more persuasive opinion if the court goes along with the losing party for the sake of the argument until the critical point where the loser's case breaks down. Implicitly, the court says "even if you were right about all this, you'd still lose because so-and-so".

But what really got me thinking was the unquestioned baseline assumption that most councilmen have to be elected in single-seat wards. Voters who happen to agree with the majority in their local ward get to be represented. Voters who are in a local minority become virtually, or nearly, disenfranchised. It doesn't matter if some political stance has a uniform 49% following everywhere; it gets zero electees because its popular support is insufficiently clumped.

I have heard people trying to justify such a system, but I've never been able to grasp their arguments. Why should geography matter? When I go to vote, I try to vote for the candidate who shares my political views the most, rather than one who by some quirk of the housing market happens to live close to me.

This would be quaint and amusing if is was a specific rarity of Aurora, Illinois. But it is sad that it is actually quite common. Most famously, perhaps, with the electoral college by which Americans chose their president. It is not a particularly American phenomenon, though. The UK House of Commons works the same way. And the way we elect the European Commission is perhaps the most indirect, convoluted and opaque of all, closely followed by the Council of Ministers which has the final political say in all matters EU.

Closer to home – in Denmark municipal councils are elected directly and proportionally, simple enough. But elections to our national parliament the Folketing, use a weird mix of geographic and proportional methods. Some members are elected in regional districts, with a number of additional at-large seats distributed afterwards such that the final party make-up of the parliament will get as proportional as possible. Then there are complex and elaborate rules for simultaneously distributing the at-large seats to ensure approximate geographical proportionality in the parliament as a body, as well as within each party.

Active politicians care about this system, because it decides which among each party's candidates win a seat, a matter of paramount importance among those running. Almost nobody else does, and look only to the final party breakdown (which, being guaranteedly proportional, can be understood without resorting to geography). When I've been a poll worker at general elections, some voters were obviously confused because the political leader of their choice was not on the ballot – he or she were running in a different district. Again, why should geography matter here? A smart voter tries to vote for the candidate who shares his political views the most, not one who happens to live in the same part of the country.

And, adding to the confusion, the district a candidate runs in does not have to be the district where he or she lives. In fact, for top politicians it is the exception more than the rule. Each party selects the running districts for its top candidates tactically, to maximize their chance of election given the above-mentioned rules that ostensibly exist to equalize the geographic origin of the MPs. Except that what it really equalizes is virtual pseudo-origins chosen solely based on the rules themselves.

Excuse me, but I fail to see that society at large benefits at all from this convoluted system.

(... now where was I? Something about a court and a city council in Illinois, I think. You mean I was supposed to have a point about that? Sorry. Still new to this blog thingie).

Take my money if you must, but stop spamming

In 2003, after I completed my PhD dissertation in Copenhagen, I moved to Edinburgh to work as a post-doc for Joe Wells. Joe was rather eager to have me start as soon as possible such that I could receive a braindump from to the previous occupant of my position, who would be leaving soon. The plan ended up being that I'd complete and deliver the dissertation on Friday, and start work in Edinburgh the following Monday.

I arrived on Monday with a suitcase containing several changes of clothes. Meanwhile, my parents were cleaning out my flat in Copenhagen, packing my stuff into boxes and having it shipped to Scotland. (Thanks, Mom and Dad – you're the best!) Note to self: such tight schedules can not be recommended for future job changes.

The first thing I was told to do after I arrived was to go a bank and open an account into which my first salary could be deposited. Salary payments must be prepared some weeks in advance (paying out money always seems to involve red tape in proportion to the size of the organization), and I was arriving near the end of the month, so payroll needed an account number for me post haste. Otherwise they'd have to, I don't know, special-case my payment or something. That, apparently, would be a Bad Thing.

The Royal Bank of Scotland had a branch right on campus. I went there and they created an "instant access savings account" for me. A few weeks later I discovered that this was not quite the type of account I wanted; I'd rather have a "current account". I don't remember what the difference was. Presumably I had good reasons for switching.

For some reason, my existing account could not just have its type changed; I had to create a new account of the right type instead. Once I'd gotten the account number at payroll updated, I went to the bank and asked to have the savings account closed and its balance transferred to the current account. This happened.

Except that the savings account turned out to be not quite closed. At the end of the year I received an account statement for it. It had earned 6 pence of interest by containing half a month's salary for a few weeks, so its balance now read £0.06. There didn't seem to be any way to react to this that was worth the trouble, so I didn't.

Time passed. Every so often, the monthly statement for my current account would be accompanied by another sheet reminding me that I had £0.06 in the savings account. In 2005 I moved back to Denmark. I had the current account closed (successfully) and its balance wired to my Danish bank.

But that poor savings account kept sending me statements for the same £0.06 several times a year. Each statement probably cost the bank at least ten times the outstanding balance to print and mail. But I'd become less than satisfied with the Royal Bank of Scotland's service (for reasons that I may blog about later if I find myself in a particularly petty mood one evening). Anyhow, I figured that they deserved it, somehow.

But perhaps three years is enough to forgive and move on. Today statement #12 arrived in the mail. I have just spent about a pound in stamps on returning it with a request to have it shut down.

Ain't I a nice guy?

Tilting Iapetus

Now that I have a program to draw world maps with nonstandard orientations, I could not resist turning it loose on this albedo map of Saturn's moon Iapetus, pieced together from images taken by the Voyager 2 (1981) and Cassini (2005-2007) spacecraft. Iapetus is one of the strangest objects in the solar system. Its most famous feature is its "two-tone coloration": it has a light side and a dark side, and is much brighter when the light side faces the sun (and us). But there is more strangeness than that; go read the Wikipedia article.

In the novel version of 2001: A Space Odyssey, Author C. Clarke explained away all the strangeness with a deus ex machina solution: the entire moon is an alien artifact! He warned, however that "the truth, as always, will be far stranger."

Here is an ordinary map, with the central meridian chosen to go through the middle of the dark area:

We see a large dark splotch (named Cassini Regio) on a light moon. On the other hand, Clarke relates in the introduction to 2010: Odyssey Two that Carl Sagan sent him a Voyager image showing a white oval on a dark moon. How can that be? Let's get out our planet tilter:

The edge of this map runs along the moon's equator, in the middle of Cassini Regio. Now we see a light splotch (called Roncevaux Terra) on a dark background. Magic!

I've cheated a bit, though, by choosing the little-used Aitoff's projection for the above maps; it exaggerates the size of areas near the edge of the map. With the equal-area projection I used for Earth in my earlier post, the Roncevaux Terra map may begin to look more like a light world with a dark edge:

Finally, a map with the poles in the centers of the light/dark areas:

The boundary between light and dark does not really divide the moon into hemispheres; it goes more like the seam on a baseball.

Cheap flights to Planet Barrel

Here is a poster I saw in the storefront of a travel agency in Frankfurt. I don't know which projection this world map tries to be, but if that isn't a barrel-shaped world it depicts, you can call me a barrel.

No war on photography in Germany

Since 2001, the home front of the questionably-named "War on Terror" has devolved into what Bruce Schneier calls the war on the unexpected, in which anybody doing anything out of the ordinary risks being hassled by authorities, on the theory that activity that the person-in-authority does not understand might somehow be part of a terrorist plot.

A particular variant of this is the war on photography. It appears that in certain locales, photographing structures or buildings in public where the motives have no clear touristic interest, is considered particularly suspect. It makes a certain, tiny, bit of sense that a terrorist cell contemplating an attack might like to use photographs of the target and its surrounding in their planning. But it stretches my imagination to think that photographs would be such a sine qua non for a plan that banning photography would help much to prevent an attack by a determined group – at least when the photographs are of things that each would-be attacker could just walk up to and look at directly.

I am pleased to report that the war on photography has apparently not reached Germany.

I write this on the way home from a week's vacation in Frankfurt. My vacations are different from most because I have the rather weird hobby of collecting and understanding railway track layouts. There are quite a number of people who photograph, and otherwise obsess over, trains, but only few of us who lavish the same attention on the tracks the trains run on. In short, my idea of a good time is to go to a large station, hike out to the very ends of each of the platforms, taking lots of pictures of the surrounding trackage as I go. Then, if there are any public footbridges or streetbridges going over the track area, I go up on those and and repeat the exercise from there. Finally I take a train to another station, observing the neighboring tracks along the way, and either taking notes or photographing out the window. Repeat as long as daylight lasts.

This probably does not sound like fun to you, but it works for me. When I get home I sometimes get time to process all of the photos and notes into nice track diagrams for the areas in question; you can see some of the finished products at my website trackmap.net.

To get to the point, I've been doing this for a week – standing on the overgrown ends of platforms that are not being weeded because no trains stop that far out anyway, in plain sight of railway employees who didn't seem particularly busy (waiting for the train they are to work on), blatantly and obviously spying on their precious infrastructure. I even wear a terrorist beard. Yet, not once did anybody approach me to suggest that I shouldn't be doing what I did, or even to question what I was doing.

This is the same experience I had for a week in Vienna in 2007, a few days in Glasgow in 2006, and a week in Berlin in 2002. (Not quite true; in Berlin a couple of good-natured Bundesgrenzschutz officers did ask me what I was drawing – this was before good digital cameras became affordable to me, so I was using binoculars and a sketchpad instead. But they seemed to be more curious than suspicious, and ended up wishing me a nice stay after I explained in halting German what I was doing. In retrospect, perhaps they were just checking whether I would act hinky upon being asked).

The world isn't quite as bad a place as you would think reading about just the egregious blog-worthy extremes of the war-on-anything. Of course, that does not mean that the extremes don't deserve the publicity, ridicule and outrage they get. That is how we keep them from becoming the norm. But they are not yet normal, and that is a Good Thing.

Actually, they may or may not be the norm in America. I have read too many scary war-on-anything blog stories to dare go there and find out.

P.S. It just now occurs to me that one of the symbols I use in my hand-drawn sketches, a stylized tree meaning roughly "these tracks are visibly abandoned; shrubs and small trees growing between the rails", could easily be interpreted as a stylized mushroom cloud. Good thing my notes did not fall into the hands of an alarmist terrorist hunter. Except in 2007 I did foolishly forget a sketchpad in a train (and lost several days' worth of sketches). Wonder what happened to that ...

Tilting the globe

We all know that the Earth is spherical (not exactly, byt close enough for my purposes here). But what world maps seem to tell us is that is more like a cylinder. Wider at the equator, though – barrel-shaped perhaps?

Why, just look at the map:

We know that the left and right edges are really the same place; there is only one Pacific Ocean. It's not too unusual either to have seen maps where the edge is some meridian other than 180° E/W, such as this:

So we're familiar with the fact that if we keep moving east or west long enough, eventually we'll end back where we started. This striking enough that circumnavigating the globe is considered something in and of itself (Phileas Fogg never ventured south of the Equator, but is nevertheless considered to have gone around the world). But it does not feel strange, as such.

The poles, however, are weird. In the projection I have chosen here, each pole has been deformed from a point into a curve that forms the entire top or bottom edge of the map. We know, intellectually, that this is just a coordinate singularity, an artifact of the map projection. To someone actually standing on the pole, the ground will appear just as flat and featureless as it does anywhere else, modulo mountain ranges and other minor details.

But knowing is not the same as really believing. We feel vaguely – or perhaps I should stop speaking for everyone else at this point – I feel vaguely that this coordinate weirdness somehow must correspond to a real weirdness, that if I were to go there I would somehow distort along with the map, like the proverbial gedankenastronaut who falls into a black hole and finds himself stretched by infinite tides in the east-west direction.

A more everyday symptom of barrel-shaped thinking is the surprise we've all felt at some point noticing just how close to the pole a great-circle route between two distant cities goes. If you fly from London to Tokyo, the standard maps invite the assumption that you should head to the east and slightly south. But actually you should start out in a northeastern direction and pass quite close by Helsinki.

I set out to disabuse myself of the barrel-shaped fallacy. The first step is to look at a map which does not distort the poles – a pole-centered azimuthal projection:

This helps a bit, but not by much. The coordinate lines of the polar map still implicitly convey the message that the pole is a very special place. There's still a feeling that it has some momentous topological significance whether a path from point A to point B passes left or right of the the pole. Perhaps I just lack imagination, but I still find myself thinking in barrels when I look at a pole-centered map. Map globes are not much better; they tend have bearings and other special decorations at the poles which fuel the barrel fallacy directly.

Stronger measures are needed here. The trouble seem to be the map grid – how about we draw a completely different grid over the polar regions? We could pretend that the Earth's axis passed through, say, Hawaii, and draw the world map that would result.

That sounds promising. More significantly, it sounds fun. So I wrote myself a program to draw world maps with alternative positions of the poles. I find the results convincing and fascinating. Here is the pole-at-Hawaii scenario, with two different central meridians:

The antipode to Hawaii proves to be in southern Africa, so that is where the other pole goes. The shape of Africa gets strangely distorted by the map projection, which should teach us to doubt what normal world maps tell us about the polar areas. The other continents look more recognizable, except – wonder of wonders! – the Arctic Sea is now clearly just another place.

The fascinating part comes from wondering: If the world was actually tilted to turn around the Hawaii axis (but otherwise with its current orbit and axial tilt), which climate would such a world have? Latitudes give a crude hint at the weather at different places, but that is far from the whole story. Sea currents transport large amounts of heat around the globe, and the currents would be vastly different on the tilted globe, driven as they are by winds and Coriolis forces. The winds themselves would be different; winds try to align more or less with latitudes but are deflected by mountain ranges and warped by differences in sea temperatures (which are themselves governed by currents, which are driven by winds, making the whole thing recursive). I cannot even start to answer the climate question, but I'm sure a good answer would be very interesting.

After climate comes culture. How would world history have unfolded on the tilted globe? For example, this world does not seem to need a Columbus. What, if anything, would that change? Would the Industrial Revolution still happen in a tropical, upside-down Britain? I suspect there's some pretty cool alternative-history fiction waiting to be written here.

There's no reason to stop at Hawaii, of course. After creating my program, I have (mis)spent several nights looking around for interesting places to put the poles. Here is one that shows all of the continents are connected:

This map has the nice feature that no continental land or shelf is bisected by the edge. That is not not trivial to achieve because the edge of a world map of a somewhat orthodox shape must represent half a great circle, and there isn't much wiggle room to place it without hitting land. I think there are only three essentially different solutions; here is a second one, showing continents in a circle around the Pacific Ocean:

On the other hand, getting both poles to be covered with land is even harder. The best possibility seems to be this, which just barely does the trick:

Note here in particular that the only "wet" passage through the edge of the map is the Bering Strait (save for the wiggliness of the Panama isthmus, which the straight edge cannot quite follow). This map tries to tell you that all of the oceans are really just a single sea surrounded by land. The previous two ones try to tell you that the continents are really just a group of islands on a water planet. Both, however, show the same planet. We shouldn't believe any single map too much.

P.S. I got the shapes of continents, with elevations and sea depths as a bonus, from the ETOPO2v2 dataset, which is a marvelous resource. My only regret is that I can't drain away the icecaps of Antarctica and Greenland, but it's not obvious how to define the result of that. And it is free! You too can create cool alternative world maps if you know a programming language and some spherical geometry.

In the future, anything can be a TLD

ICANN has announced the approval of a new policy for the creation of new top-level domains, known as gTLD's in the jargon.

A gTLD is the suffix such as .com or .net that appears at the end of an Internet address, except for two-letter country codes (such as .dk or .us). Originally the only gTLDs were .com, .org and .net, for general use, plus a few stray ones (.mil, .gov and .edu) which should probably have been under .us but was inherited from the Internet Stone Age where .us had not yet been invented. During the last decade or so, a dozen or so of new gTLDs, such as .info, .museum and .cat have been created, as an experiment in how to the Internet's namespace should evolve in the future.

The experimental process that gave us .info and its friends was, hmm, let us just call it rather heavy. Formal proposals had to be made, public comments collected, innumerable constituencies consulted, pages upon pages of reports written, read and eventually voted on by the board of ICANN. Unsurprisingly this approach has been found not to scale, so ICANN is streamlining it considerably.

In the future everyone will be able to propose a new top-level domain, and if you pass a few technical sanity checks (not yet quite defined, it seems) and pay the fee (at least several thousand dollars, it is rumored), then presto, you have your own top-level domain name.

The announcement suggests that this new process will be used to create city-based gTLDs such as .paris or .nyc in which second-level domains can be registered by the public like it happens in the existing ones. And we can readily imagine future trade-specific gTLDs – say, .food or .bank – and language-specific ones like the existing .cat for the Catalan community. (I appreciate that ICANN would not want to conduct a heavy voting-based process on .kurd ...)

Such community-based domains are the lofty, noble ideal. If there is a market for being zum-schwanen.berlin instead of zum-schwanen-wannsee.de, it's cool with me. Sure, the first one to squat the name of your city will be able to skim a profit off .yourcity domains, but they cannot bleed you too white because they need to compete with .com at least for new customers. In practice, though, I suppose the ICANN's suggestions of .brandname and .yournamehere will get more attention. Expect to see .ebay, .google, or .dell sometime soon.

This is really inevitable. It is already the prevailing wisdom in many places that if you're serious about running an internet-enabled business you need to register your name in all top-level domains where you qualify. If www.lego.net, www.lego.biz and www.lego.info all lead to the same site (which they do), then what is the point of having a gTLD there in the first place? The Market has spoken, and according to the Market, businesses do not want to fit into a hierarchical naming scheme if they can help it.

But there is a problem here. I cannot imagine that the Big Red will be satisfied to have a web site at http://www.coke/ – in the brave TLD-less world of tomorrow they'll want to be http://coke/. Fine, you say? Yes, but remember that up until now, http://coke/ has been an instruction to the browser to connect to the machine on the local network named coke, and display what that machine sends back. And, it will continue to mean that irrespective of the creation of a new TLD. If there is no such machine on the local network, you ought to get whatever the TLD resolves to. This may or may not be the case with your browser right now, but in a few years all major operating systems and browsers will be upgraded to understand this.

But what happens when you're on a local network where one machine happens to be called coke? Either you get The Coca-Cola Company or you get your local machine, but which one? That depends on seldom-explored details of your DNS resolver software, but it doesn't matter because neither answer is Right! If you get Coca-Cola, you suddenly can't access your local machine, and if you get the local machine, then you'll be misdirected when you click on a link to http://coke/ on a third-party website.

So it appears that in the future, network administrators must be careful to choose names for their machines that do not collide with any website their users may want to visit. You may think it is easy to avoid calling your machines coke, but any word out there might collide. For example, I name machines on my home network for people in Greek myth; no obvious trademarks there. The file server is called kreon, and I refer to it by this name on the command line dozens of time a day. But what if the fine people at kreon.com (which I did not know existed before I started this entry) decide they want their own TLD? I'll have to choose between renaming my machine or losing access to part of the web. Perhaps an easy choice for me to make, but imagine that you manage IT services at a university department with hundreds of machines... Choose strange names that are unlikely to collide? But how? All of pc42.com, box25.com, abc10.com, and k19.com exist today. These were the first four nonsense letter-digit combinations I tried to look up.

As far as I can see, the only way not to drive every network administrator in the world insane is if ICANN preemptively declares that, sure, you can all have the TLDs you want, but adresses like http://lego/ or foobar@lego must not be used. This can be enforced easily by a rule that one-element domain names must not resolve any A, AAAA, CNAME, or MX records, on penalty of losing control over the TLD.

I'm currently trying to figure out the right procedure for formally making this proposal.

(Thanks to Version 2 for making me aware of this.)

You may be a compiler writer if ...

Some time ago, in a (probably misguided) attempt to adapt at runtime to a bit of endian weirdness, I wrote some code that looked more or less like

   int64_t buffer[2];
   ...
   volatile int64_t *a = (volatile int64_t*)buffer;
   volatile int32_t *b = (volatile int32_t*)buffer;
   *a = 1;
   if( *b == 1 ) doSomeStuff();

There was a bit more to it, but this is representative. This code worked well for quite some time, until we needed to move the program that it is part of to machine with a different processor architecture. When we turned on optimization in the compiler, the program stopped working.

Frantic debugging ensued. Eventually I discovered that the optimizing compiler turns the snippet above into something like this (retouched into hypothetical pseudo assembly such as to protect the innocent):

   add    sp,#24,r13
   mov    #0,r3
   load   0(r13),r5
   mov    #1,r4
   store  r3,4(r13)
   cmp    #1,r5
   store  r4,0(r13)
   bsr.eq doSomeStuff

Now, an ordinary competent programmer should be able to understand that C99's strict aliasing rules authorize a compiler to assume that *a and *b refer to different objects, and therefore the optimizer may reorder the code such that the read of *b happens before *a is written. I admit it surprised me a bit that the volatile qualifiers did not prevent this, which seems to violate the letter of the C standard regarding volatile accesses and sequence points. However, apparently the compiler in question does not recognize any ordering constraints on accesses to "different" volatile-qualified objects within a basic block.

However, notice that even though the compiler is not smart enough to know that the two pointers alias, it is smart enough to figure out that they can share the same register! If you think that is perfectly reasonable and understandable, you're seriously at risk of being a compiler writer at heart.

For the record, I do and I am.

P.S. The Right way to code this is type-pun through an union instead:

   union {
     int64_t a[2];
     int32_t b;
   } buffer;
   ...
   buffer.a[0] = 1;
   if( buffer.b == 1 ) doSomeStuff();

which in this case compiled into an uncoditional call to doSomeStuff. Understanding Strict Aliasing by Mike Acton explains both the rules and the cheats that nevertheless work with admirable clarity. Respectfully recommended for your edification.

My router wants Taiwan

Every so often – actually, every so seldom – my Zyxel Prestige 660R-61 ADSL router will enter the strangest failure mode you can imagine. Everything works except I'm unable to resolve DNS names, giving the immediate impression that the entire internet has disappeared. (I once had a smart, brilliant coworker burst into my office and announce that this was a big moment in the history of the internet: Google had gone down! Turned out that our nameserver had fallen ill, and the web addresses he had used as a control group happened to be cached locally).

No, lacking DNS is not in itself strange. The strange thing is how this lack arises.

See, every time I send a DNS query packet from one of the several computers behind the router, what comes back is a response packet that purports to tell be the IP address of www.kimo.com.tw. Apparently the router is not trying to falsify the address of the host I want to find. I ask about, for example, www.google.com, and back comes a packet saying (translated from RFC-1035 speak): "Thank you for your inquiry about the IP address of www.kimo.com.tw. It is my pleasure to inform you that the IP address of www.kimo.com.tw is 207.69.188.186".

It's always www.kimo.com.tw. It's always 207.69.188.186. It only happens for UDP queries; DNS over TCP is unaffected. It's not the nameserver at my ISP that misbehaves; I get the same pattern when I ask a root server about "com.". I don't know whether the router rewrites my outgoing requests to be about www.kimo.com.tw, or responds with a stock reply on its own, or rewrites incoming answers. I don't know whether it affects UDP packets not to/from port 53.

This has happened two or three times over a period of several years. It seems to tend to follow downtime on the ADSL connection. But whenever it happens, rebooting my local router clears the problem. It's very strange.

Is the router getting infected with some malware? I have a hard time figuring out what said malware could be attempting to achieve. Because the name in the reply does not match that in the request, the resolver on my local computer will just fail instead of return a wrong answer to the application.

After intensive web searching the best I have been able to find is this page in Russian, which judging by Google's translation seems to describe exactly this syndrome. Apparently it is claimed that no malware is involved, but I cannot make sense of the machine-translated explanation of what actually happens.

Fridge logic: 2001, A Space Odyssey

– So basically we have no idea what the damned thing is for?

– Basically no.

– Or why the Chinese went and buried it under umpteen tons of moon rock?

– Well, we don't really have solid evidence that it's Chinese in the first place. It's just the working hypothesis that appeared to be least crazy at the moment.

– Hrmf. What are some of the more crazy working hypotheses?

– Natural geological formation. Aliens from outer space. Something truly evil that the NSA cooked up and have not told the rest of us about.

– Look, I know we're famous for eating little children, but could we please cease the interdepartmental potshots until we're sure the nation's security is not under imminent attack?

– Hey, he asked for crazy theories.

– Yes, and I'm sorry for that. So what I hear is that the Chinese connection is not as solid as we thought?

– Some of our analysts are pretty certain that the Chinese could not possibly have reached the spot with more than two astronauts for 5 hours without our knowing it when they went up in 1998.

– Well, personally I think it is still the least crazy theory, but I concede it is plenty crazy already.

– What about the Russians?

– Don't be silly.

– Okay, gentlemen, we know absolutely nothing. The question is, what do we do about that? We can't realistically delay briefing the President more than until tonight, and whoever goes talk to him has better have some recommendation for concrete action with him.

– Isn't that obvious? Since we don't know anything all we can do is wait until the scientists up there get us some more information.

– How is that "concrete action"?

– One thing we do have to decide is whether to go public with this or not. I'm all for putting a lid on it, but we could get into really nasty stuff if we hush it up now and then –

– I will not accept any public announcement for as long as there's a risk that this is some kind of Chinese superweapon.

– How could an inert featureless slab of whateverite be a weapon? It doesn't even point towards the earth.

– Let me tell you –

– There are rumors that it is making our people sick somehow. Some sort of bioweapon.

– Rumors, which kind of rumors? Unless I've been severely misinformed, nobody on Earth even knows the thing exists except for a few deeply trusted people who all report directly to somebody who's present in this room, and don't know who else knows. So who is spreading rumors to whom?

– Correction. The rumors do not mention this TMA thing, but there are rumors that people in Clavius are falling ill like flies.

– A natural assumption given that the base has been quarantined since yesterday afternoon. It's utterly false, but we've been discreetly encouraging it. There has to be some explanation.

– Great. We'll have the world press poking into this in a matter of hours. Then afterwards we'll have to defend not only withholding information but also lying.

– All in a day's work for you, I'd think.

– Stop that, you two. I'm more concerned about security at the site. There are two thousand people stationed on Clavius, and at least two hundred of them are aliens. The rest are civilians without any security indoctrination to speak of. I'd prefer if we –

– 1700.

– What?

– There are 1700 people in Clavius, not 2000.

– Thank you for that highly relevant correction. Now, is there any way we could get some actual military –

– Look, even if we had the ability to deploy any significant number of troops to the moon on day's notice – which I'll neither confirm nor deny even to this exclusive audience – we'd be running openly afoul of any number of international political commitments if we did. And for what good? Soldiers are not some kind of magical pixie dust that just makes everything right. We'll fight any known enemy that we can see and know how to kill, but I thought we agreed that such an enemy is simply not present on the moon right now.

– What I meant was –

– I say we pull the digging team back to base and then nuke the thing.

– WHAT?!

– I'm not even going to dignify that with a response.

– Gentlemen, please!

– Wait a moment .. I think I've got it!

– Yes?

– Let's just send a senior NASA bureaucrat to the moon and have him look at the thing in person!

– By golly! That'll solve all our problems.

– Good thinking, man.

– Excellent. We have a plan. Heywood, you're going.

– What, me?!

– Yes, you. Judging from past performance, you've contributed absolutely nothing of value so far, and you might as well continue doing that up on the moon.

– But I have to be at a tennis tournament next –

– Our hearts weep. Cancel it. I'll have one of my people put together a powerpoint for you to show to the Old Man, but you'll have to do the talking. I propose Justin go with you and provide moral support. Any other protests? Good. David, can you tell your people to start warming up a rocket or something for Dr. Floyd to go in?

* * *

Seriously, though, why did Heywood Floyd go to the moon? A fair part of 2001: A Space Odyssey is devoted to his journey, which proceeds with considerable haste and at enormous taxpayer expense. But it never becomes clear that there is anything he's uniquely qualified to do once he gets there, save for just being at the center of a Visiting VIP Tour. He does get a glowing but nonspecific introduction before he gives a peptalk on the moon base, though.

In reality his only purpose is to show us, the readers, around. He's a Watson without a Sherlock. Come to think of it, this describes many of Arthur C. Clarke's protagonists.

The origin of spin

When I was in high scool I read Stephen Hawking's A Brief History of Time. It introduced the concept of quantum-mechanical spin rather confusingly:

... a particle of spin 1 is like an arrow: it looks different from different directions. Only if one turns it round a complete revolution (360 degrees) does the particle look the same. A particle of spin 2 is like a double-headed arrow: it look the same if one turns it round half a revolution (180 degrees)... there are particles that do not look the same if one turns them through just one revolution: you have to turn them through two complete revolutions! Such particles are said to have spin ½.

I tried in vain to imagine which kind of geometrical shape would have to be turned around twice in order to look the same. And if such a shape could exist, would it stop here? Are there particles that have to be turned three or four times in order to look the same? Or perhaps two-and-a-half?

I decided that someday I would find a book with actual formulas in it and try if I could understand what was actually going on here. Almost 20 years later, I'm still making progress.

I bought The Feynman Lectures on Physics and worked my way through them. That enabled me to figure out what Hawking tried to say: It is not about how the particle "looks" from different directions, but about how your mathematical description of a particle such as an electron changes whan you express it with respect to coordinate systems that point in different directions. If you turn the coordinate system through 360° (which might be thought of as rotating the electron 360° in the other direction, although I'm not sure that it is helpful to try to imagine rotating a point particle), and make sure that all parts of the mathematical description vary continuously, you end up in with certain numbers in the mathematical model being exactly what they started as, but multiplied by -1. These negations happen to cancel each other out when you use the model to find out how the electron behaves, which is good: The particle ought not to behave any differently because you've walked around it.

So I'd say that the election "looks" the same after a single revolution, but we speak of it in a slightly different way. It's as if it was a glass that started out half full, and after we turn it through 360° it appears to be half empty instead.

So far, so good. But how about the turn-three-times (spin 1/3) or turn-two-and-a-half-times (spin 0.4) varieties I'd hypothesized? More reading had to be done.

Presently I got to the point where mathematical gibberish such as "spin is a two-state quantum property where the amplitudes transform under SU(2)" appear to make sense to me. The two-revolutions rule is because SU(2) is a double cover of SO(3) which is the group of rotations in three-dimensional space. But why does the electron choose to transform under SU(2) – say, could it have picked a different group which is a triple cover of SO(3), leading to a three-revolutions rule instead?

Recently I figured out how to think of this such that it is clear that SU(2) is special. I'm rather pleased about this, because I've had to invent it myself – none of the textbook I've consulted explain it. (It would be ridiculous to pretend that I'm the first to invent it; these is recreational musings, not serious research).

The first thing to note is that even though SO(3) is often described as the groups of rotations in space, this is a bit misleading. It would be better so say that it is the group of instantaneous rotations in space. If you use an element of SO(3) to specify how to rotate a body in space, what you really get is a mapping that tells how to get from the old position of any point in the body to the its new position, but says nothing about how it got there. Yet, in everyday language "rotation" denotes the process of rotating something, rather than the end result. If you take a tangible object such as a book and rotate it, we speak of a process that takes place over time, and during that time the book occupies various intermediate positions, which change smoothly during the roation. Just pointing to the element of SO(3) that describes the book's final state ignores all that.

For example, you can place the book front side up on a table and flip it to the back side either turning it around the left edge or around the right edge. The book ends up in precisely the same position, yet the two ways of flipping are quantitatively different. You can't construct a continuously varying family of ways-to-flip which contains right-flipping as well as left-flipping and all end up in the same orientation. Try it! What should come right in the middle between left and right? We could turn the book around the bottom edge, towards ourselves, but then the flipped book ends up upside down, and we have to decide whether to turn it clockwise or counterclockwise in order to reach the specified ending position.

The idea of a continuously varying family of continuous rotation processes turns out (ha!) to be key. Let's try to make this a bit more formal and general. Warning: higher mathematics up ahead!

Start with a topological group G, i.e., a group which is also a topological space and where the law of composition is continuous. The main example to think of is G=SO(3), but most of what we'll do does not depend on the deep inner structure of SO(3) in particular.

Define an auxiliary group A whose elements are continuous maps a:[0,1]→G such that a(0)=1_G. The law of composition on A is pointwise multiplication in G, that is, (a₁*a₂)(t)=a₁(t)*a₂(t). Clearly, A is a group. When G=SO(3), an element of A represents a particular continous rotation process. The composition in A is algebraically easy but has no intuitive geometrical interpretation.

An element of A contains more information than we're really interested in, so let's quotient out the differences between elements with the final state that are members of the same continuously varying family:

Let T consist of all elements a of A for which there exists a continuous map α:[0,1]×[0,1]→G such that α(t,0)=a(t) and α(0,u)=α(t,1)=α(1,u)=1_G for all t and u. It is easy to see that T is a normal subgroup of A.

The goal of all this is to define the quotient group A/T, which I choose to call G_spun. One may now prove the following:

• G_spun is simply connected.
• There is a continuous homomorphism from G_spun to G, since T lies in the kernel of the "end-state" homomorphism from A to G which maps a to a(1). (The kernel of G_spun→G is the "fundamental group" for the topological structure of G).
• For a∈A, choose any continuous f: [0,1]→[0,1] such that f(0)=0 and f(1)=1. Then a and a◦f represent the same element of G_spun.
• For any a, b∈A, define (a;b)(t) to be b(2t) for t≤1/2 and a(2t-1)*b(1) for t≥1/2. Then a*b and a;b represent the same element of G_spun.

Thus in G_spun the group operation does have a geometrical interpretation: it corresponds to the process of first doing one continuous rotation and then another one.

Now back to physics, fixing G=SO(3). Imagine that we have a mathematical model of some physical system and a recipe that says how to change the model when we rotate the system in a gradual, physically plausible, continuous way. Such a rotation corresponds to an element of A, so the recipe really maps A into the space of changes to the model. Now we may want to consider only recipes that do not distinguish between rotation processes that can be varied continuously into each other. If so, the recipe must be a homomorphism from G_spun to the space of changes to the model.

And for G=SO(3), it turns out by pure accident that G_spun is isomorphic to SU(2)!

The books I've read tend to start by pulling SU(2) out of a hat, and then deriving that it accidentally corresponds to certain rotations. How lucky that the group the electron chose to represent happens to have a geometrical representation! I find it much more compelling to think oppositely: The electron chose the most general way of responding to rotations it could, and that turned out, accidentally, to have a simple interpretation in terms of complex numbers.

Memetracing: Doctorow on a Balloon

What is it with Cory Doctorow and hot-air balloons? Humorous references appear to be popping up in the strangest places – last in Bruce Schneier and the King of the Crabs (which I discovered through Schneier's own blog).

But just what do these references actually reference? I find them mildly funny because they evoke memories of the Xkcd episode "Blogofaire", as well as the small print in "Online Communities".

On the other hand, I don't get out much. For all I know, Doctorow might be famous for being an avid balloon pilot in addition to a writer, and that's what everybody are alluding to. On the other-other hand, I cannot seem to google up any non-humorous Doctorow/balloon juxtapositions.

So perhaps it is all an in-joke referencing the xkcd strips, or perhaps xkcd was itself referencing some ur-joke known to only a few initiates (or, alternatively, to everybody but me). Impossible to know, really – when an Internet meme reaches a certain critical mass, half of those who pass it on have no idea what it refers to, anyway. Close to nobody ever played Zero Wing, but that does not prevent the all your X are belong to us snowclone from being productive.

Unix domain socket woes

At work we needed to create a "doorkeeper" process that accepts incoming network connections and then hands over the connected sockets to one of several, already running, service processes. The service process then talks directly to the client through the network layer. I can't go into detail about why that happens to be the right design for us, so just stipulate that it is what we want.

I was assigned the task of researching how to do the socket handover and write code to implement it. Solutions had to be found for Windows, Linux, and Mac OS X. Possibly later other BSD variants too.

On Windows things turned out to be fairly easy. There's a dedicated system call, WSADuplicateSocket(), for exactly this scenario. This syscall fills in an opaque structure in the doorkeeper process, whose binary content you then transmit to the service process (say, through pipes that you set up when the service process was started). In the service process another system recreates a copy of the socket for you, and then you're free to close the doorkeeper's socket handle.

Things were not quite as straightforward on the Unix side. (At least it works the same way on Linux and Darwin, modulo a few ifdefs). The way to move an open file descriptor between existing processes is to send it as out-of-band data (aka an "ancillary message") the the SCM_RIGHTS tag on a Unix domain socket (aka an AF_UNIX/PF_UNIX socket). The kernel knows that SCM_RIGHTS is magic and processes its payload of file descriptors such that the receiving process receives descriptors that are valid in its own context, in effect an inter-process dup(2).

Or at least, this was the only way to do it that a few hours of googling disclosed to me. It works, but ... ho boy, Unix domain sockets! In my 20+ years of programming, many of them with a distinctly Unix focus, I've never before encountered a situation where AF_UNIX is preferred solution. This turns out to be not entirely without cause.

Firstly, Unix domain sockets are sockets, which means that you have to go through all the motions of the client/server-based sockets paradigm we know and love from the TCP/IP world. First the two processes must somehow agree on a rendezvous address. Then one of the processes creates a socket, binds it to your chosen address, calls listen() and accept() on it, then gets a second socket on which the actual SCM_RIGHTS transaction can take place, and finally closes both of its sockets. Meanwhile the other process goes through a socket()–connect()–communicate–close() routine of its own. Many of these calls are potentially blocking, so if you're doing non-blocking I/O and want to schedule unrelated work packets in your thread while all this goes on (which we happen to do), the entire transaction needs to be broken into a fair number of select()-triggered work packets. Not that any of this is difficult to code as such, but it is still about the most complex-to-set-up way of doing IPC Unix offers.

Secondly, Unix domain sockets are also files, or more accurately, they are file-system objects. A listening socket has a name and a directory entry (otherwise it cannot be connected to) and a inode. The inode and directory entry are created automatically by the bind() call. This means, among other things, that you have to create your socket in a particular directory, and it has better be one where you have write permission. All of the standard security considerations about temporary files kick in – if you create your socket in /tmp, somebody might conceivably move it out of the way and substitute his own socket before the client process tries to connect, and so forth.

Further, cleaning up after the transaction becomes an issue. The inode for the listening socket will disappear by itself once nobody is using it, as is the nature of inodes. However, the directory entry counts as using the inode, and it does not go away by itself. You need to explicitly unlink(2) it in addition to closing the socket. If you forget to unlink it, it will stick around in the directory, taking up space but being utterly useless because nobody is listening to it and nobody can ever start listening to it except by unlinking it and creating a new one in its place with bind(). In particular, bind() will fail if you try to bind to an existing but unused AF_UNIX socket inode.

What happens if the server process dies while it listens for the client to connect? The kernel will close the listening socket, but that will not make the directory entry go away. You can register an atexit() handler to do it, but atexit() handlers are ignored if the process dies abnormally (e.g. if it receives a fatal signal). There is essentially no way to make sure that things are properly cleaned up after.

This is a major downside of Unix domain sockets. It is very probably impossible to change, because of the fundamental design choice of the Unix file system model that you can't get from an inode to whatever name(s) in the file system that refer to it. Not even the kernel can. But, good reason or not, it means that you either have to accept the risk of leaking uncollected garbage in the file system, or try to used the same pathname for each transaction, unlinking it if it already exists. Unfortunately the latter option conflicts with wanting to run several transfers (or several instances of the doorkeeper process) in parallel.

Access control for the Unix domain socket transaction is another issue. In theory, the permission bits on the inode control who can connect to the listening socket, which would be somewhat more useful if you could set them using fchmod(2) on the socket. But at least on Linux you can't do that. Probably you can use chmod(2) after bind() but before listen(), but you'd need to be sure that no bad guy has any window to change the meaning of the pathname before you chmod it. This sounds a bit too tricky for my taste, so I ended up just checking the EUID of the client process after the connection has been accept()ed. For your reference, the way to do this is getsockopt() with SO_PEERCRED for Linux, and the getpeereid() function for BSDs. The latter uses a socket option of its own internally, but getpeereid() appears to be more portable. Note that on Linux you have the option to check the actual process ID of your conversation partner; BSD only gives you its user and group IDs.

I'm as critical as the next guy about stuff that comes from the Dark Tower of Redmond, but in this particular case the two-click approach that works on Win32 does appear to be significantly less complex than the Unix solution.

---

(New comments disabled on 2013-06-11 due to persistent comment spam)

Proprosing a constitutional reform

Thursday was Constitution Day in Denmark. I went to a celebratory get-together organized by the party's Hvidovre branch, and spent some quality time sitting on a lawn in the sun, eating brunch and listening to live jazz. Very nice.

The main (and only) speaker was our local MP Morten Helveg Petersen, who for about a decade now has been calling for a rewrite of the constitution. Not, if I understand him correctly, because that there is anything directly wrong with our current one, but more because its language and organization is antiquated. It is hard to understand in general for people who don't know what it means already – it defines our form of government as being "limited monarchial" and says "the King" whenever it means "the government". Its enumeration of human rights and political liberties is rather sketchy compared to what our neighbouring countries have. It creates no end of trouble each time the EU wants a broader jurisdiction. And so forth.

Isn't that all exciting? I guess not, and therein lies a problem. I have nothing against most of the revisions Morten wants to make, but – I'm very sorry – it is hard for me to see why to bother. Apparently the plan is that the revised constitution should say to do things exactly how we do them already, only expressing that more clearly and thoroughly. This does not appear to me as a promising approach to constitutional reform. The optimistic take on this would be that if even our most vocal proponents of reform don't go beyond merely editorial changes, we as a country must be doing pretty well. Which we probably are, but who says we cannot do better yet?

So let us stir things up a bit. I propose that we reintroduce a bicameral legislature!

(For those following along outside Denmark, the original democratic constitution of 1849 create a legislature consisting of an upper house, the Landsting, whose election rules favored landowning and conservative interests, and a lower house, the Folketing, with a closer approximation to universal suffrage. The precise rules changed several times over the years, and after the 1936 elections the relative strengths of the parties were the same in both houses. This made the Landsting increasingly irrelevant, and it was abolished in the 1953 Constitution which is still in force. Today the Folketing alone makes up an unicameral legislature).

There are three main points in my proposal:

1. The Folketing becomes the upper house of a bicameral parliament. It is supplemented by a new Lower House, name to be decided. (Put suggestions in the comments, please!)
2. Members of the LH are not elected, but selected by lot among citizens who have registered as willing to serve. Seats are refilled on a rolling basis, such that new members are continuously entering the LH.
3. Bills are heard and voted on first in the Folketing and then in the LH. Add the percentage of ayes in the Folketing to the percentage of ayes in the LH. If the sum exceeds 100%, the bill becomes law.

The idea of selecting members by lot goes back to the democracies of ancient Greece. Classical Athens had a 500-seat executive assembly called the boule, selected by lot among the citizenry. Lots were also drawn to fill most public offices; only a small number of individual offices were filled by election. I don't know any modern democracies that have taken up this idea for its formal legislative process. But actually we're not that far from it; many politicians act with great deference to the results of random opinion polls. One way to think of my Lower House is as a standing opinion poll and "focus group" for the Folketing. Its opinions will be at least somewhat more informed than those emerging from a point-blank phone poll, because the members are full-time legislators and have some time to read and consider each bill before voting on it.

In most existing bicameral legislatures, a bill has to pass in each house individually. My "add the percentages" method is what I think is really innovative in my proposal. Here is how it works:

Because members of the LH have no hope of re-election, they cannot be held to any partisan or ideological allegiances. They are unlikely to depart from their own honest opinion just becuase it might not be popular in the electorate at large. They don't have to keep friends with anybody in the LH after their term expires. They will have few tools for enforcing parliamentary deals among themselves, and are thus unlikely to make such deals in the first place. In short, the LH will be an extremely unruly and unpredictable lot.

And this is a good thing? Yes it is, because the Folketing votes first on every bill. At that time, it is impossible to be sure how much support it will have in the LH, and therefore ministers who want their bills to pass will have an interest in securing as large as possible a majority in the Folketing as possible. It is said jokingly that politics in our current system is all about "being able to count to 90", that being the size of a majority bloc in the 179-seat Folketing. A minister who makes a concession to an opposition party in order to get 100 votes for his bill rather than 90 is a fool; he does not need more than 90 votes. With an unruly LH in the equation, a minister doing this gets a real advantage, namely that his bill is less likely to be killed in the LH.

Thus the net effect of the LH will be a much greater incentive for the government to seek broad compromises among the Folketing's parties, which I count as a definite win for our democracy.

It gets better yet. The "professional" politicians in the Folketing will have a direct interest in having the LH members vote for their bills (or against bills they would like to fail). They will want to convince a certain number of LH members that this is a good (or bad) bill. The "amateur" members of the LH have little reason to be impressed with appeals to tactics or political tit-for-tat (you might promise me to vote for something else I want next month, but how do I collect on that promise if you don't keep it and my term expires shortly after?) or technocratic gobbledygook. The professionals will need to produce and present actual convincing and intelligible arguments about the merits of each bill. Certainly it will not be possible just to look the other way, cross one's fingers and hope that people will have forgotten this come next election.

As a bonus, the list of participants in the Lower House seat lottery can also be used to draw pools of lay judges and jurors for the criminal justice system. The current procedure for this is ill-defined and highly biased towards members of organized parties. That could definitely use a makeover, too.