Communications of the ACM

Computer scientists have long believed that software is different from physical systems in one fundamental way: while the latter have continuous dynamics, the former do not. In this paper, we argue that notions of continuity from mathematical analysis are relevant and interesting even for software.

---

Luke Dunstan

August 26, 2012 04:53

When reading this I was pretty confused by the way that the bitmap "isin.gif" is used to represent both set membership (correctly, ) as well as the "Greek lunate epsilon" symbol (incorrectly, should have been ), and even worse, for the subscript lunate epsilon. It was not until I checked the paper magazine that it finally made sense.

---

CACM Administrator

April 02, 2014 11:16

The following letter was published in the Letters to the Editor in the November 2012 CACM (http://cacm.acm.org/magazines/2012/11/156596).
--CACM Administrator

Swarat Chaudhuri et al.'s article "Continuity and Robustness of Programs" (Aug. 2012) said: "The most basic reason why software systems can violate continuity is conditional branching" but ignored a more fundamental cause, namely that program variables have a limited number of states. Computer representation of real numbers is inexact, and only a finite subset of the integers can be represented exactly. Consequently, in computer arithmetic, equations (such as (x+y) + (z-y) = x+z) need not hold and can introduce discontinuity. The article ignored the problem by both declaring, "...our reals are infinite-precision" and not specifying upper and lower bounds for integers. These assumptions are common in mathematics but not valid for computer programs. Some programs can be shown to be continuous by Chaudhuri's method but will exhibit discontinuous behavior when executed.

The article also ignored real problems by proposing metrics that are based on data types alone, saying: "The metric over arrays of reals or integers of the same length is the L-norm: d(A1, A2) = maxi{|A1[i] A2[i]|}. ... We define d(A1, A2) = if A1 and A2 have different sizes." As illustrated in the following example, to get a relevant definition of continuity, the nature of the application must be considered: The inappropriateness of the article's metric for some applications can be seen by considering a "data mining" application that identifies a family through the children's Social Security numbers. If the article's metric is applied to three records

A: 101234567 104432769
B: 101234567 104432769 106222444
C: 101234568 104432768

the distance between A and B would be infinite and A and C would be very close. However, record B, an extension of record A, describes the family described by A after the birth of the third child. Record C describes a different family. An appropriate metric would consider A close to B and far from C.

Moreover, the article described its examples as "everyday programs," but these programs were typical textbook algorithms and not typical of the software we use every day. For example, the article proved that programs that compute the length of the shortest path between two nodes are continuous. However, widely used route-finding software outputs a path, not just length. A small change in one arc's length could change the output drastically by suggesting a completely different route. One reason software continues to replace analog devices is that users often require discontinuous behavior from those devices. Software with continuous behavior will always be rare.

Proving programs correct has been a goal of computer scientists for half a century; the article reflected how far we still are from achieving that goal. Rather than verify properties of an actual program, it examined models of programs. Models often have properties real mechanisms do not have, and it is possible to verify the correctness of a model of a program even if the actual program will fail.

The article's approach is useful because attempting to prove a model of a program correct can reveal subtle errors. However, when a correctness proof is obtained, it must be taken with a grain of salt.

David Lorge Parnas
Ottawa, Canada

----------------------------------------

AUTHORS' RESPONSE

From a purely mathematical perspective, any function between discrete spaces is continuous, so all computer programs are continuous. But this fact does not carry any useful information. In practice, some programs behave robustly and some do not, and infinite-precision models of programs offer a good way to predict whether a program is robust.

Also, our framework extends to programs that operate on values ranging over finite sets. Continuity is not a good robustness property for such programs, but, say, Lipschitz continuity is. The example programs in our article remain robust under these definitions; we also have evidence that our robustness analysis can be adapted to this context.

Swarat Chaudhuri
Houston, TX

Sumit Gulwani
Redmond, WA