Bertrand Meyer's technology+ blog

A Galois connection (for anyone not familiar with the concept, the Wikipedia entry is decent)  between two partially ordered sets consists of two total functions f: A → B and g: B → A such that for  all a: A and b: B

(f (a)  ≤  b)    ⇔    (g  (b)  ≥  a)

The simplest and most common example uses powersets and inclusion: for some sets X and Y, A is ℙ (X), the set of subsets of X, and B is ℙ (Y); the ≤ order relation is simply ⊆, inclusion between subsets. So the condition is that for arbitrary subsets a and b of X and Y:

(f (a)  ⊆  b)    ⇔    (g  (b)  ⊇  a)

Pictorially:

A Galois connection between powersets

(Instead of starting with total functions f and g between  ℙ (X) and ℙ (Y) you may also use possibly partial functions f’ : A -|-> B and g’ : B -|-> A, and use for f and g the associated image functions, which are total.)

Now you might think that this post continues with abstract interpretation or some such topic, but what I really want to talk about is dictionaries. Bilingual dictionaries. You need them if you are learning a language, and they would seem to be the ideal application for computers, including shirt-pocket computers (more commonly known as smartphones). Hyperlinking frees us from the tyranny of page turning and makes dictionary browsing an exciting and entirely new experience: you can type partial words and see them completed, make mistakes and see them corrected, discover a new word and see it memorized into the interactive equivalent of flashcards. If in the definition of a word you see another that catches your attention, in either the source or the target language, you can click it and see its own definition. You can travel back and forth, retain your browsing history, and test yourself repeatedly.

Unfortunately, what I have described is only the theory. Current electronic bilingual dictionaries — at least those I tried, but I tried quite a few, involving a variety of languages — fall short of this ideal. In addition, they are typically of rather bad linguistic quality as compared to their print competitors.

An example of a seemingly fundamental requirement that every bilingual dictionary should satisfy (and that dictionaries on the market fail to meet), is that the relationship it defines between two languages must  be a Galois connection, both ways. If you are looking for the translation of a word or group of words a in X, and obtain a set b of equivalents in Y, then it is pretty hard to justify that when you go back the translations for b do not include a!

I have yet, however, to find a Galois dictionary. As an example among hundreds that I encountered in recent months, take the Pons ($30) French-German dictionary. As the names suggest f will be the function yielding the French translation of a set of German words and g  the German translation of a set of French words. Now g {(“approximation“)}  includes “Näherungswert“; but then f ({“Näherungswert“}) only lists “Valeur approchée“!

The Galois requirement is not just a matter of principle; it makes the dictionary useful for native speakers of either language. If, as here,  g  (b)  ⊆  a but (f (a) ⊉    b), and a includes  the most common words in Y for the concepts at hand, the native Y speaker may find the right translation (Näherungswert is indeed pretty good for approximation in the mathematical usage of this word),  but the native speaker of X will be misled. Indeed valeur approchée is not  the best term for the concept of mathematical approximation in French.

More generally, the reader who is trying to master both of the dictionary’s languages will be cheated. Such a reader wants to use the dictionary not just to get quick translations (there’s Google and Bing Translate for that), but to gain deep insights into the languages and their correspondence. How can one learn without the ability to check translations back and forth?

I wrote to Pons to report this problem (and others). To their great credit they took the trouble to answer my message in detail; but here is their tack on the issue:

“As far as the choice of headwords for the source and the target language is concerned, PONS always is doing this choice for each language volume separatedly as we the dictionaries are made for special target groups and in different sizes we have to make a choice of words and this is done with regard to the importance a word has in each language – source and target language – and not by simply changing source and target language. This special elaboration of headword lists for each language can imply that a word which can be found in one volume of the dictionary is not necessarily part of the other volume.”

I am not sure I understand what this means, but I am much too kind to wish upon dictionary authors, if they do not fix their systems, the sad fate of Évariste Galois.

Email is fast and convenient. It is also risky. Here are three common sources of incidents with email. They are not new, but they keep biting even the most experienced email users.

1. Risks of using Bcc

Alice writes to Bob. She wants Carol to know what she wrote, but she does not want Bob to know that she is keeping Carol informed. So she copies Carol in the form of a “Blind carbon copy” (Bcc). The Bcc mechanism is meant exactly for such situations: while Bcc recipients see the list of other recipients (To and Cc), these other recipients see no mention of Bcc recipients.

Now Carol sees the messages and responds to Alice. But to respond she uses, perhaps inadvertently, “Reply all”. The reply goes to both Alice and Bob. All of Alice’s efforts to keep mum about Carol’s involvement are lost!

The risk in this situation is that Alice has no way to control what Carol may do. At issue here is not a conscious effort by Carol to break confidentiality: in that case Alice could do nothing anyway as soon as she has sent Carol the information. The worrying possibility is that Carol may use “Reply all” by mistake.

Rule 1 (temporary): never use Bcc. Alice should send the message to Bob only, and forward a copy separately to Carol alone.

I start with this form of the rule because it is easy to remember and usually appropriate, but in one case it is too strong. Remove Bob from the picture. Then if Carol is a  person, it is pointless for Alice to use Bcc for her, rather than To (or Cc), since Carol knows everything there is to know. But now assume that Carol is actually the name of a mailing list. Members of the mailing list should know the originator, Alice, but they should not know about each other, or even about the name of the list. If these are the constraints, there is no risk in using Bcc. Hence the revised version of the rule:

Rule 1 (final): never use Bcc except for all recipients of a message.

Indeed what was wrong in the first example was not the use of Bcc as such, but the mix with To (or Cc). Bcc must be used only for either all the recipients of a message or none of them.

2. Risks of not using Bcc

Very recent case (today, actually) from the refereeing process of a prestigious computer science conference. The program chair sends to all authors of submitted papers,  say <submitters@famous_computer_science_conference.org>, a general message about the refereeing process. But he uses that address in the “To” or “Cc” field, not “bcc”.

One author, say Alice, has a question about the process and responds to the message, inadvertently using “Reply all”. Then:

• Everyone knows that Alice has submitted a paper.
• Many of the other authors are away and have “automatic reply” set up. So Alice herself now knows the names of quite a few other members of the community who have submitted papers!

“famous_computer_science_conference.org” is the most important conference in its field, and essentially every researcher in that community submits at least one paper every year. Knowing who has submitted is confidential information. That information becomes interesting a few months later, when the conference program is published and you find out that Bob tried and was not accepted. All the more juicy information, of course, if Bob is a senior (and arrogant) researcher.

Rule 2: when a mailing list includes people who should not know who else is on the list, either set up the list so that only the administrators can post to it, or use Bcc (respecting Rule 1, in its final form).

3. The importance of not being Allison

Another common risk, which strikes all the time, is automatic address completion by email clients (Outlook, Thunderbird etc.). You type part of the name or address of a frequent correspondent, and the system completes the email address.  So convenient! Except when the completion is wrong and you do not check it.

I frequently receive email that was misaddressed because of unchecked completion. (The latest case was last week.) Here is an example of completion that was expected but did not happen. A few years ago, in an institution of which I was then a member, a high-level executive wanted to send to her secretary the results of a job candidate’s evaluation. Highly confidential stuff. The secretary was called Allison and had an address of the form <allison@our_department.com>. The executive was used to typing just all and relying on address completion. Somehow, that particular time the completion did not occur; perhaps she was not using her familiar email setup. As a result the message went to <all@our_department.com>, that is to say, everyone in the organization. The recipients were, of course, delighted to get the inside story on the candidate.

Rule 3:

• Always check the recipient addresses visually and carefully.
• Never hire a secretary called Allen, Allison or Allistair.

There is so much fervor around cloud computing that no one seems to note the downsides. Here is a little cautionary story.

Like many people, I have come to rely increasingly, for collaborative work, on Google Docs. As a text editor it is a kind of primitive Word. But it is web-based, so that several people can share a document. They will not just have read access, but can all write into the document, even at the same time. The system is indeed pretty good at incorporating changes by different users, as long as they do not affect the exact same place in the document. It also uses a modern approach to version management, originally popularized by wikis: a built-in history mechanism saves your successive revisions, enabling you to go back to any previous version. That mechanism is not ideal (the level of granularity is too small, so that it takes a long time to locate an earlier version), but it does provide safety.

In principle, indeed, safety is one of the great advantages of a cloud-based approach: you don’t have — so the mantra goes — to worry about backups, or even about saving your document; you don’t even need any local storage; everything is recorded on the server. If you make a mistake, or simply want to recover some piece of your text that you had discarded, just go back far enough in the history. “Control-S” (save the document) still exists, presumably for the sake of users born in the twentieth century, but it is just redundant.  With the cloud, we are told, you no longer need to save. Just write your stuff, the theory goes: the infrastructure is taking care of remembering your steps.

Thus indeed does the theory go. Reality does not always follow theory. For example, the reality  will not follow the theory if the implementation has bugs.

One beautiful evening some weeks ago I was busy polishing a technical note, and enjoying the Google Docs diagramming facilities that I had just discovered — basic, but good enough to prepare figures to illustrate a technical document. In fact the core of my document was a complex technical diagram, which I had spent several hours to develop. Then I prepared another, much simpler diagram, basically a couple of rectangles and an arrow between them. At that point I wanted to make sure my valuable efforts were not lost and, somewhat instinctively (I was born in the 20th century) I saved; if I had not, the system would have done it for me anyway. Under my very eyes, the page redisplayed, with the figures — there were 5 or 6 of them altogether — all turned into an identical one, the trivial little diagram I had entered last. After a moment of panic I realized that the history would be there, so I could at least go back to a recent version with the appropriate figures; relax, this is the cloud, the server is keeping my history for me! No such luck, though: all the figures in all the earlier versions had been overwritten in the same way. Gone forever.

At that point I realized I must have hit a major bug. Of course I am a programmer and could more or less guess what kind of bug this could be: a reference assignment instead of a clone, or maybe, in Eiffel terms, a clone rather than a deep_clone. (As far as I know Google is not using Eiffel; I’ll let the reader decide whether to jump from correlation to causation.) As to the history, any decent implementation stores “diffs”  rather than full copies, so if an object has changed but it is still at the same place the reference is the same: there is no “diffs” to store.

Guessing the programming error provided little consolation: my brilliant diagram was lost for humankind. Just to check that the bug was real I tried a couple of times to modify one of the figures again, in a small way; sure enough, all figures in the document immediately redisplayed to an identical version, the one I had just produced. The software was obviously broken.

I decided not to take any more risks and recreated the figures in a Word document, then prepared screen shots and included them in the Google Doc. It was rather painful to redo everything but at least I knew that I would have to redo it just once. In the process I did not forget to type Control-S every once in a while, with the same feeling of warmth and safety as if revisiting a treasured childhood home, carefully  maintained by the grandparents away from the fads and bustle of the big city.

I do not know if there is customer support for Google Docs; if there is, it is not obvious. In any case it is a free service, so one has little ground to complain. I happen, however, to have friends in high places, and through them was able in just a few hours to reach the Google engineers in charge. They reacted very promptly, confirmed it was a bug,  and corrected it. They were very kind and valiantly tried to recover my figures; but at least they had corrected the problem, sparing many other users from an experience that, indeed, I do not recommend.

While preparing this note I had some further contacts with Google engineers, who commented:

“At Google we use logging, on disk snapshots, replicated storage, tape backups, and other systems to deliver massively redundant data protection. In the rare cases of bugs like this one, where user data is impacted, we continue to have a consistent and impressive track-record in successfully recovering that data.”

There is an uplifting moral to the story: the bug was fixed in a matter of hours. Most Google Docs users probably did not notice it. A bug of similar severity, in a traditional product that gets released and sent out to users, would have required a new release and a new download. On the cloud it is enough to fix the server copy.

Other lessons, however, are less encouraging.

First, one may surmise that the very process of an official release in a traditional product mode, and the resulting heightened impact of bugs, lead to a more careful Quality Assurance process than the  “forever beta” culture of cloud-based deployment. I have no evidence that my bug story was due to an unsatisfactory QA process. It may just be a one-time blip. But the temptation definitely exists in a cloud-based project to lower one’s guard because of the expectation, conscious or not, that any error will be found by some user and promptly corrected for all users.

An even more scary observation is that on the cloud you are trusting everything to a provider and its software, correct or not, robust or not, secure or not. The recurring leaks of customer information from  Web sites are a constant reminder of that risk. In the text processing example, any user of a text editor or document processing knows that, if he saves his work once in a while, possible damage if the tool crashes or misbehaves is circumscribed: at worst, you will lose the changes since the last save. When working on the cloud, you typically do not make local copies: if a tool messes up and loses the record, you have lost everything. It is gone for good.

In technology we have hype, buzzwords, fads, and successful advances. These are not necessarily disjoint categories, but often successive steps in the life of  a new ideas.   What characterizes the transition from a fad to a successful technology is that in the latter case one knows clearly both the advantages and the drawbacks. Cloud computing is advanced enough to reach that stage.

It’s the implementation that counts


There was a young girl in Carmel
Who scolded her suitor, called Mel:
“Enough foreplay, now play!
I am not made of clay!
Give me code and not just UML.”

Rereading an article from last year’s August New Yorker, a discussion of e-paper devices and especially the Kindle by Nicholson Baker [1]:

Reading some of “Max,” a James Patterson novel, I experimented with the text-to-speech feature. The robo-reader had a polite, halting, Middle European intonation, like Tom Hanks in “The Terminal,” and it was sometimes confused by periods. Once it thought “miss.” was the abbreviation of a state name: “He loved the chase, the hunt, the split-second intersection of luck and skill that allowed him to exercise his perfection, his inability to Mississippi.” I turned the machine off.

Reference

Nicholson Baker: A New Page, in The New Yorker, August 3, 2009, pages 24-30, also available at http://www.newyorker.com/reporting/2009/08/03/090803fa_fact_baker?currentPage=all.

In the next few days I will post a few comments about a topic of particular relevance to the future of our field: empirical software engineering. I am starting by reposting two entries originally posted in the CACM blog. Here is the first. Let me use this opportunity to mention the LASER summer school [1] on this very topic — it is still possible to register.

Empirical software engineering papers, at places like ICSE (the International Conference on Software Engineering), used to be terrible.

There were exceptions, of course, most famously papers by Basili, Zelkowitz, Rombach, Tichy, Berry, Humphrey, Gilb, Boehm, Lehmann, Belady and a few others, who kept hectoring the community about the need to base our opinions and practices on evidence rather than belief. But outside of these cases the typical ICSE empirical paper — I sat through a number of them — was depressing: we made these measurements in our company, found these results, just believe us. A question here in the back? Can you reproduce our results? Access our code? We’d love you to, but unfortunately we work for a company — the Call for Papers said industry contributions were welcome, didn’t it? — and we can’t give you the details. So sorry. But trust us, we checked our results.

Actually, there was another kind of empirical paper, which did not suffer from such secrecy: the university study. Hi, I am professor Bright, the well-known author of the Bright method of software development. Everyone knows it’s the best, but we wanted to assess it scientifically through a rigorous empirical study. I gave the same programming problem to two groups of third-year undergraduates; one group was told to use the Bright method, the other not. Guess what? The Bright group performed 67.94% better! I see the session chair wanting to move to the next speaker; see the details in the paper.

For years, this was most of what we had: unverifiable industry reports and unconvincing student experiments.

And suddenly the scene has changed. Empirical software engineering studies are in full bloom; the papers are flowing, and many are good!

What triggered this radical change is the availability of open-source repositories. Projects such as Linux, Eclipse, Apache, EiffelStudio and many others have records going back 10, 15, sometimes 20 years. These records contain the true history of the project: commits (into the configuration management system), bug reports, bug fixes, test runs and their results, developers involved, and many more elements of project data. All of a sudden empirical research has what any empirical science needs: a large corpus of objects to analyze.

Open-source projects have given the decisive jolt, but now we can rely on industrial data as well: Microsoft and other companies have started making their own records selectively available to researchers. In the work of authors such as Zeller from Sarrebruck, Gall from Uni. Zurich or Nagappan from Microsoft, systematic statistical techniques yield answers, sometimes surprising, to questions on which we could only speculate. Do novices or experts cause more bugs? Does test coverage correlate with software quality, and if so, positively or negatively? Little by little, we are learning about the true properties of software products and processes, based not on fantasies but on quantitative analysis of meaningful samples.

The trend is unmistakable, and irreversible.

Not all is right yet; in the second installment of this post I will describe some of what still needs to be improved for empirical software engineering to achieve full scientific rigor.

Reference

[1] LASER summer school 2010, at http://se.ethz.ch/laser.

The software world is not flat; it is multipolar. Gone are the days of one-site, one-team developments. The increasingly dominant model today is a distributed team; the place where the job gets done is the place where the appropriate people reside, even if it means that different parts of the job get done in different places.

This new setup, possibly the most important change to have affected the practice of software engineering in this early part of the millennium,  has received little attention in the literature; and even less in teaching techniques. I got interested in the topic several years ago, initially by looking at the phenomenon of outsourcing from a software engineering perspective [1]. At ETH, since 2004, Peter Kolb and I, aided by Martin Nordio and Roman Mitin, have taught a course on the topic [2], initially called “software engineering for outsourcing”. As far as I know it was the first course of its kind anywhere; not the first course about outsourcing, but the first to explore the software engineering implications, rather than business or political issues. We also teach an industry course on the same issues [3], attended since 2005 by several hundred participants, and started, with Mathai Joseph from Tata Consulting Services, the SEAFOOD conference [4], Software Engineering Advances For Outsourced and Offshore Development, whose fourth edition starts tomorrow in Saint Petersburg.

After a few sessions of the ETH course we realized that the most important property of the mode of software development explored in the course is not that it involves outsourcing but that it is distributed. In parallel I became directly involved with highly distributed development in the practice of Eiffel Software’s development. In 2007 we renamed the ETH course “Distributed and Outsourced Software Engineering” (DOSE) to acknowledge the broadened scope. The topic is still new; each year we learn a little more about what to teach and how to teach it.

The 2007 session saw another important addition. We felt it was no longer sufficient to talk about distributed development, but that students should practice it. Collaboration between groups in Zurich and other groups in Zurich was not good enough. So we contacted colleagues around the world interested in similar issues, and received an enthusiastic response. The DOSE project is itself distributed: teams from students in different universities collaborate in a single development. Typically, we have two or three geographically distributed locations in each project group. The participating universities have been Politecnico di Milano (where our colleagues Carlo Ghezzi and Elisabetta di Nitto have played a major role in the current version of the project), University of Nijny-Novgorod in Russia, University of Debrecen in Hungary, Hanoi University of Technology in Vietnam, Odessa National Polytechnic in the Ukraine and (across town for us) University of Zurich. For the first time in 2010 a university from the Western hemisphere will join: University of Rio Cuarto in Argentina.

We have extensively studied how the projects actually fare (see publications [4-8]). For students, the job is hard. Often, after a couple of weeks, many want to give up: they have trouble reaching their partner teams, understanding their accents on Skype calls, agreeing on modes of collaboration, finalizing APIs, devising a proper test plan. Yet they hang on and, in most cases, succeed. At the end of the course they tell us how much they have learned about software engineering. For example I know few better way of teaching the importance of carefully documented program interfaces — including contracts — than to ask the students to integrate their modules with code from another team halfway around the globe. This is exactly what happens in industrial software development, when you can no longer rely on informal contacts at the coffee machine or in the parking lot to smooth out misunderstandings: software engineering principles and techniques come in full swing. With DOSE, students learn and practice these fundamental techniques in the controlled environment of a university project.

An example project topic, used last year, was based on an idea by Martin Nordio. He pointed out that in most countries there are some card games played in that country only. The project was to program such a game, where the team in charge of the game logic (what would be the “business model” in an industrial project) had to explain enough of their country’s game, and abstractly enough, to enable the other team to produce the user interface, based on a common game engine started by Martin. It was tough, but some of the results were spectacular, and these are students who will not need more preaching on the importance of specifications.

We are currently preparing the next session of DOSE, in collaboration with our partner universities. The more the merrier: we’d love to have other universities participate, including from the US. Adding extra spice to the project, the topic will be chosen among those from the ICSE SCORE competition [9], so that winning students have the opportunity to attend ICSE in Hawaii. If you are teaching a suitable course, or can organize a student group that will fit, please read the project description [10] and contact me or one of the other organizers listed on the page. There is a DOSE of madness in the idea, but no one, teacher or student,  ever leaves the course bored.

References

[1] Bertrand Meyer: Offshore Development: The Unspoken Revolution in Software Engineering, in Computer (IEEE), January 2006, pages 124, 122-123. Available here.

[2] ETH course page: see here for last year’s session (description of Fall 2010 session will be added soon).

[3] Industry course page: see here for latest (June 2010( session (description of November 2010 session will be added soon).

[4] SEAFOOD 2010 home page.

[5] Bertrand Meyer and Marco Piccioni: The Allure and Risks of a Deployable Software Engineering Project: Experiences with Both Local and Distributed Development, in Proceedings of IEEE Conference on Software Engineering & Training (CSEE&T), Charleston (South Carolina), 14-17 April 2008, ed. H. Saiedian, pages 3-16. Preprint version  available online.

[6] Bertrand Meyer:  Design and Code Reviews in the Age of the Internet, in Communications of the ACM, vol. 51, no. 9, September 2008, pages 66-71. (Original version in Proceedings of SEAFOOD 2008 (Software Engineering Advances For Offshore and Outsourced Development,  Lecture Notes in Business Information Processing 16, Springer Verlag, 2009.) Available online.

[7] Martin Nordio, Roman Mitin, Bertrand Meyer, Carlo Ghezzi, Elisabetta Di Nitto and Giordano Tamburelli: The Role of Contracts in Distributed Development, in Proceedings of SEAFOOD 2009 (Software Engineering Advances For Offshore and Outsourced Development), Zurich, June-July 2009, Lecture Notes in Business Information Processing 35, Springer Verlag, 2009. Available online.

[8] Martin Nordio, Roman Mitin and Bertrand Meyer: Advanced Hands-on Training for Distributed and Outsourced Software Engineering, in ICSE 2010: Proceedings of 32th International Conference on Software Engineering, Cape Town, May 2010, IEEE Computer Society Press, 2010. Available online.

[9] ICSE SCORE 2011 competition home page.

[10] DOSE project course page.

More than once I have emphasized here [1] [2] the urgency of rules requiring systematic a posteriori analysis of software mishaps that have led to disasters. I have a feeling that many more posts will be necessary before the idea registers.

Some researchers are showing the way. In a June 2009 article [4], Tetsuo Tamai from the University of Tokyo published a fascinating dissection of the 2005 Mizuo Securities incident at the Tokyo Stock Exchange, where market havoc resulted from a software fault that prevented proper execution of the cancel command after an employee who wanted to sell one share at 610,000 yen mistakenly switched the two numbers.

I found out only recently about the article while browsing Dines Bjørner’s page and hitting on an unpublished paper [3] where Bjørner proposes a mathematical model for the trading rules. Tamai’s article deserves to be widely read.

References

[1] The one sure way to advance software engineering: this blog, see here.
[2] Dwelling on the point: this blog, see here.
[3] Dines Bjørner: The TSE Trading Rules, version 2, unpublished report, 22 February 2010, available online.
[4] Tetsuo Tamai: Social Impact of Information System Failures, in IEEE Computer, vol. 42, no. 6, June 2009, pages 58-65, available online (with registration); the article’s text is also included in [3].

In response to many requests, I have made available [1] the slides of my education keynote at ICSE earlier this month. The theme was “From programming to software engineering: notes of an accidental teacher”. Some of the material has been presented before, notably at the Informatics Education Europe conference in Venice in 2009. (In research you can give a new talk every month, but in education things move at a more senatorial pace.) Still, part of the content is new. The talk is a summary of my experience teaching programming and software engineering at ETH.

The usual caveats apply: these are only slides (I did not write a paper), and not all may be understandable independently of the actual talk.

Reference

[1] From programming to software engineering: notes of an accidental teacher, slides from a keynote talk at ICSE 2010.

What’s in a URL? To someone who gains access to your computer, your browsing history will provide interesting information. More interesting, in some cases, than you might think.

Try Google Translate, for example. Say you want to translate “To be or not to be, that is the question” into the language of your choice. Go to http://translate.google.com, type your text, select the source language (actually you can skip this step, the tool will detect the language automatically) and the target language (that you will have to do, Google does not read into your mind yet). You get the translation; rather, a Pretty Good Translation, almost never quite right in my experience, but sufficient to give you a Pretty Good Idea. This is the result of modern work in computational linguistics, based on statistics and large-scale data mining rather than a traditional syntax-directed attempt at perfection.

Now look into the URL:

    http://translate.google.com/#auto|sv|To%20be%20or%20not%20to%20be%2C%20that%20is%20the%20question

Your text is encoded in it! This is true even for very long texts. Building up such complex URLs is one of the time-honored techniques for simulating state in the stateless HTTP protocol. But now anyone who sees your browsing history will know the precise texts that interested you enough to make you want to translate them. A Pretty Good Window on your personal interests! And not necessarily something that you want automatically archived.

Google Translate and other translation sites are great tools to facilitate our life, especially when dealing with languages we know superficially or not at all. But maybe there is a way to provide the service without opening such a large window on the detailed questions that occupy our minds?

In the decades since structured programming, many of the advances in software engineering have come out of non-university sources, mostly of four kinds:

• Start-up technology companies  (who played a large role, for example, in the development of object technology).
• Industrial research labs, starting with Xerox PARC and Bell Labs.
• Independent (non-university-based) author-consultants. 
• Independent programmer-innovators, who start open-source communities (and often start their own businesses after a while, joining the first category).

 Academic research has had its part, honorable but limited.

Why? In earlier posts [1] [2] I analyzed one major obstacle to software engineering research: the absence of any obligation of review after major software disasters. I will come back to that theme, because the irresponsible attitude of politicial authorities hinders progress by depriving researchers of some of their most important potential working examples. But for university researchers there is another impediment: the near-impossibility of developing serious software.

If you work in theory-oriented parts of computer science, the problem is less significant: as part of a PhD thesis or in preparation of a paper you can develop a software prototype that will support your research all the way to the defense or the publication, and can be left to wither gracefully afterwards. But software engineering studies issues that arise for large systems, where  “large” encompasses not only physical size but also project duration, number of users, number of changes. A software engineering researcher who only ever works on prototypes will be denied the opportunity to study the most significant and challenging problems of the field. The occasional consulting job is not a substitute for this hands-on experience of building and maintaining large software, which is, or should be, at the core of research in our field.

The bodies that fund research in other sciences understood this long ago for physics and chemistry with their huge labs, for mechanical engineering, for electrical engineering. But in computer science or any part of it (and software engineering is generally viewed as a subset of computer science) the idea that we would actually do something , rather than talk about someone else’s artifacts, is alien to the funding process.

The result is an absurd situation that blocks progress. Researchers in experimental physics or mechanical engineering employ technicians: often highly qualified personnel who help researchers set up experiments and process results. In software engineering the equivalent would be programmers, software engineers, testers, technical writers; in the environments that I have seen, getting financing for such positions from a research agency is impossible. If you have requested a programmer position as part of a successful grant request, you can be sure that this item will be the first to go. Researchers quickly understand the situation and learn not even to bother including such requests. (I have personally never seen a counter-example. If you have a different experience, I will be interested to learn who the enlightened agency is. )

The result of this attitude of funding bodies is a catastrophe for software engineering research: the only software we can produce, if we limit ourselves to official guidelines, is demo software. The meaningful products of software engineering (large, significant, usable and useful open-source software systems) are theoretically beyond our reach. Of course many of us work around the restrictions and do manage to produce working software, but only by spending considerable time away from research on programming and maintenance tasks that would be far more efficiently handled by specialized personnel.

The question indeed is efficiency. Software engineering researchers should program as part of their normal work:  only by writing programs and confronting the reality of software development can we hope to make relevant contributions. But in the same way that an experimental physicist is helped by professionals for the parts of experimental work that do not carry a research value, a software engineering researcher should not have to spend time on porting the software to other architectures, performing configuration management, upgrading to new releases of the operating system, adapting to new versions of the libraries, building standard user interfaces, and all the other tasks, largely devoid of research potential, that software-based innovation requires.

Until  research funding mechanisms integrate the practical needs of software engineering research, we will continue to be stymied in our efforts to produce a substantial effect on the quality of the world’s software.

References

[1] The one sure way to advance software engineering: this blog, see here.
[2] Dwelling on the point: this blog, see here.

Efforts to attract more women to computer science evoke C. Northcote Parkinson’s analysis of the progression of the British Navy after World War I: ever more admirals, ever fewer ships [1]. There have been some successes, notably at Carnegie Mellon [2], but mostly we tear our hair in despair while percentages of female informatics students hover around 10%, less than in the seventies, regardless of how hard we try (one department I know has a full-fledged “Frauenförderung” —women’s promotion — organization, with as much effect on enrollment as if it were hiring admirals).

The best analysis, going beyond the usual pieties and providing concrete recommendations, is the Informatics Europe report by Jan van Leeuwen and Letizia Tanca [3]. Even the simple steps it recommends, however, still face technical difficulties and faculty resistance.

The report was right to concentrate on the image of the discipline. In one of its conclusions, it encourages us to remind the world that “Informatics/Computing provides the science and the technology that underpins the development of today’s digital world”.

Is help coming from some unlikely quarters? Yesterday’s Wall Street Journal describes [4] the campaign for a new personality of the Barbie doll. In a public vote started by Mattel, girls overwhelmingly chose “Barbie the Anchorwoman”; but the vote was open to anyone, and a campaign of women IT professionals led to the triumph of “Barbie the Computer Engineer”, which as a result will be one of the new models. For the little girl in your life, with her special affinity for logic and her special people skills (the harbinger of IT success), it is never too early to place your order.

References

[1] C. Northcote Parkinson: Parkinson’s Law: The Pursuit of Progress, London, John Murray, 1958; see also original article in The Economist.

[2] Joanne McGrath Cohoon: Must there be so few?: including women in CS, , International Conference on Software Engineering, Portland, 2003, pages 668-674, available online (with ACM registration).

[3] Jan van Leeuwen and Letizia Tanca (Eds.): Student Enrollment and Image of the Informatics Discipline, Informatics Europe Report IE-2008-01, October 2008, available online.

[4] Ann Zimmerman: Revenge of the Nerds: How Barbie Got Her Geek On, in the Wall Street Journal, 9 April 2010, currently available online.

I am blogging live from the “Cloud Futures” conference organized by Microsoft in Redmond [1]. We had two excellent keynotes today, by Ed Lazowska [1] and David Patterson.

Lazowska emphasized the emergence of a new kind of science — eScience — based on analysis of enormous amounts of data. His key point was that this approach is a radical departure from “computational science” as we know it, based mostly on large simulations. With the eScience paradigm, the challenge is to handle the zillions of bytes of data that are available, often through continuous streams, in such fields as astronomy, oceanography or biology. It is unthinkable in his view to process such data through super-computing architectures specific to an institution; the Cloud is the only solution. One of the reasons (developed more explicitly in Patterson’s talk) is that cloud computing supports scaling down as well as scaling up. If your site experiences sudden bursts of popularity — say you get slashdotted — followed by downturns, you just cannot size the hardware right.

Lazowska also noted that it is impossible to convince your average  university president that Cloud is the way to go, as he will get his advice from the science-by-simulation  types. I don’t know who the president is at U. of Washington, but I wonder if the comment would apply to Stanford?

The overall argument for cloud computing is compelling. Of course the history of IT is a succession of swings of the pendulum between centralization and delocalization: mainframes, minis, PCs, client-server, “thin clients”, “The Network Is The Computer” (Sun’s slogan in the late eighties), smart clients, Web services and so on. But this latest swing seems destined to define much of the direction of computing for a while.

Interestingly, no speaker so far has addressed issues of how to program reliably for the cloud, even though cloud computing seems only to add orders of magnitude to the classical opportunities for messing up. Eiffel and contracts have a major role to play here.

More generally the opportunity to improve quality should not be lost. There is a widespread feeling (I don’t know of any systematic studies) that a non-negligible share of results generated by computational science are just bogus, the product of old Fortran programs built by generations of graduate students with little understanding of software principles. At the very least, moving to cloud computing should encourage the use of 21-th century tools, languages and methods. Availability on the cloud should also enhance a critical property of good scientific research: reproducibility.

Software engineering is remarkably absent from the list of scientific application areas that speaker after speaker listed for cloud computing. Maybe software engineering researchers are timid, and do not think of themselves as deserving large computing resources; consider, however, all the potential applications, for example in program verification and empirical software engineering. The cloud is a big part of our own research in verification; in particular the automated testing paradigm pioneered by AutoTest [3] fits ideally with the cloud and we are actively working in this direction.

Lazowska mentioned that development environments are the ultimate application of cloud computing. Martin Nordio at ETH has developed, with the help of Le Minh Duc, a Master’s student at Hanoi University of Technology, a cloud-based version of EiffelStudio: CloudStudio, which I will present in my talk at the conference tomorrow. I’ll write more about it in later posts; just one note for the moment: no one should ever be forced again to update or commit.

References

[1] Program of the Cloud Futures conference.

[2] Keynote by Ed Lazowska. You can see his slides here.

[3] Bertrand Meyer, Arno Fiva, Ilinca Ciupa, Andreas Leitner, Yi Wei, Emmanuel Stapf: Programs That Test Themselves. IEEE Computer, vol. 42, no. 9, pages 46-55, September 2009; online version here.

At the ACM Symposium on Applied Computing (SAC) in Sierre last week, I gave a talk entitled “How you will be programming in 10 years”, describing a number of efforts by various people, with a special emphasis on our work at both ETH and Eiffel Software, which I think point to the future of software development. Several people have asked me for the slides, so I am making them available [1].

It occurred to me after the talk that the slogan “Verification As a Matter Of Course” (VAMOC) characterizes the general idea well. The world needs verified software, but the software development community is reluctant  to use traditional heavy-duty verification techniques. While some of the excuses are unacceptable, others sources of resistance are justified and it is our job to make verification part of the very fabric of everyday software development.

My bet, and the basis of large part of both Eiffel and the ETH verification work, is that it is possible to bring verification to practicing developers as a natural, unobtrusive component of the software development process, through the tools they use.

The talk also broaches on concurrency, where many of the same ideas apply; CAMOC is the obvious next slogan.

Reference

[1] Slides of “How you will be programming in 10 years” talk (PDF).

Let me start, dear reader of this blog, by probing your view of equality, and also of assignment. Two questions:  

• Is a value x always equal to itself? (For the seasoned programmers in the audience: I am talking about a value, as in mathematics, not an expression, as in programming, which could have a side effect.)
• In programming, if we consider an assignment

       x := y

and v is the value of y before that assignment (again, this little detour is to avoid bothering with side effects), is the value of x always equal to v after the assignment?  

Maybe I should include here one of these Web polls that one finds on newspaper sites, so that you can vote and compare your answer to the Wisdom of Crowds. My own vote is clear: yes to both. Equality is reflexive (every value is equal to itself, at any longitude and temperature, no excuses and no exceptions); and the purpose of assignment is to make the value of the target equal to the value of the source. Such properties are some of the last ramparts of civilization. If they go away, what else is left?  

754 enters the picture

Now come floating-point numbers and the famous IEEE “754” floating-point standard [1]. Because not all floating point operations yield a result usable as a floating-point number, the standard introduces a notion of “NaN”, Not a Number; certain operations involving floating-point numbers may yield a NaN. The term NaN does not denote a single value but a set of values, distinguished by their “payloads”.  

Now assume that the value of x is a NaN. If you use a programming language that supports IEEE 754 (as they all do, I think, today) the test in  

        if x = x then …  

is supposed to yield False. Yes, that is specified in the standard: NaN is never equal to NaN (even with the same payload); nor is it equal to anything else; the result of an equality comparison involving NaN will always be False.  

Assignment behavior is consistent with this: if y (a variable, or an expression with no side effect) has a NaN value, then after  

        x := y  

the test x = y will yield False. 

Before commenting further let me note the obvious: I am by no means a numerics expert; I know that IEEE 754 was a tremendous advance, and that it was designed by some of the best minds in the field, headed by Velvel Kahan who received a Turing Award in part for that success. So it is quite possible that I am about to bury myself in piles of ridicule. On the other hand I have also learned that (1) ridicule does not kill, so I am game; and more importantly (2) experts are often right but not always, and it is always proper to question their reasoning. So without fear let me not stop at the arguments that “the committee must have voted on this point and they obviously knew what they were doing” and “it is the standard and implemented on zillions of machines, you cannot change it now”. Both are true enough, but not an excuse to censor questions.  

What are the criteria?

The question is: compatibility with an existing computer standard is great, but what about compatibility with a few hundred years of mathematics? Reflexivity of equality  is something that we expect for any data type, and it seems hard to justify that a value is not equal to itself. As to assignment, what good can it be if it does not make the target equal to the source value?  

The question of assignment is particularly vivid in Eiffel because we express the expected abstract properties of programs in the form of contracts. For example, the following “setter” procedure may have a postcondition (expressed by the ensure clause):  

        set_x (v: REAL)
                        — Set the value of x (an attribute, also of type REAL) the value of v.
                do
                        …
                        x := v  
                ensure
                        x = v
                end  

   
If you call this procedure with a NaN argument for a compiler that applies IEEE 754 semantics, and monitor contracts at run time for testing and debugging, the execution will report a contract violation. This is very difficult for a programmer to accept.  

A typical example arises when you have an assignment to an item of an array of REAL values. Assume you are executing a [i] := x. In an object-oriented view of the world (as in Eiffel), this is considered simplified syntax  for the routine call a.put (x, i). The postcondition is that a [i] = x. It will be violated!  

The experts’ view

I queried a number of experts on the topic. (This is the opportunity to express my gratitude to members of the IFIP working group 2.5 on numerical software [2], some of the world’s top experts in the field, for their willingness to respond quickly and with many insights.) A representative answer, from Stuart Feldman, was:  

If I remember the debate correctly (many moons ago), NaN represents an indefinite value, so there is no reason to believe that the result of one calculation with unclear value should match that of another calculation with unclear value. (Different orders of infinity, different asymptotic approaches toward 0/0, etc.)  

Absolutely correct! Only one little detail, though: this is an argument against using the value True as a result of the test; but it is not an argument for using the value False! The exact same argument can be used to assert that the result should not be False:  

… there is no reason to believe that the result of one calculation with unclear value should not match that of another calculation with unclear value.  

Just as convincing! Both arguments complement each other: there is no compelling reason for demanding that the values be equal; and there is no compelling argument either to demand that they be different. If you ignore one of the two sides, you are biased.  

What do we do then?

The conclusion is not that the result should be False. The rational conclusion is that True and False are both unsatisfactory solutions. The reason is very simple: in a proper theory (I will sketch it below) the result of such a comparison should be some special undefined below; the same way that IEEE 754 extends the set of floating-point numbers with NaN, a satisfactory solution would extend the set of booleans with some NaB (Not a Boolean). But there is no NaB, probably because no one (understandably) wanted to bother, and also because being able to represent a value of type BOOLEAN on a single bit is, if not itself a pillar of civilization, one of the secrets of a happy life.  

If both True and False are unsatisfactory solutions, we should use the one that is the “least” bad, according to some convincing criterion . That is not the attitude that 754 takes; it seems to consider (as illustrated by the justification cited above) that False is somehow less committing than True. But it is not! Stating that something is false is just as much of a commitment as stating that it is true. False is no closer to NaB than True is. A better criterion is: which of the two possibilities is going to be least damaging to time-honored assumptions embedded in mathematics? One of these assumptions is the reflexivity of equality:  come rain or shine, x is equal to itself. Its counterpart for programming is that after an assignment the target will be equal to the original value of the source. This applies to numbers, and it applies to a NaN as well. 

Note that this argument does not address equality between different NaNs. The standard as it is states that a specific NaN, with a specific payload, is not equal to itself.  

What do you think?

A few of us who had to examine the issue recently think that — whatever the standard says at the machine level — a programming language should support the venerable properties that equality is reflexive and that assignment yields equality.

Every programming language should decide this on its own; for Eiffel we think this should be the specification. Do you agree?  

Some theory

For readers who like theory, here is a mathematical restatement of the observations above. There is nothing fundamentally new in this section, so if you do not like strange symbols you can stop here.  

The math helps explain the earlier observation that neither True nor False is more“committing” than the other. A standard technique (coming from denotational semantics) for dealing with undefinedness in basic data types, is to extend every data type into a lattice, with a partial order relation meaning “less defined than”. The lattice includes a bottom element, traditionally written “⊥” (pronounced “Bottom”) and a top element written ⊤ (“Top”). ⊥ represents an unknown value (not enough information) and ⊤ an error value (too much information). Pictorially, the lattice for natural numbers would look like this:  

The lattice of integers

On basic types, we always use very simple lattices of this form, with three kinds of element: ⊥, less than every other element; ⊤, larger than all other elements; and in-between all the normal values of the type, which for the partial order of interest are all equal. (No, this is not a new math in which all integers are equal. The order in question simply means “is less defined than”. Every integer is as defined as all other integers, more defined than ⊥, and less defined than ⊤.) Such lattices are not very exciting, but they serve as a starting point; lattices with more interesting structures are those applying to functions on such spaces — including functions of functions —, which represent programs.  

The modeling of floating-point numbers with NaN involves such a lattice; introducing NaN means introducing a ⊥ value. (Actually, one might prefer to interpret NaN as ⊤, but the reasoning transposes immediately.)  More accurately, since there are many NaN values, the lattice will look more like this:

The lattice of floats in IEEE 754

For simplicity we can ignore the variety of NaNs and consider a single ⊤.

Functions on lattices — as implemented by programs — should satisfy a fundamental property: monotonicity. A function f  is monotone (as in ordinary analysis) if, whenever x ≤ y, then f (x) ≤ f (y). Monotonicity is a common-sense requirement: we cannot get more information from less information. If we know less about x than about y, we cannot expect that any function (with a computer, any program) f will, out of nowhere, restore the missing information.  

Demanding monotonicity of all floating-point operations reflects this exigency of monotonicity: indeed, in IEEE 754, any arithmetic operation — addition, multiplication … — that has a NaN as one of its arguments must yield a Nan as its result. Great. Now for soundness we should also have such a property for boolean-valued operations, such as equality. If we had a NaB as the ⊥ of booleans, just like NaN is the ⊥ of floating-point numbers,  then the result of NaN = NaN would be NaB. But the world is not perfect and the IEEE 754 standard does not govern booleans. Somehow (I think) the designers thought of False as somehow less defined than True. But it is not! False is just as defined as True in the very simple lattice of booleans; according to the partial order, True and False are equal for the relevant partial order:

The lattice of booleans

Because any solution that cannot use a NaB will violate monotonicity and hence will be imperfect, we must resort to heuristic criteria. A very strong criterion in favor of choosing True is reflexivity — remaining compatible with a fundamental property of equality. I do not know of any argument for choosing False. 

The Spartan approach

There is, by the way, a technique that accepts booleans as we love them (with two values and no NaB) and achieves mathematical rigor. If operations involving NaNs  truly give us pimples, we can make any such operation trigger an exception. In the absence of ⊥ values,  this is an acceptable programming technique for representing undefinedness. The downside, of course, is that just about everywhere the program must be ready to handle the exception in some way. 

It is unlikely that in practice many people would be comfortable with such a solution. 

Final observations

Let me point out two objections that I have seen. Van Snyder wrote: 

NaN is not part of the set of floating-point numbers, so it doesn’t behave as if “bottom” were added to the set. 

Interesting point, but, in my opinion not applicable: ⊥ is indeed not part of the mathematical set of floating point numbers, but in the form of NaN it is part of the corresponding type (float in C, REAL in Eiffel); and the operations of the type are applicable to all values, including NaN if, as noted, we have not taken the extreme step of triggering an exception every time an operation uses a NaN as one of its operands. So we cannot free ourselves from the monotonicity concern by just a sleight of hands. 

Another comment, also by Van Snyder (slightly abridged): 

Think of [the status of NaN] as a variety of dynamic run-time typing. With static typing, if  x is an integer variable and y

        x := y 

does not inevitably lead to 

        x = y

 True; and a compelling argument to require that conversions satisfy equality as a postcondition! Such  reasoning — reflexivity again — was essential in the design of the Eiffel conversion mechanism [3], which makes it possible to define conversions between various data types (not just integers and reals and the other classical examples, but also any other user types as long as the conversion does not conflict with inheritance). The same conversion rules apply to assignment and equality, so that yes, whenever the assignment x := y is permitted, including when it involves a conversion, the property x = y  is afterwards always guaranteed to hold.

It is rather dangerous indeed to depart from the fundamental laws of mathematics. 

References

[1] IEEE floating-point standard, 754-2008; see summary and references in the Wikipedia entry.  

[2] IFIP Working Group 2.5 on numerical software: home page. 

[3] Eiffel standard (ECMA and ISO), available on the ECMA site.

(This entry originated as a post on the EiffelStudio user group mailing list.) 

Here are a couple of actual examples of the new loop variants discussed in the blog entry immediately preceding this one. They came out of my current work; I started updating a program to take advantage of the new facility.

As a typical example, I replaced

        local
                eht: HASH_TABLE [EXPRESSION, EXPRESSION]
        do
                …
        from
                eht := item (e)
                eht.start
         until
                eht.off
        loop
                Result.extend (eht.key_for_iteration)
                eht.forth
        end 

 by

        across item (e) as eht loop Result.extend (eht.key) end

 which also gets rid of the local variable declaration. The second form is syntactic sugar for the first, but I find it justified. 

 Another case, involving nested loops: 

— Previously:

        from
                other.start
        until
                other.off
        loop
                oht := other.item_for_iteration
                e := other.key_for_iteration
                from
                        oht.start
                until
                        oht.off
                loop
                        put (e, oht.item_for_iteration)
                        oht.forth
                end
                other.forth
        end

— Now:

        across other as o loop
                across o.item as oht loop put (o.key, oht.item) end
        end

here getting rid of two local variable declarations (although I might for efficiency reintroduce the variable e  to compute o.key just once). 

It is important to note that these are not your grandmother’s typical loops: they iterate on complex data structures, specifically hash tables where the keys are lists and the items are themselves hash tables, with lists as both items and keys. 

The mechanism is applicable to all the relevant data structures in EiffelBase (in other words, no need for the programmer to modify anything, just apply the across  loop to any such structure), and can easily extended to any new structure that one wishes to define. In the short term at least, I still plan in my introductory teaching to show the explicit variants first, as it is important for beginners to understand how a loop works. (My hunch based on previous cases is that after a while we will feel comfortable introducing the abstract variants from the start, but it takes some time to learn how to do it right.)

New variants of the loop construct have been introduced into Eiffel, allowing a safer, more concise and more abstract style of programming. The challenge was to remain compatible with the basic loop concept, in particular correctness concerns (loop invariant and loop variant), to provide a flexible mechanism that would cover many different cases of iteration, and to keep things simple.

Here are some examples of the new forms. Consider a structure s, such as a list, which can be traversed in sequence. The following loop prints all elements of the list:

      across s as c loop print (c.item) end

(The procedure print is available on all types, and can be adapted to any of them by redefining the out feature; item gives access to individual values of the list.) More about c in just a moment; in the meantime you can just consider consider that using “as c” and manipulating the structure through c rather than directly through s  is a simple idiom to be learned and applied systematically for such across loops.

The above example is an instruction. The all and some variants yield boolean expressions, as in

across s as c all c.item > 0 end

which denotes a boolean value, true if and only if all elements of the list are positive. To find out if at least one is positive, use

across s as c some c.item > 0 end

Such expressions could appear, for example, in a class invariant, but they may be useful in many different contexts.

In some cases, a from clause is useful, as in

        across s as c from sum := 0  loop sum := sum + c.index ∗ c.item end
— Computes Σ i * s [i]

The original form of loop in Eiffel is more explicit, and remains available; you can achieve the equivalent of the last example, on a suitable structure, as

A list and a cursor

      from
sum := 0 ; s.start
until
s.after
loop
sum := sum + s.index ∗ s.item
s.forth
        end

which directly manipulates a cursor through s, using start to move it to the beginning, forth to advance it, and after to test if it is past the last element. The forms with across achieve the same purpose in a more concise manner. More important than concision is abstraction: you do not need to worry about manipulating the cursor through start, forth and after. Under the hood, however, the effect is the same. More precisely, it is the same as in a loop of the form

from
sum := 0 ; c.start
until
c.after
loop
sum := sum + c.index ∗ c.item
c.forth
        end

where c is a cursor object associated with the loop. The advantage of using a cursor is clear: rather than keeping the state of the iteration in the object itself, you make it external, part of a cursor object that, so to speak, looks at the list. This means in particular that many traversals can be active on the same structure at the same time; with an internal cursor, they would mess up with each other, unless you manually took the trouble to save and restore cursor positions. With an external cursor, each traversal has its own cursor object, and so does not interfere with other traversals — at least as long as they don’t change the structure (I’ll come back to that point).

With the across variant, you automatically use a cursor; you do not have to declare or create it: it simply comes as a result of the “as c” part of the construct, which introduces c as the cursor.

On what structures can you perform such iterations? There is no limitation; you simply need a type based on a class that inherits, directly or indirectly, from the library class ITERABLE. All relevant classes from the EiffelBase library have been updated to provide this inheritance, so that you can apply the across scheme to lists of all kinds, hash tables, arrays, intervals etc.

One of these structures is the integer interval. The notation  m |..| n, for integers m and n, denotes the corresponding integer interval. (This is not a special language notation, simply an operator, |..|, defined with the general operator mechanism as an alias for the feature interval of INTEGER classes.) To iterate on such an interval, use the same form as in the examples above:

        across m |..| n  as c from sum := 0  loop sum := sum + a [c.item] end
— Computes Σ a [i], for i ranging from m to n, for an array (or other structure) a. 

The key feature in ITERABLE is new_cursor, which returns a freshly created cursor object associated with the current structure. By default it is an ITERATION_CURSOR, the most general cursor type, but every descendant of ITERABLE can redefine the result type to something more specific to the current structure. Using a cursor — c in the above examples —, rather than manipulating the structure s directly, provides considerable flexibility thanks to the property that ITERATION_CURSOR itself inherits from ITERABLE   and hence has all the iteration mechanisms. For example you may write

across s.new_cursor.reversed as c loop print (c.item) end

to print elements in reverse order. (Using Eiffel’s operator  mechanism, you may write – s.new_cursor, with a minus operator, as a synonym for new_cursor.reversed.) The function reversed gives you a new cursor on the same target structure, enabling you to iterate backwards. Or you can use

        across s.new_cursor + 3 as c loop print (c.item) end

(using s.new_cursor.incremented (3) rather than s.new_cursor + 3 if you are not too keen on operator syntax) to iterate over every third item. A number of other possibilities are available in the cursor classes.

A high-level iteration mechanism is only safe if you have the guarantee that the structure remains intact throughout the iteration. Assume you are iterating through a structure

across s   as c loop some_routine end

and some_routine changes the structure s: the whole process could be messed up. Thanks to Design by Contract mechanisms, the library protects you against such mistakes. Features such as item and index, accessing properties of the structure during the iteration, are equipped with a precondition clause

require
is_valid

and every operation that changes the structure sets is_valid to false. So as soon as any change happens, you cannot continue the iteration; all you can do is restart a new one; the command start, used internally to start the operation, does not have the above precondition.

Sometimes, of course, you do want to change a structure while traversing it; for example you may want to add an element just to the right of the iteration position. If you know what you are doing that’s fine. (Let me correct this: if you know what you are doing, express it through precise contracts, and you’ll be fine.) But then you should not use the abstract forms of the loop, across…; you should control the iteration itself through the basic form from … until … with explicit cursor manipulation, protected by appropriate contracts.

The two styles, by the way, are not distinct constructs. Eiffel has always had only one form of loop and this continues the case. The across forms are simply new possibilities added to the classical loop construct, with obvious constraints stating for example that you may not have both a some or all form and an explicit  loop body.  In particular, an across loop can still have an invariant clause , specifying the correctness properties of the loop, as in

        across s as c from sum := 0  invariant sum = sigma (s, index)  loop sum := sum + c.index ∗ c.item end

EiffelStudio 6.5 already included the language update; the library update (not yet including the is_valid preconditions for data structure classes) will be made available this week.

These new mechanisms should increase the level of abstraction and the reliability of loops, a fundamental element of  almost all programs.

In a previous post I briefly mentioned some work that I am doing on aliasing. There is a draft paper [1], describing the theory, calculus, graphical notation (alias diagrams) and implementation. Here I will try to give an idea of what it’s about, with the hope that you will be intrigued enough to read the article. Even before you read it you might try out the implementation[2], a simple interactive interface with all the examples of the article .

What the article does not describe in detail — that will be for a companion paper— is how the calculus will be used as part of a general framework for developing object-oriented software proved correct from the start, the focus of our overall  “Trusted Components” project’ [3]. Let me simply state that the computation of aliases is the key missing step in the effort to make correctness proofs a standard part of software development. This is a strong claim which requires some elaboration, but not here.

The alias calculus asks a simple question: given two expressions representing references (pointers),  can their values, at a given point in the program, ever reference the same object during execution?

As an example  application, consider two linked lists x and y, which can be manipulated with operations such as extend, which creates a new cell and adds it at the end of the list:

 The calculus makes it possible to prove that if  x and y are not aliased to each other, then none of the pointers in any of the cells in either of the lists can point to  (be aliased to) any cell of  the other. If  x is initially aliased to y, the property no longer holds. You can run the proof (examples 18 and 19) in the downloadable implementation.

The calculus gives a set of rules, each applying to a particular construct of the language, and listed below.

The rule for a construct p is of the form

          a |= p      =   a’ 

where a and a’ are alias relations; this states that executing p  in a state where the alias relation is a will yield the alias relation a’ in the resulting state. An alias relation is a symmetric, irreflexive relation; it indicates which expressions and variables can be aliased to each other in a given state.

The constructs p considered in the discussion are those of a simplified programming language; a modern object-oriented language such as Eiffel can easily be translated into that language. Some precision will be lost in the process, meaning that the alias calculus (itself precise) can find aliases that would not exist in the original program; if this prevents proofs of desired properties, the cut instruction discussed below serves to correct the problem.

The first rule is for the forget instruction (Eiffel: x := Void):

          a |= forget x       =   a \- {x}

where the \- operator removes from a relation all the elements belonging to a given set A. In the case of object-oriented programming, with multidot expressions x.y.z, the application of this rule must remove all elements whose first component, here x, belongs to A.

The rule for creation is the same as for forget:

         a |= create x          =   a \- {x}

The two instructions have different semantics, but the same effect on aliasing.

The calculus has a rule for the cut instruction, which removes the connection between two expressions:

        a |= cut x, y       =   a — <x, y>

where — is set difference and <x, y> includes the pairs [x, y] and [y, x] (this is a special case of a general notation defined in the article, using the overline symbol). The cut   instruction corresponds, in Eiffel, to cut   x /= y end:  a hint given to the alias calculus (and proved through some other means, such as standard axiomatic semantics) that some references will not be aliased.

The rule for assignment is

      a |= (x := y)      =   given  b = a \- {x}   then   <b È {x} x (b / y)}> end

where b /y (“quotient”), similar to an equivalence class in an equivalence relation, is the set of elements aliased to y in b, plus y itself (remember that the relation is irreflexive). This rule works well for object-oriented programming thanks to the definition of the \- operator: in x := x.y, we must not alias x to x.y, although we must alias it to any z that was aliased to x.y.

The paper introduces a graphical notation, alias diagrams, which makes it possible to reason effectively about such situations. Here for example is a diagram illustrating the last comment:

Alias diagram for a multidot assignment

(The grayed elements are for explanation and not part of the final alias relation.)

For the compound instruction, the rule is:

           a |= (p ;  q)      =   (a |= p) |= q)

For the conditional instruction, we get:

           a |= (then p else  q end)      =   (a |= p) È  (a |= q)

Note the form of the instruction: the alias calculus ignores information from the then clause present in the source language. The union operator is the reason why  alias relations,  irreflexive and symmetric, are not  necessarily transitive.

The loop instruction, which also ignores the test (exit or continuation condition), is governed by the following rule:

           a |= (loop p end)       =   t_N

where span style=”color: #0000ff;”>N is the first value such that t_N = t_N+1 (in other words, t_N is the fixpoint) in the following sequence:

            t₀          =    a
           t_n+1       =   (t_n È (t_n |= p))     

The existence of a fixpoint and the correctness of this formula to compute it are the result of a theorem in the paper, the “loop aliasing theorem”; the proof is surprisingly elaborate (maybe I missed a simpler one).

For procedures, the rule is

         a |= call p        =   a |= p.body

where p.body is the body of the procedure. In the presence of recursion, this gives rise to a set of equations, whose solution is the fixpoint; again a theorem is needed to demonstrate that the fixpoint exists. The implementation directly applies fixpoint computation (see examples 11 to 13 in the paper and implementation).

The calculus does not directly consider routine arguments but treats them as attributes of the corresponding class; so a call is considered to start with assignments of the form f : = a for every pair of formal and actual arguments f and a. Like the omission of conditions in loops and conditionals, this is a source of possible imprecision in translating from an actual programming language into the calculus, since values passed to recursive activations of the same routine will be conflated.

Particularly interesting is the last rule, which generalizes the previous one to qualified calls of the form x. f (…)  as they exist in object-oriented programming. The rule involves the new notion of inverse variable, written x’ where x is a variable. Laws of the calculus (with Current denoting the current object, one of the fundamental notions of object-oriented programming) are

        Current.x            = x   
        x.Current            = x
        x.x’                      = Current
        x’.x                      = Current

In other words, Current plays the role of zero element for the dot operator, and variable inversion is the inverse operation. In a call x.f, where x denotes the supplier object (the target of the call), the inverse variable provides a back reference to the client object (the caller), indispensable to interpret references in the original context. This property is reflected by the qualified client rule, which uses  the auxiliary operator n (where x n a, for a relation a and a variable x, is the set of pairs [x.u, y.v] such that the pair [u, v] is in a). The rule is:

         a |= call x.r       =   x n ((x’ n a ) |= call r)

You need to read the article for the full explanation, but let me offer the following quote from the corresponding section (maybe you will note a familiar turn of phrase):

Thus we are permitted to prove that the unqualified call creates certain aliasings, on the assumption that it starts in its own alias environment but has access to the caller’s environment through the inverted variable, and then to assert categorically that the qualified call has the same aliasings transposed back to the original environment. This change of environment to prove the unqualified property, followed by a change back to the original environment to prove the qualified property, explains well the aura of magic which attends a programmer’s first introduction to object-oriented programming.

I hope you will enjoy the calculus and try the examples in the implementation. It is fun to apply, and there seems to be no end to the potential applications.

Reference

[1] Bertrand Meyer: The Theory and Calculus of Aliasing, draft paper, first published 12 January 2009 (revised 21 January 2010), available here and also at arxiv.org.
[2] Implementation (interactive version to try all the examples of the paper): downloadable Windows executable here.
[3] Bertrand Meyer: The Grand Challenge of Trusted Components, in 2003 International Conference on Software Engineering, available here.

In the past few weeks I wrote a program to compute the aliases of variables and expressions in an object-oriented program (based on a new theory [1]).

For one of the data structures, I needed a specific notion of equality, so I did the standard thing in Eiffel: redefine the is_equal function inherited from the top class ANY, to implement the desired variant.

The first time I ran the result, I got a postcondition violation. The violated postcondition clauses was not even any that I wrote: it was an original postcondition of is_equal (other: like Current)  in ANY, which my redefinition inherited as per the rules of Design by Contract; it reads

symmetric: Result implies other ~ Current

meaning: equality is symmetric, so if Result is true, i.e. the Current object is equal to other, then other must also be equal to Current. (~ is object equality, which applies the local version is is_equal).  What was I doing wrong? The structure is a list, so the code iterates on both the current list and the other list:

from
    start ; other.start ; Result := True
until (not Result) or after loop
        if other.after then Result := False else
              Result := (item ~ other.item)
              forth ; other.forth
        end
end

Simple enough: at each position check whether the item in the current list is equal to the item in the other list, and if so move forth in both the current list and the other one; stop whenever we find two unequal elements, or we exhaust either list as told by after list. (Since is_equal is a function and not produce any side effect, the actual code saves the cursors before the iteration and restores them afterwards. Thanks to Ian Warrington for asking about this point in a comment to this post. The new across loop variant described in  two later postings uses external cursors and manages them automatically, so this business of maintaining the cursor manually goes away.)

The problem is that with this algorithm it is possible to return True if the first list was exhausted but not the second, so that the first list is a subset of the other rather than identical. The correction is immediate: add

Result and other_list.after

after the loop; alternatively, enclose the loop in a conditional so that it is only executed if count = other.count (this solution is  better since it saves much computation in cases of lists of different sizes, which cannot be equal).

The lesson (other than that I need to be more careful) is that the error was caught immediately, thanks to a postcondition violation — and one that I did not even have to write. Just another day at the office; and let us shed a tear for the poor folks who still program without this kind of capability in their language and development environment.

Reference

[1] Bertrand Meyer: The Theory and Calculus of Aliasing, draft paper, available here.

The book page for Touch of Class (my introductory programming textbook), announced in the book, is finally available, courtesy Vladimir Tochilin:

touch.ethz.ch

It includes some book extracts (prefaces, table of contents, an entire sample chapter, for which I chose the Recursion chapter), a list of known errata and a wiki page to report new errata, a discussion forum, links to the full set of slides (PowerPoint, PDF) for the associated course, video recordings of that course at ETH, and a special “instructor’s corner” for those having adopted the textbook for their courses.

Once again, and we are not learning!

La Repubblica of last Thursday [1] and other Italian newspapers have reported on a “computer” error that temporarily brought thousands of accounts at the national postal service bank into the red. It is a software error, due to a misplacement of the decimal points in some transactions.

As usual the technical details are hazy; La Repubblica writes that:

“Because of a software change that did not succeed, the computer system did not always read the decimal point during transactions”.

As a result, it could for example happen that a 15.00-euro withdrawal was understood as 1500 euros.
I have no idea what “reading the decimal point ” means. (There is no mention of OCR, and the affected transactions seem purely electronic.) Only some of the 12 million checking or “Postamat” accounts were affected; the article cites a number of customers who could not withdraw money from ATMs because the system wrongly treated their accounts as over-drawn. It says that this was the only damage and that the postal service will send a letter of apology. The account leaves many questions unanswered, for example whether the error could actually have favored some customers, by allowing them to withdraw money they did not have, and if so what will happen.

The most important unanswered question is the usual one: what was the software error? As usual, we will probably never know. The news items will soon be forgotten, the postal service will somehow fix its code, life will go on. Nothing will be learned; the next time around similar causes will produce similar effects.

I criticized this lackadaisical attitude in an earlier column [2] and have to hammer its conclusion again: any organization using public money should be required, when it encounters a significant software malfunction, to let experts investigate the incident in depth and report the results publicly. As long as we keep forgetting our errors we will keep repeating them. Where would airline safety be in the absence of thorough post-accident reports? That a software error did not kill anyone is not a reason to ignore it. Whether it is the Italian post messing up, a US agency’s space vehicle crashing on the moon or any other software fault causing systems to fail, it is not enough to fix the symptoms: we must have a professional report and draw the lessons for the future.

Reference

[1] Luisa Grion: Poste in tilt per una virgola — conti gonfiati, stop ai prelievi. In La Repubblica, 26 November 2009, page 18 of the print version. (At the time of writing it does not appear at repubblica.it,  but see  the TV segment also titled “Poste in tilt per una virgola” on Primocanale Web TV here, and other press articles e.g. in Il Tempo here.)

[2] On this blog: The one sure way to advance software engineering (post of 21 August 2009).

Alina was, as noted, on Pařížská (Paris avenue). Heeding the unknown voice, she started walking clockwise; she did not hesitate as to what this means since, conveniently, she was standing right next to a clock:

Luca was standing on the other side of the block. He too saw a clock:

Pařížská was built in the late nineteenth century, as Prague’s answer to the Paris Champs-Élysées; it cut through Josefov, the old Prague ghetto. Most of the old Josefov was destroyed at the time; among the buildings that survived were six synagogues, the famous cemetery, and the “Jewish Town Hall”. This last building had been reconstructed in the 18th century with a fancy clock using Hebrew letters and, as an homage to the right-to-left reading of Hebrew script, running in the opposite of the direction of ordinary clocks. The clock figures in Guillaume Apollinaire’s Alcools:

Tu ressembles au Lazare affolé par le jour
Les aiguilles de l’horloge du quartier juif vont à rebours
Et tu recules aussi dans ta vie lentement
En montant au Hradchin et le soir en écoutant
Dans les tavernes chanter des chansons tchèques

(You look like Lazarus scared by daylight
The hands of the Jewish quarter clock go backwards
And you too step back slowly through your life
As you walk up to the Hradčany and in the evening
Listen to Czech songs sung in taverns)

Luca started walking clockwise, according to the clock next to him; you know the rest.

Normal clocks all go the same way; the backwards clock is no more than a wink and a whim. Had Luca raised his eyes more:

he would have gone by one of the other, ordinary clocks, going in the same direction as Alina; and we would not have a story.

For the text of the puzzle see this earlier post.

Hints (by popular demand):

(1) Prague
(2) Guillaume Apollinaire

Yesterday’s New York Times carries an article by John Tierney about the 95th anniversary of the king of mathematical puzzles, Martin Gardner. The article is so well done that I will not even try a summary, referring you instead directly to it [1]. Just one detail worthy of note:  when he undertook to write a monthly puzzle column for Scientific American at the age of 37, Gardner “had never taken a math course beyond high school. He had struggled with calculus and considered himself poor at solving basic mathematical puzzles, let alone creating them.”

Logical and mathematical puzzles are a great way to keep the mind alert; one of the attractions of going to meetings of IFIP Working Group 2.3 on Programming Methodology[2]  is that members constantly tease each other with puzzles of diverse nature and difficulty; Rustan Leino, the group’s current secretary, keeps a fascinating collection on one of his Web pages [3].

It would be imprudent to promise anything like a “ monthly puzzle” here, but let me at least announce an “occasional series”, which is not too harsh a commitment, and propose the first installment today. This little teaser is definitely original: The Case of the Handsome Couple.

At a dinner, one couple stands out as particularly hansome; both the wife and the husband (Alina and Luca). Conversation turns to the inevitable question: “How did you two meet?”.

“ Interesting indeed”, says the wife. “It was love at first sight: I was walking and came face to face with Luca;  on the spot, I knew he was the one.”

“Tell us more! Where and how?”

“It was in Prague. I was walking along the Pařížská avenue, this kind of Champs-Élysées of Prague, window-shopping at the luxury shops. Then my Blackberry rang; I picked it up. I heard an unknown voice, telling me to start walking clockwise around the block. For some reason I felt compelled to obey it; soon after I came face to face with him. You know the rest.”

The host turns to Luca: “How was it for you?”

“Will you believe me: exactly the same! I was actually, as we later reconstructed, on the other side of that same city block. Suddenly my iPhone rang and I heard that strange voice ordering me to keep walking clockwise around the block. And suddenly I find myself face to face with her! You see the result.”

It’s a normal city block, and they were both faithfully obeying the injunction to walk clockwise, yet met face to face. How was that possible?

References

[1] John Tierney: For Decades, Puzzling People With Mathematics, in New York Times, 19 October 2009, available here.

[2] IFIP WG 2.3, Programming Methodology: see the group’s Web page.

[3] Rustan Leino’s puzzle collection at research.microsoft.com/en-us/um/people/leino/puzzles.html. (Disclaimer: Rustan says he obtained two puzzles — originally from other sources —through me.)

Remember Stacey’s in Palo Alto and San Francisco? Only a decade ago these and other technical bookstores were the mecca of the tech industry, where developers would swarm at any time of day to catch up on the latest releases. One well-known Valley entrepreneur even told me she did her hiring there, spotting customers who looked like developers and picked the right books.

Times have changed. After all the other branches, Stacey’s venerable San Francisco’s store finally closed earlier this year [1], the victim of the bubble’s burst, of Amazon, and of the crisis. Many others in the US and elsewhere met the same fate.

But wait… In Gaul, a little village is resisting the onslaught. A couple of streets away from the Shakespeare and company bookstore immortalized by Hemingway, Scott Fitzgerald and so many others, the Paris technical bookstore Le Monde en Tique [3] is a true legend of its own. Le Monde en Tique has, for the past twenty years, carried the best selection of computer and other technology books within a good thousand kilometers. I was there on Oct. 10, after the European Computer Science Summit (more on ECSS soon) for a book signing of Touch of Class:

The store’s name, “the World in Tics”, is a wink to the many “tics” served by its books, from informatics (computer science and information technology) to “telematics” (computer  communication). Housed in a beautiful stone edifice in the heart of medieval Paris, on a little winding street close to the river, Le Monde en Tique is more than a bookstore: it is a haven for the local developer community, a place to stop by on a Saturday afternoon for a passionate discussion on agility, Ajax or Agitar. There is even a small garden:

There is a secret to Le Monde en Tique’s continued success: the quality of its offerings. The unique skill of  Jean Demétreau and his team is their availability to locate hot new books, including those from the US and elsewhere, before anyone else does; the large Paris bookstores like FNAC, and the Web sites such as fnac.fr and amazon.fr are often several weeks behind. Not just the French sites, as a matter of fact: in the case of Touch of Class, Le Monde en Tique had the book about a month ahead of amazon.com USA. This is why people come from very far away to get both the latest offerings and the classics.

So here’s my plug: whether you have just heard about a great new book, or haven’t heard anything and want to find out what is the latest great new book, this is the place to go. It might already be late when you finally take yourself away from browsing the shelves; but as you go out of the store and walk a few steps, the sight will not be too bad:

References

[1] Matthai Kuruvila, Stacey’s Bookstore closing down in S.F., in SFGate (San Francisco Chronicle), 5 January 2009, available here.

[2] Shakespeare and company bookstore in Paris: see here.

[3] Le Monde en Tique bookstore, 6 rue Maître Albert, Paris: see www.lmet.fr.

On how to build software, there is still much we do not know for sure; but we have also learned a few principles that can be considered firm.  By definition these are not new ideas; today’s principle, for example, is related to what agile developers know as “timeboxing”. But even if they have been published and discussed they are not universally applied or understood.

An  example is the CPU Clock principle: release at fixed frequency.

When planning for a new release of a system you can play with three parameters: functionality; quality; release time. The CPU Clock principle states that once a release time has been set you should never budge. If something has to go, it will be functionality.

At Eiffel Software we have been applying this principle systematically since shortly after we released EiffelStudio into open source in 2006. There are two releases a year, the  “Northern Spring release” on May 15 and the “Southern Spring release” on November 15 [2]. The content of each release is finalized six weeks before (April 1st, October 1st) and no delay is tolerated [3].

This scheme is a radical departure from the previous mode of operation. Of course every release had a planned delivery date, but it also had planned functionality; often, the functionality was not all ready at the appointed time, so the delivery date would shift, often by many months. No doubt the release plan was thought realistic at the time the team devised it, but it is a natural human tendency to promise too much and hope for the best. Delays came not so much from major obstacles, as features would get dropped if found too hard to include, but from functionality which the team believed to be “almost there” as the release date approached; a week passed, then a month, then maybe a half-year or more.

The better technique, as we have learned (no doubt many others have too) is to make release time the non-negotiable target. As with the clock cycle of a CPU in a modern computer, the sequence of release deadlines is the heartbeat to which everything else in the process must synchronize. The scale is different from that of a computer by a few orders of magnitude (months rather than pico- or nanoseconds), but the principle is the same.

The scheme requires a strict rule that whatever is not ready in time will not make it into the release. Indeed it has occurred a few times that some scheduled functionality had to be dropped, or at least moved to the next release. But now — with two and a half years of experience — comes the remarkable lesson: this case, dropping a planned feature because it is not ready at the appointed time, happens only exceptionally. It is not hard to analyze the reasons:

• Developers work better. It is not pleasant, for a developer who has devoted considerable effort to a new mechanism, to see that it does not make it to the product. Knowing that the deadline is coming, and that it is for real, is a powerful incentive to finish the work.
• Everyone, managers and developers, learns to be realistic. Managers will not set impossible goals; developers will not commit to impossible implementations.

Traditionally, some software projects have always had to treat delivery time as the number one goal. If you had to adapt an automatic teller machine network to the introduction of the euro, there was not much other choice than to be ready on January 1, 2002, and preferably a little before that. But many projects have a more lackadaisical attitude. They would fare better by adhering to the CPU Clock principle.

In describing it I have left a question open. Functionality should yield to  release punctuality, but we saw that there is a third parameter:  quality. What about it? Should we be ready to sacrifice it as well? I will not address the question furtherfor the moment, if only because this may be a good topic for reader comments before I come back to it in a future post.

The CPU clock principle addresses release times: the times when new versions of the product are made available to its users. It does not necessarily apply to internal milestones of the development team. Timeboxing, a related idea made popular by agile methods, is about such internal, intermediate steps; the typical iteration period of timeboxing is a f ew weeks. While fixed deadlines and a fixed frequency may be useful for such short internal iterations, the case for timeboxing is less compelling, especially for a large project where the various components may evolve along different timelines.

Because the CPU Clock principle governs the global scheduling of a product development, the scale is different. I cited above the 6-month periodicity of EiffelStudio development; although each project will define its own period, it makes no sense to go below one month for any significant software effort.

How universal is the principle? Only two exceptions come to mind: very small projects, and the initial phase of a project, when the development is taking shape and it is too early to define the ideal release scheme. Outside of these two cases, I see the CPU Clock principle, on the basis of our experience and of discussions with many developers and project leaders, as the only sustainable model for healthy software projects.

Notes

[1] EiffelStudio open-source development page, see here.

[2] Formerly known as the “Spring release” and “Fall release” until someone complained of hemisphere bias.

[3] Actually some last-minute technical problems have occasionally caused short delays in the actual delivery, without affecting the overall cycle. We have taken measures to ensure that these do not occur again.

I am jealous of Emmanuel (Manu) Stapf who blogged about this before I had the time to; but I can at least refer you to his entry [1].

The idea actually comes from Martin Nordio, who as part of his thesis work formalized the exception semantics of both Eiffel and Java. In the process he came across some (shall we say) interesting properties of Java, and got into the habit of asking people first if they know Java well, and then if they can predict the results of some simple programs.

So, do you think you know Java? If so, please take the test, and wait for the answer next week in Manu’s blog.

Reference

[1] Emmanuel Stapf: “And people are still using Java?” blog entry.

The next SEAFOOD (Software Engineering Advances For Offshore and Outsourced Development) conference will take place in Saint Petersburg, Russia, on 17 and 18 June 2010. The conference co-chairs are Andrey Terekhov from Saint Petersburg State University and Lanit-Tercom, and Martin Nordio from ETH are conference co-chairs. Mathai Joseph from Tata Consulting Services and I will be co-chairing the PC. The Call for Papers will be issued soon; information about this year’s conference at seafood.ethz.ch.

Airplanes today are incomparably safer than 20, 30, 50 years ago: 0.05 deaths per billion kilometers. That’s not by accident.

Rather, it’s by accidents. What has turned air travel from a game of chance into one of the safest modes of traveling is the relentless study of crashes and other mishaps. In the US the National Transportation Safety Board has investigated more than 110,000 accidents since it began its operations in 1967. Any accident must, by law, be investigated thoroughly; airplanes themselves carry the famous “black boxes” whose only purpose is to provide evidence in the case of a catastrophe. It is through this systematic and obligatory process of dissecting unsafe flights that the industry has made almost all flights safe.

Now consider software. No week passes without the announcement of some debacle due to “computers” — meaning, in most cases, bad software. The indispensable Risks forum [1] and many pages around the Web collect software errors; several books have been devoted to the topic.

A few accidents have been investigated thoroughly; two examples are Nancy Leveson’s milestone study of the Therac-25 patient-killing medical device [2], and Gilles Kahn’s analysis of the Ariane 5 crash (which Jean-Marc Jézéquel and I used as a basis for our 1997 article [3]). Both studies improved our understanding of software engineering. But these are exceptions. Most of what we have elsewhere is made of hearsay and partial information, and plain urban legends (like the endlessly repeated story about the Venus probe that supposedly failed because a period was typed instead of a comma — most likely a canard).

Software disasters continue; they attract attention when they arise, and inevitably some kind of announcement is made that the problem is being corrected, or that a committee will study the causes; almost as inevitably, that is the last we hear of it. In the latest issue of Risks alone, you can find several examples (such as [4]). In the past months, breakdowns at Skype, Google and Twitter made headlines; we all learned about the failures, but have you seen precise analyses of what actually happened?

As another typical example, we heard a few months ago from the French press that an “IT error” (une erreur informatique) led to overestimating the pensions of about a million people; since (strangely!)  no one was suggesting that they would be asked to pay the money back, the cost to taxpayers will be over 300 million euros. I looked in vain for any follow-up story: what happened? What was the actual error? Were the tools at fault? The quality assurance procedures? The programmers’ qualifications? Or was it a matter of bad deployment? Of erroneous data, and if so, what was the process for validating inputs? And so on. Most likely we will never know.

But we should know. Especially with public money, any such incident should have a post-mortem, with experts called in (surely at a fraction of the cost of the failure) to analyze what happened and produce a public report.

At least this was a public project, for which some disclosure was inevitable. The software engineering community buzzes with unconfirmed reports of huge software-induced errors, that go unreported because they happen in private companies eager to avoid bad publicity. It’s as if we had allowed aircraft manufacturers, decade after decade, to keep mum about accidents. Where then would air travel safety be today?

Progress in software engineering will come from many sources. Research is critical, including on topics which today appear exotic. But if anyone is looking for one practical, low-tech idea that has an iron-clad guarantee of improving software engineering, here it is: pass a law that requires extensive professional analysis of any large software failure.

The details are not so hard to refine. The initiative would probably have to start at the national level; any industrialized country could be the pioneer. (Or what about Europe as whole?) The law would have to define what constitutes a “large” failure; for example it could be any failure that may be software-related and has resulted in loss either of human life or of property beyond a certain threshold, say $50 million. In the latter case, to avoid accusations of government meddling in private matters, the law could initially be limited to cases involving public money; when it has shown its value, it could then be extended to private failures as well. Even with some limitations, such a law would have a tremendous effect. Only with a thorough investigation of software projects gone wrong can we help the majority of projects to go right.

We can no longer afford to let the IT industry get away with covering up its failures. Lobbying for a Software Incident Full Disclosure Law is the single most important step we can take today to make the world’s software better.

Note (2011)

Later articles have come back to the theme discussed here, and there will probably be more in the future as it remains ever current. They can be found by selecting the tag “Advance”.

References

[1] Peter G. Neumann, moderator: The Risks Digest Forum on Risks to the Public in Computers and Related Systems, available online (going back to 1985!).

[2] Nancy Leveson: Medical Devices: The Therac-25, extract from her book Safeware: System Safety and Computers, Addison-Wesley, 1995, available online.

[3] Jean-Marc Jézéquel and Bertrand Meyer: Design by Contract: The Lessons of Ariane, in Computer (IEEE), vol. 30, no. 1, January 1997, pages 129-130, also available here.

[4] Monty Solomon: Computer Error Caused Rent Troubles for Public Housing Tenants, in Risks 25.76, 15 August 2009, see here.

[5] Une erreur informatique à 300 millions d’euros, in Le Point, 12 May 2009, available here.