Headline of a recent article in the Financial Times, part of a supplement on “Investing in Germany”:
Germany’s coffers are overflowing but optimism is wearing thin
Oh, the humanity!
On reflection, though, better than the other way around.
Software engineering, programming methodology, languages, verification, general technology, publication culture, and more
Headline of a recent article in the Financial Times, part of a supplement on “Investing in Germany”:
Germany’s coffers are overflowing but optimism is wearing thin
Oh, the humanity!
On reflection, though, better than the other way around.
The character of Ubu, created by Alfred Jarry (1873-1907), deserves to be better known. The Wikipedia entry on Jarry’s 1896 play Ubu Roi (Ubu the King) explains:
According to Jane Taylor, “the central character is notorious for his infantile engagement with his world. Ubu inhabits a domain of greedy self-gratification”. Jarry’s metaphor for the modern man, he is an antihero — fat, ugly, vulgar, gluttonous, grandiose, dishonest, stupid, jejune, voracious, greedy, cruel, cowardly and evil …
“There is”, wrote Taylor, “a particular kind of pleasure for an audience watching these infantile attacks. Part of the satisfaction arises from the fact that in the burlesque mode which Jarry invents, there is no place for consequence. While Ubu may be relentless in his political aspirations, and brutal in his personal relations, he apparently has no measurable effect upon those who inhabit the farcical world which he creates around himself. He thus acts out our most childish rages and desires, in which we seek to gratify ourselves at all cost”.
The derived adjective ubuesque is recurrent in French and francophone political debate.
The AutoProof technology pursues the goal of “Verification As a Matter Of Course”, integrated into the EVE development environment. (The AutoProof project page here; see particularly the online interactive tutorial.) A one-day workshop devoted to the existing AutoProof and current development will take place on October 1 near Toulouse in France. It is an informal event (no proceedings planned at this point, although based on the submissions we might decide to produce a volume), on a small scale, designed to bring together people interested in making the idea of practical verification a reality.
The keynote will be given by Rustan Leino from Microsoft Research, the principal author of the Boogie framework on which the current implementation of AutoProof relies.
For submissions (or to attend without submitting) see the workshop page here. You are also welcome to contact me for more information.
In spite of all the interest in both agile methods and MOOCs (Massive Open Online Courses) there are few courses on agile methods; I know only of some specialized MOOCs focused on a particular language or method.
I produced for EdX, with the help of Marco Piccioni, a new MOOC entitled Agile Software Development. It starts airing today and is supported by exercises and quizzes. The course uses some of the material from my Agile book.
Registration is free and open to anyone at this address.
Many robotics applications are by nature concurrent; in his ongoing PhD work, Andrey Rusakov  is building a comprehensive concurrent robot programming framework, Roboscoop , based on the SCOOP model for simple concurrent object-oriented programming  and the Ros operating system. As part of this work it is important to know how much robotics applications use concurrency, stay away from concurrency — perhaps because programmers are afraid of the risks — and could benefit from more concurrency. Rusakov has prepared a questionnaire  to help find out. If you have experience in robot programming, please help him by answering the questionnaire, which takes only a few minutes.
 Rusakov’s home page here.
 Roboscoop project page, here,
 Simple Concurrent Object-Oriented Programming, see here.
 The questionnaire is here.
The 2016 session of the LASER summer school, now in its 13th edition, has just been announced. The theme is new for the school, and timely: software for robotics. Below is the announcement.
School site: here
The 2016 LASER summer school will be devoted to Software for Robotics. It takes place from 10 to 18 September in the magnificent setting of the Hotel del Golfo in Procchio, Elba Island, Italy.
Robotics is progressing at an amazing pace, bringing improvements to almost areas of human activity. Today’s robotics systems rely ever more fundamentally on complex software, raising difficult issues. The LASER 2016 summer school both covers the current state of robotics software technology and open problems. The lecturers are top international experts with both theoretical contributions and major practical achievements in developing robotics systems.
The LASER school is intended for professionals from the industry (engineers and managers) as well as university researchers, including PhD students. Participants learn about the most important software technology advances from the pioneers in the field. The school’s focus is applied, although theory is welcome to establish solid foundations. The format of the school favors extensive interaction between participants and speakers.
The speakers include:
Organized by Politecnico di Milano, the school takes place at the magnificent Hotel del Golfo (http://www.hoteldelgolfo.it/) in Golfo di Procchio, Elba. Along with an intensive scientific program, participants will have time to enjoy the natural and cultural riches of this history-laden jewel of the Mediterranean.
For more information about the school, the speakers and registration see here.
— Bertrand Meyer
(A version of this article also appeared on the CACM blog.)
Many months ago I accepted, perhaps too fast, a kind invitation to talk at the European Computer Science Summit, the annual conference of Informatics Europe, this week in Vienna. It came with a catch: I was not to choose my own topic but to talk on an imposed theme, ethics in relation to computer science.
As the summer advanced, I became increasingly worried about the talk. What was I going to say? For a nerd, an invited lecture on a free topic is easy: talk about how alias analysis makes automatic frame inference possible, explain the bizarre mixture of the best and worst in agile methods, present a simple method of concurrent programming, describe an environment enabling common mortals to prove programs correct, reflect on our 13-year experience of teaching programming and the supporting MOOCs, and so on. All straightforward stuff which one can present in one’s sleep. But ethics!
The summer receded, but the worry did not. What in the world would I talk about?
From the deepest of my heart: thank you, Volkswagen.
A third ACM webinar this year (after two on agile methods): I will be providing a general introduction to Design by Contract. The date is this coming Thursday, September 17, and the time is noon New York (18 Paris/Zurich, 17 London, 9 Los Angeles, see here for hours elsewhere). Please tune in! The event is free but requires registration here.
Sometimes it is better not to know French. You will never quite get what Voltaire, Molière, Beauvoir, Zola, Hugo and Proust really mean and what Carmen and Faust really sing. But at least you will not find out what the Marseillaise really says. It is France’s national anthem and, according to a site dedicated to it, marseillaise.org, “believed by many to be the most stirring of all anthems“. Stirring, sure. Until you pay attention to the words.
I wrote an article on this blog, in French, proposing to shed the Marseillaise from its worst parts. A few people asked me to provide an English version; here it is. A rendition rather than a translation.
July the 14th, “Bastille day”, was France’s national holiday, and the opportunity for singing the Marseillaise. Politicians in towns large and small make a point of intoning it, in tune or (more often) out of it. One assumes — rather, one hopes — that occasionally they feel some embarrassment. You see, they understand French. The rest of the world hears the music, apparently good enough to have led such diverse composers as Rossini, Tchaikovsky, Schumann and Beethoven to cite it in their own works, and has the luxury of ignoring the words. Better so. Here are some of the gems (in my almost literal translation, all those I found on the Web are awful):
It’s us versus tyranny
We have raised our blood-stained flag
Do you hear, in the countryside,
The howling of these ferocious soldiers?
They come to snatch our sons and wives from our arms
And slit their throats
and the triumphal part of the chorus:
Let’s march, let’s march!
Let an impure blood
Soak the grooves of our fields!
So kind and welcoming.
What makes someone’s blood so impure that every patriot must take as his sacred duty to spill floods of it?
As a matter of fact, it happened, three quarters of a century ago. Hundreds of thousands of French people learned that their blood was now officially non-conformant. There are a few more episodes of that kind in the country’s history. They are not, to put it politely, the most glorious, and not the most appropriate to recall for celebration in the national anthem.
In the days before the festivities, hearing a 7-year old sing (in tune) the impure blood that must soak the grooves, I wondered what kind of thoughts such slogans can evoke among schoolchildren, who are instructed to memorize them and sing along. What about the blood-stained flag? What about the tyrants (Matteo Renzi? Mario Draghi?) who unleash on us their ferocious soldiers, not only to howl, but to snatch, from our arms, our sons and our wives, and slit their throats?
It is time to reform this racist and hateful song.
We need not quarrel about history. The song had a role. The revolution faced enemies, it was defending itself. When we commemorate that revolution today, we think not of Robespierre and the murder of Lavoisier (the creator of modern chemistry, whose executors famously explained that “the republic has no use for scientists“); we think of its message of liberty and fraternity. Enough blood, battles, ferocity. Sing what unites us today.
A national anthem should not, of course, be changed every year as a response to changes in fashion. By nature, it will always be a bit off. But after two hundred and thirteen years of existence, including one hundred and thirty-six of service as national anthem, it is time to shed the Marseillaise of the most shameful remnants of its original text. The music will stay; but the words must adapt to today’s France, which does not whine about a troubled past but looks forward to a bright future.
Only weak peoples seek unity only through the detestation of others. Their songs are full of rejection and negation. Strong peoples, for their part, invoke positive images. Which phrase better projects the proud attitude of a nation that believes in its destiny: “it’s us versus tyranny“, or “with us, marches democracy”? “Their impure blood” or “our pure hearts”? “Slit throats” or “admire”? Be the judge.
There have been proposals for alternative Marseillaises before, but they tend to be mirror images of the original, falling into their own excesses, such as a rabidly anti-militaristic version which can only exacerbate divisions. We will not gain anything by replacing ancient grievances by modern insults.
The following version, illustrated below by the first verse and the chorus (and given in a literal English translation not meant for singing, whereas the French text respects the prosody and versification of the original Marseillaise) pursues a different goal: not antagonizing people, but uniting them; highlighting not differences, but affinities; and allowing everyone to bellow it: with no shame; instead, with pride.
Children of the fatherland, come along
The day of glory has come
With us, marches democracy
We have raised our shining flag.
Do you hear, in the countryside,
The murmur of those envious peoples?
They come to our towns and mountains
And cannot stop admiring them.
Let us make our union stronger!
Let our pure hearts
Vibrate in unison.
[This blog is normally in English, but today’s article is particularly relevant to French speakers. The topic: freeing a national anthem of its hateful overtones.]
Mardi dernier quatorze juillet, une fois de plus, la Marseillaise a retenti un peu partout. C’est le jour où les hommes politiques s’essayent à l’entonner, juste ou (plus souvent) faux. On peut s’imaginer, en fait on espère, qu’ils sont ici et là un peu gênés. “D’un sang impur, abreuve les sillons!“. Vraiment ? Qu’est-ce qui rend un sang si impur que tout bon patriote ait le devoir de le faire jaillir ?
Certes, c’est arrivé, il y a trois quarts de siècle, quand on a soudain avisé des centaines de milliers de Français que leur sang était désormais classé non conforme. Il y a quelques autres épisodes de ce genre dans l’histoire du pays ; ce ne sont pas — pour dire les choses poliment — les plus reluisants, et certainement pas ceux que le chant national devrait glorifier.
À entendre ces jours-ci une petite tête blonde de sept ans chanter (juste) le sang impur qui doit abreuver les sillons, je me suis demandé quelles pensées ces slogans pouvaient bien éveiller pour les enfants des écoles à qui l’on enjoint de les répéter en choeur. Et l’étendard sanglant ? Et les tyrans (Matteo Renzi ? Mario Draghi ?) qui nous envoient leurs féroces soldats non seulement mugir mais, jusque dans nos bras, égorger nos fils, nos compagnes?
Il est temps de réformer ce chant raciste et haineux. Qu’il ait joué son rôle n’est pas la question. La révolution avait ses ennemis, elle se défendait. Quand nous l’invoquons aujourd’hui, cette révolution, ce n’est pas à Robespierre et à l’assassinat de Lavoisier (la république n’a pas besoin de savants) que nous devrions faire appel, mais à son message de liberté et de fraternité. Assez de sang, de batailles, de férocité. Place à ce qui nous définit vraiment aujourd’hui.
Il ne s’agit pas de changer tous les ans d’hymne national en réponse aux modes. Il sera toujours, par nature, un peu déphasé. Mais après deux cent treize ans de Marseillaise, dont cent trente-six ans de service continu comme chant officiel du pays, il est temps de se séparer des relents les plus honteux de son texte d’origine. La musique restera, assez bonne pour avoir été reprise par Schumann, Tchaikowsky, Beethoven, Rossini et bien d’autres ; mais les paroles doivent être adaptées à ce qu’est la France moderne, tournée vers l’avenir.
Seuls les peuples faibles ne savent s’unir qu’à travers la détestation des autres. Leurs chants sont emplis de rejets et de négations. Les peuples forts s’appuient, eux, sur des images positives. Quelle formule projette le mieux l’attitude fière d’une nation confiante en son avenir : “contre nous, de la tyrannie“, ou “avec nous, la démocratie” ? “Un sang impur” ou “nos coeurs purs” ? “Égorger” ou “admirer” ?Jugez-en.
Il existe des Marseillaises alternatives, mais souvent elles ne sont que le miroir de la première, avec leurs propres excès ; voir par exemple cette version sympathique de prime abord mais d’un anti-militarisme qui ne peut que diviser encore. Point n’est besoin de remplacer les anciens cris par des insultes nouvelles.
La version qui suit — chantable, respectant la métrique, et dont je fournirai les autres couplets si elle provoque autre chose que des invectives — a un tout autre but : non pas diviser, mais réunir ; attiser non pas les différences mais les affinités ; et permettre à chacun de la chanter à pleine voix : sans honte ; au contraire, avec fierté.
Allons enfants de la patrie
Le jour de gloire est arrivé
Avec nous la démocratie
L’étendard vaillant est levé (bis)
Entendez-vous, dans les campagnes,
Frémir tous ces peuples envieux ?
Ils viennent, jusque sous nos cieux,
Admirer nos villes, nos montagnes.
Ensemble, citoyens !
Renforçons notre union !
Que nos cœurs purs
Vibrent à l’unisson.
Most people in technology, trade, research or education work in an international environment and need to use a foreign language which they learned at some earlier stage . It is striking to see how awfully most of us perform. International conferences are a particular pain; many speakers are impossible to understand. You just want to go home and read the paper — or, often, not.
Teachers — English teachers in the case of the most commonly used international language — often get the blame, as in “They teach us Shakespeare’s English instead of what we need for today’s life“, but such complaints are unfounded: look at any contemporary language textbook and you will see that it is all about some Svetlanas or Ulriches or Natsukos meeting or tweeting their friends Cathy and Bill.
It is true, though, that everyone teaches languages the wrong way.
There is only one way to teach languages right: start with the phonetics. Languages were spoken  millennia before they ever got written down. The basis of all natural languages is vocal. If you do not pronounce a language right you do not speak that language. It is unconscionable for example that most of us non-native speakers, when using English, still have an accent. We should have got rid of its last traces by age 12.
I cannot understand why people who are otherwise at the vanguard of intellectual achievement make a mess of their verbal expression, seemingly not even realizing there might be a problem. Some mistakes seem to be handed out from generation to generation. Most French speakers of English, for example, pronounce the “ow” of “allow” as in “low”, not “cow” (it took a long time before a compassionate colleague finally rid me of that particular mistake, and I don’t know how many more I may still be making); Italians seem to have a particular fondness for pronouncing as a “v” the “w” of “write”; an so on.
The only place I ever saw that taught languages right was a Soviet school for interpreters. Graduating students of French, having had no exposure to the language before their studies, spoke it like someone coming out of a Métro station. (Actually they spoke more like a grandmother coming out of the Métro, since they had little access to contemporary materials, but that would have been easy to fix.) The trick: they spent their entire first year doing phonetics, getting the “r”and the “u” and so on right, shedding the intonation of their native tongue. That year was entirely devoted to audio practice in a phonetics lab. At the end of it they did not know the meaning of what they were saying,but they said it perfectly. Then came a year of grammar, then a year of conversation. Then came the Métro result. (This is not an apology of the Soviet Union. Someone there just happened to get that particular thing right.)
We should teach everyone this way. There is no reason to tolerate phonetic deviations. If you do not get the sounds exactly as they should be, everything else will be flawed. Take, for example, the “r”. If, like me, you cannot roll your “r”s, then when you try to speak Russian or Italian, even if you think you can get the other sounds right you don’t because your tongue or palate or teeth are in the wrong place. Another example is the “th” sound in English (two distinct sounds in fact) which I never got right. I can fake it but then something else comes out wrong and I still sound foreign. My high-school teachers — to whom I owe gratitude for so much else — should have tortured me until my “th”s were perfect. True, teaching time is a fixed-pie problem, but I am sure something else could have been sacrificed. Since, for example, I can answer in a blink that seven times nine is sixty-three, I must at some stage have taken the time to memorize it. In retrospect I would gladly sacrifice that element of knowledge, which I can reconstruct when needed, for the ability to roll my “r”s.
Age is indeed critical. While we humans can learn anything at any time, it is a well-known fact (although the reasons behind it remain mysterious) that until puberty we are malleable and can learn languages perfectly. Witness bilingual and trilingual children; they do not have any accent. But around the time we develop new abilities and desires our brain shuts itself off to that particular skill; from then on we can only learn languages at great pain, with only remote hopes of reaching the proficiency of natives. The time to learn the phonetics of a foreign language, and learn it perfectly, is around the age of nine or ten at the latest. Then, at the age of reason, we should learn the structures — the grammar. Declensions in German, the use of tenses in English. Conversation — Svetlana greeting Cathy — can come later if there is time left. Once you have the basics wired into your head, the rest is trivial.
Focusing children on phonetics as the crucial part of learning a language will also help them shine. Like physical appearance, verbal clarity is an enormous advantage. I must not be the only one in conferences who pays far more attention to the content of an article if the speaker has impeccable pronunciation, innate or learned. Syntax and choice of words come next. Of course substance matters; we have all heard top scientists with accents thicker than a Humvee tire and grammar thinner than a summer dress. Everyone else needs fluency.
Conceivably, someone might object that a year of phonetic drilling is not the most amusing pastime for a 10-year-old. Without even noting that it’s not worse than having to learn to play the violin — where did we ever get the idea that learning should be fun?
As to me, like those who before they die want to get into space, visit the capitals of all countries on earth or reach the top of Mount Everest, I have my dream; it has lesser impact on the environment and depends on me, not on the help of others: just once, I’d like to roll an “r” like a Polish plumber.
 Many native English speakers provide the exception to this observation, since they often do not learn any foreign language beyond “Buon giorno” and “melanzane alla parmigiana”, and hence will probably not see the point of this note.
 And motioned. Sign language as practiced by deaf people (informally before it was codified starting from the 17th century on) is also a potential teaching start.
Programming, wrote Dijkstra many years ago, is a branch of applied mathematics. That is only half of the picture: the other half is engineering, and this dual nature of programming is part of its attraction.
Descriptions of the mathematical side are generally, in my view, too complicated. This article  presents a mathematical theory of programs and programming based on concepts taught in high school: elementary set theory. The concepts covered include:
One of the principal ideas is that a program is simply the description of a mathematical relation. The program text is a rendering of that relation. As a consequence, one may construct programming languages simply as notations to express certain kinds of mathematics. This approach is the reverse of the usual one, where the program text and its programming languages are the starting point and the center of attention: theoreticians develop techniques to relate them to mathematical concepts. It is more effective to start from the mathematics (“unparsing” rather than parsing).
All the results (74 properties expressed formally, a number of others in the text) are derived as theorems from rules of elementary set theory; there are no new axioms whatsoever.
The paper also has a short version , omitting proofs and many details.
After my earlier ACM Webinar on Agile Methods! The Good, the Hype and the Ugly there were so many questions from the audience, left unanswered for lack of time, that a follow-up session has been set up. It will take place tomorrow (Friday, 27 March 2015) at noon New York time (18 Paris/Berlin/Zurich, 5 PM London etc.). Like the first one it is free and you can find the registration information here.
ACM is offering this coming Wednesday a one-hour webinar entitled Agile Methods: The Good, the Hype and the Ugly. It will air on February 18 at 1 PM New York time (10 AM West Coast, 18 London, 19 Paris, see here for more cities). The event is free and the registration link is here.
The presentation is based on my recent book with an almost identical title . It will be a general discussion of agile methods, analyzing both their impressive contributions to software engineering and their excesses, some of them truly damaging. It is often hard to separate the beneficial from the indifferent and the plain harmful, because most of the existing presentations are of the hagiographical kind, gushing in admiration of the sacred word. A bit of critical distance does not hurt.
As you can see from the Amazon page, the first readers (apart from a few dissenters, not a surprise for such a charged topic) have relished this unprejudiced, no-nonsense approach to the presentation of agile methods.
Another characteristic of the standard agile literature is that it exaggerates the contrast with classic software engineering. This slightly adolescent attitude is not helpful; in reality, many of the best agile ideas are the direct continuation of the best classic ideas, even when they correct or adapt them, a normal phenomenon in technology evolution. In the book I tried to re-place agile ideas in this long-term context, and the same spirit will also guide the webinar. Ideological debates are of little interest to software practitioners; what they need to know is what works and what does not.
Actually not that new: this paper  was published in August of last year. It is part of Christian Estler’s work for this PhD thesis, defended a few weeks ago, and was pursued in collaboration with Martin Nordio and Carlo Furia. It received the best paper award at the International Conference on Global Software Engineering; in fact this was the third time in a row that this group received the ICGSE award, so it must have learned a few things about collaborative development.
The topic is an issue that affects almost all software teams: how to make sure that people are aware of each other’s changes to a shared software base, in particular to avoid the dreaded case of a merge conflict: you and I are working on the same piece of code, but we find out too late, and we have to undergo the painful process of reconciling our conflicting changes.
The paper builds once again on the experience of our long-running “Distributed and Outsourced Software Engineering” course project, where students from geographically spread universities collaborate on a software development . It relies on data from 105 student developers making up twelve development teams located in different countries.
The usual reservations about using data from students apply, but the project is substantial and the conditions not entirely different from those of an industrial development.
The study measured the frequency and impact of merge conflicts, the effect of insufficient awareness (no one told me that you are working on the same module that I am currently modifying) and the consequences for the project: timeliness, developer morale, productivity.
Among the results: distribution does not matter that much (people are not necessarily better informed about their local co-workers’ developments than about remote collaborators); lack of awareness occurs more often than merge conflicts, and causes more damage.
 H-Christian Estler, Martin Nordio, Carlo A. Furia and Bertrand Meyer: Awareness and Merge Conflicts in Distributed Software Development, in proceedings of ICGSE 2014, 9th International Conference on Global Software Engineering, Shanghai, 18-21 August 2014, IEEE Computer Society Press (best paper award), see here.
 Distributed and Outsourced Software Engineering course and project, see here. (The text mentions “DOSE 2013” but the concepts remains applicable and it will be updated.)
Among the open problems of verification, particularly the verification of object-oriented programs, one of the most vexing is framing: how to specify and verify what programs element do not change. Continuing previous work, this article presents a “double frame inference” method, automatic on both sides the specification and verification sides. There is no need to write frame specifications: they will be inferred from routine postconditions. For verification, the method computes the set of actually changed properties through a “change calculus”, itself based on the previously developed alias calculus.
Some verification techniques, such as Hoare-style proofs, require significant annotation effort and potentially yield full functional verification; others, such as model checking and abstract interpretation, have more limited goals but seek full automation. Framing, in my opinion, should be automatic, freeing the programmer-verifier to devote the annotation effort to truly interesting properties.
 Bertrand Meyer: Framing the Frame Problem, in Dependable Software Systems, Proceedings of August 2014 Marktoberdorf summer school, eds. Alexander Pretschner, Manfred Broy and Maximilian Irlbeck, NATO Science for Peace and Security, Series D: Information and Communication Security, Springer, 2015 (to appear), pages 174-185; preprint available here.
To verify sequential programs, we have to prove that they do the right thing, but also that they do it within our lifetime — that they terminate. The termination problem is considerably harder with concurrent programs, since they add a new form of non-termination: deadlock. A set of concurrent processes or threads will deadlock if they end up each holding a resource that another wants and wanting a resource that another holds.
There is no general solution to the deadlock problem, even a good enough general solution. (“Good enough” is the best we can hope for, since like many important problems deadlock is undecidable.) It is already hard enough to provide run-time deadlock detection, to be able at least to cancel execution when deadlock happens. The research reported in this new paper  pursues the harder goal of static detection. It applies to an object-oriented context (specifically the SCOOP model of concurrent OO computation) and relies fundamentally on the alias calculus, a static alias analysis technique developed in previous publications.
The approach is at its inception and considerable work remains to be done. Still, the example handled by the paper is encouraging: analyzing two versions of the dining philosophers problem and proving — manually — that one can deadlock and the other cannot.
 Bertrand Meyer: An automatic technique for static deadlock prevention, in PSI 2014 (Ershov Informatics Conference), eds. Irina Virbitskaite and Andrei Voronkov, Lecture Notes in Computer Science, Springer, 2015, to appear.; draft available here.
I write a sentence, but Microsoft Word’s indefatigable grammar checker catches me:
I see! Word underlined “well-argued” in blue because the hyphen is bad style. Thanks! I choose the obligingly provided correction (just click the first menu entry). “Well argued“. Then:
In support of his view of software methodology, Leslie Lamport likes to use the example of non-recursive Quicksort. Independently of the methodological arguments, his version of the algorithm should be better known. In fact, if I were teaching “data structures and algorithms” I would consider introducing it first.
As far as I know he has not written down his version in an article, but he has presented it in lectures; see . His trick is to ask the audience to give a non-recursive version of Quicksort, and of course everyone starts trying to remove the recursion, for example by making the stack explicit or looking for invertible functions in calls. But his point is that recursion is not at all fundamental in Quicksort. The recursive version is a specific implementation of a more general idea.
Lamport’s version — let us call it Lampsort —is easy to express in Eiffel. We may assume the following context:
a: ARRAY [G -> COMPARABLE] — The array to be sorted.
pivot: INTEGER — Set by partition.
picked: INTEGER_INTERVAL — Used by the sorting algorithm, see below.
partition (i, j: INTEGER)
……..require — i..j is a sub-interval of the array’s legal indexes:
……..……..i < j
……..……..i >= a.lower
……..……..j <= a.upper
……..……..… Usual implementation of partition …
……..ensure — The expected effect of partition:
……..……..pivot >= i
……..……..pivot < j
……..……..— a [i..j] has been reshuffled so that elements in i..pivot are less than
……..……..— or equal to those in pivot+1 .. j.
We do not write the implementation of partition since the point of the present discussion is the overall algorithm. In the usual understanding, that algorithm consists of doing nothing if the array has no more than one element, otherwise performing a partition and then recursively calling itself on the two resulting intervals. The implementation can take advantage of parallelism by forking the recursive calls out to different processors. That presentation, says Lamport, describes only a possible implementation. The true Quicksort is more general. The algorithm works on a set of integer intervals; in Eiffel:
intervals: SET [INTEGER_INTERVAL]
It initializes intervals to contain a single element, the entire interval; at each iteration, it removes an interval from the set, partitions it if that makes sense (i.e. the interval has more than one element), and inserts the resulting two intervals into the set. It ends when the set is empty. Here it is:
……..from — Initialize interval set to contain a single interval, the array’s entire index range:
……..…..create intervals.make_one (a.lower |..| a.upper)…. ..……..
……..…..— See below
……..…..intervals.is_empty — Stop when there are no more intervals in set
……..…..picked := intervals.item — Pick an interval from (non-empty) interval set.
……..……if picked.count > 1 then — (The precondition of partition holds, see below.)
……..……..…..partition (picked.lower, picked.upper) — Split it, moving small items before and large ones after pivot.
……..……..…..intervals.extend (picked.lower |..| pivot) — Insert new intervals into interval set: first
……..……....…intervals.extend (pivot + 1 |..| picked.upper) — and second.
……..…...intervals.remove (picked) — Remove interval that was just partitioned.
Eiffel note: the function yielding an integer interval is declared in the library class INTEGER using the operator |..| (rather than just ..).
The query item from SET, with the precondition not is_empty, returns an element of the set. It does not matter which element. In accordance with the Command-Query Separation principle, calling item does not modify the set; to remove the element you have to use the command remove. The command extend adds an element to the set.
The abstract idea behind Lampsort, explaining why it works at all, is the following loop invariant (see  for a more general discussion of how invariants provide the basis for understanding loop algorithms). We call “slice” of an array a non-empty contiguous sub-array; for adjacent slices we may talk of concatenation; also, for slices s and t, s <= t means that every element of s is less than or equal to every element of t. The invariant is:
a is the concatenation of the members of a set slices of disjoint slices, such that:
– The elements of a are a permutation of its original elements.
– The index range of any member of slices having more than one element is in intervals.
– For any adjacent slices s and t (with s before t), s <= t.
The first condition (conservation of the elements modulo permutation) is a property of partition, the only operation that can modify the array. The rest of the invariant is true after initialization (from clause) with slices made of a single slice, the full array. The loop body maintains it since it either removes a one-element interval from intervals (slices loses the corresponding slice) or performs partition with the effect of partitioning one slice into two adjacent ones satisfying s <= t, whose intervals replace the original one in intervals. On exit, intervals is empty, so slices is a set of one-element slices, each less than or equal to the next, ensuring that the array is sorted.
The invariant also ensures that the call to partition satisfies that routine’s precondition.
The Lampsort algorithm is a simple loop; it does not use recursion, but relies on an interesting data structure, a set of intervals. It is not significantly longer or more difficult to understand than the traditional recursive version
sort (i, j: INTEGER)
……..……..i <= j
……..……..i >= a.lower
……..……..j <= a.upper
……..……if j > i then — Note that precondition of partition holds.
……..……..…..partition (i, j) — Split into two slices s and t such that s <= t.
……..……..…..sort (i, pivot) — Recursively sort first slice.
……..……..…..sort (pivot+1, j) — Recursively sort second slice.
Lampsort, in its author’s view, captures the true idea of Quicksort; the recursive version, and its parallelized variants, are only examples of possible implementations.
I wrote at the start that the focus of this article is Lampsort as an algorithm, not issues of methodology. Let me, however, give an idea of the underlying methodological debate. Lamport uses this example to emphasize the difference between algorithms and programs, and to criticize the undue attention being devoted to programming languages. He presents Lampsort in a notation which he considers to be at a higher level than programming languages, and it is for him an algorithm rather than a program. Programs will be specific implementations guided in particular by efficiency considerations. One can derive them from higher-level versions (algorithms) through refinement. A refinement process may in particular remove or restrict non-determinism, present in the above version of Lampsort through the query item (whose only official property is that it returns an element of the set).
The worldview underlying the Eiffel method is almost the reverse: treating the whole process of software development as a continuum; unifying the concepts behind activities such as requirements, specification, design, implementation, verification, maintenance and evolution; and working to resolve the remaining differences, rather than magnifying them. Anyone who has worked in both specification and programming knows how similar the issues are. Formal specification languages look remarkably like programming languages; to be usable for significant applications they must meet the same challenges: defining a coherent type system, supporting abstraction, providing good syntax (clear to human readers and parsable by tools), specifying the semantics, offering modular structures, allowing evolution while ensuring compatibility. The same kinds of ideas, such as an object-oriented structure, help on both sides. Eiffel as a language is the notation that attempts to support this seamless, continuous process, providing tools to express both abstract specifications and detailed implementations. One of the principal arguments for this approach is that it supports change and reuse. If everything could be fixed from the start, maybe it could be acceptable to switch notations between specification and implementation. But in practice specifications change and programs change, and a seamless process relying on a single notation makes it possible to go back and forth between levels of abstraction without having to perform repeated translations between levels. (This problem of change is, in my experience, the biggest obstacle to refinement-based approaches. I have never seen a convincing description of how one can accommodate specification changes in such a framework without repeating the whole process. Inheritance, by the way, addresses this matter much better.)
The example of Lampsort in Eiffel suggests that a good language, equipped with the right abstraction mechanisms, can be effective at describing not only final implementations but also abstract algorithms. It does not hurt, of course, that these abstract descriptions can also be executable, at the possible price of non-optimal performance. The transformation to an optimal version can happen entirely within the same method and language.
Quite apart from these discussions of software engineering methodology, Lamport’s elegant version of Quicksort deserves to be known widely.
 Lamport video here, segment starting at 0:32:34.
 Carlo Furia, Bertrand Meyer and Sergey Velder: Loop invariants: Analysis, Classification and Examples, in ACM Computing Surveys, September 2014, preliminary text here.
Our online course Computing: Art, Magic, Science, available from EdX, opens this Tuesday (tomorrow, 30 September) at 9 AM Zurich time (and at this time in your area).
An earlier article on this blog described the course, which integrates ten years of experience teaching introductory programming at ETH, and takes advantage of remote-compilation and remote-execution technology from our distributed development research.
You can find the course here.
The Paris computer science bookstore Le Monde en Tique is organizing, this coming Friday, Oct. 3, starting at 5 PM, a signing session for my book Agile! The Good, the Hype and the Ugly .
About the book (for readers new to this site): it provides a cold-blooded analysis of agile methods and examines their claims, their value and their limitations.
Le Monde en Tique is well known to technology aficionados in Paris and far beyond. Jean Demétreaux and his team established it at a time when it was hard, slow and expensive to order technical books from international publishers. While other legendary bookstores such a Stacey’s in San Francisco had to close in response to competition from chain stores and Internet offerings, le Monde en Tique (a pun on “tique” words such as informatics and bureautics, and also on ICT, in French TIC) has found new markets and lives on. It is set in a historic building in the medieval heart of Paris . They already organized such book signings for the publication of the French translation of Object-Oriented Software Construction  and of Touch of Class, the latter reported in this blog . If you are nearby, please come on Friday!
 Book signing announcement with access instructions: here.
 Bertrand Meyer: Conception et Programmation Orientées Objet (translation of Object-Oriented Software Construction, 2nd edition, Prentice Hall), Eyrolles, Paris 2008, book page here.
 Knuth and Company, article on this blog, 19 October 2009, see here.
The French National Research Center (CNRS) has just awarded  its annual gold medal to Gérard Berry, a great recognition for an outstanding computer scientist. I first discovered Berry’s work through a brilliant 1976 article, Bottom-Up Computation of Recursive Programs , which explained recursion using methods of denotational semantics, and should really figure in collections of classic CS articles. One can hardly understand dynamic programming algorithms, for example, without realizing that they are bottom-up versions of recursive algorithms, through transformations described in the article. I relied extensively on its techniques for my own textbooks, from the advanced concepts of Introduction to the Theory of Programming Languages all the way down to the introductory presentation of recursion in Touch of Class.
Berry then went on to play a founding role in synchronous languages, explaining (in a paper whose reference I don’t have right now) that he went through a revelation of sorts after realizing that the automatic-control industry needed languages completely different from those computer scientists typically love. He created the Estérel language and shepherded it all the way to industrialization, serving as Chief Scientist of Estérel Technologies in the 2000 decade, before coming back to research.
He is also well known in France as a popularizer of informatics (computer science) through a number of successful books aiming at a large audience. He was appointed the first professor of informatics at the Collège de France, and in his inaugural lecture series presented a sweeping description of how information technology advances, based on powerful scientific concepts, permeate today’s world and raise ever new challenges. Hardly could the CNRS have chosen to distinguish a better representative of our discipline.
 CNRS announcement: here.
 Gérard Berry, Bottom-Up Computation of Recursive Programs, in RAIRO (Revue Française d’Automatique, Informatique, Recherche Opérationnelle, Informatique Théorique), tome 10, no R1 (1976), pp. 47-82, available here.
The IEEE’s Harlan Mills award is the principal prize in software engineering. The 2014 recipients are Patrick and Radhia Cousot, recognized for their groundbreaking work on abstract interpretation; Patrick will receive the award at ICSME 2014 on Oct. 1st. The list of previous recipients is here.
I have the privilege of serving as the current committee chair; the deadline for nomination is October 15. Please nominate your favorite software engineering grandee! You can find more information and the nomination form here.
First week of semester at ETH. The number of incoming informatics (computer science) students has reached an all-time high: 345; see the (bad-quality) picture from day one of “Introduction to Programming”. (And no, the gender distribution has not changed.) So much for fears that MOOCs and such will displace universities; in fact we have not one but two MOOCs to support the course. Computer science is back in fashion!
My colleagues and I have just finished recording our new MOOC (online course), an official ETH offering on the EdX platform. The preview is available  and the course will run starting in September.
As readers of this blog know, I have enthusiastically, under the impulsion of Marco Piccioni at ETH, embraced MOOC technology to support and spread our courses. The particular target has been the introduction to programming that I have taught for over a decade at ETH based on the Touch of Class textbook . In February this blog announced  the release of our first MOOC, embodying the essentials of our ETH course and making it available not only to ETH students but to the whole world. The course does not just include video lectures: it also supports active student participation through online exercises and programs that can be compiled and tested on the cloud, with no software installation. These advanced features result from our research on support for distributed software development (by Christian Estler and Martin Nordio, with Carlo Furia and others).
This first course was a skunkworks project, which we did entirely on our own without any endorsement from ETH or any of the main MOOC players. We and our students have very much benefited from the consequent flexibility, and the use of homegrown technology relying on the MOODLE framework. We will keep this course for our own students and for any outside participant who prefers a small-scale, “boutique” version. But the EdX brand and EdX’s marketing power will enable us to reach a much broader audience. We want to provide the best introductory computing course on the market and the world needs to know about it. In addition, the full support of media services at ETH helped us reach a higher standard on the technical side. (For our first course, the home-brewed one, we did not have a studio, so that every time an ambulance drove by — our offices are close to the main Zurich hospital — we had to restart the current take.)
The course’s content is not exactly the same: we have broadened the scope from just programming to computing, although it retains a strong programming component. We introduced additional elements such as an interview with Professor Peter Widmayer of ETH on the basics of computer science theory. For both new material and the topics retained from the first version we have adapted to the accepted MOOC practice of short segments, although we did not always exactly meet the eight-minute upper limit that was suggested to us.
We hope that you, and many newcomers, will like the course and benefit from it.
 EdX course: Computing: Art, Magic, Science, preview available here.
 Bertrand Meyer: Touch of Class: Learning how to Program Well, with Objects and Contracts, Springer Verlag, revised printing, 2013, book page here.
 Learning to Program, Online: article from this blog, 3 February 2014, available here.
One of the most improvable characteristics of scientific papers is the graphical presentation of numerical data. It is sad to see that thirty years after Tufte published the first edition of his masterpiece  many authors are still including grossly inaccurate graphics. Sadder still when the authors are professional graphists, who should know better. Take this chart  from the last newsletter of Migros, Switzerland’s largest supermarket chain. To convince Swiss people that they should not worry about their food bills, it displays the ratio of food expenses to revenue in various countries. There would be many good ways to represent this information graphically, but someone thought it clever to draw variable-size coins of the respective currencies. According to the text, “the bigger the circle, the larger the income’s share devoted to food“.
Just a minor problem: the visual effect is utterly misleading. Taking three examples from the numbers given, the ratio is roughly 10% for Switzerland, 30% for Russia, 40% for Morocco. And, sure enough, compared to the Swiss coin in the figure, the Russian coin is about three times bigger and the Moroccan coin four times… in diameter! What the eye sees, of course, is the area. Since the area varies as the square of the diameter, one gets the impression that Russians spend nine times, not three, and Moroccans sixteen times, not four, as much as the Swiss.
To convey the correct suggestion, the diameter of the Russian coin should have been about 73% larger than the Swiss coin’s diameter (the square root of three is about 1.73) , and the diameter of the Moroccan coin twice larger, that is to say half of what it is.
The impression is particularly misleading for countries where the ratio, unlike in Russia or Morocco, is close to Switzerland’s. Most interestingly, although no doubt by accident, for neighboring countries, where Swiss people are prone to go shopping in search of a bargain, a practice that possibly does not enthuse Migros. The extra percentage devoted to food (using this time no longer rough approximations but precise values from the figures given in the Migros page) is 4% for Austria (10.9 ratio vs Switzerland’s 10.2), 8% for Germany (11.1), 30% for France (13.3) and 43% for Italy (14.6). But if you look at the picture the circles suggest much bigger differences; for example the Italian circle is obviously computed from the ratio of the squares, 14.62 / 10.62, showing an increase of 104%. In other words, Italians proportionally devote to food a little over two-fifths more than the Swiss, but the graph suggests they spend twice as much.
On the premise that one should not ascribe to malevolence what can be explained by ignorance, I hope the Migros graphists will get a copy of Tufte’s book for their future endeavors.
Read Tufte too if you want the pictures in your papers to be not just attractive but accurate.
 Edward R. Tufte: The Visual Display of Quantitative Information, Graphics Press, second edition, 2001. See his site here.
 “How much do we spend to feed ourselves?” on the Migros site, available here for the French version (replace “fr” in the URL by “de” for German and “it” for Italian, I did not see an English version). Click on the figure for a readable version.
EiffelStudio releases are semi-annual, end of May and end of November. Release 14-05 just came out. The next release (14-11) is entirely devoted to documentation. We are hoping for extensive community involvement in this first-time Eiffel Documentation Drive.
Many people regularly comment that there is not enough Eiffel and EiffelStudio documentation, and some of what exists is not good enough. We have decided to tackle the problem seriously, hence the dedication of an entire release cycle to documentation. The term is taken here in a broad sense: “documentation” means what is at http://docs.eiffel.com, but also everything else that can help understand Eiffel, for example updating Wikipedia entries on topics for which Eiffel has something to offer.
Anyone with an understanding of an Eiffel-related topic can help. We particularly need help from two (non-disjoint) categories of contributors
The process will involve reviewing, so if you are an Eiffelist with moderate taste for writing, or a good writer with incomplete knowledge of Eiffel, we need your help anyway; someone else will compensate for the missing side. In particular, a common criticism is that some of the documentation was written by developers who do not have English as their mother tongue; if you can help improve it everyone will benefit. Of course if you are good at both technology and writing it’s even better.
We are mentioning English because it is the first target, but documentation in other languages, either original or a translation of existing English pages, is needed too.
Here is how the Eiffel Documentation Drive works:
Each row includes among its fields the following: topic, link to existing documentation, volunteer writer(s), planned completion, volunteer reviewer(s).
The full Eiffel Software team will participate – as noted above, improving the documentation is the strategic goal for the release – but we hope for considerable community participation. Please help make EiffelStudio documentation shine as much as the environment itself.
InfoWorld is currently publishing a series of programming language assessments:
Notable in these articles is what they do not mention: Eiffel has most of what the author misses in Objective-C and Java; and most of what Swift “stole” it stole from Eiffel.
In this article let us concentrate on the nine Objective-C complaints, by Peter Wayner ; subsequent articles will examine the Java “hates” and the Swift “steals”.
“Objective-C lovers tout that Objective-C is a strict superset of C: If you can do it in C, you should be able to do it in Objective-C. But it doesn’t go the other way, so you’re stuck wondering, “Should I use an Objective-C method description or a C one?” Achieving portability to C programs requires constant vigilance and forethought.”
This is what happens when you mix language paradigms. Eiffel has a close relationship with C, but the two sides are clearly separated. You can call C from Eiffel, and the other way around. You can declare an Eiffel routine as “external C” and even include the C code inline: in other words an Eiffel “method description” can have a C implementation. The structure is always object-oriented (no need to fear that a novice programmer will revert to a C style for the design) but for access to low-level system mechanisms and small functions that should be optimized to the byte and microsecond you use C directly, in its ideal role.
“For all its object-oriented coolness, you don’t get much else from Objective-C. It’s more of a way to organize your code for large systems than a way to write better code. You’re still responsible for pointers. You’re still responsible for keeping track of memory. “
Eiffel is object-oriented all the way. You are not “responsible for pointers“. References are tame: no pointer arithmetic. You are not “responsible for keeping track of memory“: objects are garbage-collected
“The C programmers loved to call their software a ‘portable assembly code’, and the same is true for Objective-C … except it’s only portable from the Mac to the iPad.”
“Portable assembly code” is exactly what C provides, and hence an excellent target for an Eiffel compiler. As to Eiffel, it runs on all platforms, from Windows to Linux to Solaris to VMS to the Mac.
Criticism 3: Stuck in the 80’s
“Parachute pants, big hair, ‘The Breakfast Club’ — and the NeXT machine: Objective-C is like a time machine in programming-language land.”
Eiffel has undergone constant evolution, innovating on all fronts of programming constructs and integrating the best of known techniques.
“The primitives aren’t first-class citizens. Garbage collection, that wonderful idea that sustained Lisp, was adopted by Java ages ago. Objective-C got it in 2006. The same goes for properties and closures.”
All this has been in Eiffel forever. Agents (closures) were introduced in 1999, long before Java, C# and other OO languages had anything of the sort. Eiffel’s assigner commands are vastly superior to properties (no need to write all these boring getter functions).
“The cool modern kids writing Python, Ruby, and CoffeeScript can craft billion-dollar companies without using brackets, braces, and parentheses. You’ll be wearing out your punctuation keys writing Objective-C. Colons, at-signs, asterisks? Is there any character that the language doesn’t use?”
Come on. How can one be so misinformed? The semicolon has been optional in Eiffel for fifteen years. The high-priest style of C, Objective-C, Java, C# and so many others, with its piling up of strange symbols, is something that Eiffel users never had to suffer.
Not modern syntax, that is:
“Objective-C”s syntax is like Coke: They tried to modernize it in the ’90s, but it never stuck.”
Eiffel’s syntax is clear and simple. Total beginners, including high-school students, pick it up just as easily and naturally as advanced programmers, and as application experts who want to concentrate on their problem, not on learning strange language conventions going back to the nineteen-sixties.
Here Eiffel does not provide what the journalist wants: it is “post-namespaces” (as in “postmodern”). The Eiffel community has decided that the complexity of namespaces was not worth the trouble (what happens when you move packages around?) and prefers simple mechanisms for resolving class name clashes.
” Variety is the spice of life. It’s even more important in a world where not everything is an iPhone. If a Windows or Linux shop recruits you, you can forget all of those extra Objective-C extensions you learned because they’ll be of no use.”
Eiffel is not tied to any manufacturer, computer architecture or operating system. If a new processor comes out, or a user needs an exotic platform, a port can usually be produced in a matter of hours. The compiler and the entire environment to which it belongs, EiffelStudio, are written in Eiffel; the supporting runtime is in a highly portable form of C, which requires very little customization, if any, for a new platform. (Here “the compiler” means the Eiffel Software implementation, but other implementations also put a strong emphasis on portability.)
“In the Objective-C world, you get really only one choice. Why do you need to be different, comrade?”
Besides EiffelStudio other compilers and tools are available for Eiffel.
“Do you want to give out more than 100 copies of your iPhone app? Forget it. Do you want to “think different” with your UI? Please go back and read the user interface guidelines. You can’t do anything without Apple’s permission because Apple uses strong crypto to lock down everything — and fanatically tyrannical policies to lock down the rest.”
The Eiffel language definition is steered by a standards committee under Ecma (the organization behind many of the major standards in IT), which anyone can join. EiffelStudio itself is available in open source. The Eiffel world knows nothing like the close control Apple exerts over its product; it welcomes all contributors.
Maybe someone should talk to Mr. Wayner and help him broaden his scope of programming language knowledge.
 Peter Wayner, 9 Things We Hate About Objective-C, InfoWorld, 4 June 2014, available here.
It is remarkable that almost half a century after Dijkstra’s goto article, and however copiously and reverently it may be cited, today’s programs (other than in Eiffel) are still an orgy of gotos. There are not called gotos, being described as constructs that break out of a loop or exit a routine in multiple places, but they are gotos all the same. Multiple routine exits are particularly bad since they are in effect interprocedural gotos.
Ian Joyner has just released a simple and cogent summary of why routines should always have one entry and one exit.
 Ian Joyner: Single-entry, single-exit (SESE) heuristic, available here.