Archive for the ‘Mathematics’ Category.

Statement Considered Harmful

I harbor no illusion about the effectiveness of airing this particular pet peeve; complaining about it has about the same chance of success as protesting against split infinitives or music in restaurants. Still, it is worth mentioning that the widespread use of the word “statement” to denote a programming language element, such as an assignment, that directs a computer to perform some change, is misleading. “Instruction” is the better term.

A “statement” is “something stated, such as a single declaration or remark, or a report of fact or opinions” (Merriam-Webster).

Why does it matter? The use of “statement” to mean “instruction” obscures a fundamental distinction of software engineering: the duality between specification and implementation. Programming produces a solution to a problem; success requires expressing both the problem, in the form of a specification, and the devised solution, in the form of an implementation. It is important at every stage to know exactly where we stand: on the problem side (the “what”) or the solution side (the “how”). In his famous Goto Statement Considered Harmful of 1968, Dijkstra beautifully characterized this distinction as the central issue of programming:

Our intellectual powers are rather geared to master static relations and our powers to visualize processes evolving in time are relatively poorly developed. For that reason we should do (as wise programmers aware of our limitations) our utmost to shorten the conceptual gap between the static program and the dynamic process, to make the correspondence between the program (spread out in text space) and the process (spread out in time) as trivial as possible.

Software verification, whether conducted through dynamic means (testing) or static techniques (static analysis, proofs of correctness), relies on having separately expressed both a specification of the intent and a proposed implementation intended to realize that intent. They have to remain distinct; otherwise we cannot even define what it means that the program should be correct (correct with respect to what?), and even less what it means to validate the program (validate it against what?).

In many approaches to verification, the properties against which we validate programs are called assertions. An assertion expresses a property that should hold at some point of program execution. For example, after the assignment instruction a := b + 1, the assertion ab will hold. This notion of assertion is used both in testing frameworks, such as JUnit for Java or PyUnit for Python, and in program proving frameworks; see, for example, the interactive Web-based version of the AutoProof program-proving framework for Eiffel at autoproof.sit.org, and of course the entire literature on axiomatic (Floyd-Hoare-Dijkstra-style) verification.

The difference between the instruction and the assertion is critical: a := b + 1 tells the computer to do something (change the value of a), as emphasized here by the “:=” notation for assignment; ab does not direct the computer or the computation to do anything, but simply states a property that should hold at a certain stage of the computation if everything went fine so far.

In the second case, the word “states” is indeed appropriate: an assertion states a certain property. The expression of that property, ab, is a “statement” in the ordinary English sense of the term. The command to the computer, a := b + 1, is an instruction whose effect is to ensure the satisfaction of the statement ab. So if we use the word “statement” at all, we should use it to mean an assertion, not an instruction.

If we start calling instructions “statements” (a usage that Merriam-Webster grudgingly accepts in its last entry for the term, although it takes care to define it as “an instruction in a computer program,” emphasis added), we lose this key distinction.

There is no reason for this usage, however, since the word “instruction” is available, and entirely appropriate.

So, please stop saying “an assignment statement” or “a print statement“; say “an assignment instruction” and so on.

Maybe you won’t, but at least you have been warned.

Recycled This article was first published in the “Communications of the ACM” blog.

VN:F [1.9.10_1130]
Rating: 9.9/10 (9 votes cast)
VN:F [1.9.10_1130]
Rating: +1 (from 1 vote)

The mathematics of the seven messengers

In my previous article I referred to the short story The Seven Messengers by Dino Buzzati, of which I have written a translation. Here is a quantitative analysis. I will also refer the reader to a very nice article published in 2009 on this topic: The Seven Messengers and the “Buzzati Sequence” by Giorgio D’Abramo from the National Institute of Astrophysics in Rome. It is available here on arXiv. I discovered ita few years ago after working out my own “sequence” and had a short and pleasant correspondence with Dr. D’Abramo. You can compare our respective derivations, which I think are equivalent. Here is mine.

Although Buzzati gives absolute values (40 leagues per day), all that matters is the ratio m between the messengers’ and caravan’s speeds (m > 1). The relevant measures of time are:

  • The messenger-day, which take as unit of time.
  • The caravan-day, which is m times a messenger-day.

If as unit of distance we take ground covered in one day by a messenger, then time is equal to distance.

So if Tn is the time when a messenger rejoins the caravan after his n-th trip back home, we have

Tn + Tn+1  = m (Tn+1 – Tn)                  [1]

Justification of [1]:  both sides measure the time from when the messenger leaves (for the n-th time) to when he next rejoins the caravan. Note that the messenger goes back for his n+1-st trip on the very day he completes the n-th one.  On the left we have the time/distance  covered by the messenger (Tn to go home, plus Tn+1 to catch up). On the right, Tn+1 – Tn is the time/distance covered by the caravan in caravan units, which we multiply by m to get messenger-days.

The equality can be rewritten

Tn+1 = (m + 1) / (m – 1) Tn

yielding a geometric progression

 Tn = Kn T0                  [2]

where T0 is when the messenger leaves for his first trip, and the constant K is (m + 1) / (m – 1).

The Prince, who is as bad at horses as he (unlike Buzzati) is at math, had initially expected m = 2. Then K is 3 / 1, that is to say, 3. In that case the progression [2] would have been Tn = 3n T0. Even then, he would have found the result disappointing: while the first messenger returns the first time after three days, the third messenger, for example, returns the fifth time after about almost 1000 days (35 is 243, to be multiplied by 4), i.e. close to a year, and the last messenger returns for the sixth time after 16 years ( 36 × 8 /365).

The way things actually happen in the the story, the Prince determines after a while that m = 3/2 (the messengers go faster by half than the caravan), so K is 5. (In the text: Soon enough, I realized that it sufficed to multiply by five the number of days passed so far to know when the messenger would be back with us.) The unit travel times (Kn) of messengers are as follows, giving return times if multiplied by two for the first messenger (since he first leaves on the second day), three for the second messenger) and so on:

 

(1)          5 days: as stated in the story, the first return is after 10 days for Alexander, 15 for Bartholomew, 20 for Cameron…

(2)          25 days: Alexander returns for the second time after almost one month.

(3)          4 months

(4)          Close to two years (20 months)

(5)          8 years and a half

(6)          43 years

(7)          214 years

(8)          Millennium

Buzzati was a journalist by trade; I do not know what mathematical education he had, but find his ingenuity and mastery impressive.

(By the way, there might be a good programming exercise here, with a graphical interface showing the caravan and the messengers going about their (opposite) business, and controls to vary the parameters and see what happens.)

Another point on which the Prince is delusional is his suspicion that he would have fared better by selecting more than 7 messengers, a number he now finds “ridiculously low”. It would have cost him more money but not helped him much, since the number of messengers only affects the initial value in the geometric progression: T0 in [2]. What truly matters is the exponential multiplier Kn, where the constant K  — defined as (m + 1) / (m – 1) — is always greater than 1, inexorably making the Tn values take off to dazzling heights by the law of compound interest  (the delight of investors and curse of borrowers).

Obviously, as m goes to infinity that constant K = (m + 1) / (m – 1)  approaches its limit 1. Concretely, what messenger speed would it take for the Prince’s scheme to work to his satisfaction? The story indicates that the caravan covers 40 leagues a day; that is about 160 kilometers (see here). Ambitious but feasible (8 hours a day excluding the inevitable stops, horses on trot); in any case, I would trust Buzzati, not just because people in the 1930s had a much more direct informal understanding of horse-based travel than we do, but mostly because of his own incredible attention to details. So they are going at about 20 kilometers per hour. Now assume that for the messengers, instead of horses that only go 50% faster than the caravan, he has secured a small fleet of Cessna-style individual planes. They might fly at 180 km/h. That’s m = 9, nine times faster. Hence now K = 10 / 8 = 1.25. So we only lose 25% on each return trip; planes or no planes, the law of compound interest takes its revenge on the prince all the same, only a bit later.

VN:F [1.9.10_1130]
Rating: 10.0/10 (2 votes cast)
VN:F [1.9.10_1130]
Rating: +1 (from 1 vote)

The Seven Messengers

A number of years ago I discovered the short stories of the Italian writer Dino Buzzati (most famous for his novel translated as The Desert of the Tartars). They have a unique haunting quality, for which the only equivalent which I can summon is Mahler’s Des Knaben Wunderhorn or perhaps the last variation of the Tema Con Variazoni in Mozart’s Gran Partita. I was particularly fascinated by the first one, I Sette Messaggeri (The Seven Messengers) in a collection entitled La Boutique del Mistero (The Mystery Boutique, Mondadori, first published in 1968 although I have a later softcover edition). I resolved to translate it. I completed the translation only now. It starts like this:

Day after day, having set out to explore my father’s realm, I am moving further away from the city, and the dispatches that reach me become ever more infrequent.

I began the journey not long after my thirtieth birthday and more than eight years have since passed; to be exact, eight years, six months and fifteen days of unceasing travel. I believed, when I departed, that within a few weeks I would easily have reached the confines of the kingdom, but instead I have continued to encounter new people and new lands, and, everywhere, men who spoke my own language and claimed to be my subjects.

At times I think that my geographer’s compass has gone awry and that while always believing to be heading south we may in reality have gone into circles, stepping back into our tracks without increasing the distance from the capital city; such might be the reason why we have not yet reached the outer frontier.

More often, though, I am tormented by a suspicion that the frontier may not exist, that the realm spreads out without any limit whatsoever, and that no matter how far I advance I will never arrive at its end. I set off on my journey when I was already past thirty years old, too late perhaps. My friends, and even my family, were mocking my project as a pointless sacrifice of the best years of my life. In truth, few of my faithful followers consented to leave with me. Insouciant as I was – so much more than now! – I was anxious to maintain communication, during the journey, with those dear to me, and among the knights in my escort I chose the seven best ones to serve as my messengers.

I believed, without having given it more thought, that seven would be more than enough. With the passing of time I have realized that this number was, to the contrary, ridiculously low; this even though none among them has fallen ill, or run into bandits, or exhausted his mounts. All seven have served with a tenacity and a devotion that I will find it hard ever to recompense.

To distinguish more easily between them, I assigned them names with initial letters in alphabetical order: Alexander, Bartholomew, Cameron, Dominic, Emilian, Frederic, Gregory.

Not being used to straying so far away from my home, I dispatched the first, Alexander, at the end of the second evening of our journey, when we had already traveled some eighty leagues. The next evening, to ensure the continuity of communications, I sent out the second one, then […]

That is only the beginning. The full text appears here but it is password-protected. Here is why: in 2010 I managed to locate the right holders and wrote to them asking for permission to publish an English translation and put it on the web. I received a polite, negative answer. So I gave up. Browsing around more recently, though, I found two freely available translations on the Web. (I also found the original Italian text here, although with a few differences from the published version.) All for the better, you would say, except that one of the translations is in my opinion awful and the other not that much better. Buzzati is a stylist in the tradition of Flaubert, in whose texts you quickly notice (especially when translating) that every word is exactly the right one, the only possible one, at the only possible place in the only possible sentence. You cannot translate a Buzzati story as you would an article in today’s paper. You have at least to try to respect the music of the text. So I completed my own attempt after all, but I still don’t want to violate anyone’s copyright. (Perhaps I am being silly.) In any case, though, I can certainly publish a fair-use extract as above and use the text for myself and my colleagues and friends. So if you want access just ask me.

One unique feature of the Seven Messengers is that it is a geek’s delight: it is actually based on a mathematical series. I wrote an analysis of the underlying math, but to avoid spoiling your pleasure if you want to look at it by yourself first I put it in a separate entry of this blog. Click here only if you do want the spoiler.

VN:F [1.9.10_1130]
Rating: 10.0/10 (1 vote cast)
VN:F [1.9.10_1130]
Rating: 0 (from 0 votes)