title: Call Graph Construction in Object-Oriented Languages

authors:
David Grove
Greg DeFouw
Jeffrey Dean
Craig Chambers

abstract: Interprocedural analyses enable optimizing compilers to more precisely model the effects of non-inlined procedure calls, potentially resulting in substantial increases in application performance. Applying interprocedural analysis to programs written in object-oriented or functional languages is complicated by the difficulty of constructing an accurate program call graph. This paper presents a parameterized algorithmic framework for call graph construction in the presence of message sends and/or first class functions. We use this framework to describe and to implement a number of well-known and new algorithms. We then empirically assess these algorithms by applying them to a suite of medium-sized programs written in Cecil and Java, reporting on the relative cost of the analyses, the relative precision of the constructed call graphs, and the impact of this precision on the effectiveness of a number of interprocedural optimizations.

awards: Most Influential OOPSLA Paper (awarded 2007)


venue: oopsla

title: An Open Implementation Analysis and Design for Lightweight Threads

abstract: Open Implementation Analysis and Design (OIA/D) has been introduced as a design methodology for object-oriented software systems, and in particular for substrate software. In this paper we detail our experiences with using OIA/D to design and implement a common substrate component for parallel language runtime systems: a lightweight threads package. We show how existing thread packages employ a "black-box" design, hiding crucial design decisions that drastically reduce their ability to be re-used. We detail these design decisions (dilemmas) and show how an implementation based on OIA/D principles results in a thread package that is flexible, efficient, portable, and re-usable.


title: The Design and Performance of a Hard Real-Time Object Event Service

authors:
Timothy H. Harrison
David L. Levine
Douglas C. Schmidt

abstract: The CORBA Event Service provides a flexible model for asynchronous communication among objects. However, the standard CORBA Event Service specification lacks important features required by real-time applications. For instance, operational flight programs for fighter aircraft have complex real-time processing requirements. This paper describes the design and performance of an object-oriented, real-time implementation of the GORBA Event Service that is designed to meet these requirements.This paper makes three contributions to the design and performance measurement of object-oriented real-time systems. First, it illustrates how to extend the CORBA Event Service so that it is suitable for real-time systems. These extensions support periodic rate-based event processing and efficient event filtering and correlation. Second, it describes how to develop object-oriented event dispatching and scheduling mechanisms that can provide real-time guarantees. Finally, the paper presents benchmarks that demonstrate the performance tradeoffs of alternative concurrent dispatching mechanisms for real-time Event Services.


title: Ephemerons: A New Finalization Mechanism

abstract: Finalization occurs when a garbage collector informs an application that an object is "almost collectable." It is used to help an application maintain its invariants. To make finalization more useful, this paper defines "almost collectable" in terms of a new class of objects, called ephemerons. Ephemerons are similar to weak pairs, but an object in an ephemeron's key field may be classed as "almost collectable" even if it is reachable from the epehemeron's value fields.


title: The OT Life-cycle: From Eureka! to Shrink Wrap (Panel)

authors:
Laura Hill
Bruce Anderson
Adele Goldberg
Gregor Kiczales
Colin Scott
Kevin Tyson

abstract: Over the past years, the Object Technology community has seen the birth of a number of new technology ideas that have changed the way we do computing. These ideas have affected compiler design, analysis approaches, project management techniques, user interface design, deployment strategies and implementation tactics. But where do these ideas come from? And how do they evolve? Do they address the needs as specified by members of the Object Community? Is there a way we can nurture the introduction and assimilation of these ideas to and by the community at large? And what are the market forces that bend ideas to their will. This panel will look at new ideas in Object Technology from a variety of perspectives and will attempt to get to the heart of the way that we, as technologists, create, buy, sell and grow ideas.


title: Garbage Collecting the World: One Car at a Time

authors:
Richard L. Hudson
Ronald Morrison
J. Eliot B. Moss
David S. Munro

abstract: A new garbage collection algorithm for distributed object systems, called DMOS (Distributed. Mature Object Space), is presented. It is derived from two previous algorithms, MOS (Mature Object Space), sometimes called the train algorithm, and PMOS (Persistent Mature Object Space). The contribution of DMOS is that it provides the following unique combination of properties for a distributed collector: safety, completeness, non-disruptiveness, incrementality, and scalability. Furthermore, the DMOS collector is non-blocking and does not use global tracing.


title: Back to the Future: The Story of Squeak - A Usable Smalltalk Written in Itself

authors:
Dan Ingalls
Ted Kaehler
John Maloney
Scott Wallace
Alan C. Kay

abstract: Squeak is an open, highly-portable Smalltalk implementation whose virtual machine is written entirely in Smalltalk, making it easy to. debug, analyze, and change. To achieve practical performance, a translator produces an equivalent C program whose performance is comparable to commercial Smalltalks.Other noteworthy aspects of Squeak include: a compact object format that typically requires only a single word of overhead per object; a simple yet efficient incremental garbage collector for 32-bit direct pointers; efficient bulk-mutation of objects; extensions of BitBlt to handle color of any depth and anti-aliased image rotation and scaling; and real-time sound and music synthesis written entirely in Smalltalk.


title: Constraint Diagrams: Visualizing Assertions in Object-Oriented Models

abstract: A new visual notation is proposed for precisely expressing constraints on object-oriented models, as an alternative to mathematical logic notation used in methods such as Syntropy and Catalysis. The notation is potentially intuitive, expressive, integrates well with existing visual notations, and has a clear and unambiguous semantics. It is reminiscent of informal diagrams used by mathematicians for illustrating relations, and borrows much from Venn diagrams. It may be viewed as a generalization of instance diagrams.


title: Query-Based Debugging of Object-Oriented Programs

authors:
Raimondas Lencevicius
Urs Hölzle
Ambuj K. Singh

abstract: Object relationships in modem software systems are becoming increasingly numerous and complex. Programmers who try to find violations of such relationships need new tools that allow them to explore objects in a large system more efficiently. Many existing debuggers present only a low-level, one-object-at-a-time view of objects and their relationships. We propose a new solution to overcome these problems: query-based debugging. The implementation of the query-based debugger described here offers programmers an effective query tool that allows efficient searching of large object spaces and quick verification of complex relationships. Even for programs that have large numbers of objects, the debugger achieves interactive response times for common queries by using a combination of fast searching primitives, query optimization, and incremental result delivery.


title: Modeling Dynamic Collections of Interdependent Objects Using Path-Based Rules

authors:
Diane J. Litman
Anil Mishra
Peter F. Patel-Schneider

abstract: Standard object-oriented languages do not provide language support for modeling changing collections of interdependent objects. We propose that R++, an integration of the rule and objectoriented paradigms, provides a mechanism for easily implementing such models. R++ extends C++ by adding a new programming construct called the path-based rule. Such data-driven rules are restricted to follow pointers between objects, and are like "automatic methods" that are triggered by changes to monitored objects. Path-based rules encourage a more abstract level of programming, and unlike previous rule integrations, are not at odds with the object-oriented paradigm and offer performance advantages for natural applications. 1 Introduction Object-oriented languages have simplified the design and implementation of sophisticated applications. However, as application domains have become increasingly dynamic and complex, it has become necessary to model such domains using changing collections of interdep...


title: Tiling Design Patterns - A Case Study Using the Interpreter Pattern

abstract: This paper explains how patterns can be used to describe the implementation of other patterns. It is demonstrated how certain design patterns can describe their own design. This is a fundamental reflexive relationship in pattern relationships. The process of assembling patterns by other patterns is named pattern tiling. Tiling enables us to interweave simple understood concepts of patterns into their complex real-life implementation. Several pattern tilings for the Interpreter design pattern are illustrated.


title: Maintaining the Consistency of Class Libraries During Their Evolution

abstract: Two important problems of object-oriented reuse are the propagation of design and implementation specifics of the base software to the inheritors, and the protection of the inheritors against changes in the base software. In this paper, we argue that the simple inheritance rules of existing object-oriented languages are not sufficient for properly dealing with these problems. In the proposal presented in this paper, programmers are enabled to make metalevel declarations of the internal protocols and dependencies of their classes. Additionally, changes of the base module are automatically monitored to filter out information about the alterations that may invalidate already existing inheritors. Based on these informations, the subclassing semantics is adjusted such that the maintenance of the base module properties and the protection of the inheritor is ensured during their integration, In this way, language support is provided for keeping the behavior of reusable software consistent during its evolution.


title: Migrating Relational Data to an OODB: Strategies and Lessons from a Molecular Biology Experience

authors:
Jon R. Oler
Gary Lindstrom
Terence Critchlow

abstract: The growing maturity of ODBMS technology is causing many enterprises to consider migrating relational databases to ODBIMS's. While data remapping is relatively straight-forward in most cases, greater challenges lie in economically and non-invasively adapting legacy application software. We report on a genetics laboratory database migration experiment, which was facilitated by both organization of the relational data in object-like form and a C++-framework designed to insulate application code from relational artifacts. Although this experiment was largely successful, we discovered to our surprise that the framework failed to encapsulate three subtle aspects of the relational implementation, thereby ''contaminating'' application code. We analyze the underlying issues, and offer cautionary guidance to future migrators.


title: Analyzing and Measuring Reusability in Object-Oriented Designs

authors:
Margaretha W. Price
Steven A. Demurjian

abstract: In this paper, we present a technique to analyze and measure the reusability of object-oriented (OO) designs. The metrics can be incorporated into a design/development environment, so that reusability measurements, analysis, and improvements can be part of "business as usual" for an organization. Design reusability measurements also enable early identification of poor reuse potential, when it is still possible to modify/refine the design. The essential components of our approach are two reuse-specific characterizations of classes and hierarchies, and a set of metrics which objectively measures the dependencies among design components based on those reuse-specific characterizations.


title: Exploring Largebess, Complexity and Scalability from the OOT Perspective (Panel)

authors:
Bindu Rama Rao
Chad Edwards
Ted Linden
Reagan W. Moore
Mark Seager

abstract: This panel will lay the foundation for understanding the needs of Large Systems so that OO practitioners can:• appreciate the problems faced;• understand the issues involved; and• re-orient the approaches to provide a viable solution when participating in similar efforts.Specifically, this panel will establish the foundation for discussions on Large Systems by establishing concepts, exposing terminology, and highlighting the state-of-the art.Large applications are usually complex and display one or more of the following dimensions of largeness:• Processing power: requiring tens to hundreds of gigabytes of memory and hundreds of gigaflops performance• High connectivity: highly-connected, systems can show aggregate behavior with complex characteristics: they can become chaotic.• Online access: Archival of terabytes of information, with the need to provide online access to information• Archival and online retrieval: The two technologies (database and archival storage), however, currently do not interoperate. There is a need to develop interfaces to integrate these two technologies.• Data-intensive scientific applications: These involve constructing a data handling infrastructure that simplifies the effort required to maintain petabyte archives, identify relevant data sets within the archive, move, the data to processing platforms, and distribute the data sets across multiple nodes.• Internet access: Large applications often require simultaneous access of information by millions of users worldwide;they must provide acceptable response times.• Scaleable architecture: The systems must be prepared to support exponential growth of application load.Is OOT up to the task? OO practitioners will be encountering some of these application domains in the near future. Some may have already gained some experience in trying to solve these problems. However, the literature in OO does not provide sufficient evidence to believe that OO is ready for such large systems today. Part of the problem is the cross-disciplinary nature of these problems requires a steep learning curve for OO practitioners to be effective. The modeling of these problems with an OO approach is also a challenge. Current 00 methods do not do a good job of supporting multiple views of a domain, and multiple layers of a complex application domain.


title: Composite Design Patterns

abstract: Software design patterns are the core abstractions from successful recurring problem solutions in software design. Composite design patterns are the core abstractions from successful recurring frameworks. A composite design pattern is a pattern that is best described as the composition of further patterns the integration of which shows a synergy that makes the composition more than just the sum of its parts. This paper presents examples of composite patterns, discusses a role-based analysis and composition technique, and demonstrates that composite patterns extend the pattern idea from single problem solutions to object-oriented frameworks.


title: Class Hierarchy Specialization

authors:
Frank Tip
Peter F. Sweeney

abstract: Class libraries are generally designed with an emphasis on versatility and extensibility. Applications that use a library typically exercise only part of the library's functionality. As a result, objects created by the application may contain unused members. We present an algorithm that specializes a class hierarchy with respect to its usage in a program P. That is, the algorithm analyzes the member access patterns for P's variables, and creates distinct classes for variables that access different members. Class hierarchy specialization reduces object size, and is hence primarily a space optimization. However, execution time may also be reduced through reduced object creation/destruction time, and caching/paging effects.


title: Efficient Type Inclusion Tests

authors:
Jan Vitek
R. Nigel Horspool
Andreas Krall

abstract: A type inclusion test determines whether one type is a subtype of another. Efficient type testing techniques exist for single subtyping, but not for languages with multiple subtyping. To date, the fast constant-time technique relies on a binary matrix encoding of the subtype relation with quadratic space requirements. In this paper, we present three new encodings of the subtype relation, the packed encoding, the bit-packed encoding and the compact encoding. These encodings have different characteristics. The bit-packed encoding delivers the best compression rates: on average 85% for real life programs. The packed encoding performs type inclusion tests in only 4 machine instructions. We present a fast algorithm for computing these encoding which runs in less than 13 milliseconds for PE and BPE, and 23 milliseconds for CE on an Alpha processor. Finally, we compare our results with other constant-time type inclusion tests on a suite of 11 large -benchmark hierarchies.


title: Declarative Specialization of Object-Oriented Programs

authors:
Eugen-Nicolae Volanschi
Charles Consel
Gilles Muller
Crispin Cowan

abstract: Designing and implementing generic software components is encouraged by languages such as object-oriented ones and commonly advocated in most application areas. Generic software components have many advantages among which the most important is reusability. However, it comes at a price: genericity often incurs a loss of efficiency.This paper presents an approach aimed at reconciling genericity and efficiency. To do so, we introduce declarations to the Java language to enable a programmer to specify how generic programs should be specialized for a particular usage pattern. Our approach has been implemented as a compiler from our extended language into standard Java.


title: Reuse of Algorithms: Still a Challenge to Object-Oriented Programming

abstract: This paper is about reusable, efficient implementations of complex algorithms and their integration into software packages. It seems that this problem is not yetwell understood, and that it is not at all clear how object-oriented and other approaches may contribute to a solution. We analyze the problem and try to reduce it to a few key design goals. Moreover, we discuss various existing approaches in light of these goals, and we briefly report experiences with experimental case studies, in which these goals were rigorously addressed.


title: Efficient Dynamic Dispatch without Virtual Function Tables: The SmallEiffel Compiler

authors:
Olivier Zendra
Dominique Colnet
Suzanne Collin

abstract: SmallEiffel is an Eiffel compiler which uses a fast simple type inference mechanism to remove most late binding calls, replacing them by static bindings. Starting from the system's entry point, it compiles only statically living code, which saves compiling and then removing dead code. As the whole system is analyzed at compile time, multiple inheritance and genericity do not cause any overhead.SmallEiffel features a coding scheme which eliminates the need for virtual function tables. Dynamic dispatch is implemented without any array access but uses a simple static binary branch code. We show that this implementation makes it possible to use modern hardware very efficiently. It also allows us to inline more calls even when dynamic dispatch is required. Some more dispatch sites are removed after the type inference algorithm has been performed, if the different branches of a dispatch site lead to the same code.The advantage of this approach is that it greatly speeds up execution time and considerably decreases the amount of generated code.


title: How to Preserve the Benefits of Design Patterns

authors:
Ellen Agerbo
Aino Cornils

abstract: The rapid evolution of Design Patterns has hampered the benefits gained from using Design Patterns. The increase in the number of Design Patterns makes a common vocabulary unmanageable, and the tracing problem obscures the documentation that should be enhanced by using Design Patterns. We present an analysis of Design Patterns that will strongly reduce the number of Fundamental Design Patterns and show how strong language abstractions can solve the tracing problem and thereby enhance the documentation.


title: Object-Oriented Practice in 1998: Does it help or hinder collaboration? (Panel)

authors:
John Artim
Charlie Bridgeford
Lillian Christman
James Coplien
Mary Beth Rosson
Stanley Taylor
Rebecca Wirfs-Brock

abstract: Groups of people working in concert perform most commercial, industrial or in-house software development. These groups are often quite diverse. This panel brings together object-oriented consultants and developers as well as practitioners and researchers interested in human factors and user-centered design, project management and technical writing. The panel will address the question, "To successfully complete today's projects, does object-oriented development as practiced today do an adequate job of supporting ALL of the participants who must collaborate?"


title: The New Crop of Java Virtual Machines (Panel)

authors:
Lars Bak
John Duimovich
Jesse Fang
Scott Meyer
David M. Ungar


title: Extending the ODMG Object Model with Composite Objects

authors:
Elisa Bertino
Giovanna Guerrini

abstract: In this paper we extend the ODMG object data model with composite objects. A composite object is an object built by aggregating other component objects. Exclusiveness and dependency constraints, as well as referential integrity, can be associated with composition relationships among objects. Our composite object model is developed in the framework of the ODMG object database standard data model, but can be used in both object-oriented and object-relational database systems. In the paper, we propose a language for defining composite objects and we define the semantics of update operations on composite objects. Keywords Object-oriented database systems, composite objects, integrity constraints, data models. INTRODUCTION Object-oriented DBMS (OODBMS) and object-relational DBMS (ORDBMS) are establishing themselves as the new generation DBMS. Object database systems overcome the limitations of relational systems with respect to several emerging data-intensive applications because of thei...


title: Safe Metaclass Programming

authors:
Noury M. N. Bouraqadi-Saâdani
Thomas Ledoux
Fred Rivard

abstract: In a system where classes are treated as first class objects, classes are defined as instances of other classes called metaclasses. An important benefit of using metaclasses is the ability to assign properties to classes (e.g. being abstract, being final, tracing particular messages, supporting multiple inheritance), independently from the base-level code. However, when both inheritance and instantiation are explicitly and simultaneously involved, communication between classes and their instances raises the metaclass compatibility issue. Some languages (such as SMALLTALK) address this issue but do not easily allow the assignment of specific properties to classes. In contrast, other languages (such as CLOS) allow the assignment of specific properties to classes but do not tackle the compatibility issue well.In this paper, we describe a new model of metalevel organization, called the compatibility model, which overcomes this difficulty. It allows safe metaclass programming since it makes it possible to assign specific properties to classes while ensuring metaclass compatibility. Therefore, we can take advantage of the expressive power of metaclasses to build reliable software. We extend this compatibility model in order to enable safe reuse and composition of class specific properties. This extension is implemented in NEOCLASSTALK, a fully reflective SMALLTALK.


title: Making the Future Safe for the Past: Adding Genericity to the Java Programming Language

authors:
Gilad Bracha
Martin Odersky
David Stoutamire
Philip Wadler

abstract: We present GJ, a design that extends the Java programming language with generic types and methods. These are both explained and implemented by translation into the unextended language. The translation closely mimics the way generics are emulated by programmers: it erases all type parameters, maps type variables to their bounds, and inserts casts where needed. Some subtleties of the translation are caused by the handling of overriding.GJ increases expressiveness and safety: code utilizing generic libraries is no longer buried under a plethora of casts, and the corresponding casts inserted by the translation are guaranteed to not fail.GJ is designed to be fully backwards compatible with the current Java language, which simplifies the transition from non-generic to generic programming. In particular, one can retrofit existing library classes with generic interfaces without changing their code.An implementation of GJ has been written in GJ, and is freely available on the web.


title: Compound Types for Java

authors:
Martin Büchi
Wolfgang Weck

abstract: Type compatibility can be defined based on name equivalence, that is, explicit declarations, or on structural matching. We argue that component software has demands for both. For types expressing individual contracts, name equivalence should be used so that references are made to external semantical specifications. For types that are composed of several such contracts, the structure of this composition should decide about compatibility.We introduce compound types as the mechanism to handle such compositions. To investigate the integrability into a strongly typed language, we add compound types to Java and report on a mechanical soundness proof of the resulting type system.Java users benefit from the higher expressiveness of the extended type system. We introduce compound types as a strict extension of Java, that is without invalidating existing programs. In addition, our proposal can be implemented on the existing Java Virtual Machine.


title: Compatible Genericity with Run-Time Types for the Java Programming Language

authors:
Robert Cartwright
Guy L. Steele Jr.

abstract: The most serious impediment to writing substantial programs in the Java™ programming language is the lack of a gentricity mechanism for abstracting classes and methods with respect to type. During the past two years, several research groups have developed Java extensions that support various forms of genericity, but none has succeeded in accommodating general type parameterization (akin to Java arrays) while retaining compatibility with the existing. Java Virtual Machine. In this paper, we explain how to support general type parameterization---including both non-variant and covariant subtyping---on top of the existing Java Virtual Machine at the cost of a larger code footprint and the forwarding of some method calls involving parameterized classes and methods. Our language extension is forward and backward compatible with the Java 1.2 language and run-time environment: programs in the extended language will run on existing Java 1.2 virtual machines (relying only on the unparameterized Java core libraries) and all existing Java 1.2 programs have the same binary representation and semantics (behavior) in the extended language.


title: Ownership Types for Flexible Alias Protection

authors:
David G. Clarke
John Potter
James Noble

abstract: Object-oriented programming languages allow inter-object aliasing. Although necessary to construct linked data structures and networks of interacting objects, aliasing is problematic in that an aggregate object's state can change via an alias to one of its components, without the aggregate being aware of any aliasing.Ownership types form a static type system that indicates object ownership. This provides a flexible mechanism to limit the visibility of object references and restrict access paths to objects, thus controlling a system's dynamic topology. The type system is shown to be sound, and the specific aliasing properties that a system's object graph satisfies are formulated and proven invariant for well-typed programs.

awards: Most Influential OOPSLA Paper (awarded 2008)


title: Question time! about Use Cases

authors:
Alistair Cockburn
Martin Fowler

abstract: In Britain there is a very successful form of panel session, on a television program called “Question Time.” In this programme, four panelists, all public figures, are chosen to give a spectrum of viewpoints. There is always a figure from the two main political p<a.rties, usually one from the third largest party, and some complementary figure, perhaps a a business leader, union leader, or media person. This gives a wide spread of views. There are no position statements, the program is filled by discussing questions at about 10 minutes each. Each question is asked by an audience member, all four panelists respond, moderated by the panel moderator (a well known BBC ligure). The questioner then makes a brief reply, and there is a brief period of comments from the floor. The questions are submitted in advance by the audience members and the progr‘am organizers pick six questions that will be interesting. This panel on use cases follows roughly the same format. A well known (English!) 00 figure will question four expert panelists with differing views, to expose their views and their reasons for differing. There are no position statements, the 90-minute pane1 is filled by discussing eight questions. The questions are submitted in advance by the public and audience members. The moderator picks eight questions that will be interesting and help tease ap‘art subtle issues and differences between the panelists. For each question, all four panelists respond, moderated by the pane1 moderator. The questioner makes a brief reply, and there is a brief period of comments from the floor.


title: JRes: A Resource Accounting Interface for Java

authors:
Grzegorz Czajkowski
Thorsten von Eicken

abstract: With the spread of the Internet the computing model on server systems is undergoing several important changes. Recent research ideas concerning dynamic operating system extensibility are finding their way into the commercial domain, resulting in designs of extensible databases and Web servers. In addition, both ordinary users and service providers must deal with untrusted downloadable executable code of unknown origin and intentions.Across the board, Java has emerged as the language of choice for Internet-oriented software. We argue that, in order to realize its full potential in applications dealing with untrusted code, Java needs a flexible resource accounting interface. The design and prototype implementation of such an interface --- JRes --- is presented in this paper. The interface allows to account for heap memory, CPU time, and network resources consumed by individual threads or groups of threads. JRes allows limits to be set on resources available to threads and it can invoke callbacks when these limits are exceeded. The JRes prototype described in this paper is implemented on top of standard Java virtual machines and requires only a small amount of native code.


title: An Evaluation of Automatic Object Inline Allocation Techniques

authors:
Julian Dolby
Andrew A. Chien

abstract: Object-oriented languages such as Java and Smalltalk provide a uniform object reference model, allowing objects to be conveniently shared. If implemented directly, these uniform reference models can suffer in efficiency due to additional memory dereferences and memory management operations. Automatic inline allocation of child objects within parent objects can reduce overheads of heap-allocated pointer-referenced objects.We present three compiler analyses to identify inlinable fields by tracking accesses to heap objects. These analyses span a range from local data flow to adaptive whole-program, flow-sensitive inter-procedural analysis. We measure their cost and effectiveness on a suite of moderate-sized C++ programs (up to 30,000 lines including libraries). We show that aggressive interprocedural analysis is required to enable object inlining, and our adaptive inter-procedural analysis [23] computes precise information efficiently. Object inlining eliminates typically 40% of object accesses and allocations (improving performance up to 50%). Furthermore,


title: What is Java Binary Compatibility?

authors:
Sophia Drossopoulou
David Wragg
Susan Eisenbach

abstract: Separate compilation allows the decomposition of programs into units that may be compiled separately, and linked into an executable. Traditionally, separate compilation was equivalent to the compilation of all units together, and modification and re-compilation of one unit required re-compilation of all importing units.Java suggests a more flexible framework, in which the linker checks the integrity of the binaries to be combined. Certain source code modifications, such as addition of methods to classes, are defined as binary compatible. The language description guarantees that binaries of types (i.e. classes or interfaces) modified in binary compatible ways may be re-compiled and linked with the binaries of types that imported and were compiled using the earlier versions of the modified types.However, this is not always the case: some of the changes considered by Java as binary compatible do not guarantee successful linking and execution. In this paper we study the concepts around binary compatibility. We suggest a formalization of the requirement of safe linking and execution without re-compilation, investigate alternatives, demonstrate several of its properties, and propose a more restricted definition of binary compatible changes. Finally, we prove for a substantial subset of Java, that this restricted definition guarantees error-free linking and execution.


title: Software Reuse: Nemesis or Nirvana? (Panel)

authors:
Steven Fraser
Maggie Davis
Martin L. Griss
Luke Hohmann
Ian Hopper
Rebecca Joos
Bill Opdyke


title: A Type System for Object Initialization in the Java Bytecode Language

authors:
Stephen N. Freund
John C. Mitchell

abstract: In the standard Java implementation, a Java language program is compiled to Java bytecode. This bytecode may be sent across the network to another site, where it is then interpreted by the Java Virtual Machine. Since bytecode may be written by hand, or corrupted during network transmission, the Java Virtual Machine contains a bytecode verifier that performs a number of consistency checks before code is interpreted. As illustrated by previous attacks on the Java Virtual Machine, these tests, which include type correctness, are critical for system security. In order to analyze existing bytecode verifiers and to understand the properties that should be verified, we develop a precise specification of statically-correct Java bytecode, in the form of a type system. Our focus in this paper is a subset of the bytecode language dealing with object creation and initialization. For this subset, we prove that for every Java bytecode program that satisfies our typing constraints, every object is initialized before it is used. The type system is easily combined with a previous system developed by Stata and Abadi for bytecode subroutines. Our analysis of subroutines and object initialization reveals a previously unpublished bug in the Sun JDK bytecode verifier.


title: A Lambda Calculus of Objects with Self-Inflicted Extension

authors:
Pietro Di Gianantonio
Furio Honsell
Luigi Liquori

abstract: In this paper we investigate, in the context of functional prototype-based languages, objects which might extend themselves upon receiving a message. The possibility for an object of extending its own "self", referred to by Cardelli, as a self-inflicted operation, is novel in the context of typed object-based languages. We present a sound type system for this calculus which guarantees that evaluating a well-typed expression will never yield a message-not-found run-time error. We give several examples which illustrate the increased expressive power of our system with respect to existing calculi of objects. The new type system allows also for a flexible width-subtyping, still permitting sound method override, and a limited form of object extension. The resulting calculus appears to be a good starting point for a rigorous mathematical analysis of class-based languages.


title: System Support for Object Groups

authors:
Rachid Guerraoui
Pascal Felber
Benoît Garbinato
Karim Mazouni

abstract: This paper draws several observations from our experiences in building support for object groups. These observations actually go beyond our experiences and may apply to many other developments of object based distributed systems.Our first experience aimed at building support for Smalltalk object replication using the Isis process group toolkit. It was quite easy to achieve group transparency but we were confronted with a strong mismatch between the rigidity of the process group model and the flexible nature of object interactions. Consequently, we decided to build our own object oriented protocol framework, specifically dedicated to support object groups (instead of using a process group toolkit). We built our framework in such a way that basic distributed protocols, such as failure detection and multicasts, are considered as first class entities, directly accessible to the programmers. To achieve flexible and dynamic protocol composition, we had to go beyond inheritance and objectify distributed algorithms.Our second experience consisted in building a CORBA service aimed at managing group of objects written on different languages and running on different platforms. This experience revealed a mismatch between the asynchrony of group protocols and the synchrony of standard CORBA interaction mechanisms, which limited the portability of our CORBA object group service. We restricted the impact of this mismatch by encapsulating asynchrony issues inside a specific messaging sub-service.We dissect the cost of object group transparency in our various implementations, and we point out the recurrent sources of overheads, namely message indirection, marshaling/unmarshaling and strong consistency.


title: Lightweight Object-Oriented Shared Variables for Distributed Applications on the Internet

authors:
Jacob Harris
Vivek Sarkar

abstract: This paper describes a lightweight yet powerful approach for writing distributed applications using shared variables. Our approach, called SHAREHOLDER, is inspired by the flexible and intuitive model of information access common to the World Wide Web. The distributed applications targeted by our approach all share a weak consistency model and loose transaction semantics, similar to a user's model of accessing email, bulletin boards, chat rooms, etc. on the Internet. The SHAREHOLDER infrastructure has several advantages. Its highly object-oriented view of shared variables simplifies their initialization and configuration. A shared variable's distribution mechanism is specified through an associated configuration object, and the programmer does not need to write any extra code to implement the sharing mechanism. These configuration objects can be initialized at run-time, allowing tremendous flexibility in dynamic control of distribution of shared variables. Finally, the programmer can treat shared variables and local variables interchangeably, thus simplifying conversion of a serial application into a distributed application.


title: Reasoning about Java Classes (Preliminary Report)

authors:
Bart Jacobs
Joachim van den Berg
Marieke Huisman
Martijn van Berkum

abstract: We present the first results of a project called LOOP, on formal methods for the object-oriented language Java. It aims at verification of program properties, with support of modern tools. We use our own front-end tool (which is still partly under construction) for translating Java classes into higher order logic, and a back-end theorem prover (namely PVS, developed at SRI) for reasoning. In several examples we demonstrate how non-trivial properties of Java programs and classes can be proven following this two-step approach.


title: Building Distributed Systems (Panel)

authors:
Doug Lea
David W. Forslund
Tom Barry
Don Vines
Rajendra K. Raj
Ashutosh Tiwary

abstract: Everyone is building a distributed systems these days, but the "how" has become a matter for religious debate and the "why" is often neglected completely.This panel brings together a variety of practitioners to explain the joys and woes of building a distributed system including: .why a distributed solution was chosen .what middleware was selected and why .what issues and gotchas reared their ugly heads and what was done about it


title: Multiple Dispatch as Dispatch on Tuples

authors:
Gary T. Leavens
Todd D. Millstein

abstract: Many popular object-oriented programming languages, such as C++, Smalltalk-80, Java, and Eiffel, do not support multiple dispatch. Yet without multiple dispatch, programmers find it difficult to express binary methods and design patterns such as the "visitor" pattern. We describe a new, simple, and orthogonal way to add multimethods to single-dispatch object-oriented languages, without affecting existing code. The new mechanism also clarifies many differences between single and multiple dispatch.


title: Data Groups: Specifying the Modification of Extended State

abstract: This paper explores the interpretation of specifications in the context of an object-oriented programming language with subclassing and method overrides. In particular, the paper considers annotations for describing what variables a method may change and the interpretation of these annotations. The paper shows that there is a problem to be solved in the specification of methods whose overrides may modify additional state introduced in subclasses. As a solution to this problem, the paper introduces data groups, which enable modular checking and rather naturally capture a programmer's design decisions.


title: Dynamics Class Loading in the Java Virtual Machine

authors:
Sheng Liang
Gilad Bracha

abstract: Class loaders are a powerful mechanism for dynamically loading software components on the Java platform. They are unusual in supporting all of the following features: laziness, type-safe linkage, user-defined extensibility, and multiple communicating namespaces.We present the notion of class loaders and demonstrate some of their interesting uses. In addition, we discuss how to maintain type safety in the presence of user-defined dynamic class loading.


title: Contraint-Based Polymorphism in Cecil: Towards a Practical and Static Type System

abstract: We present a static type system for object-oriented languages which strives to provide static typechecking without resorting to dynamic "type casts," restricting what code the programmer can write, or being too verbose or difficult to use in practice. The type system supports bounded parametric polymorphism where the bounds on type variables can be expressed using general recursive subtype or signature constraints, with F-bounded polymorphism and covariant type parameters being special cases.We implemented this type system in the Cecil language and used it to successfully typecheck a 100,000-line Cecil program, the Vortex optimizing compiler. Our experience was very good: dynamically-typed code needed very little rewriting. We also observed several common programming situations that presented a challenge for our type system. We discuss these situations and ways to typecheck them statically.


title: Vclusters: A Flexible, Fine-Grained Object Clustering Mechanism

authors:
Mark L. McAuliffe
Michael J. Carey
Marvin H. Solomon


title: Adaptive Plug-and-Play Components for Evolutionary Software Development

authors:
Mira Mezini
Karl J. Lieberherr

abstract: In several works on design methodologies, design patterns, and programming language design, the need for program entities that capture the patterns of collaboration between several classes has been recognized. The idea is that in general the unit of reuse is not a single class, but a slice of behavior affecting a set of collaborating classes. The absence of large-scale components for expressing these collaborations makes object-oriented programs more difficult to maintain and reuse, because functionality is spread over several methods and it becomes difficult to get the "big picture". In this paper, we propose Adaptive Plug and Play Components to serve this need. These components are designed such that they not only facilitate the construction of complex software by making the collaborations explicit, but they do so in a manner that supports the evolutionary nature of both structure and behavior.


title: Object Lessons Learned from a Distributed System for Remote Building Monitoring and Operation

authors:
Frank Olken
Hans-Arno Jacobsen
Chuck McParland
Mary Ann Piette
Mary F. Anderson

abstract: In this paper we describe our experiences with the design, the deployment, and the initial operation of a distributed system for the remote monitoring and operation of multiple heterogeneous commercial buildings across the Internet from a single control center. Such systems can significantly reduce building energy usage. Our system is distinguished by its ability to interface to multiple heterogeneous legacy building Energy Management Control Systems (EMCSs), its use of the Common Object Request Broker Architecture (CORBA) standard communication protocols for the former task, development of a standardized naming system for monitoring points in buildings, the use of a relational DBMS to store and process time series data, automatic time and unit conversion, and a scripted time series visualization system. We describe our design choices and our experiences in development and operation. We note requirements for future distributed systems software for interoperability of heterogeneous re...


title: Role Model Based Framework Design and Integration

authors:
Dirk Riehle
Thomas R. Gross

abstract: Today, any large object-oriented software system is built using frameworks. Yet, designing frameworks and defining their interaction with clients remains a difficult task. A primary reason is that today's dominant modeling concept, the class, is not well suited to describe the complexity of object collaborations as it emerges in framework design and integration. We use role modeling to overcome the problems and limitations of class-based modeling. Using role models, the design of a framework and its use by clients can be described succinctly and with much better separation of concerns than with classes. Using role objects, frameworks can be integrated into use-contexts that have not been foreseen by their original designers.


title: Logical Observable Entities

abstract: We show how finite-state machines can standardize the protocol used by a component object to notify other interested objects of its state changes, resulting in a more effective use of static types to constrain both parties, and a more efficient dissemination of information. The enhanced component specification is called a logical observable entity, or LOE. We address two key issues in effectively applying such a strategy: how to extend subtyping to consider the state machines, and how to ensure some kind of compliance between the state-machine specification and its implementation. This leads to an unusual subtyping predicate for LOEs on the one hand, and a prototype code generation strategy on the other. 1 Introduction When a component object is developed in isolation from its clients, it cannot send messages directly to objects in the client systems since it does not know their actual class names. Instead, a level of indirection must be employed, usually by having the component spec...


title: Borrow, Copy or Steal? Loans and Larceny in the Orthodox Canonical Form

abstract: Dynamic memory management in C++ is complex, especially across the boundaries of library abstract data types. C++ libraries designed in the orthodox canonical form (OCF) alleviate some of the problems by ensuring that classes which manage any kind of heap structures faithfully copy and delete these. However, in certain common circumstances, OCF heap structures are wastefully copied multiple times. General reference counting is not an option in OCF, since a shared body violates the intended value semantics; although a copy-on-write policy can be made to work with borrowed heap structures. A simpler ownership policy, based on larceny, allows low-level memory manager objects to steal heap structures from temporary variables, in properly isolated circumstances. Various strategies for regulating theft are presented, ranging from pilfer-constructors to locks on heap data. Larceny has similarities with other transfer of ownership patterns, but is more a core implementation technique designed to improve the efficiency and effectiveness of OCF-conformant libraries.


title: Parametric Polymorphism for Java: A Reflective Solution

authors:
Jose Solorzano
Suad Alagic

abstract: A number of inadequacies of existing implementation techniques for extending Java™ with parametric polymorphism are revealed. Homogeneous translations are the most space-efficient but they are not compatible with reflection, some models of persistence, and multiple dispatch. Heterogeneous translations, on the other hand, can potentially produce large amounts of redundant information. Implementation techniques that address these concerns are developed. In languages that support run-time reflection, an adequate implementation of parametric, bounded and F-bounded polymorphism is shown to require (reflective) run-time support. In Java, extensions to the core classes are needed. This is in spite of the fact that parametric polymorphism is intended to be managed statically.


title: Visualizing Dynamic Software System Information Through High-Level Models

authors:
Robert J. Walker
Gail C. Murphy
Bjørn N. Freeman-Benson
Darin Wright
Darin Swanson
Jeremy Isaak

abstract: Dynamic information collected as a software system executes can help software engineers perform some tasks on a system more effectively. To interpret the sizable amount of data generated from a system's execution, engineers require tool support. We have developed an off-line, flexible approach for visualizing the operation of an object-oriented system at the architectural level. This approach complements and extends existing profiling and visualization approaches available to engineers attempting to utilize dynamic information. In this paper, we describe the technique and discuss preliminary qualitative studies into its usefulness and usability. These studies were undertaken in the context of performance tuning tasks.


title: An Efficient Meta-Lock for Implementing Ubiquitous Synchronization

authors:
Ole Agesen
David Detlefs
Alex Garthwaite
Ross C. Knippel
Y. S. Ramakrishna
Derek White

abstract: Programs written in concurrent object-oriented languages, especially ones that employ thread-safe reusable class libraries, can execute synchronization operations (lock, notify, etc.) at an amazing rate. Unless implemented with utmost care, synchronization can become a performance bottleneck. Furthermore, in languages where every object may have its own monitor, per-object space overhead must be minimized. To address these concerns, we have developed a meta-lock to mediate access to synchronization data. The meta-lock is fast (lock + unlock executes in 11 SPARC™ architecture instructions), compact (uses only two bits of space), robust under contention (no busy-waiting), and flexible (supports a variety of higher-level synchronization operations). We have validated the meta-lock with an implementation of the synchronization operations in a high-performance product-quality Java™ virtual machine and report performance data for several large programs.


title: Implementing Jalapeño in Java

authors:
Bowen Alpern
C. Richard Attanasio
John J. Barton
Anthony Cocchi
Susan Flynn Hummel
Derek Lieber
Ton Ngo
Mark F. Mergen
Janice C. Shepherd
Stephen E. Smith

abstract: Jalape~no is a virtual machine for Java TM servers written in Java. A running Java program involves four layers of functionality: the user code, the virtual-machine, the operating system, and the hardware. By drawing the Java / non-Java boundary below the virtual machine rather than above it, Jalape~no reduces the boundary-crossing overhead and opens up more opportunities for optimization. To get Jalape~no started, a boot image of a working Jalape ~no virtual machine is concocted and written to a file. Later, this file can be loaded into memory and executed. Because the boot image consists entirely of Java objects, it can be concocted by a Java program that runs in any JVM. This program uses reflection to convert the boot image into Jalape~no's object format. A special Magic class allows unsafe casts and direct access to the hardware. Methods of this class are recognized by Jalape~no's three compilers, which ignore their bytecodes and emit special-purpose machine code. User code w...

awards: Most Influential OOPSLA Paper (awarded 2009)


title: Escape Analysis for Object-Oriented Languages: Application to Java

abstract: Escape analysis [27, 14, 5] is a static analysis that determines whether the lifetime of data exceeds its static scope.


title: Removing Unnecessary Synchronization in Java

authors:
Jeff Bogda
Urs Hölzle

abstract: Java programs perform many synchronization operations on data structures. Some of these synchronization are unnecessary; in particular, if an object is reachable only by a single thread, concurrent access is impossible and no synchronization is needed. We describe an interprocedural, flow- and context-insensitive dataflow analysis that finds such situations. A global optimizing transformation then eliminates synchronizations on these objects. For every program in our suite of ten Java benchmarks consisting of SPECjvm98 and others, our system optimizes over 90% of the alias sets containing at least one synchronized object. As a result, the dynamic frequency of synchronizations is reduced by up to 99%. For two benchmarks that perform synchronizations very frequently, this optimization leads to speedups of 36% and 20%.


title: Efficient Multiple and Predicated Dispatching

authors:
Craig Chambers
Weimin Chen

abstract: The speed of message dispatching is an important issue in the overall performance of object-oriented programs. We have developed an algorithm for constructing efficient dispatch functions that combines novel algorithms for efficient single dispatching, multiple dispatching, and predicate dispatching. Our algorithm first reduces methods written in the general predicate dispatching model (which generalizes single dispatching, multiple dispatching, predicate classes and classifiers, and pattern-matching) into ones written using a simpler multimethod dispatching model. Our algorithm then computes a strategy for implementing multiple dispatching in terms of sequences of single dispatches, representing the strategy as a lookup DAG. Finally, our algorithm computes an implementation strategy separately for each of the single dispatches, producing for each dispatch a dispatch tree, which is a binary decision tree blending class identity tests, class range tests, and table lookups. Our algorithm exploits any available static information (from type declarations or class analysis) to prune unreachable paths from the lookup DAG, and uses any available dynamic profile information to minimize the expected time to search the dispatch trees. We measure the effectiveness of our dispatching algorithms on a collection of large Cecil programs, compiled by the Vortex optimizing compiler, showing improvements of up to 30% over already heavily optimized baseline versions.


title: Escape Analysis for Java

authors:
Jong-Deok Choi
Manish Gupta
Mauricio J. Serrano
Vugranam C. Sreedhar
Samuel P. Midkiff

abstract: This paper presents a simple and efficient data flow algorithm for escape analysis of objects in Java programs to determine (i) if an object can be allocated on the stack; (ii) if an object is accessed only by a single thread during its lifetime, so that synchronization operations on that object can be removed. We introduce a new program abstraction for escape analysis, the connection graph, that is used to establish reachability relationships between objects and object references. We show that the connection graph can be summarized for each method such that the same summary information may be used effectively in different calling contexts. We present an interprocedural algorithm that uses the above property to efficiently compute the connection graph and identify the non-escaping objects for methods and threads. The experimental results, from a prototype implementation of our framework in the IBM High Performance Compiler for Java, are very promising. The percentage of objects that may be allocated on the stack exceeds 70% of all dynamically created objects in three out of the ten benchmarks (with a median of 19%), 11% to 92% of all lock operations are eliminated in those ten programs (with a median of 51%), and the overall execution time reduction ranges from 2% to 23% (with a median of 7%) on a 333 MHz PowerPC workstation with 128 MB memory.


title: Subject-Oriented Design: Towards Improved Alignment of Requirements, Design, and Code

authors:
Siobhán Clarke
William H. Harrison
Harold Ossher
Peri L. Tarr

abstract: article Free Access Share on Subject-oriented design: towards improved alignment of requirements, design, and code Authors: Siobhán Clarke School of Computer Applications, Dublin City University, Dublin 9, Republic of Ireland School of Computer Applications, Dublin City University, Dublin 9, Republic of IrelandView Profile , William Harrison IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NYView Profile , Harold Ossher IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NYView Profile , Peri Tarr IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NYView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 34Issue 10Oct. 1999 pp 325–339https://doi.org/10.1145/320385.320420Online:01 October 1999Publication History 94citation1,710DownloadsMetricsTotal Citations94Total Downloads1,710Last 12 Months24Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF


title: Modular Type-Based Reverse Engineering of Parameterized Types in Java Code

abstract: An analysis is provided for Java programs that reverse engineers parameterized types into existing Java code. This analysis propagates precise type information about the contents of container objects. As an application, the analysis can be used to justify the safe removal of downcasts that are guaranteed to succeed. Another application is in automatically reverse engineering parameterized types into existing Java libraries, so that they can be used in Java dialects with parameterized types.


title: Zones, Contracts and Absorbing Changes: An Approach to Software Evolution

authors:
James Huw Evans
Peter Dickman

abstract: This paper describes a novel approach to managing the evolution of distributed, persistent systems at run-time. This is achieved by partitioning a system into disjoint zones, each of which can be evolved without affecting code in any other. Contracts are defined between zones, making type-level interdependencies and inter-zone communication explicit. Programmer supplied code is added to the running system, at the boundary between zones, to constrain the scope of changes. A change methodology is presented which the software engineer uses to help describe and manage the evolution of the system. Knowledge of the application semantics is essential when evolving a system and our approach allows the engineer to concentrate on these semantic aspects of change. Our Java-based demonstration platform and methodology reduce or remove some of the burdensome tasks the software engineer is normally expected to perform when changing a system, making evolution more tractable.


title: A Problem-Oriented Analysis of Basic UML Static Requirements Modeling Concepts

abstract: The Unified Modeling Language (UML) is a standard modeling language in which some of the best object-oriented (OO) modeling experiences are embedded. In this paper we illustrate the role formal specification techniques can play in developing a precise semantics for the UML. We present a precise characterization of requirements-level (problem-oriented) Class Diagrams and outline how the characterization can be used to semantically analyze requirements Class Diagrams.


title: A Formal Framework for the Java Bytecode Language and Verifier

authors:
Stephen N. Freund
John C. Mitchell

abstract: This paper presents a sound type system for a large subset of the Java bytecode language including classes, interfaces, constructors, methods, exceptions, and bytecode subroutines. This work serves as the foundation for developing a formal specification of the bytecode language and the Java Virtual Machine's bytecode verifier. We also describe a prototype implementation of a type checker for our system and discuss some of the other applications of this work. For example, we show how to extend our work to examine other program properties, such as the correct use of object locks.


title: Mostly-copying Reachability-based Orthogonal Persistence

authors:
Antony L. Hosking
Jiawan Chen

abstract: We describe how reachability-based orthogonal persistence can be supported even in uncooperative implementations of languages such as C++ and Modula-3, and without modification to the compiler. Our scheme extends Bartlett's mostly-copying garbage collector to manage both transient objects and resident persistent objects, and to compute the reachability closure necessary for stabilization of the persistent heap. It has been implemented in our prototype of reachability-based persistence for Modula-3, yielding performance competitive with that of comparable, but non-orthogonal, persistent variants of C++. Experimental results, using the 007 object database benchmarks, reveal that the mostly-copying approach offers a straightforward path to efficient orthogonal persistence in these uncooperative environments. The results also characterize the performance of persistence implementations based on virtual memory protection primitives.


title: Featherwieght Java: A Minimal Core Calculus for Java and GJ

authors:
Atsushi Igarashi
Benjamin C. Pierce
Philip Wadler

abstract: Several recent studies have introduced lightweight versions of Java: reduced languages in which complex features like threads and reflection are dropped to enable rigorous arguments about key properties such as type safety. We carry this process a step further, omitting almost all features of the full language (including interfaces and even assignment) to obtain a small calculus, Featherweight Java, for which rigorous proofs are not only possible but easy.


title: A Performance Evaluation of the Mobile Agent Paradigm

authors:
Leila Ismail
Daniel Hagimont

abstract: This paper presents a performance evaluation of the mobile agent paradigm in comparison to the client/server paradigm. This evaluation has been conducted on top of the Java environment, using respectively RMI, the Aglets mobile agents platform and a mobile agents prototype that we implemented. The measurements give the cost of the basic mechanisms involved in the implementation of a mobile agent platform, and a comparative evaluation of the two considered models (client/server and mobile agents) through two application scenarios. The results show that significant performance improvements can be obtained using mobile agents.


title: Role Model Designs and Implementations with Aspect-oriented Programming

abstract: This paper describes research in applications of aspect-oriented programming (AOP) as captured in the AspectJ™ language. In particular, it compares object-oriented and aspect-oriented designs and implementations of role models.


title: Atlas: A Case Study in Building a Web-Based Learning Environment using Aspect-oriented Programming

authors:
Mik Kersten
Gail C. Murphy

abstract: The Advanced Teaching and Learning Academic Server (Atlas) is a software system that supports web-based learning. Students can register for courses, and can navigate through personalized views of course material. Atlas has been built according to Sun Microsystem's Java™ Servlet specification using Xerox PARC's aspect-oriented programming support called Aspect™. Since aspect-oriented programming is still in its infancy, little experience with employing this paradigm is currently available. In this paper, we start filling this gap by describing the aspects we used in Atlas and by discussing the effect of aspects on our object-oriented development practices. We describe some rules and policies that we employed to achieve our goals of maintainability and modifiability, and introduce a straightforward notation to express the design of aspects. Although we faced some obstacles along the way, this combination of technology helped us build a fast, well-structured system in a reasonable amount of time.


title: Reducing Transfer Delay Using Java Class File Splitting and Prefetching

authors:
Chandra Krintz
Brad Calder
Urs Hölzle

abstract: The proliferation of the Internet is fueling the development of mobile computing environments in which mobile code is executed on remote sites. In such environments, the end user must often wait while the mobile program is transferred from the server to the client where it executes. This downloading can create significant delays, hurting the interactive experience of users.


title: The Generic Graph Component Library

authors:
Lie-Quan Lee
Jeremy G. Siek
Andrew Lumsdaine

abstract: In this paper we present the Generic Graph Component Library (GGCL), a generic programming framework for graph data structures and graph algorithms. Following the theme of the Standard Template Library (STL), the graph algorithms in GGCL do not depend on the particular data structures upon which they operate, meaning a single algorithm can operate on arbitrary concrete representations of graphs. To attain this type of flexibility for graph data structures, which are more complicated than the containers in STL, we introduce several concepts to form the generic interface between the algorithms and the data structures: Vertex, Edge, Visitor, andDecorator. We describe the principal abstractions comprising the GGCL, the algorithms and data structures that it provides, and provide examples that demonstrate the use of GGCL to implement some common graph algorithms. Performance results are presented which demonstrate that the use of novel lightweight implementation techniques and static polymorphism in GGCL results in code which is significantly more efficient than similar libraries written using the objectoriented paradigm. Submitted as a Research Paper to OOPSLA99. Subject Areas: frameworks, design patterns


title: Object Views: Language Support for Intelligent Object Caching in Parallel and Distributed Computations

authors:
Ilya Lipkind
Igor Pechtchanski
Vijay Karamcheti

abstract: Object-based parallel and distributed applications are becoming increasingly popular, driven by the programmability advantages of component technology and a flat shared-object space. However, the flat shared-object space introduces a performance challenge: applications that rely on the transparent coherent caching of objects achieve high performance only on tightly coupled parallel machines. In distributed environments, the overheads of object caching force application designers to choose other solutions. Consequently, most applications sacrifice programmability, relying instead on either the explicit coherence management of cached objects, or on vastly different middleware abstractions such as multicast and events.


title: Semantic Analysis of Virtual Classes and Tested Classes

abstract: Virtual classes and nested classes are distinguishing features of BETA. Nested classes originated from Simula, but until recently they have not been part of main stream object- oriented languages. C++ has a restricted form of nested classes and they were included in Java 1.1. Virtual classes is the BETA mechanism for expressing generic classes and virtual classes is an alternative to parameterized classes. There has recently been an increasing interest in virtual classes and a number of proposals for adding virtual classes to other languages, extending virtual classes, and unifying virtual classes and parameterized classes have been made. Although virtual classes and nested classes have been used in BETA for more than a decade, their implementation has not been published. The purpose of this paper is to contribute to the understanding of virtual classes and nested classes by presenting the central elements of the semantic analysis used in the Mjølner BETA compiler.


title: A Study of Locking Objects with Bimodal Fields

authors:
Tamiya Onodera
Kiyokuni Kawachiya

abstract: Object locking can be efficiently implemented by bimodal use of a field reserved in an object. The field is used as a lightweight lock in one mode, while it holds a reference to a heavyweight lock in the other mode. A bimodal locking algorithm recently proposed for Java achieves the highest performance in the absence of contention, and is still fast enough when contention occurs.


title: A Language for Specifying Recursive Traversals of Object Structures

authors:
Johan Ovlinger
Mitchell Wand

abstract: We present a domain-specific language for specifying recursive traversals of object structures, for use with the visitor pattern. Traversals are traditionally specified as iterations, forcing the programmer to adopt an imperative style, or are hard-coded into the program or visitor. Our proposal allows a number of problems best approached by recursive means to be tackled with the visitor pattern, while retaining the benefits of a separate traversal specification.


title: Correspondence Polymorphism for Object-Oriented Languages

authors:
Ran Rinat
Menachem Magidor
Scott F. Smith

abstract: In this paper we propose a new form of polymorphism for object-oriented languages, called correspondence polymorphism. It lies in a different dimension than either parametric or subtype polymorphism. In correspondence polymorphism, some methods are declared to correspond to other methods, via a correspondence relation. With this relation, it is possible to reuse non-generic code in various type contexts—not necessarily subtyping or matching contexts—without having to plan ahead for this reuse. Correspondence polymorphism has advantages over other expressive object type systems in that programmer-declared types still may be simple, first-order types that are easily understood. We define a simple language LCP that reflects these new ideas, illustrating its behavior with multiple examples. We present formal type rules and an operational semantics for LCP, and establish soundness of the type system with respect to reduction.


title: Age-Based Garbage Collection

authors:
Darko Stefanovic
Kathryn S. McKinley
J. Eliot B. Moss

abstract: Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, called age-based, some of which postpone consideration of the youngest objects. Collecting less than the whole heap requires write barrier mechanisms to track pointers into the collected region. We describe here a new, efficient write barrier implementation that works for age-based and traditional generational collectors. To compare several collectors, their configurations, and program behavior, we use an accurate simulator that models all heap objects and the pointers among them, but does not model cache or other memory effects. For object-oriented languages, our results demonstrate that an older-first collector, which collects older objects before the youngest ones, copies on average much less data than generational collectors. Our results also show that an older-first collector does track more pointers, but the combined cost of copying and pointer tracking still favors an older-first over a generational collector in many cases. More importantly, we reopen for consideration the question where in the heap and with which policies copying collectors will achieve their best performance.


title: Space and Time-Efficient Memory Layout for Multiple Inheritance

authors:
Peter F. Sweeney
Joseph Gil

abstract: Traditional implementations of multiple inheritance bring about not only an overhead in terms of run-time but also a significant increase in object space. For example, the number of compiler-generated fields in a certain object can be as large as quadratic in the number of its subobjects. The problem of efficient object layout is compounded by the need to support two different semantics of multiple inheritance: shared, in which a base class inherited along distinct paths occurs only once in the derived class, and repeated, in which this base has multiple distinct occurrences in the derived. In this theoretical and foundational paper, we introduce two new techniques to optimize memory layout for multiple inheritance. The main ideas behind these techniques are the inlining of virtual bases and bidirectional memory layout. Our techniques never increase time overhead, and usually even decrease it. We show that in some example hierarchies, more than ten-fold reduction in the space overhead can be achieved. We analyze the complexity of the algorithms to apply these techniques, and give theorems to estimate the efficacy of this application. For concreteness, techniques and examples are discussed in the context of C++.


title: Practical Experience with an Application Extractor for Java

authors:
Frank Tip
Chris Laffra
Peter F. Sweeney
David Streeter

abstract: Java programs are routinely transmitted over low-bandwidth network connections as compressed class file archives (i.e., zip files and jar files). Since archive size is directly proportional to download time, it is desirable for applications to be as small as possible. This paper is concerned with the use of program transformations such as removal of dead methods and fields, inlining of method calls, and simplification of the class hierarchy for reducing application size. Such “extraction” techniques are generally believed to be especially useful for applications that use class libraries, since typically only a small fraction of a library's functionality is used. By “pruning away” unused library functionality, application size can be reduced dramatically. We implemented a number of application extraction techniques in Jax, an application extractor for Java, and evaluate their effectiveness on a set of realistic benchmarks ranging from 27 to 2,332 classes (with archives ranging from 56,796 to 3,810,120 bytes). We report archive size reductions ranging from 13.4% to 90.2% (48.7% on average).


title: Detecting Defects in Object-Oriented Designs: Using Reading Techniques to Increase Software Quality

authors:
Guilherme Travassos
Forrest Shull
Michael Fredericks
Victor R. Basili

abstract: Inspections can be used to identify defects in software artifacts. In this way, inspection methods help to improve software quality, especially when used early in software development. Inspections of software design may be especially crucial since design defects (problems of correctness and completeness with respect to the requirements, internal consistency, or other quality attributes) can directly affect the quality of, and effort required for, the implementation.


title: Confined Types

authors:
Jan Vitek
Boris Bokowski

abstract: Sharing and transfer of object references is difficult to control in object-oriented languages. Unconstrained sharing poses serious problems for writing secure components in object-oriented languages. In this paper, we present a set of inexpensive syntactic constraints that strengthen encapsulation in object-oriented programs and facilitate the implementation of secure systems. We introduce two mechanisms: confined types to impose static scoping on dynamic object references and, for technical reasons, anonymous methods which are methods that do not reveal the identity of the current instance (this). Confined types protect objects from use by untrusted code, while anonymous methods allow standard classes to be reused from confined classes. We have implemented a verifier which performs a modular analysis of Java programs and provides a static guarantee that confinement is respected. We present security related programming examples.


title: Compositional Pointer and Escape Analysis for Java Programs

authors:
John Whaley
Martin C. Rinard

abstract: This paper presents a combined pointer and escape analysis algorithm for Java programs. The algorithm is based on the abstraction of points-to escape graphs, which characterize how local variables and fields in objects refer to other objects. Each points-to escape graph also contains escape information, which characterizes how objects allocated in one region of the program can escape to be accessed by another region. The algorithm is designed to analyze arbitrary regions of complete or incomplete programs, obtaining complete information for objects that do not escape the analyzed regions.


title: A Distributed Object-Oriented Framework for Dependable Multiparty Interactions

authors:
Avelino F. Zorzo
Robert J. Stroud

abstract: In programming distributed object-oriented systems, there are several approaches for achieving binary interactions in a multiprocess environment. Usually these approaches take care only of synchronisation or communication. In this paper we describe a way of designing and implementing a more general concept: multiparty interactions. In a multiparty interaction, several parties (objects or processes) somehow “come together” to produce an intermediate and temporary combined state, use this state to execute some activity, and then leave this interaction and continue their normal execution. The concept of multiparty interactions has been investigated by several researchers, but to the best of our knowledge none have considered how failures in one or more participants of the multiparty interaction can be dealt with. In this paper, we propose a general scheme for constructing dependable multiparty interactions in a distributed object-oriented system, and describe its implementation in Java. In particular, we extend the notion of multiparty interaction to include facilities for handling exceptions. To show how our scheme can be used, we use our framework to build an abstraction mechanism that supports cooperative and competitive concurrency in distributed systems. This mechanism is then applied to program a system in which multiparty interactions are more than simple synchronisations or communications.


title: Adaptive optimization in the Jalapeño JVM

authors:
Matthew Arnold
Stephen J. Fink
David Grove
Michael Hind
Peter F. Sweeney

abstract: Future high-performance virtual machines will improve performance through sophisticated online feedback-directed optimizations. this paper presents the architecture of the Jalapeño Adaptive Optimization System, a system to support leading-edge virtual machine technology and enable ongoing research on online feedback-directed optimizations. We describe the extensible system architecture, based on a federation of threads with asynchronous communication. We present an implementation of the general architecture that supports adaptive multi-level optimization based purely on statistical sampling. We empirically demonstrate that this profiling technique has low overhead and can improve startup and steady-state performance, even without the presence of online feedback-directed optimizations. The paper also describes and evaluates an online feedback-directed inlining optimization based on statistical edge sampling. The system is written completely in Java, applying the described techniques not only to application code and standard libraries, but also to the virtual machine itself.

awards: Most Influential OOPSLA Paper (awarded 2010)


title: Guava: a dialect of Java without data races

authors:
David F. Bacon
Robert E. Strom
Ashis Tarafdar

abstract: We introduce Guava, a dialect of Java whose rules statically guarantee that parallel threads access shared data only through synchronized methods. Our dialect distinguishes three categories of classes: (1) monitors, which may be referenced from multiple threads, but whose methods are accessed serially; (2) values, which cannot be referenced and therefore are never shared; and (3) objects, which can have multiple references but only from within one thread, and therefore do not need to be synchronized. Guava circumvents the problems associated with today's Java memory model, which must define behavior when concurrent threads access shared memory without synchronization.We present an overview of the syntax and the semantic rules of Guava. We discuss how implementations of Guava can exploit these rules to re-enable compiler optimizations inhibited by standard Java. We discuss how compilers for certain multiprocessor architectures can automatically generate certain programming idioms, such as double-check reads, as optimizations of serialized monitors.


title: Formal specification of CORBA services: experience and lessons learned

authors:
Rémi Bastide
Philippe A. Palanque
Ousmane Sy
David Navarre

abstract: CORBA is now established as one of the main contenders in object-oriented middleware.Beyond the definition of this standard for distributed object systems, the Object Management Group (OMG) has specified several object services (Common Object Services, COS) that should foster the interoperability of distributed applications.Based on experiment, the goal of this paper is to show that the OMG's style of specification of the CORBA services is not suited to guarantee that implementers will produce interoperable and substitutable implementations.To illustrate our point, we give an account of an experiment based upon the formal specification of one COS, namely the CORBA Event Service.This formal specification highlights several ambiguities and under-specifications in the OMG document.We then test several commercial and public domain implementations of the CORBA Event Service, in order to assess how the implementers have dealt with these underspecifications.We show that the choices made by the implementers lead to incompatible implementations.We finally suggest a solution to overcome the problem of specification of object services, which satisfies the views of both implementers and users.Specifically, we suggest that the specification of such services be made using a formal description technique, and that implementers be provided with test cases derived from the formal specification.


title: An approach to safe object sharing

authors:
Ciarán Bryce
Chrislain Razafimahefa

abstract: It is essential for security to be able to isolate mistrusting programs from one another, and to protect the host platform from programs. Isolation is difficult in object-oriented systems because objects can easily become aliased. Aliases that cross program boundaries can allow programs to exchange information without using a system provided interface that could control information exchange. In Java, mistrusting programs are placed in distinct loader spaces but uncontrolled sharing of system classes can still lead to aliases between programs. This paper presents the object spaces protection model for an object-oriented system. The model decomposes an application into a set of spaces, and each object is assigned to one space. All method calls between objects in different spaces are mediated by a security policy. An implementation of the model in Java is presented.


title: Object-oriented real-time concurrency

authors:
Peter A. Buhr
Ashif S. Harji
Philipp E. Lim
Jiongxiong Chen

abstract: The primary goal of a real-time system is predictability. Achieving this goal requires all levels of the system to work in concert to provide fixed worst-case execution-times. Un-fortunately, many real-time systems are overly restrictive, providing only ad-hoc scheduling facilities and basic concurrent functionality. Ad-hoc scheduling makes developing, verifying, and maintaining a real-time system extremely difficult and time consuming. Basic concurrent functionality forces programmers to develop complex concurrent programs without the aid of high-level concurrency features.Encouraging the use of sophisticated real-time theory and methodology, in conjunction with high-level concurrency features, requires flexibility and extensibility. Giving real-time programmers access to the underlying system data-structures makes it possible to interact with the system to incorporate new ideas and fine-tune specific applications. This paper explores this approach by examining its effect on a selection of crucial real-time issues: real-time monitors, timeouts, dynamic-priority scheduling and basic priority inheritance. The approach is implemented in μC++.


title: MultiJava: modular open classes and symmetric multiple dispatch for Java

authors:
Curtis Clifton
Gary T. Leavens
Craig Chambers
Todd D. Millstein

abstract: We present MultiJava, a backward-compatible extension to Java supporting open classes and symmetric multiple dispatch. Open classes allow one to add to the set of methods that an existing class supports without creating distinct subclasses or editing existing code. Unlike the "Visitor" design pattern, open classes do not require advance planning, and open classes preserve the ability to add new subclasses modularly and safely. Multiple dispatch offers several well-known advantages over the single dispatching of conventional object-oriented languages, including a simple solution to some kinds of "binary method" problems. MultiJava's multiple dispatch retains Java's existing class-based encapsulation properties. We adapt previous theoretical work to allow compilation units to be statically typechecked modularly and safely, ruling out any link-time or run-time type errors. We also present a n compilation scheme that operates modularly and incurs performance overhead only where open classes or multiple dispatching are actually used.


title: Application isolation in the JavaTM Virtual Machine

abstract: To date, systems offering multitasking for the Java™ programming language either use one process or one class loader for each application. Both approaches are unsatisfactory. Using operating system processes is expensive, scales poorly and does not fully exploit the protection features inherent in a safe language. Class loaders replicate application code, obscure the type system, and non-uniformly treat 'trusted' and 'untrusted' classes, which leads to subtle, but nevertheless, potentially harmful forms of undesirable inter-application interaction.In this paper we propose a novel, simple yet powerful solution. The new model improves on existing designs in terms of resource utilization while offering strong isolation among applications. The approach is applicable both on high-end servers and on small devices. The main idea is to maintain only one copy of every class, regardless of how many applications use it. Classes are transparently and automatically modified, so that each application has a separate copy of its static fields. Two prototypes are described and selected performance data is analyzed. Various aspects of the proposed architectural changes to the Java Virtual Machine are discussed.


title: Finding refactorings via change metrics

authors:
Serge Demeyer
Stéphane Ducasse
Oscar Nierstrasz

abstract: Reverse engineering is the process of uncovering the design and the design rationale from a functioning software system. Reverse engineering is an integral part of any successful software system, because changing requirements lead to implementations that drift from their original design. In contrast to traditional reverse engineering techniques ---which analyse a single snapshot of a system--- we focus the reverse engineering effort by determining where the implementation has changed. Since changes of object-oriented software are often phrased in terms of refactorings, we propose a set of heuristics for detecting refactorings by applying lightweight, object-oriented metrics to successive versions of a software system. We validate our approach with three separate case studies of mature object-oriented software systems for which multiple versions are available. The case studies suggest that the heuristics support the reverse engineering process by focusing attention on the relevant parts of a software system.


title: An efficient class and object encoding

abstract: An object encoding translates a language with object primitives to one without. Similarly, a class encoding translates classes into other primitives. Both are important theoretically for comparing the expressive power of languages and for transferring results from traditional languages to those with objects and classes. Both are also important foundations for the implementation of object-oriented languages as compilers typically include a phase that performs these translations.This paper describes a language with a primitive notion of classes and objects and presents an encoding of this language into one with records and functions. The encoding uses two techniques often used in compilers for single-inheritance class-based object-oriented languages: the self-application semantics and the method-table technique. To type the output of the encoding, the encoding uses a new formulation of self quantifiers that is more powerful than previous approaches.


title: Mapping UML designs to Java

authors:
William Harrison
Charles Barton
Mukund Raghavachari

abstract: Tools for the generation of code from model descriptions are valuable in helping developers maintain consistency between a model and its implementation. In this paper, we describe a new method for generating Java implementation code from UML diagrams. Our method accepts UML diagrams specified at a higher-level than current tools, and places fewer constraints on the supported UML constructs, like multiple generalizations and association classes. Unlike current tools, it generates implementation code that shields system implementers from the low-level details of how associations and other UML constructs are mapped to Java. Furthermore, it supports the modular design of systems according to concerns[2, 10] by being able to generate code from a set of related UML diagrams. While our discussion is focused on the special problem of generating Java implementation code, the issues discussed in this paper are applicable more generally to object-oriented implementation languages.


title: PIROL: a case study for multidimensional separation of concerns in software engineering environments

authors:
Stephan Herrmann
Mira Mezini

abstract: In this paper, we present our experience with applying multidimensional separation of concerns to a software engineering environment. By comparing two different designs of our system, we show the importance of separating integration issues from the implementation of the individual concerns. We present a model in which integration issues are encapsulated into rst--class connector objects and indicate how this facilitates the understandability, maintenance and evolution of the system. We identify issues of binding time, binding granularity and binding cardinality as important criteria in selecting an appropriate model for separation of concerns. We finally show how a good choice following these criteria and considering the requirements of software engineering environments leads to a system with dynamic configurability, high--level component integration and support for multiple instantiable views.


title: A study of devirtualization techniques for a JavaTM Just-In-Time compiler

authors:
Kazuaki Ishizaki
Motohiro Kawahito
Toshiaki Yasue
Hideaki Komatsu
Toshio Nakatani

abstract: Many devirtualization techniques have been proposed to reduce the runtime overhead of dynamic method calls for various object-oriented languages, however, most of them are less effective or cannot be applied for Java in a straightforward manner. This is partly because Java is a statically-typed language and thus transforming a dynamic call to a static one does not make a tangible performance gain (owing to the low overhead of accessing the method table) unless it is inlined, and partly because the dynamic class loading feature of Java prohibits the whole program analysis and optimizations from being applied.We propose a new technique called direct devirtualization with the code patching mechanism. For a given dynamic call site, our compiler first determines whether the call can be devirtualized, by analyzing the current class hierarchy. When the call is devirtualizable and the target method is suitably sized, the compiler generates the inlined code of the method, together with the backup code of making the dynamic call. Only the inlined code is actually executed until our assumption about the devirtualization becomes invalidated, at which time the compiler performs code patching to make the backup code executed subsequently. Since the new technique prevents some code motions across the merge point between the inlined code and the backup code, we have furthermore implemented recently-known analysis techniques, such as type analysis and preexistence analysis, which allow the backup code to be completely eliminated. We made various experiments using 16 real programs to understand the effectiveness and characteristics of the devirtualization techniques in our Java Just-In-Time (JIT) compiler. In summary, we reduced the number of dynamic calls by ranging from 8.9% to 97.3% (the average of 40.2%), and we improved the execution performance by ranging from -1% to 133% (with the geometric mean of 16%).


title: Middleware object query processing with deferred updates and autonomous sources

authors:
Jerry Kiernan
Michael J. Carey

abstract: This paper presents a query processing algorithm called DECAF for use in middleware object query systems that are based on the use of an object cache. The DECAF algorithm is designed to work correctly even in the presence of updates to the underlying databases that don't go through the object cache (i.e., even for autonomous data sources that can be updated through legacy applications that do not perform their updates through the middleware object layer). DECAF's query results are consistent with updates performed by such transactions; its results are also consistent with any deferred updates that are present in the object cache but not yet committed at the database server. The DECAF algorithm attempts to push down query predicates to the underlying DBMSs to take advantage of the query processing capabilities of these systems and to reduce the amount of data transferred from these systems to the object cache.


title: A real world object modeling method for creating simulation environment of real-time systems

authors:
Ji Y. Lee
Hye J. Kim
Kyo Chul Kang

abstract: Most real-time embedded control software feature complex interactions with asynchronous inputs and environment objects, and a meaningful simulation of a real-time control software specification requires realistic simulation of its environment. Two problems that need to be addressed in the simulation of a target software system and its environment: First, integration and simulation of the specifications of a target software system and its artificial environment are often performed too late in the lifecycle to provide any significant value. Second, real world objects in the environment usually have spatial characteristics (form) such as shape, motion, etc. that must be specified for simulation, and there is no method to express these spatial characteristics at various levels of abstraction that are adequate for the required simulation fidelity.To address these problems, we have developed a method that supports incremental specification and simulation of both the target software system and its environmental objects. The method includes: (1) a specification method for behavior, function, and form integrated objects; (2) form specification primitives that abstract common spatial characteristics of real world objects, their typical spatial relations, and spatial interactions; and (3) a methodology that refines, verifies, and validates behavior, function, and form specification of both the real-time embedded control software and its environment in a systematic and incremental manner. The proposed specification, verification, and validation method has been applied to a robot control system example to demonstrate its effectiveness and usefulness.