Sign In

Communications of the ACM

Research highlights

Continuity and Robustness of Programs


falling dominoes

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.

The full text of this article is premium content


Comments


Luke Dunstan

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

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


Displaying all 2 comments

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.
  

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account