Search
Join ACM

Software Engineering and Programming Languages

Advertisement

Opinion

Legally speaking: how to interpret the Lotus decision (and how not to)

On June 28, 1990, a federal court judge in Boston made public his decision in favor of Lotus Development Corporation in its software copyright lawsuit against Paperback Software. People in the software industry had been waiting for this decision since the lawsuit was first filed in January 1987, certain that it would be a landmark case and would resolve many vexing questions about copyright protection for user interfaces.The trade press has abounded with varying interpretations of Judge Keeton's opinion in the Lotus case: Some have said the decision is a narrow one, making illegal only the direct copying of another firm's interface [9]; Some have seen it has a much broader ruling—one that will have a chilling effect on development of competitive software products [5]; Others have asserted the case draws a reasonable line, and will have a positive effect overall [4]; Several have argued the ruling will be harmful because it ignores the interests of users of software, and will make standardization of user interfaces impossible to achieve. [3] Still others perceive the opinion as only setting the stage for a new confrontation over the issues in the appellate courts. [1] Lotus has given some indication of how broadly it interprets the Paperback decision by filing a new round of user interface copyright lawsuits against two of its other spreadsheet competitors.his column, rather than just adding one more interpretation of the Lotus decision to the bin of those already expressed, will give the reader a glimpse of the nature of the legal process and of judicial opinions so he or she can see why people can interpret the Lotus opinion differently. The following three factors make it difficult to know what the Lotus decision means: 1) The legal process is not yet over, and the meaning of the case will depend in part on the outcome of this further process. 2) While Judge Keeton makes some statements that seem to suggest his ruling is a narrow one, some of his other statements could be interpreted much more broadly. 3) Even from unambiguous statements Judge Keeton makes, different people can draw reasonable but nonetheless differing inferences about what the judge would do in similar (though somewhat different) cases. For these reasons, it is impossible to know with any certainty what the law concerning copyright protection for user interfaces is in the aftermath of the Lotus decision.
Research and Advances

Transaction processing monitors

A transaction processing (TP) application is a program that performs an administrative function by accessing a shared database on behalf of an on-line user. A TP system is an integrated set of products that supports TP applications. These products include both hardware, such as processors, memories, disks and communications controllers, and software such as operating systems (Oss), database management systems (DBMSs), computer networks and TP monitors. Much of the integration of these products is provided by TP monitors which coordinate the flow of transaction request between terminals that issue requests and TP applications that can process them.Today, TP represents over 25 percent of the computer systems market and is one of the growing segments of the computer business. TP applications appear in most sectors of large-scale enterprises such as airline reservation, electronic banking, securities trading, inventory and production control, communications switching, videotex, sales management, military command and control and government services. 84552 75 CACM 33 10 Consider a computer system having a CPU that feeds jobs to two input/output (I/O) devices having different speeds. Let &thgr; be the fraction of jobs routed to the first I/O device, so that 1 - &thgr; is the fraction routed to the second. Suppose that @@@@ = @@@@(&thgr;) is the steady-sate amount of time that a job spends in the system. Given that &thgr; is a decision variable, a designer might wish to minimize @@@@(&thgr;) over &thgr;. Since @@@@(·) is typically difficult to evaluate analytically, Monte Carlo optimization is an attractive methodology. By analogy with deterministic mathematical programming, efficient Monte Carlo gradient estimation is an important ingredient of simulation-based optimization algorithms. As a consequence, gradient estimation has recently attracted considerable attention in the simulation community. It is our goal, in this article, to describe one efficient method for estimating gradients in the Monte Carlo setting, namely the likelihood ratio method (also known as the efficient score method). This technique has been previously described (in less general settings than those developed in this article) in [6, 16, 18, 21]. An alternative gradient estimation procedure is infinitesimal perturbation analysis; see [11, 12] for an introduction. While it is typically more difficult to apply to a given application than the likelihood ratio technique of interest here, it often turns out to be statistically more accurate. In this article, we first describe two important problems which motivate our study of efficient gradient estimation algorithms. Next, we will present the likelihood ratio gradient estimator in a general setting in which the essential idea is most transparent. The section that follows then specializes the estimator to discrete-time stochastic processes. We derive likelihood-ratio-gradient estimators for both time-homogeneous and non-time homogeneous discrete-time Markov chains. Later, we discuss likelihood ratio gradient estimation in continuous time. As examples of our analysis, we present the gradient estimators for time-homogeneous continuous-time Markov chains; non-time homogeneous continuous-time Markov chains; semi-Markov processes; and generalized semi-Markov processes. (The analysis throughout these sections assumes the performance measure that defines @@@@(&thgr;) corresponds to a terminating simulation.) Finally, we conclude the article with a brief discussion of the basic issues that arise in extending the likelihood ratio gradient estimator to steady-state performance measures.
Opinion

Personal computing: Windows, DOS and the MAC

Direct-manipulation or graphical user interfaces (GUIs) are nearly as old as command-line interfaces.1 At the ACM Conference on The History of Personal Workstations, Doug Ross told of drawing on an oscilloscope screen by using his finger to move a spot of light in 1954. Graphic software has been a bastion of direct manipulation since the 195Os, and Douglas Englebart demonstrated direct manipulation of text to large audiences in the 1960s. The style of contemporary direct-manipulation interfaces evolved largely from prototypes developed at the Xerox Palo Alto Research Center (PARC) in the 1970s. The Xerox Star offered a commercial GUI in 1981 (see Figure 1), and several early GUIs, like VisiOn, TopView, and Windows version 1, failed on underpowered PCs. The Macintosh, introduced in 1984, was a major commercial success. Although GUIs have been used for years, the hardware to support them is expensive, so the vast majority of personal computer users still control their software by typing commands. With the introduction of Windows Version 3, Microsoft hopes to move DOS users away from their command-line interface to a direct-manipulation interface. Let us take a quick look at Windows, then compare it to DOS and the Mac.
Practice

SCISOR: extracting information from on-line news

The future of natural language text processing is examined in the SCISOR prototype. Drawing on artificial intelligence techniques, and applying them to financial news items, this powerful tool illustrates some of the future benefits of natural language analysis through a combination of bottom-up and top-down processing.
and
Research and Advances

Parallel discrete event simulation

Parallel discrete event simulation (PDES), sometimes called distributed simulation, refers to the execution of a single discrete event simulation program on a parallel computer. PDES has attracted a considerable amount of interest in recent years. From a pragmatic standpoint, this interest arises from the fact that large simulations in engineering, computer science, economics, and military applications, to mention a few, consume enormous amounts of time on sequential machines. From an academic point of view, parallel simulation is interesting because it represents a problem domain that often contains substantial amounts of parallelism (e.g., see [59]), yet paradoxically, is surprisingly difficult to parallelize in practice. A sufficiently general solution to the PDES problem may lead to new insights in parallel computation as a whole. Historically, the irregular, data-dependent nature of PDES programs has identified it as an application where vectorization techniques using supercomputer hardware provide little benefit [14].A discrete event simulation model assumes the system being simulated only changes state at discrete points in simulated time. The simulation model jumps from one state to another upon the occurrence of an event. For example, a simulator of a store-and-forward communication network might include state variables to indicate the length of message queues, the status of communication links (busy or idle), etc. Typical events might include arrival of a message at some node in the network, forwarding a message to another network node, component failures, etc.We are especially concerned with the simulation of asynchronous systems where events are not synchronized by a global clock, but rather, occur at irregular time intervals. For these systems, few simulator events occur at any single point in simulated time; therefore parallelization techniques based on lock-step execution using a global simulation clock perform poorly or require assumptions in the timing model that may compromise the fidelity of the simulation. Concurrent execution of events at different points in simulated time is required, but as we shall soon see, this introduces interesting synchronization problems that are at the heart of the PDES problem.This article deals with the execution of a simulation program on a parallel computer by decomposing the simulation application into a set of concurrently executing processes. For completeness, we conclude this section by mentioning other approaches to exploiting parallelism in simulation problems.Comfort and Shepard et al. have proposed using dedicated functional units to implement specific sequential simulation functions, (e.g., event list manipulation and random number generation [20, 23, 47]). This method can provide only a limited amount of speedup, however. Zhang, Zeigler, and Concepcion use the hierarchical decomposition of the simulation model to allow an event consisting of several subevents to be processed concurrently [21, 98]. A third alternative is to execute independent, sequential simulation programs on different processors [11, 39]. This replicated trials approach is useful if the simulation is largely stochastic and one is performing long simulation runs to reduce variance, or if one is attempting to simulate a specific simulation problem across a large number of different parameter settings. However, one drawback with this approach is that each processor must contain sufficient memory to hold the entire simulation. Furthermore, this approach is less suitable in a design environment where results of one experiment are used to determine the experiment that should be performed next because one must wait for a sequential execution to be completed before results are obtained.
Research and Advances

NEST: a network simulation and prototyping testbed

The Network Simulation Testbed (NEST) is a graphical environment for simulation and rapid-prototyping of distributed networked systems and protocols. Designers of distributed networked systems require the ability to study the systems operations under a variety of simulated network scenarios. For example, designers of a routing protocol need to study the steady-state performance features of the mechanism as well as its dynamic response to failure of links or switching nodes. Similarly, designers of a distributed transaction processing system need to study the performance of the system under a variety of load models as well as its response to failure conditions. NEST provides a complete environment for modeling, execution and monitoring of distributed systems of arbitrary complexity. NEST is embedded within a standard UNIX environment. A user develops a simulation model of a communication network using a set of graphical tools provided by the NEST generic monitor tools. Node functions (e.g., routing protocol) as well as communication link behaviors (e.g., packet loss or delay features) are typically coded by the user in C; in theory, any high-level block-structured language could be supported for this function. These procedures provided by the user are linked with the simulated network model and executed efficiently by the NEST simulation server. The user can reconfigure the simulation scenario either through graphical interaction or under program control. The results of an execution can be graphically monitored through custom monitors, developed using NEST graphical tools. NEST may thus be used to conduct simulation studies of arbitrary distributed networked systems. However, unlike pure simulation tools, NEST may also be used as an environment for rapid prototyping of distributed systems and protocols. The actual code of the systems developed in this manner can be used at any development stage as the node functions for a simulation. The behavior of the system may be examined under a variety of simulated scenarios. For example, in the development of a routing protocol for a mobile packet radio network, it is possible to examine the speed with which the routing protocol responds to changes in the topology, the probability and expected duration of a routing loop. The actual code of the routing protocol may be embedded as node functions within NEST. The only modifications of the code will involve use of NEST calls upon the simulated network to send, receive or broadcast a message. Thus NEST is particularly useful as a tool to study the performance behavior of real (or realisticly modeled) distributed systems in response to simulated complex dynamical network behaviors. Such dynamic response is typically beyond the scope of analytical techniques restricted to model steady-state equilibrium behaviors. Traditional approaches to simulation are either language-based or model-based. Language-based approaches (e.g., Simula, Simscript) provide users with specialized programming language constructs to support modeling and simulation. The key advantage of these approaches is their generality of applications. These approaches, however, are fundamentally limited as tools to study complex distributed systems: First, they separate the tasks of modeling and simulation from those of design and development. A designer of a network protocol is required to develop the code in one environment using one language (e.g., C), while simultaneously developing a consistent simulation model (e.g., in Simscript). The distinctions between the simulation model and the actual system may be significant enough to reduce the effectiveness of simulation. This is particularly true for complex systems involving a long design cycle and significant changes. Second, these approaches require the modeler to efficiently manage the complexity of scheduling distributed system models (under arbitrary network scenarios). Model-based approaches (e.g., queuing-network simulators such as IBM's RESQ [12]) provide users with extensive collections of tools supporting a particular simulation-modeling technique. The key advantage of model-based approaches is the efficiency with which they may handle large-scale simulations by utilizing model-specific techniques (e.g., fast algorithms to solve complex queuing network models). Their key disadvantage is a narrower scope of applications and questions that they may answer. For example, it is not possible within a pure queuing-network model to model and analyze complex transient behaviors (e.g., formation of routing loops in a mobile packet radio network). The model-based approach, like the language-based approaches, suffers from having simulation/testing separated from design/development. It has the additional important disadvantage of requiring users to develop in-depth understanding of the modeling techniques. Designers of distributed database transaction systems are often unfamiliar with queuing models. NEST pursues a different approach to simulation studies: extending a networked operating system environment to support simulation modeling and efficient execution. This environment-based approach to simulation shares the generality of its modeling power with language-based approaches. NEST may be used to model arbitrary distributed interacting systems. NEST also shares with the language-based approach an internal execution architecture that accomplishes very efficient scheduling of a large number of processes. However, unlike language-based approaches, the user does not need to be concerned with management of complex simulation scheduling problems. Furthermore, NEST does not require the user to master or use a separate simulation language facility; the processes of design, development and simulation are fully integrated. The user can study the behavior of the actual system being developed (at any level of detail) under arbitrary simulated scenarios. The routing protocol designer, for example, can attach the routing protocol designed (actual code with minor adjustments) to a NEST simulation and study the system behavior. As the system changes through the design process, new simulation studies may be conducted by attaching the new code to the same simulation models. NEST can thus be used as an integral part of the design process along with other tools (e.g., for debugging). In similarity to model-based approaches, NEST is specifically targeted toward a limited scope of applications: distributed networked systems. NEST supports a built-in customizable communication network model. However, this scope has been sufficiently broad to support studies ranging from low-level communication protocols to complex distributed transaction processing systems, avionic systems and even manufacturing processes. The environment-based approach to simulation offers a few important attractions to users: 1. Simulation is integrated with the range of tools supported by the environment. The user can utilize graphics, statistical packages, debuggers and other standard tools of choice in the simulation study. Simulation can become an integral part of a standard development process. 2. Users need not develop extensive new skills or knowledge to pursue simulation studies. 3. Standard features of the environment can be used to enhance the range of applicability. NEST simulation is configured as a network server with monitors as clients. The client/server model permits multiple remote accesses to a shared testbed. This can be very important in supporting a large-scale multisite project. In this article we describe the architecture of NEST, illustrate its use, and describe some aspects of NEST implementation. We will also feature its design and provide examples of NEST applications.
, , , and
Opinion

Practical programmer: Software teams

I have often heard the phrase, “We see what we know.” As technicians, we concentrate on technical ways to manage complexity: abstraction, design techniques, high-level languages, and so on. That is what we know best. But when the tale is told of a project that failed, the blame is often laid not on technical difficulties, but on management and interpersonal problems.In the last six months, I have seen firsthand how attention to the social organization of a software team can make a big difference in the success of a development project. I work in a “Research and Development” group. “Research” means that some aspects of the project are experimental—we do not know for sure what is going to work. “Development” means we are expected to produce high-quality software for real users. So while we want to encourage creative thought, we must pay heed to the lessons of commercial software developers in quality assurance, testing, documentation, and project control.Our all-wise project leader decided we also needed to pay heed to the lessons of sociology. In particular, we began to apply the ideas found in Larry Constantine's work on the organization of software teams. Our efforts have resulted in a team that is productive, flexible, and comfortable. I thought these qualities are unusual enough to merit a column on the subject.
Research and Advances

Introduction—object-oriented design

Object-oriented, a buzzword of the late 1980s, has evolved into an accepted technology that has recognized benefits for the software development process. In its progression from a purely procedural approach, software development reached a data-driven—object-based—approach, and has grown beyond that to the object-oriented approach. The impact of the object-oriented approach is not limited to the design portion of the software development life cycle—its effects are evident at every phase. One of the strengths of the object model is that it provides a unifying element that is common to every phase of the life cycle. This uniformity provides a smooth transition from one phase to the next. The article by Henderson-Sellers and Edwards presents a revision of the traditional life cycle based on the object-oriented approach. It discusses the unique view of the design process and describes how it works: the process takes a specified problem and decomposes it. The resulting product forms the framework for a computer-based solution to the problem. Object-oriented techniques begin this decomposition process in the analysis phase and carry it on into the design phase. A modeling paradigm is used for the decomposition process: The top layer of an object-oriented system is a model of the real-life situation for which the software system is being created. The underlying layers provide the implementation of this model.The “pieces” produced by object-oriented techniques are as unique as the design perspective. Its obvious similarities to and subtle differences from abstract data type (ADT) technology have led to much discussion of objects and classes in terms of ADTs. The unique coupling of data and behavior in the object-oriented components provides much more than a syntactic distinction from the usual ADT. Added to the modeling approach, it produces a recognizably different approach to systems development.The term object-oriented is defined differently by different people. Many professionals agree with the basics of Wegner's definition1 that object-oriented includes three concepts: objects, classes, and class inheritance. Some would add a variety of other requirements including such concepts as polymorphism, dynamic binding, encapsulation, etc. The article by Korson and McGregor provides an overview of these concepts, leaving room for the reader to decide which to include and which to exclude; it also provides an overview of the basic concepts of object-oriented design.The production of software in an increasingly competitive environment is making reuse a priority of software professionals. The popularity of the object-oriented technique is due, in part, to its support for reuse. Two important factors influence reuse: First, it is necessary to have a set of high-quality components that are worth reusing. Second, the components must be well-defined, easy to integrate, and efficient. Meyer's article presents some experiences in developing the classes for the Eiffel library; it also discusses characteristics of the library. For components to be reused, the designer must have the means to locate a component which models an entity in the current problem. Not only must the component be located, but often necessary supporting pieces must be found as well. The article by Gibbs et al. provides information on the management of classes and the software components of the object-oriented paradigm.Tom DeMarco, in a recent interview,2 declared parallel computing to be the emerging new paradigm. According to DeMarco object-oriented techniques will be an integral partner in this emergence. DeMarco observed that designing with objects preserves the natural parallelism in a problem. Agha addresses models for parallel objects, presenting an overview of the problem and focusing on the actor model as a possible solution. He presents examples of design issues when using the actor model. He also considers a basic reflective design architecture.The importance of well-defined and well-managed abstractions in the software development process is discussed in the articles by Meyer and by Gibbs et al as they explore what has come to be called the software base, the set of software components from which future products will be built.The unique components developed by object-oriented methods are characterized by an interface that is separate from the implementation of that behavior. The designer is free to concentrate on modeling the problem at hand either by developing specific classes or by locating and reusing existing classes that model some subset of the needed behavior. Meyer focuses on what he quotes McIlroy as terming a “software components subindustry,”3 presenting a case study of the development of the Eiffel libraries.The final article in this special issue, by Henderson-Sellers and Edwards discusses modifications to the traditional life cycle supported by the object-oriented approach. The modified life cycle recognizes the iterative nature of the development process and incorporates that characteristic into its model.Wirfs-Brock and Johnson present a sampling of current research into several aspects of object-oriented design. Their survey includes efforts to improve reusability through design technique and paradigm-specific tools. The works are representative of the broad spectrum of research activity currently under way.We would like to thank the authors in this special issue for their hours of work both in developing their own articles and for the time spent evaluating and commenting upon the other articles.
and
Opinion

Inside risks: a few old coincidences

Computer Puns Considered Harmful: Presented here are two old examples of harmful input sequences that might be called computer puns. Each has a double meaning, depending upon context.Xerox PARC's pioneering WYSI-WYG editor BRAVO [1] had a lurking danger. In edit mode, BRAVO interpreted the sequence edit as “Everything Deleted Insert t,” which did exactly that—transformed a large file into the letter ‘t’ without blinking. After the first two characters, it was still possible to undo the ‘ed,’ but once the ‘i’ was typed the only remaining fallback was to replay the recorded keystroke log from the beginning of the editing session (except for ‘edit’) against the still-unaltered original file.A similar example was reported by Norman Cohen of SofTech: he had been entering text using the University of Maryland line editor on the Univac 1100 for an hour or two, when he entered two lines that resulted in the entire file being wiped out. The first line contained exactly 80 characters (demarcated by a final carriage return); the second line began with the word “about.” Cohen said: “Because the first line was exactly 80 characters long, the terminal handler inserted its own CR just before mine, but I started typing the second line before the generated CR reached the terminal. When I finished entering the second line, a series of queued output lines poured out of the terminal. It seems that, having received the CR generated by the terminal handler, the editor interpreted my CR as a request to return from input mode to edit mode. In edit mode, the editor processed the second line by interpreting the first three letters as an abbreviation for abort and refused to be bothered by the rest of the line. Had the editing session been interrupted by a system crash, an autosave feature would have saved all but the last 0-20 lines I had entered. However, the editor treated the abort request as a deliberate action on my part, and nothing was saved.Two Wrongs Make a Right (Sometimes):A somewhat obscure wiring fault remained undetected for many years in the Harvard Mark I. Each decimal memory register consisted of 23 ten-position stepping switches (plus a sign switch). Registers were used dually as memory locations and as adders. The wires into (and out of) the least significant two digits of the last register were crossed, so that the least significant position was actually the second-to-least position and vice versa with respect to memory. No problems arose for many years during which that register was used fortuitously only for memory in the computation of tables of Bessel functions of the nth kind; the read-in error corrected itself on read-out. The problem finally manifested itself on the n + 1st tables when that register was used as an adder and a carry went in the wrong direction. This was detected only because it was standard practice in those days to difference the resulting tables by hand (using very old adding machines). Things have changed and we have learned a lot; however, similar problems continue to arise, often in new guises. Discussion:Today's systems have comparable dangers lurking, with even more global effects. In user interfaces, we have all experienced a slight error in a command having devastating consequences. In software, commands typed in one window or in one directory may have radically different effects in other contexts. Programs are often not written carefully enough to be independent of environmental irregularities and less-than-perfect users. Search paths provide all sorts of opportunities for similar computer puns (including triggering of Trojan horses). Accidental deletion is still quite common, although we now have undelete operations. In hardware, various flaws in chip designs have persisted into delivery.Many of you will have similar tales to tell. Please contribute them.Conclusions: Designers of human interfaces should spend much more time anticipating human foibles. Crosschecking and backups are ancient techniques, but still essential. Computers do not generally appreciate puns.
Research and Advances

Understanding object-oriented: a unifying paradigm

The need to develop and maintain large complex software systems in a competitive and dynamic environment has driven interest in new approaches to software design and development. The problems with the classical waterfall model have been cataloged in almost every software engineering text [19,23]. In response, alternative models such as the spiral [2], and fountain [9] have been proposed. Problems with traditional development using the classical life cycle include no iteration, no emphasis on reuse, and no unifying model to integrate the phases. The difference in point of view between following data flows in structured analysis and building hierarchies of tasks in structured design has always been a major problem [4]. Each system is built from scratch and maintenance costs account for a notoriously large share of total system costs. The object-oriented paradigm addresses each of these issues. A look at the object-oriented software life cycle, as described by Meyer [5], Coad and Yourdon [4], and Henderson-Sellers and Edwards [9], identifies the three traditional activities of analysis, design, and implementation. However, each of the referenced descriptions eliminates the distinct boundaries between the phases. The primary reason for this blurring of boundaries is that the items of interest in each phase are the same: objects. Objects and the relationships between objects are identified in both the analysis and design phases. Objects and relationships identified and documented in the analysis phase serve not only as input to the design phase, but as an initial layer in the design. This continuity provides for a much more seamless interface between the phases. Analysts, designers and programmers are working with a common set of items upon which to build. A second reason for the blurring of these boundaries is that the object-oriented development process is iterative. Henderson-Sellers and Edwards further refine this idea by replacing the waterfall model of software development with a fountain model. Development reaches a high level only to fall back to a previous level to begin the climb once again. As an example of the blurring of the traditional boundaries of the life cycle phases, Coad and Yourdon recommend that classification relationships between objects be captured and documented during the object-oriented analysis (OOA) phase. This classification will be directly reflected in the class inheritance structure developed in the design and in the code. This classification is in no way required in order to document the system requirements. In other words, Coad and Yourdon are recommending a traditional design activity in the analysis phase. The blurring of the traditional design and implementation phases has been fueled by the development of encapsulation and abstraction mechanisms in object-oriented and object-based languages. For example, Meyer claims [14] that Eiffel is both a design and an implementation language. He goes on to say that software design is sometimes mistakenly viewed as an activity totally secluded from actual implementation. From his point of view, much is to be gained from an approach that integrates both activities within the same conceptual framework. The object-oriented design paradigm is the next logical step in a progression that has led from a purely procedural approach to an object-based approach and now to the object-oriented approach. The progression has resulted from a gradual shift in point of view in the development process. The procedural design paradigm utilizes functional decomposition to specify the tasks to be completed in order to solve a problem. The object-based approach, typified by the techniques of Yourdon, Jackson and Booth, gives more attention to data specifications than the procedural approach but still utilizes functional decomposition to develop the architecture of a system. The object-oriented approach goes beyond the object-based technique in the emphasis given to data by utilizing the relationships between objects as a fundamental part of the system architecture. The goal in designing individual software components is to represent a concept in what will eventually be an executable form. The Abstract Data Type (ADT) is the object-based paradigm's technique for capturing this conceptual information. The class is the object-oriented paradigm's conceptual modeling tool. The design pieces resulting from the object-oriented design technique represent a tighter coupling of data and functionality than traditional ADTs. These artifacts of the design process used in conjunction with a modeling-based decomposition approach yield a paradigm, a technique, which is very natural and flexible. It is natural in the sense that the design pieces are closely identified with the real-world concepts which they model. It is flexible in the sense of quickly adapting to changes in the problem specifications. Object-oriented remains a term which is interpreted differently by different people. Before presenting an overview of a set of techniques for the design process, we will give our perspective so the reader may judge the techniques in terms of those definitions. Briefly, we adapt Wegner's [27] definition for object-oriented languages to object-oriented design. The pieces of the design are objects which are grouped into classes for specification purposes. In addition to traditional dependencies between data elements, an inheritance relation between classes is used to express specializations and generalizations of the concepts represented by the classes. As natural and flexible as the object-oriented technique is, it is still possible to produce a bad design when using it. We will consider a number of general design criteria and will discuss how the object-oriented approach assists the designer in meeting these criteria. We will refer to a number of design guidelines developed specifically for the object-oriented design paradigm and will discuss how these properties reinforce the concepts of good design. The paradigm sprang from language, has matured into design, and has recently moved into analysis. The blurring of boundaries between these phases has led us to include topics in this article that are outside the realm of design, but which we consider important to understanding the design process. Since the paradigm sprang from language, we define the concepts basic to object-oriented programming in the following section.
and
Research and Advances

Concurrent object-oriented programming

Three significant trends have underscored the central role of concurrency in computing. First, there is increased use of interacting processes by individual users, for example, application programs running on X windows. Second, workstation networks have become a cost-effective mechanism for resource sharing and distributed problem solving. For example, loosely coupled problems, such as finding all the factors of large prime numbers, have been solved by utilizing ideal cycles on networks of hundreds of workstations. A loosely coupled problem is one which can be easily partitioned into many smaller subproblems so that interactions between the subproblems is quite limited. Finally, multiprocessor technology has advanced to the point of providing supercomputing power at a fraction of the traditional cost.At the same time, software engineering considerations such as the need for data abstraction to promote program modularity underlie the rapid acceptance of object-oriented programming methodology. By separating the specification of what is done (the abstraction) from how it is done (the implementation), the concept of objects provides modularity necessary for programming in the large. It turns out that concurrency is a natural consequence of the concept of objects. In fact Simula, the first object-oriented language, simulated a simple form of concurrency using coroutines on conventional architectures. Current development of concurrent object-oriented programming (COOP) is providing a solid software foundation for concurrent computing on multiprocessors, Future generation computing systems are likely to be based on the foundations being developed by this emerging software technology.The goal of this article is to discuss the foundations and methodology of COOP. Concurrency refers to the potentially parallel execution of parts of a computation. In a concurrent computation, the components of a program may be executed sequentially, or they may be executed in parallel. Concurrency provides us with the flexibility to interleave the execution of components of a program on a single processor, or to distribute it among several processors. Concurrency abstracts away some of the details in an execution, allowing us to concentrate on conceptual issues without having to be concerned with a particular order of execution which may result from the quirks of a given system.Objects can be defined as entities which encapsulate data and operations into a single computational unit. Object models differ in how the internal behavior of objects is specified. Further, models of concurrent computation based on objects must specify how the objects interact, and different design concerns have led to different models of communication between objects. Object-oriented programming builds on the concepts of objects by supporting patterns of reuse and classification, for example, through the use of inheritance which allows all instances of a particular class to share the same method.In the following section, we outline some common patterns of concurrent problem solving. These patterns can be easily expressed in terms of the rich variety of structures provided by COOP. In particular, we discuss the actor model as a framework for concurrent systems1 and some concepts which are useful in building actor systems. We will then describe some other models of objects and their relation to the actor model along with novel techniques for supporting reusability and modularity in concurrent object-oriented programming. The last section briefly outlines some major on-going projects in COOP.It is important to note that the actor languages give special emphasis to developing flexible program structures which simplify reasoning about programs. By reasoning we do not narrowly restrict ourselves to the problem of program verification—an important program of research whose direct practical utility has yet to be established. Rather our interest is in the ability to understand the properties of software because of clarity in the structure of the code. Such an understanding may be gained by reasoning either informally or formally about programs. The ease with which we can carry out such reasoning is aided by two factors: by modularity in code which is the result of the ability to separate design concerns, and by the ability to abstract program structures which occur repeatedly. In particular, because of their flexible structure, actor languages are particularly well-suited to rapid prototyping applications.
Research and Advances

Surveying current research in object-oriented design

The state of object-oriented is evolving rapidly. This survey describes what are currently thought to be the key ideas. Although it is necessarily incomplete, it contains both academic and industrial efforts and describes work in both the United States and Europe. It ignores well-known ideas, like that of Coad and Meyer [34], in favor of less widely known projects.Research in object-oriented design can be divided many ways. Some research is focused on describing a design process. Some is focused on finding rules for good designs. A third approach is to build tools to support design. Most of the research described in this article does all three.We first present work from Alan Snyder at Hewlett-Packard on developing a common framework for object-oriented terminology. The goal of this effort is to develop and communicate a corporate-wide common language for specifying and communicating about objects.We next look into the research activity at Hewlett-Packard, led by Dennis de Champeaux. De Champeaux is developing a model for object-based analysis. His current research focuses on the use of a trigger-based model for inter-object communications and development of a top-down approach to analysis using ensembles.We then survey two research activities that prescribe the design process. Rebecca Wirfs-Brock from Tektronix has been developing an object-oriented design method that focuses on object responsibilities and collaborations. The method includes graphical tools for improving encapsulation and understanding patterns of object communication. Trygve Reenskaug at the Center for Industriforskning in Oslo, Norway has been developing an object-oriented design method that focuses on roles, synthesis, and structuring. The method, called Object-Oriented Role Analysis, Syntheses and Structuring, is based on first modeling small sub-problems, and then combining small models into larger ones in a controlled manner using both inheritance (synthesis) and run-time binding (structuring).We then present investigations by Ralph Johnson at the University of Illinois at Urbana-Champaign into object-oriented frameworks and the reuse of large-scale designs. A framework is a high-level design or application architecture and consists of a suite of classes that are specifically designed to be refined and used as a group. Past work has focused on describing frameworks and how they are developed. Current work includes the design of tools to make it easier to design frameworks.Finally, we present some results from the research group in object-oriented software engineering at Northeastern University, led by Karl Lieberherr. They have been working on object-oriented Computer Assisted Software Engineering (CASE) technology, called the Demeterm system, which generates language-specific class definitions from language-independent class dictionaries. The Demeter system include tools for checking design rules and for implementing a design.
and
Research and Advances

Trellis: turning designs into programs

When designing an object-oriented program, there are several goals to achieve: The program should accurately model the real-world objects to be represented. This leads to a program that is easier to understand and therefore simpler to maintain. Code that implements the model accurately must also be robust. Inconsistent models should be detected at design time, not diagnosed as a run-time error at a customer's installation. The programming environment must allow for convenient exploration of the application; it should foster a reuse of existing types of objects, thus reducing the scale of the design. It should also facilitate changes to the program as the application design is updated. The Trellis programming system is an integrated language and environment that provides many of the mechanisms needed to design and implement object-oriented programs. The remainder of this sidebar discusses how Trellis helps attain the goals outlined above.
Research and Advances

Lessons from the design of the Eiffel libraries

The nature of programming is changing. Most of the software engineering literature still takes for granted a world of individual projects, where the sole aim is to produce specific software systems in response to particular requirements, little attention being paid to each system's relationship to previous or subsequent efforts. This implicit model seems unlikely to allow drastic improvements in software quality and productivity. Such order-of-magnitude advances will require a process of industrialization, not unlike what happened in those disciplines which have been successful at establishing a production process based on the reuse of quality-standardized components. This implies a shift to a “new culture” [14] whose emphasis is not on projects but instead on components. The need for such a shift was cogently expressed more than 20 years ago by Doug McIlroy in his contribution, entitled Mass-Produced Software Components [10], to the now-famous first conference on software engineering: Software production today appears in the scale of industrialization somewhere below the more backward construction industries. I think its proper place is considerably higher, and would like to investigate the prospects for mass-production techniques in software. [...] My thesis is that the software industry is weakly founded [in part because of] the absence of a software components subindustry [...] A components industry could be immensely successful. Although reuse has enjoyed modest successes since this statement was made, by all objective criteria McIlroy's prophecy has not been fulfilled yet; many technical and non-technical issues had to be addressed before reuse could become a reality on the scale he foresaw. (See [1] and [20] for a survey of current work on reuse.) One important development was needed to make this possible: the coming age of object-oriented technology, which provides the best known basis for reusable software construction. (That the founding document of object-oriented methods, the initial description of Simula 67, was roughly contemporary with McIlroy's paper tends to confirm a somewhat pessimistic version of Redwine and Riddle's contention [18] that “it takes on the order of 15 to 20 years to mature a technology to the point that it can be popularized to the technical community at large.”) Much of the current excitement about object-oriented software construction derives from the growing realization that the shift is now technically possible. This article presents the concerted efforts which have been made to advance the cause of component-based software development in the Eiffel environment [12, 17] through the construction of the Basic Eiffel Libraries. After a brief overview of the libraries, this article reviews the major language techniques that have made them possible (with more background about Eiffel being provided by the sidebar entitled “Major Eiffel Techniques”); it then discusses design issues for libraries of reusable components, the use of inheritance hierarchies, the indexing problem, and planned developments.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More