NP

In the Communications of the ACM, David Lindley “defined an NP problem as one for which no polynomial-time solution is known”. Scott Aaronson, please call your office (two minutes into the podcast).

Historical systematics

As Sigit’s cadre of systematic historians travel through branching time, they practice the art of curating library furniture. Thankfully, there is usually free surplus to acquire. To a systematic historian, every study carrel and reshelving cart, covered in residual fiberdust, announces its heritage in a loud, regulated voice: Was it made before or after the Geneva Convention? Did colonialism or socialism come first? Rocket launch or space elevator?

For the purpose of recovering phylogeny, the most useful features are the least consequential and least correlated: “junk events” such as the conclusion of wars, the exchange of promises, and the migration of bodies. That’s the real reason why systematic historians love diasporas. Like a junk gene, a junk event is copied and mutated by chance without much affecting the branching rate of a history, but like a borrowed word or a healed wound, it indelibly dents the design space of artifacts that a civilization will consider and consume in its future. Mostly, people prefer their artifacts to remind them of the past either head-on or not at all. To be sure, a junk event may well hurt or please many people, and in that sense they are consequential, but what we’re talking about is the fitness of a possibility, not of a person. The ideal junk event is one that “commutes” with all other events—one that does not affect their availability.

In neighborhoods of history where the study of systematics flourishes, the value of junk events is more widely recognized, which makes them unusable. Thus, systematic historians validate an ironic sort of uncertainty principle: they know the least about their own home, the surrounding possibilities closest to them. That’s what makes Sigit’s group so precious, its mere existence.

Frankfurt sculpture 法蘭克福雕塑

這是什麼雕像、誰的雕像？西元 2005 年 6 月見於法蘭克福總站屋頂。

What is this sculpture; who are this sculpture? Seen in June 2005 above Frankfurt main station.

With love

(Translated to English from zonble’s promptbook in Mandarin. Those readers with a background in Asia will recognize the story as an Asian take on Star Wars as well as a Star Wars take on Asia.)

Dear Lukie:

It’s time to let you know.

Son, I’m not sure if you recall—in your teenage rebellion several years ago, before you mastered the Force, you kids blew up the Empire’s most important military facility at that time.

You probably still remember the thrill of conquest as your young self swiftly destroyed the giant enemy core. As if a classmate never paid you any attention, then one day you scored with her—eventually a forgettable experience, but not for a while. Your father was young once, and knows the need for bragging rights among buddies.

You might have wondered. As a Force wannabe who could only receive calls from other Jedi Knights—calls that perhaps you mistook as gut feelings stirred by the Force—how could you have blown up the Death Star with Molotov cocktails and a bunch of X-Wing fighters, or “X-Wees” as they were universally disparaged? How could a military facility that was indestructible by all accounts have crumbled in your hands? But when you dived into the heart of the Death Star in your X-Wee, you might have been surprised, behind the pretty facade—that is what Father wants to tell you about.

The Death Star would have been blown up, sooner or later. More precisely, it had to be blown up.

The day after you kids blew up the Death Star, the Emperor was to send a henchman to certify its construction before acceptance.

As you know, since its dawn, the Empire had been pouring in tremendous resources seized from the galactic population into the Death Star’s construction. Of course, this crucial military project was top secret in the Empire, from the design blueprints to the firepower statistics. Naturally, the Imperial budget of the Death Star was the top secret of top secrets.

As for how much of that budget was actually spent on construction, it was the top secret of top secrets of top secrets.

Few were privy to this secret. First, the Imperial commander in charge of the construction. Second, the building contractors—though they were all killed shortly before construction came to a close, they and their planet turned into milky, starry dust by the Death Star’s very first shot (exhausting the facility’s firepower, as it were). The commander in charge presented it to the Emperor as secrecy maintenance. It was true: the mere existence of the contractors threatened a leak. The Emperor thus sentenced the whole planet to some made-up crime, as was Imperial business as usual—naturally, the secret that was maintained was not the secret the Emperor had in mind.

When the Death Star blew up, the only witnesses on it were those blindly loyal clones, completely out to lunch (look, even robots fall in love, but have you seen clones fall in love?), who also all died. Who could doubt the truth? After the destruction, the Empire allowed no doubts, and any doubts would have found no corroboration. After all, the Death Star was a military facility, and all military facilities are subject to attrition.

Still, others knew, and they were the dearest to you. Your sister Leia knew. You might now realize why, as you kids wandered from system to system in the last several years, wherever and whenever the Millennium Falcon docked, Leia always told you first to visit the local financial institution for an account.

There was also your Uncle Obi-Wan. I’m really sorry what I did to this old friend, but I had no choice. Sigh!

Speaking of Leia, I shouldn’t have relied on her. When I gave her the designs of the Death Star, I told her especially to stay on the down low, to enlist you only, but she was still so unsure of herself as to ask Obi-Wan for help, and so inept at hiding her plot that my cunning old friend saw right through her. I tried so hard to call her back, oh did I try. Damn that Obi-Wan—think of it, twenty years! After twenty years out of touch, the first thing this old friend contacts me for at this crucial juncture was to blackmail me for hush money!

Despicable Obi-Wan! It was him who created this gulf of misunderstanding between you and me, father and son. Did he tell you that your father had perished under Darth Vader’s lightsaber? He made you think you had no father, made it unthinkable who your father really was. That’s why you thought my guys looking for you were the Empire hunting you down. The true reason, besides the money under your name, that Father looked for you, after twenty years of humiliation, after calling you with the Force to finish off the biggest money-laundering scheme of the Galaxy, was of course to enjoy the loot with a loving family, in another galaxy, unfettered.

It turns out, Obi-Wan had it all planned. I took care of him, but he passed the news and you to that greedy old fart Yoda! Did Yoda then lure you with his magic while pretending to shoo you away? Did he then tell you that you were not skilled enough with the Force to leave him? —When will you be skilled enough for him? When he gets your account information, of course!

Your sister, on the other hand, went from inept to dishonest. I don’t know if she fell under that wicked Yoda’s magic too, but after the Emperor stopped investigating the done deal, she tried to leave Father behind. Does she think she can outwit Yoda the old fox? Do you think they are just old fencing fogies spewing nonsense about the Force? Do I have to remind you of the Jedi Council of the Republic, of how much Yoda and Obi-Wan embezzled from classified clone-army accounts?

Son, were you also influenced by them to think that the Republic was progressive, glorious, wonderful? For them, of course it was—I couldn’t believe it when the Emperor first told me—they each took a cut! As I kept trying to teach you, to convey to you, don’t let them fool you with the Force. Yes, the Force is good to have, but could it protect your right hand? No, just as it could not protect my body back then. But with enough dataries (or other currency; dataries are not worth much these days), you can buy a new right hand. Do you really think the Jedi Knights kept the Galaxy running during the Republic with just that measly Force?

But you were young; you didn’t listen to me. Oh well; I was never good with words. Though I did tell you: You don’t know the power of the dark side.

Father is not telling you all this to reminisce, but to help you deal with some new developments in the Dynasty.

First, the Emperor recently ordered a second Death Star built. He hand-picked the contractors and sent a separate team of inspectors on-site. The Emperor believes in two things: the Death-Star technology he got in the Clone Wars, and that practice is the only criterion of truth. Once a second Death Star is finished, any difference between it and the one you blew up would call into question the construction of the first Death Star, and thus Father’s fate.

Second, the Emperor just sent his Royal Guards after you, so watch out: the Imperial soldiers you are about to encounter are not my guys looking for you, even though you might mistake both as the Empire going after you as the chosen Rebel leader.

The real reason the Emperor wants you is that you are an eyewitness. Everyone perished with the Death Star, except Father, on whom the Emperor’s shock-and-awe mind-control techniques are ineffective, but I don’t know about you. If the Emperor were to pry his purple lightning into your visual memory for a full-scan query that reenacts the workmanship of the Death Star, then Father would be in real trouble. In the worst case, Father might have to fight the Emperor to death. Even a Jedi Knight at my level faces the Emperor with uncertainty—the thought, as I enjoy a majestic view of stars large and small from this observation deck, brings a chill to my spine.

Son, it is through this window that I followed your life journey from afar over the years. Even your mother would be pleased, I think. But it is also through this window that I see in you more and more of myself.

And of the Emperor.

I have no idea how you’ll turn out.

The Emperor and I were both poor kids from the countryside. Our childhoods were miserable—of course, the Siths were probably more miserable in those days. I bet neither Obi-Wan nor Yoda told you that Sith and sex are cognates. The Siths had to bribe Jedi Knights for sex, and the Jedi Council derided the Siths as evil, only because the Siths thought all day long about sex in that environment. That’s why, when the Emperor couldn’t get any in those days, he resolved to become a power monger and eliminate corruption. He believed that totalitarianism was the least corrupt form of government.

He really went overboard, and I can understand why you kids turned anti-establishment. Where did the Emperor get the idea for his Edict on Sex? Maybe fidelity is worth legislating, but a minimum of five times a day? What got it into his head that this kind of sex would earn him loyalty and admiration from his subjects? Strangely enough, it did win some people over. I have no clue why.

It was this jealousy, this hate, that led the Emperor to me, a young Knight unvested in the status quo, shunned by the old boy’s club of corrupt Jedis. He got what he wanted from me—my aversion to Jedi nepotism, my help, almost my sex. After I sent y’all off, my lightsaber sliced through the other Jedi Knights like butter, even though I got my training on the grounds of the Jedi Academy and my milk through the nipples of the Jedi Council. If anything, it was that training, that milk, that made me hate all the world’s injustice, all the guys’ corruption, and what’s more—why couldn’t I get in?

I was yellow with greed. I was greedier than them all!

I wanted numbers that Obi-Wan and Yoda couldn’t imagine for their lives!

You grew up the same way, in the wastelands of Tatooine. Blame Father if you want, but how could I appear to be weak when you were still in the cradle? I know you don’t always love your uncle and aunt either. They knew Father was a Jedi Knight. They thought I was keeping enormous corruption proceeds all to myself, sharing nothing with my family but the burden of raising my son, so it was understandable that they disavowed me as their older brother. In reality, I had no proceeds to keep to myself, much less to share. On the other hand, don’t blame them now that I’ve made it. If they were still around, well, neither a borrower nor a lender be, and we’re not really brothers anyway.

Poor kid, we all used to be poor, but what now? It’s up to you.

Do you want to be rich? Or dead?

At the beginning, Leia let you join the Rebels just to finish laundering the Death Star money, not to lead a bunch of poor kids hoping to strike it rich in a role-playing game. I don’t know what Yoda and Leia have been giving you to smoke, that you think a circus can overthrow an empire, but they’ve kept you completely in the dark. They start these fights only to keep you around and get rid of me on the side, because I am the only one left who knows about this dirty money and where it came from in the Universe.

Yoda hasn’t bothered me directly, actually. I guess Obi-Wan’s fate showed him.

If you keep fighting against the Empire and, the Force forbid, fall into the hands of the Emperor, then even setting your life aside, you should keep in mind the hordes of cash in your four billion accounts throughout the Galaxy (as for which accounts, you need to check your own books), and in six billion accounts under Leia’s name. What’s more likely is if, as you lead the Rebels, they get to your accounts. Neither you nor I know what would happen then—revolts always come with casualties, don’t they?

Another possibility, son, is that you are a true Skywalker, not ruined by Jedi Knights as a child like your tragic father was—though I don’t know how they affected you more recently. Then you would hate corruption to your bones, especially when you find out that Tatooine was dirt poor precisely because the Death Star broke people’s backs with taxes, taxes that fell into the pockets of people like your father—strictly speaking, pockets of you currently, though you’re not yet sure which pockets.

By the way, you might all despise the Emperor for your poverty, but he’s actually quite thrifty in private, wearing nothing but a threadbare robe. You may not know that the Emperor’s frugality branding helped with his coup to some extent.

Anyway, your jealousy and ability may steer you in the footsteps of the Emperor. You might just overcome the grim dangers around you one day and even overthrow the Empire with your Force and charisma. You might just clear away, as the morning sun clears away a pea-soup fog, the world of us old people—of course, the chance is minuscule—and be chosen to lead the Galaxy.

Then what?

What new order do you want to bring to the Galaxy? Do you want to return to a republic? Or establish a second empire?

Republic or empire, the name of the game is corruption; the Galaxy will not change its course just for you. The only issue is whether you want corruption to occur among the select few, or among the select fewer; whether you want tacit corruption practiced by a privileged class, or invisible corruption practiced under everyone’s nose; whether you want people like Obi-Wan and Yoda to be corrupt under your rule, or people like your father to be corrupt. All heroes become corrupt, or rather, all heroes become heroes in order to descend finally into corruption.

In the Republic, some people were happy and some people were unhappy; Obi-Wan and Yoda were happy, whereas people like the Emperor and me were unhappy. Same thing with the Empire: some people are happy and some unhappy. If the Empire were overthrown, you kids might be happy, but another group would be unhappy, just like when the coup replaced the Republic by the Empire, making some people unhappy but others happy. It’s always the same, some happy and some unhappy. The only possible difference is—is it others who are happy, or is it you, but do you really know what makes you happy? You might think now that a republic would make you happy, but that’s just because you have not experienced a republic. I have. Republic or empire, I’m not happy.

—Do people really know what makes them happy? Sometimes people are happy because others are happy, or unhappy because others are unhappy. But sometimes people are unhappy because others are happy, or happy because others are unhappy.

There’s another way. We can evade our pursuers and head to another galaxy to create an unprecedented society, a truly pure galaxy. On every star—green stars, red stars, black stars, gold stars, stars of all colors and stripes, we will be a united galaxy of Skywalker clones. Son, if you wish, they can all be Luke Skywalker clones. Yes, we can. We’ve got the dough.

Please contact me ASAP. The situation is tight. Stay away from the Emperor. Beware your friends. Beware those you think are mentors. Beware those you think are family.

I know it’s not like you ever believed I was your father, but I must still remind you, when push comes to shove, don’t even trust me. But I hope you trust me a bit right now. After your mother passed away, everything I did was for you and Leia. It is also at great peril that I send this letter to you, even authenticating it with my red lightsaber—but I actually don’t think I can trust Leia nowadays.

To close, I must still bless you as usual, however ridiculous the blessing sounds coming out of my mouth. It’s looking more and more as if I doubted the Force. —Until now, all species in the Galaxy believed that I command a mighty Force, to the point where even I thought so, and it was indeed handy for a while. However, after losing one confidant after another, I don’t even find the Force trustworthy anymore.

What I mean is this. In the past, even though I doubted the Force had two sides, I did grant that each individual’s Force is limited. What matters is how the Force admits the individual to something bigger, even if the real point is that something bigger. But what I now doubt is, does the Force even deserve its name? Even if you’ve got the Force, and even if you’ve got that something bigger, yet…

I’m at a loss for words.

Recently I’ve been thinking a lot about something Yoda used to say—never mind how nasty he is with money—he retold an ancient prophecy, that someone will bring balance between the light side and the dark side of the Force, namely me. I’ve always thought the old man was talking rubbish, simply because nobody actually knew what balance means for the Force, or how to achieve it, I bet not even Yoda himself.

I actually barely remembered what Yoda said, but now that I’m reminded, I want to forget again. In the time since I used the Force to call you to blow up the Death Star, facing this observation window, I seem to have figured out, bit by bit, what it means to restore balance to the Force. I’m not sure—but maybe to restore balance is to eliminate the Force from the Galaxy. Of course, as we both know, that is impossible. We both have been immersed in the Force, inflamed by the Force, imbued with the Force senseless. We both know that the Force is there, will always be there.

The next best thing may be for the whole Galaxy to forget the Force. Well, with an Imperial officer like me and a Rebel leader like you, the Galaxy can hardly forget Jedi Knights or the Force. Moving on to the third best thing, we can make a wish in lieu of reality. People like Yoda and Obi-Wan cannot be the Chosen One, then, not because they fence badly or their strength is impure or their conduct is immoral, but because they’ve never had the wish, they don’t want to forget the Force, they even pose as tutors of the Force. Perhaps the true meaning of the prophecy, I’m thinking, is that I will be the first Jedi Knight to want to forget the Force, the first time a Jedi Knight has carried such a wish in the epic yet elusive pages of history—though this interpretation is still incredible.

I really want to forget. I want to forget the Force.

It probably won’t affect the Galaxy, but I have such a wish. To forget the Force.

I want no Force but to bless you. The phrase dooms me to ridicule as I said, snaring me firmly in an awkward loss for words. Oh Galaxy, how I curse you! I can attack you, damage you, ignite you, trample you, but in the end I am at a loss for words to you. Oh son, I departed you then pursued you, abandoned you yet recollected you, but in the end I am at a loss for words to you.

Sigh!

May the Force be with you,

Father

P.S. I looked into the company you’ve been keeping, which worries me.

I think you should stay out of Han Solo and Chewbacca’s relationship. They got the Millennium Falcon in the first place to elope from their legally assigned partners under the Edict on Sex. I know what you’re thinking; young Skywalkers tend to be fascinated with exotic furry creatures. When I was a kid, I was quite taken by a certain long-eared species. They were naturals at viscous fluids and balloons. But son, I don’t want you to be disappointed when the time comes. Really, muscular does not mean big. Besides, you don’t want to attract the vigilance of hidden enemies around you.

If you really need to, ask R2D2. D2 used to be with me, and I’ll tell you this: when it comes to Skywalkers, it’s still the vacuum cleaners that know our bodies best. If you wipe off the video Leia taped, you’ll find other holograms from when I was a kid. Maybe it’s too old-fashioned for you, but you can try and splice Chewbacca in too. If you need anything else, C3PO is also good.

In any case, great works call for great caution. If you still can’t control yourself, just cut it off. You know lightsabers; it won’t hurt long. Put it in a box and hang it on your chest for daily motivation. Once it’s all over, you can always pay to have a new one made.

The pointed-set monad

Chatting with Andres Löh, I wondered: Is the following pointed-set monad useful, besides for analyzing focus in natural language (Rooth 1985, 1996)?

data Pointed a = Pointed a [a]
  deriving (Eq, Ord, Show, Read)

toList (Pointed x xs) = x:xs

instance Monad Pointed where
  return x = Pointed x []
  Pointed x xs >>= k = Pointed y (ys ++ (xs >>= toList.k))
    where Pointed y ys = k x

Here is an example of use:

*Main> Pointed 3 [4] >>= \x -> Pointed x [x*10,x*20]
Pointed 3 [30,60,4,40,80]

Ok, I know, I should put it on Hackage. Is there a corresponding monad transformer?

---

Rooth, Mats. 1985. Association with focus. Ph.D. thesis, Department of Linguistics, University of Massachusetts.

Rooth, Mats. 1996. Focus. In The handbook of contemporary semantic theory, ed. Shalom Lappin, 271–297. Oxford: Blackwell.

Metalinguistics

This is something I should have done ages ago, I know, but what isn’t? I finally got around to reading some classic papers about what names and variables mean in opaque contexts (such as quotation and belief):

• Quine, Willard Van Orman. 1956. Quantifiers and propositional attitudes. Journal of Philosophy 53(5):177–187.

• Kaplan, David. 1968. Quantifying in. Synthese 19(1–2).

• Kaplan, David. 1989. Demonstratives: An essay on the semantics, logic, metaphysics, and epistemology of demonstratives and other indexicals. In Themes from Kaplan, ed. Joseph Almog, John Perry, and Howard Wettstein, chap. 17, 481–563. New York: Oxford University Press.

It’s a shame that people working on embedding of natural languages and embedding of programming languages don’t talk more to each other. (It doesn’t help that these great reads are not terribly easy to access online—email me for a copy.) If you care about topics like multilanguage interoperability, denotational/extensional vs operational/intensional semantics, values and constant expressions that evaluate to them(selves), polymorphic lift, and cross-stage persistence, then these papers are definitely worth your time. (And vice versa: philosophy of language can benefit from computational thinking too; I name two equally classic papers below.)

For example, Kaplan (1989:497) distinguishes literal expressions (directly referential terms such as (quote 3) in Scheme) from other expressions that evaluates to the same value in all circumstances (definite descriptions such as (if (snow-is-slight) (sqrt 9) (- (* 2 2) 1))):

The propositional component need not choose its designatum from those offered by a passing circumstance; it has already secured its designatum before the encounter with the circumstance.

He goes on to note that this distinction tends to be exposed by syntax but masked by semantics (or in finally tagless terms, exposed when the representation of terms is polymorphic in their interpreters):

When we think in terms of possible world semantics this fundamental distinction becomes subliminal. This is because the style of the semantical rules obscures the distinction and makes it appear that directly referential terms differ from ordinary definite descriptions only in that the propositional component in the former case must be a constant function of circumstances. In actual fact, the referent, in a circumstance, of a directly referential term is simply independent of the circumstance and is no more a function (constant or otherwise) of circumstance, than my action is a function of your desires when I decide to do it whether you like it or not. The distinction that is obscured by the style of possible world semantics is dramatized by the structured propositions picture. That is part of the reason why I like it.

Quine and Kaplan both worry about what goes wrong when you can’t find an expression that evaluates to a given value, or when the only expression you find is an unspeakable mental structure, or when you find two expressions that evaluate to the same value but they are not observationally equivalent. (The same worries concern André Aciman, by the way. The evening rain in Århus reminds me of the Taipei where I presumably used to imagine I lived. But I digress.)

If you think philosophy is dry to read, well, these papers serve up counterexamples on page after page. Quine (1956:179) writes of lion-hunting, presidential candidates, and spy intrigue:

There is a certain man in a brown hat whom Ralph has glimpsed several times under questionable circumstances on which we need not enter here; suffice it to say that Ralph suspects he is a spy. Also there is a gray-haired man, vaguely known to Ralph as rather a pillar of the community, whom Ralph is not aware of having seen except once at the beach. Now Ralph does not know it, but the men are one and the same. Can we say of this man that Ralph believes him to be a spy?

Responding, Kaplan (1968) suggests “taking advantage of Ralph’s belief that all members of the C.P.U.S.A. are spies”, then discusses spy pictures:

Let me recite just a few of the familiar facts of portraiture. First, not all pictures of a person resemble that person. Of two recent pictures taken of me, one resembles Steve Allen and the other resembles nothing on earth. Secondly, not all pictures which resemble a person are of that person. It is obvious that a picture of one twin will, if it resembles the twin it is of, also resemble the other twin. … Of course, if photographs did not frequently, indeed usually, resemble their subjects, they could not serve many of the purposes for which we use them. Still, on occasion, things can and do go awry, and a bad photograph of one is yet a photograph of one.

… A police artist’s reconstruction of Santa Claus, based on a careful reading of the poem The Night Before Christmas, is not a picture of anyone no matter how many people make themselves up so that it exactly resembles them, and no matter whether the artist regards the poem as fact or fiction. …

In addition to the link with reality provided by the relation of resemblance the descriptive content of a picture determines its vividness. A faded picture showing the back of a man wearing a cloak and lurking in shadow will lack vividness. A clear picture, head on, full length, life size, showing fingerprints, etc. would be counted highly vivid. What is counted as vivid may to some extent depend on special interests. To the clothier, nude portraits may be lacking in detail, while to the foot fetishist a picture showing only the left big toe may leap from the canvas.

I wish I could write like that. I wish I could overcome the habits of terseness and Anglo-Saxon monosyllabary that page limits on conference papers and grant proposals have long instilled in me. I wish I would not revise my luck away should the monkey in me rediscover Landin’s passion—“This discussion of i reveals the possibility that primitives might be sensationally nonalgorithmic”—or Reynolds’s irony—“Definitional interpreters often achieve clarity by sacrificing all semblance of efficiency.”

• Landin, Peter J. 1966. The next 700 programming languages. Communications of the ACM 9(3):157–166. [abstract]

• Reynolds, John C. 1972. Definitional interpreters for higher-order programming languages. In Proceedings of the ACM national conference, vol. 2, 717–740. New York: ACM Press. Reprinted in Higher-Order and Symbolic Computation 11(4): 363–397. [abstract]

These two papers are standard references in computer science for embedding and defining one language in another. Nowadays it’s fashionable to call the embedded language a domain-specific language (DSL). Surely Ralph’s mind qualifies as a specific domain.

(Incidentally, some things never change: after Landin presented his paper, the audience spent half a page discussing whitespace in his programming language.)

Bowling balls

Solving the nice puzzle below, I found it easier to define a stream coinductively than to define a function from natural numbers inductively.

You’re standing in front of a 100 story building with two identical bowling balls. You’ve been tasked with testing the bowling balls’ resilience. The building has a stairwell with a window at each story from which you can (conveniently) drop bowling balls.

To test the bowling balls you need to find the first floor at which they break. It might be the 100th floor or it might be the 50th floor, but if it breaks somewhere in the middle you know it will break at every floor above.

Devise an algorithm which guarantees you’ll find the first floor at which one of your bowling balls will break. You’re graded on your algorithm’s worst-case running time.

“Running time” here means the number of times we drop a ball.

Before testing begins, all we know is that the answer is somewhere between the bottom of the building and the top. There are 101 possibilities in all, because maybe the balls are so strong that even dropping them from the 100th floor doesn’t break them, or maybe the balls are so weak that even dropping them from the first floor breaks them. At any time during testing, the set of possible answers remaining a contiguous set of floors: the lower bound is established by a drop that did not break the ball, and the upper bound by a drop that did break the ball.

Let c(n) denote the minimum worst−case running time, starting with 2 balls and n possible answers (so we want to calculate c(101)). We can stop once we know the answer, so c(1) = 0. If n > 1, suppose that we next drop a ball from the i-th possible floor from the top. (It only makes sense for i to be between 2 and n, inclusive, because if i < 2 then we already know the ball would break, and if i > n then we already know the ball would not break.) If the ball doesn’t break, then we have narrowed the answer down to i − 1 possibilities, so we have only c(i − 1) drops to go. If the ball does break, then we have narrowed the answer down to n − i + 1 possibilities, but we have only 1 ball left, so we’d better be careful and test the remaining floors from bottom to top, which takes n − i drops. To sum up, we have

c(1) = 0
c(n) = 1 + min_2≤i≤n max { c(i − 1), n − i } if n > 1.

A nice way to calculate c(101) in Haskell is to define a stream of numbers count, such that count!!n-1 is c(n).

count :: [Int]
count = 0 : [ 1 + minimum (zipWith max counts [0..])
            | counts <- inits' count ]

Look ma, no indices! The list [0..] above enumerates all possible values of n − i. This definition uses an auxiliary function inits', which is equivalent to map reverse . tail . inits but produces a result with more sharing.

inits' :: [a] -> [ [a] ]
inits' = f [] where
    f accum []     = []
    f accum (x:xs) = accum' : f accum' xs where
        accum' = x:accum

(The first clause defining f is not really necessary for our purpose, because the list count never ends.)

Let’s try it out.

*Main> take 101 count
[0,
 1,
 2, 2,
 3, 3, 3,
 4, 4, 4, 4,
 5, 5, 5, 5, 5,
 6, 6, 6, 6, 6, 6,
 7, 7, 7, 7, 7, 7, 7,
 8, 8, 8, 8, 8, 8, 8, 8,
 9, 9, 9, 9, 9, 9, 9, 9, 9,
10,10,10,10,10,10,10,10,10,10,
11,11,11,11,11,11,11,11,11,11,11,
12,12,12,12,12,12,12,12,12,12,12,12,
13,13,13,13,13,13,13,13,13,13,13,13,13,
14,14,14,14,14,14,14,14,14]

So the best we can do is indeed 14 drops. What about general n? Note that 1 appears once, 2 appears twice, 3 appears thrice, and so on in the list above. It’s not hard to see (and to prove by induction on n) that the pattern continues, so c(n) is the least such that 1 + … + c(n) ≥ n − 1.

*Main> and $ take 10000 $ zipWith (==) count $
       [ ceiling ((-1 + sqrt (8 * n - 7)) / 2) | n <- [1..] ]
True

Thus, indeed

c(n) = ⌈(−1 + √(8n−7))/2⌉.

But can we prove the pattern by equational reasoning on streams, ideally more concisely than by induction on n?

Airports

坐了這麼多年的飛機，我已經有點不清楚到底去過哪些機場了。以後恐怕越來越享受不到航空旅遊的樂趣了。 After so many years of flying, I am no longer sure exactly which airports I have been to. I’m afraid the joys of air travel will be scarcer in the future.

要是能把去過的火車站也畫成地圖就太好了，不過想必很難。 It would be great if I could also draw a map of all the train stations I have been to. It’s pretty difficult though.

The exponent being 2, to wit

Chief Justice Roberts delivered the opinion of the Court.

There is an exponential relationship between radius length and surface area (Area = π r²). Increasing the radius of the shutdown zone from 200 to 2,200 yards would accordingly expand the surface area of the shutdown zone by a factor of over 100 (from 125,664 square yards to 15,205,308 square yards).

Well, it’s all O(1) anyway when it comes to the Supreme Court. James Grimmelmann, please call your office.

(Via The New York Times.)

炒螺絲麵

1. 紅蘿蔔刨絲，加上鹽巴、薑末、蒜末、白醋、麻油，在碗中拌勻備用。
2. 同時用湯鍋開始燒開水，準備煮麵。
3. 茴香根切絲。
4. 菜鍋裡熱橄欖油，加茴香根絲炒一兩分鐘，然後轉小火燜。
5. 同時用湯鍋下螺絲麵（即 fusilli，用 campanelle 也不錯）。
6. 趁兩個鍋正在煮的空檔，切蔥（丁或絲）與香菜。
7. 麵快煮熟時，把碗中出的鹽水倒進菜鍋，同時加入白蔥。
8. 麵熟時馬上瀝水，加入菜鍋拌炒，混合其餘材料（青蔥、香菜、紅蘿蔔）即成。

改天來畫個 sequence diagram 吧。

兩岸關係的邏輯

台灣官員使用的邏輯好像比美國法官使用的直覺邏輯更細密一點：不但「互不否認 φ」不一定蘊涵「φ」，而且「互不否認互不否認 φ」也不一定蘊含「互不否認 φ」。直覺邏輯裡 ¬¬¬φ → ¬φ 是定理（證明是 λc.λx.c(λk.kx)），換言之「互不否認」是續繼 monad。

囚犯兩難

「個人自由以不妨害他人自由為前提。」
「他人自由以不妨害個人自由為前提。」

「警察行使的是公權力，出手打警察就是錯！警察在值勤時受傷，誰來道歉負責？」
「人民行使的是私權利，警察打出手就是錯！民眾在下班時受傷，誰來道歉負責？」

「動員了民眾就得管好，不能以『有宣佈解散』等藉口卸責，無論申請書的動線寫到哪。」
「動員了警察就得管好，不能以『沒下令撤旗』等藉口卸責，無論管制區的界線畫在哪。」

「民眾集結，迫使警察耗資動員、強勢防範，以免因小失大。警察的暴力是被逼出來的！」
「警察集結，迫使民眾耗資動員、強勢防範，以免因小失大。民眾的暴力是被逼出來的！」

「可見台灣人民還不會平和訴求，所以集會遊行應需申請，並提高保證金的門檻。」
「可見台灣政府還不會保障人權，所以警察值勤應需繳械，並進行監視器的攝影。」

「學生的本分就是讀書，更應守法。」
「警察的本分就是挨打，更應守法。」

「警方受到公共監督，所以應可壟斷使用暴力，以維護社會的法治與人民的安全。」
「警方可壟斷使用暴力，所以應受到公共監督，以維護社會的法治與人民的安全。」

「警察行為若涉嫌觸法，大家應靜待司法公訴，民眾不應訴諸暴力。」（但是司法的權力，還不是靠人民的賦予才有所依據嗎？又若狀況緊急，或司法不公呢？）
「民眾行為若涉嫌觸法，大家應靜待司法公訴，警察不應訴諸暴力。」（但是司法的權力，還不是靠警察的執行才有所落實嗎？又若狀況緊急，或司法不公呢？）

羅宋粉絲湯

紅菜頭用滾水煮過後剝皮剁碎，放回水中繼續用小火煮，並且加入蕃茄的醬 (tomato paste)、切片的洋蔥、鹽、以及少許泰式紅咖哩醬。等到所有原料融為一鍋深紅，再煮沸加入粉絲。小心粉絲超會吸水，不要加太多，不然變成羅宋炒粉絲。約十分鐘後粉絲煮軟，即可撒香菜告成。

Cognitive jobs

For people like me, who enjoys studying computation and cognition from each other’s perspectives, two academic job openings have appeared this year that resemble the great job that I am lucky to have. The Carleton position is in cognitive science, whereas the Chicago position focuses on computational linguistics. The deadlines are in this month, unlike the typical opening in pure computer science in North American academia.

Haruki Birnbaum can be more verbose than Murakami 明珠

Actually, not all of Alfred Birnbaum’s translation of Haruki Murakami’s novel Hard-boiled Wonderland and the End of the World is abridged compared to 賴明珠’s Mandarin Chinese translation in Taiwan of the book with the opposite title.

In some places, the opposite is the case, and I enjoy the English version more. Because the following comparison is a bit long, let me intersperse the two versions.

Stepping out from behind a pillar, we mounted the ladder at the end of the platform, nonchalant and disinterested, as if we did this sort of thing every day.We stepped around the railing. Several people looked our way, visibly alarmed. We were covered with mud, clothes drenched, hair matted, eyes squinting at the ordinary light—I guess we didn’t look like subway employees. Who the hell were we?

我們從柱子後面出來快步走到月台前面的盡頭，然後裝成這種事情每天做慣了沒什麼意思的樣子步上鐵梯，越過柵欄。有幾個乘客往我們的方向看，滿臉不可思議。到底這些傢伙在做什麼，他們好像很訝異的樣子。我們怎麼看都不像是地下鐵的關係者。不過到底什麼地方有誰會喜歡在地下鐵的軌道上散步呢？

Before they’d reached any conclusions, we’d sauntered past and were already at the wicket. That’s when it occurred to me, we didn’t have tickets.

他們在到達他們的結論之前，我們快速穿過月台走到收票口。然後走到收票口前面時才發現沒帶票的事。

「沒有票。」我說。

“We’ll say we lost them and pay the fare,” she said.

「當作遺失了付錢不就行了嗎？」她說。

So that’s what I told the young attendant at the gate.

我向收票口的年輕站員說票遺失了。

“Did you look carefully?” he asked. “You have lots of pockets. Could you please check again?”

「有沒有好好找？」站員說。「口袋有好幾個啊，再找一次看看好嗎？」

We stood there dripping and filthy and searched our clothes for tickets that had never been there, while the attendant eyed us incredulously.

我們在收票口裝成尋找衣服的每個口袋。在那時間裏站員以懷疑的眼神骨碌碌地盯著我們的樣子。

No, it seemed we’d really lost them, I said.

還是沒有，我說。

“Where did you get on?”

「從哪裏上車的？」

“Shibuya.”

澁谷，我說。

“How much did you pay?”

「付了多少錢，從澁谷到這裏？」

“A hundred twenty, hundred forty yen, something like that.”

忘了，我說。「我想大概是一百二十圓或一百四十圓左右吧？」

“You don’t remember?”

「不記得嗎？」

“I was thinking about other things.”

「因為正在想事情。」我說。

“Honestly, you got on at Shibuya?”

「真的是從澁谷上車嗎？」

“The line starts from Shibuya, doesn’t it? How could we cheat on the fare?”

「這個月台不是從澁谷起站的嗎？不可能亂講啊。」我抗議。

“You could have come through the underpass from the opposite platform. The Ginza Line’s pretty long. For all I know, you could have caught the Tozai Line all the way from Tsudanuma and transferred at Nihonbashi.”

「也可能是從那邊月台到這邊來呀。銀座線相當長的。而且比方從津田沼搭東西線到日本橋，在那兒轉車到這裏也行啊。」

“Tsudanuma?”

「津田沼？」

“Strictly hypothetical,” said the station attendant.

「我打個比方啊。」站員說。

“So how much is it from Tsudanuma? I’ll pay that. Will that make you happy?”

那麼從津田沼到這裏要多少錢？我付好了。這樣可以吧？」

“Did you come from Tsudanuma?”

「是從津田沼來的嗎？」

“No,” I said. “Never been to Tsudanuma in my life.”

「不。」我說。「從來沒到過什麼津田沼。」

“Then why pay the fare?”

「那你為什麼要付？」

“I’m just doing what you said.”

「你不是這樣說嗎？」

“I said that was strictly hypothetical.”

「所以我不是告訴你那只是個比方嗎？」

By now, the next train had arrived. Twelve passengers got off and passed through the wicket. We watched them. Not one of them had lost a ticket. Whereupon we resumed negotiations with the attendant.

“Okay, tell me from where do I have to pay?” I said.

“From where you got on,” he insisted.

“Shibuya, like I’ve been trying to tell you.”

“But you don’t remember the fare.”

“Who remembers fares? Do you remember how much coffee costs at McDonald’s?”

“I don’t drink McDonald’s coffee,” said the station attendant. “It’s a waste of money.”

“Purely hypothetical,” I said. “But you forget details like that.”

“That may be, but people who say they’ve lost tickets always plead cheaper fares. They all come over to this platform and say they got on in Shibuya.”

“I already said I’d pay whatever fare you want, didn’t I? Just tell me how much.”

“How should I know?”

I threw down a thousand-yen bill and we marched out. The attendant yelled at us, but we pretended not to hear.

沒完沒了的爭論繼續下去太麻煩了，於是我放了一張一千圓鈔票就自顧自地走出外面。雖然聽見後面站員呼喊的聲音，但我們裝成沒聽見地繼續走。

The use of 什麼 in the retort 從來沒到過什麼津田沼 is inspired indeed, but 關係者 and 到達他們的結論 are not part of Mandarin the last time I checked. Moreover, the part about McDonald’s coffee is a even more brilliant retort—completely missing in the Mandarin—and what is a Murakami novel without counting how many passengers got off the next train?

Then again, I would call the wickets turnstiles in English even though I know they don’t turn. It’s true, 沒完沒了的爭論繼續下去太麻煩了. I’m like the blind man’s two arms arguing with each other about the elephant.

My interpretation of this book’s ending is that the tide turns and everyone lives happily ever after like they always do in Hollywood. The separation represents that the two ‘I’s only brush past each other, like the trains in Café Lumière. Does anyone agree?

村上明珠比春樹 Birnbaum 來得囉唆

我從美國的圖書館借到賴明珠翻譯的《世界末日與冷酷意境》，而 Dylan 則從丹麥的圖書館借到 Alfred Birnbaum 翻譯的 Hard-boiled Wonderland and the End of the World。為什麼兩本書連書名的順序都相反呢？我搞不清楚。難道日文說「張三と李四は依序上車」的意思，是李四先上、張三後上嗎？真傷腦筋。

我也很驚訝，中文譯本看似長篇的一本小說，為什麼譯成英文就縮水成中篇的樣子了？中譯本有 535 頁，英譯本則只有 400 頁，而且內頁本文所占的面積 (typeblock 中文怎麼說？) 差不多，英文的字體還稍大一些。

細看才發現，的確村上春樹的書在英譯過程中常會有所編修 (可能作者本人也有參與)，要不然就是賴明珠成天胡思亂想。試比較：

「胃擴張。」她說。「所以怎麼吃都不會胖。」

「喔。」我感嘆道。「那飯錢可要花不少囉。」事實上她把我連明天中午的飯量都一個人吃完了。

「那當然。」她說。「在外面吃的時候，通常連吃兩家。首先是吃拉麵或餃子輕微暖暖身，然後再正式吃飯。薪水大概都是吃掉的吧。」

… 像用重機關槍掃射倉庫一樣驚人的食慾。我準備吃一星期採購來的食品眼看著就要光了。那些法蘭克福香腸我原來打算用來做美味的 Sauerkraut 酸菜香腸的。

“Gastric dilation,” she confessed. “It doesn’t matter matter how much I eat. I don’t gain weight.”

“Must run up quite a food bill,” I said. Truth was, she’d gastrically dilated her way through tomorrow’s dinner in one go.

“It’s frightening,” she said. “Most of my salary disappears into my stomach.”

… A regular machine gun of a hunger, this girl!

前面這一句 “gastrically dilated her way” 實為妙筆，但是且慢，拉麵呢？餃子呢？酸菜呢？一星期的採購、在外面連吃兩家的美味，就這樣胃擴張掉了，有點可惜。之後還有分段留白等的差異。我個人覺得，比較冗長的中譯本，讀起來比較有味道。可能我的閱讀也有胃擴張的毛病。是不是跟吃素有關。

我對本書結局的解讀，是情勢逆轉、皆大歡喜的好萊塢完結篇。分道揚鑣代表兩個「我」只擦身而過，就像《珈琲時光》裡的電車那樣。有別人看法相同嗎？

(後記：有些地方中譯反而比英譯少了一段。)

Higher-order shell

Many Unix utilities execute their arguments as a command line in turn. Some well-known examples are nice, sudo, xargs, and find. These programs are sometimes called meta-commands, but I think of them as higher-order programs by analogy to higher-order functions.

Surely I was not the first to write the following two higher-order programs, given how useful they are.

tmp :: String -> (FilePath -> IO ()) -> IO ()

The first program is tmp. It puts standard input in a temporary file, then invokes the arguments as a command with the name of the temporary file appended.

This program is useful because some programs require input in the form of an ordinary file rather than a pipe. For example, say that we want to retrieve a URL and display the contents using xdvi. It would be nice to be able to say

curl http://www.diku.dk/~andrzej/papers/RC.dvi | xdvi -

or

xdvi <(curl http://www.diku.dk/~andrzej/papers/RC.dvi)

but my xdvi only works on an ordinary file named on the command line:

$ curl http://www.diku.dk/~andrzej/papers/RC.dvi | xdvi -
xdvi.bin: Fatal error: -: No such file,
          and -.dvi doesn't exist either.

$ xdvi <(curl http://www.diku.dk/~andrzej/papers/RC.dvi)
xdvi.bin: Fatal error: /dev/fd/63: File has zero size,
          and /dev/fd/63.dvi doesn't exist either.

Instead, we can use tmp to adapt xdvi to our purpose.

$ curl --silent http://www.diku.dk/~andrzej/papers/RC.dvi |
  tmp xdvi

When the command is done, tmp deletes the temporary file.

$ echo foo | tmp cat
foo

$ echo foo | tmp echo | xargs cat
cat: /tmp/uyocf2fHQx: No such file or directory

Often I use tmp when I need to process the same data twice. For example, it takes two invocations of psselect to print duplex using manual feed on a printer without duplex.

$ a2ps -o- Higher-order_shell.mdwn |
  tmp sh -c 'psselect -e -r $0 | lpr;
             read </dev/tty;
             psselect -o $0 | lpr'

The use of $0 above is documented in the sh man page:

-c

Read commands from the command_string operand. Set the value of special parameter 0 (see Special Parameters) from the value of the command_name operand and the positional parameters ($1, $2, and so on) in sequence from the remaining argument operands. No commands shall be read from the standard input.

We can also use sh -c in the same way to nest multiple invocations of tmp together. For example, the following command uses lynx to convert two HTML files into plain text, then uses xxdiff to show how the results differ. We need to invoke tmp twice because xxdiff requires both of its arguments to name ordinary files rather than pipes.

$ lynx -dump Control-Monad-State-Lazy.html |
  tmp sh -c 'lynx -dump Control-Monad-State-Strict.html |
             tmp xxdiff $0'

Because xxdiff takes the argument - to mean standard input, the following command works too.

$ lynx -dump Control-Monad-State-Lazy.html |
  tmp sh -c 'lynx -dump Control-Monad-State-Strict.html |
             xxdiff $0 -'

keep :: (forall m. MonadIO m => m ()) -> IO a

The second program is keep. It invokes the arguments as a command and monitors the files the command accesses. Whenever any of the files change, keep invokes the command again. Most of the time, I use keep to invoke LaTeX when I don’t want to bother writing a Makefile:

$ keep pdflatex talk.tex

Internally, keep uses strace (another higher-order program) to find out which files are accessed by the command, and Linux’s inotify facility to watch the files for changes. The incron utility also uses inotify to run a command when files change, but keep discovers which files to watch automatically.

Errata

Thanks to bennymack on reddit for pointing out that file can work on standard input. I changed the example from file to xdvi.

I also fixed the out-of-scope type variable in the faux signature of keep.

Shadow cities

The essay collection Letters of Transit: Reflections on Exile, Identity, Language, and Loss, published after a lecture series at the New York Public Library, includes “Shadow Cities” by André Aciman. An excerpt follows.

¶ And, indeed, there was something physically central about Straus Park. This, after all, was where Broadway and West End Avenue intersected, and the park seemed almost like a raised hub on West 106th Street, leading to Riverside Park on one side and to Central Park on the other. Straus Park was not on one street but at the intersection of four. Suddenly, before I knew why, I felt quite at home. I was in one place that had at least four addresses.

¶ Here you could come, sit, and let your mind drift in four different directions: Broadway, which at this height had an unspecified Northern European cast;

West End, decidedly Londonish;

107th, very quiet, very narrow, tucked away around the corner, reminded me of those deceptively humble alleys where one finds stately homes along the canals of Amsterdam.

And 106th, as it descended toward Central Park, looked like the main alley of a small town on the Italian Riviera,

where, after much trundling in the blinding light at noon as you take in the stagnant odor of fuel from the train station where you just got off, you finally approach a sort of cove, which you can’t make out yet but which you know is there, hidden behind a thick row of Mediterranean pines,

over which, if you really strain your eyes, you’ll catch sight of the tops of striped beach umbrellas jutting beyond the trees, and beyond these, if you could just take a few steps closer, the sudden, spectacular blue of the sea.

¶ To the west of Straus Park, however, the slice of Riverside and 106th had acquired a character that was strikingly Parisian,

and with the fresh breeze which seems to swell and subside all afternoon long, you sensed that behind the trees of Riverside Park,

serene and silent flowed an elusive Seine,

and beyond it, past the bridges that were to take you across, though you couldn’t see any of it yet, was not the Hudson, not New Jersey, but the Left Bank—

not the end of Manhattan, but the beginning of a whole bustling city waiting beyond the trees—as it waited so many decades ago when, as a boy, dreaming of Paris, I would go to the window, look out to the sea at night, and think that this was not North Africa at all, but the Ile de la Cité. Perhaps what lay beyond the trees was not the end of Manhattan, or even Paris, but the beginnings of another, unknown city, the real city, the one that always beckons, the one we invent each time and may never see and fear we’ve begun to forget.

¶ There were moments when, despite the buses and the trucks and the noise of people with boom boxes, the traffic light would change and everything came to a standstill and people weren’t speaking, and the unrelenting sun beat strong on the pavement, and I would almost swear this was an early summer afternoon in Italy, and that what lay behind Riverside Park was not just my imaginery Seine, but the Tiber as well. What made me think of Rome was that everything here reminded me of the kind of place all tourists know well: that tiny, empty piazza with a little fountain, where, thirsty and tired with too much walking all day, you douse your face, then unbuckle your sandals, sit on the scalding marble edge of a Baroque fountain, and simply let your feet rest a while in what is always exquisitely clear, non-drinkable water.

¶ Depending on where I sat, or on which corner I moved to within the park, I could be in any of four or five countries and never for a second be in the one I couldn’t avoid hearing, seeing, and smelling. This, I think, is when I started to love, if love is the word for it, New York. I would return to Straus Park every day, because returning was itself now part of the ritual of remembering the shadow cities hidden there—so that I, who had put myself there, the way squatters put themselves somewhere and start to build on nothing, with nothing, would return for no reason other than perhaps to run into my own footprints. This became my habit, and ultimately my habitat. Sometimes finding that you are lost where you were lost last year can be oddly reassuring, almost familiar. You may never find yourself; but you do remember looking for yourself. That too can be reassuring, comforting.

…

¶ How uncannily appropriate, therefore, to find out fifteen years later that the statue that helped me step back in time was not that of a nymph, but of Memory herself.

In Greek, her name is Mnemosyne, Zeus’s mistress, mother of the Muses. I had, without knowing it, been coming to the right place after all. This is why I was so disturbed by the imminent demolition of the park: my house of memories would become a ghost park. If part of the city goes, part of us dies as well.

免窗升級想板基本輸入輸出系統法門

為了讓我的 ThinkPad 風扇安靜一點，最近想要把它的 BIOS 升級到最新的版本。因為我的電腦上沒有裝 Windows，只有裝 Linux，所以除非麻煩地重灌 Windows，否則不能使用 IBM 或聯想發佈的 Windows 版 BIOS 升級程式。

以往在 ThinkPad X20 系列的年代，IBM 除了 Windows 版的升級程式以外，還會發佈一張軟碟開機片。也就是我可以下載一個 1.44MB 的檔案，寫到一張軟碟上用來開機。這張軟碟的內容其實是 IBM 用 DOS 拼湊而成的，開機以後 AUTOEXEC.BAT 會自動執行升級程式。就算沒有 ThinkPad 擴充的軟碟機，或手邊沒有空著不用的軟碟（我最近一次看到軟碟好像是馬蓋先的「醜小鴨」那集吧），也可以用 SYSLINUX 的 MEMDISK，直接從下載檔案裡的虛擬軟碟開機。例如我用 GRUB，在 /boot/grub/menu.lst 裡加上一段

title  MEMDISK
kernel (hd0,5)/lib/syslinux/memdisk
initrd (hd0,7)/ccshan/tmp/floppy.img

即可用 /usr/lib/syslinux/memdisk 從 /home/ccshan/tmp/floppy.img 裡的虛擬軟碟開機，因為 (hd0,5) 是我的 /usr 分割區，而 (hd0,7) 是我的 /home 分割區。就算既不用 GRUB 也不用 Linux，也可以用 PXELINUX 從網路上別台電腦上的虛擬軟碟開機進行升級。

現在時代不同了，ThinkPad X60 系列的 BIOS 已經大得軟碟裝不下了，於是 IBM 發佈的開機片不再是軟碟而是光碟。我沒有光碟機，也不想重灌 Windows，所以希望從虛擬光碟開機進行升級，但是事情沒那麼簡單，因為 MEMDISK 只會模擬磁碟，不會模擬光碟。這是因為從光碟開機的過程比從磁碟複雜，要遵從 El Torito 標準進行。IBM 的這張光碟開機片，除了把新的 BIOS 及其更新程式放在一般的 ISO 9660 檔案系統以外，另含一張虛擬的軟碟開機片。當一位有錢擴充 ThinkPad 的用戶，用燒好的實體光碟開機時，ThinkPad 會從實體光碟上載入虛擬軟碟，執行虛擬軟碟上的 DOS。這份 DOS 的 CONFIG.SYS 與 AUTOEXEC.BAT 得先載入實體光碟機的驅動程式，才能讀到前述的 ISO 9660 檔案系統，以執行實體光碟上的 BIOS 更新程式。

我徹夜試驗，發現可以用實體硬碟代替實體光碟，成功升級了我的 BIOS。基本的想法是，在一個實體硬碟的新分割區裡，結合軟碟上的 DOS 開機程式以及光碟上的 BIOS 升級程式。詳情如下。

首先得在實體硬碟裡造一個分割區，如下例 /dev/sda2。這個分割區不用很大，比 IBM 發佈的光碟檔稍大一點就夠了（約 5MB），不過必須位於實體硬碟的前 1024 個磁柱以內（這是 DOS 的限制，迫使我用 gparted 把原本在硬碟最前面的分割區稍微縮小了一點，幸好那只是我的 /usr/local 分割區而已，不很麻煩），而且必須是初選而非邏輯分割區（迫使我用 sfdisk -d 把一個不常用的初選分割區備份然後暫時刪除，升級完再用 sfdisk -uS -N… -O… 小心放回分割表內）。

在分割表裡，這個分割區的型別應設為 6 號（也就是 FAT16 的意思），並且可開機旗標應設為真，因為我們就是要用它開機。但是要把它作成 DOS 的開機分割區，除了新造檔案系統

$ sudo mkdosfs /dev/sda2

以外，還需一番移花接木。我從 IBM 下載的光碟檔名為 7buj25uc.iso，其中內含的虛擬軟碟開機片是從位元組位址 0xA800 (= 43008) 開始的 1.44M (= 1474560) 個位元組。為了方便，我把這部份資料擷取成為另一個檔案 7buj25uc.img。

$ dd if=7buj25uc.iso of=7buj25uc.img skip=43008 count=1474560 bs=1

這兩個數字是我邊用 tweak 查看光碟檔、邊參考 El Torito 標準文件找到的。我早知道的話，也可以用 Joachim Selke 寫好的程式直接擷取。

要能從 /dev/sda2 這個分割區開機，必須把 7buj25uc.img 這張軟碟的內容複製進去，但是有兩點需要注意的地方。第一，不只要複製檔案，還要複製檔案系統最開頭的開機磁區，但是不能蓋掉裡面所謂的 BIOS 參數區塊，因為那裡存有分割區大小等資訊。第二，根目錄裡表列的第一個檔案必須是 IBMBIO.COM，第二個必須是 IBMDOS.COM，不然開機磁區裡的程式會找不到。

開機磁區是檔案系統開頭的 512 個位元組，其中 BIOS 參數區塊佔用的是位址 3 到 62 之間的 59 個位元組，所以我把區塊前的 3 個位元組與區塊後的 450 個位元組分別從軟碟複製到分割區裡。

$ sudo dd bs=1 count=3 if=7buj25uc.img of=/dev/sda2
$ sudo dd bs=1 seek=62 skip=62 count=450 if=7buj25uc.img of=/dev/sda2

然後我把軟碟裡的所有檔案都複製到分割區裡，但是先複製 IBMBIO.COM 與 IBMDOS.COM。（以下指令假設已存兩個空目錄 /mnt/pool 以及 /mnt/loop。）

$ sudo mount -t msdos /dev/sda2 /mnt/pool
$ sudo mount -t msdos -o loop 7buj25uc.img /mnt/loop
$ sudo cp /mnt/loop/ibmbio.com /mnt/pool
$ sudo cp /mnt/loop/ibmdos.com /mnt/pool
$ sudo cp -u /mnt/loop/* /mnt/pool
$ sudo umount /mnt/loop

此時查看 /mnt/pool/config.sys 與 /mnt/pool/autoexec.bat 可以了解，這張虛擬開機片在掛上光碟以後會執行光碟上的另一個 COMMAND.COM。所以我在把光碟內容複製到分割區裡的同時，乾脆用光碟上的 COMMAND.COM 取代軟碟上 DOS 的 COMMAND.COM。

$ sudo mount -o loop 7buj25uc.iso /mnt/loop
$ sudo cp -i /mnt/loop/* /mnt/pool
cp: overwrite `/mnt/pool/COMMAND.COM'? y
$ sudo umount /mnt/loop

最後，我用文字編輯器修改 /mnt/pool/config.sys，把其中的 A: 統統換成 C:（因為要從硬碟而非軟碟開機），並且拿掉呼叫 COMMAND.COM 那一行後面給的參數。

$ vi /mnt/pool/config.sys
$ sudo umount /mnt/pool

大功告成。重新開機以後，請 GRUB 啟動這個新的分割區

root (hd0,1)
makeactive
chainloader +1

即可進入 IBM 的 BIOS 更新程式。

Differentiating regions

(An alternative title for this post is, what is the type of differentiation? Hint: it’s not quite (ℝ→ℝ)→(ℝ→ℝ), because how would you make sure the input function is differentiable?)

You can download this post as a literate Haskell program.

{-# LANGUAGE Rank2Types             #-}
{-# LANGUAGE MultiParamTypeClasses  #-}
{-# LANGUAGE FlexibleInstances      #-}
{-# LANGUAGE FunctionalDependencies #-}
{-# LANGUAGE UndecidableInstances   #-}
{-# LANGUAGE OverlappingInstances   #-}

module Differentiation where

Automatic differentiation

The overloading approach to automatic differentiation has become more popular recently among typed functional programmers. The basic idea is to overload arithmetic operators such as +, ×, and sin so that they work on not just floating-point numbers but pairs (or more generally, sequences) of them, which track quantities along with their rates of change. The overloaded operators are easy to define because, unlike with integration, the rules of differentiation are compositional: you know, d(x + y) = dx + dy, d(x × y) = dx × y + x × dy, d(sin x) = cos x × dx, and so on. Here they are in Haskell.

data D a = D a a
  deriving Show

lift :: Num a => a -> D a
lift x = D x 0

infinitesimal :: Num a => D a
infinitesimal = D 0 1

instance Eq a => Eq (D a) where
  D x _ == D y _ = x == y

instance Ord a => Ord (D a) where
  compare (D x _) (D y _) = compare x y

instance Num a => Num (D a) where
  D x x' + D y y' = D (x + y) (x' + y')
  D x x' * D y y' = D (x * y) (x' * y + x * y')
  negate (D x x') = D (negate x) (negate x')
  abs    (D x x') = D (abs x) (signum x * x')
  signum (D x _)  = lift (signum x)
  fromInteger x   = lift (fromInteger x)

instance Fractional a => Fractional (D a) where
  recip (D x x') = D (recip x) (-x'/x/x)
  fromRational x = lift (fromRational x)

The two components of a D value are a quantity and its derivative, so the lift function ‘lifts’ a number to a constant quantity, and infinitesimal is a quantity with value 0 and derivative 1. Were abs defined by abs x = signum x * x by default, we wouldn’t have to define abs for D above.

Let us use these definitions to model how a parabola reflects light.

Suppose that a light ray (red above) enters a parabolic mirror y = x²/4 from above. Where does the reflected ray cross the y axis? In the diagram above, if the point where the ray hits the parabola is (x,y), then the derivative of y with respect to x is tan θ, and the y coordinate where the reflected ray crosses the y axis is y + x/tan 2θ, which is equal to y + x (1/tan θ − tan θ)/2. We can compute this coordinate by automatically differentiating y with respect to x:

curve x = x^2/4

reflect x = let D y y' = curve (lift x + infinitesimal)
            in y + x * (recip y' - y') / 2

As expected, the parabola reflects all incoming rays from above to the focal point (0,1).

*Differentiation> map reflect [1..5]
[1.0,1.0,1.0,1.0,1.0]

To be sure, this code does not work by symbolically differentiating y = x²/4 to yield y′ = x/2. Rather, it computes y alongside y′ for one particular x at a time, so the curve could just as well be defined by a more complex program that uses if and recursion. For example, a ray tracer usually deals with scenes much more complex than a single parabola. This code also does not work by numerically comparing the values of y at nearby values of x. Instead of approximating dy/dx by Δy/Δx where Δx is a very small real number, we compute with an actually infinitesimal dx.

Differentiation is a higher-order function

Before we continue, let us abstract the pattern for differentiation in reflect above into a new higher-order function d, which differentiates any given function at the input 0. For convenience, d also returns the value of the given function at 0.

d :: Num a => (D a -> D b) -> (b, b)
d f = let D y y' = f infinitesimal
      in (y,y')

reflect :: Fractional a => a -> a
reflect x = let (y,y') = d (\h -> curve (lift x + h))
            in y + x * (recip y' - y') / 2

Even though the reflect function uses differentiation internally, we can still differentiate it. Such differentiate is said to be nested. For the parabola, we can confirm that the reflected ray hits the focal point not just at but also around x = 3, because the derivative computed below is zero.

*Differentiation> d (\k -> reflect (3 + k))
(1.0,0.0)

For other curves and surfaces, the derivative is typically not zero and tells us the density of light energy that falls around each point on the y axis. Hence, as Dan Piponi noted, this kind of calculation is performed by ray tracers and other programs that sample from probability distributions.

Another application of automatic differentiation is to find roots of a function using Newton’s method. Therefore, we can use nested automatic differentiation to find local extrema and saddle points of a function using Newton’s method.

The danger of confusing infinitesimals

Jeff Siskind and Barak Pearlmutter pointed out a kind of programmer mistake that makes nested differentiation give the wrong result. As they show, this kind of mistake is easy to make in the framework defined above, because all it takes is putting a call to the lift function in the wrong place. The definition of reflectBug below is only slightly different from reflect, but the result is very different and very wrong.

reflectBug x = let (y,y') = d (\h -> lift (curve (x + h)))
               in y + x * (recip y' - y') / 2

*Differentiation> d (\k -> reflectBug (3 + k))
(Infinity,NaN)

They demonstrate this problem using running code in Haskell and Scheme that computes

to be 2 rather than the correct answer 1.

The essence of this problem is that the two nested invocations of differentiation use two different infinitesimals, which a mathematician would denote by dh and dk. These two infinitesimals should not be confused, just as years and feet and persons should not be confused.

Using types to check units

Björn Buckwalter showed that we can use a generic type system to prevent such confusion statically, just as Haskell uses state threads to distinguish pointers into different memory regions. Recall that the type ST s a in Haskell represents a monadic computation that yields a result of type a using mutable cells in the state thread represented by the phantom type s. To construct such a computation, we can use primitive operations such as

newSTRef :: a -> ST s (STRef s a)

and the fact that ST s is a monad. To run such a computation, we must use the primitive function

runST :: (forall s. ST s a) -> a

in which forall s forces different state threads, created by different calls to runST, to be represented by different phantom types s. One way to understand this rank-2 type is that it makes the type checker generate a new phantom type s for each argument to runST. Analogously, Buckwalter redefines the type constructor D to take a phantom-type argument s, which represents an infinitesimal unit.

data D s a = D a a
  deriving Show

Accordingly, the other definitions above change in their types, but not in their terms or behavior. The most important change is the new rank-2 type of d, which forces different infinitesimals, created by different invocations of differentiation, to be represented by different phantom types s.

d :: Num a => (forall s. D s a -> D s a) -> (a, a)
d f = let D y y' = f infinitesimal
      in (y,y')

lift :: Num a => a -> D s a
lift x = D x 0

infinitesimal :: Num a => D s a
infinitesimal = D 0 1

instance Eq a => Eq (D s a) where
  D x _ == D y _ = x == y

instance Ord a => Ord (D s a) where
  compare (D x _) (D y _) = compare x y

instance Num a => Num (D s a) where
  D x x' + D y y' = D (x + y) (x' + y')
  D x x' * D y y' = D (x * y) (x' * y + x * y')
  negate (D x x') = D (negate x) (negate x')
  abs    (D x x') = D (abs x) (signum x * x')
  signum (D x _)  = lift (signum x)
  fromInteger x   = lift (fromInteger x)

instance Fractional a => Fractional (D s a) where
  recip (D x x') = D (recip x) (-x'/x/x)
  fromRational x = lift (fromRational x)

Because the phantom type s is part of the type of a number, and because arithmetic operations such as + require the arguments and the return value to have the same type, it is a type error to add numbers denominated in different infinitesimals. In particular, the erroneous definition reflectBug above is now a type error, as desired.

Occurs check: cannot construct the infinite type: t = D s t
  Expected type: t
  Inferred type: D s t
In the first argument of `lift', namely `(curve (x + h))'
In the expression: lift (curve (x + h))

For this checking of infinitesimal units to be sound, this library for automatic differentiation should not export the values D and infinitesimal to its users, though of course the type constructor D and its type-class instances need to be exported, along with the functions d and lift.

(In the discussion that ensued, David Roundy noted that the same kind of static safety can be achieved by exporting just a function

d :: Num a => (forall b.
      Num b => (a -> b) -> b -> b) -> (a, a)

for differentiation. The type b makes it unnecessary and useless to export the type constructor D, even though d is still implemented using D. Also, the new argument of type a -> b makes it unnecessary and useless to export the lift function. Finally, the type-class context Num b makes it unnecessary and useless to export the Eq, Show, and Num instances for D. However, as Chris Smith lamented, we need additional differentiation functions of the types

Fractional a => (forall b.
 Fractional b => (a -> b) -> b -> b) -> (a, a)

Floating a => (forall b.
 Floating b => (a -> b) -> b -> b) -> (a, a)

in order to differentiate functions that use Fractional or Floating operations. Oleg Kiselyov used similar types to express symbolic differentiation.)

Automatic lifting

Although the type system now prevents us from putting calls to lift in the wrong place, it is still annoying to have to invoke lift manually—especially for nested differentiation, a useful case as discussed above. Depending on ‘how constant’ a quantity is, we need to feed it through a composition of exactly the right number of lifts. This manual coding is frustrating because the unique right number of lifts to apply is obvious from the input and output types desired: to convert a type a to the type D s a, apply lift once; to convert a to D s (D s' a), apply lift twice; and so on. We want the compiler to manage these subtyping coercions automatically.

An analogous situation arises with state threads, which can be organized into a hierarchy of memory regions. As part of a monadic computation that uses mutable cells in a parent region, we can create a child region and perform a subcomputation that allocates and accesses mutable cells in both regions. After the subcomputation completes, the child region is destroyed en bloc, but we can still use the parent region and observe any effect on it brought about by the subcomputation. To allow the subcomputation to use the parent region, we want every region to be a subtype of its descendents. Matthew Fluet and Greg Morrisett’s implementation of nested regions in Haskell uses explicit subtyping coercions just like our lift: depending on ‘how senior’ a region is, we need to compose exactly the right number of region coercions.

In a pending submission to the Haskell symposium, Oleg and I show how to automate region subtyping coercions using type classes. One might hope to apply that approach to lifting in automatic differentiation. Indeed we can, but I only know how to automate counting lifts, not how to automate placing them. That is, instead of feeding each use of an input quantity to the lift function exactly the right number of times, we can feed it to a new function once. The new function, called lifts, belongs to a new type class Lifts, which takes two type parameters. The constraint Lifts a b holds if and only if the type b is the result of applying zero or more type constructors D s to the type a.

class Lifts a b where
  lifts :: a -> b

More concretely, the following instances incompletely approximate the intended meaning of Lifts.

instance Lifts a a where
  lifts = id

instance Num a => Lifts a (D s a) where
  lifts = lift

instance Num a => Lifts a (D s (D s' a)) where
  lifts = lift . lift

instance Num a => Lifts a (D s (D s' (D s'' a))) where
  lifts = lift . lift . lift

The definition above of reflect in terms of d applies lift once to one occurrence of x but not to other occurrences of x and h. The same function can be expressed using Lifts, by applying lifts once to each occurrences of the input variables x and h.

reflectAuto :: Fractional a => a -> a
reflectAuto x
  = let (y,y') = d (\h -> curve (lifts x + lifts h))
    in y + lifts x * (recip y' - y') / 2

Expressing reflect in this new way frees us from counting how many times to lift the inputs x and h each time they are used.

How to implement Lifts? On one hand, as an implementation of Lifts, the approximate instances above are incomplete and unsatisfactory in theory, in that they restrict how many lift each lifts can stand for. They are perfectly useful in practice, however, and rely on no extension to Haskell other than rank-2 types and multiparameter type classes with flexible instances. On the other hand, a complete implementation is possible using the TypeCast class for type improvement (originally used by Kiselyov, Lämmel, and Schupke to implement heterogeneous collections), but it requires more Haskell extensions: functional dependencies, overlapping instances, and undecidable instances. Without further ado, below is the complete implementation.

instance Lifts a a where
  lifts a = a

instance (TypeCast (D s b') b, Num b', Lifts a b')
  => Lifts a b where
  lifts = typeCast . lift . lifts

class TypeCast a b | a -> b, b -> a where
  typeCast :: a -> b
class TypeCast' t a b | t a -> b, t b -> a where
  typeCast' :: t -> a -> b
class TypeCast'' t a b | t a -> b, t b -> a where
  typeCast'' :: t -> a -> b
instance TypeCast' () a b => TypeCast a b where
  typeCast x = typeCast' () x
instance TypeCast'' t a b => TypeCast' t a b where
  typeCast' = typeCast''
instance TypeCast'' () a a where
  typeCast'' _ x  = x

Although Lifts makes it easier to use automatic differentiation, this implementation is heavy lifting. I wonder if it is easier to express this combination of subtyping and rank-2 polymorphism in a language like Scala?