title: Language-independent aspect-oriented programming

authors:
Donal Lafferty
Vinny Cahill

abstract: The term aspect-oriented programming (AOP) has come to describe\nthe set of programming mechanisms developed specifically to\nexpress crosscutting concerns. Since crosscutting concerns cannot\nbe properly modularized within object-oriented programming, they\nare expressed as aspects and are composed, or woven, with\ntraditionally encapsulated functionality referred to as components.\nMany AOP models exist, but their implementations are typically\ncoupled with a single language. To allow weaving of existing\ncomponents with aspects written in the language of choice, AOP\nrequires a language-independent tool.\nThis paper presents Weave.NET, a load-time weaver that allows\naspects and components to be written in a variety of languages and\nfreely intermixed. Weave.NET relies on XML to specify aspect\nbindings and standardized Common Language Infrastructure to\navoid coupling aspects or components with a particular language.\nBy demonstrating language-independence, Weave.NET provides a\nmigration path to the AOP paradigm by preserving existing\ndeveloper knowledge, tools, and software components. The tool?s\ncapabilities are demonstrated with logging aspects written in and\napplied to Visual Basic and C# components.


venue: oopsla

title: HydroJ: object-oriented pattern matching for evolvable distributed systems

authors:
Keunwoo Lee
Anthony LaMarca
Craig Chambers

abstract: In an evolving software system, components must be able to change independently while remaining compatible with their peers. One obstacle to independent evolution is the brittle parameter problem: the ability of two components to communicate can depend on a number of inessential details of the types, structure, and/or contents of the values communicated. If these details change, then the components can no longer communicate, even if the essential parts of the message remain unaffected.We present HydroJ, an extension of Java that addresses this problem. In HydroJ, components communicate using self-describing, semi-structured messages, and programmers use pattern matching to define the handling of messages. This design stems from two central ideas: first, that self-describing messages reduce dependence on inessential message format details; and second, that object-oriented pattern matching naturally focuses on the essential information in a message and is insensitive to inessential information.We have developed these ideas in the context of Rain, a distributed, heterogeneous messaging system for ubiquitous computing. To evaluate the design, we have constructed a prototype HydroJ compiler, implemented some Rain services in HydroJ, studied the evolution of an existing Rain service over time, and formalized HydroJ's key features in a core language.


title: Object equality profiling

authors:
Darko Marinov
Robert O'Callahan

abstract: We present Object Equality Profiling (OEP), a new technique for helping programmers discover optimization opportunities in programs. OEP discovers opportunities for replacing a set of equivalent object instances with a single representative object. Such a set represents an opportunity for automatically or manually applying optimizations such as hash consing, heap compression, lazy allocation, object caching, invariant hoisting, and more. To evaluate OEP, we implemented a tool to help programmers reduce the memory usage of Java programs. Our tool performs a dynamic analysis that records all the objects created during a particular program run. The tool partitions the objects into equivalence classes, and uses collected timing information to determine when elements of an equivalence class could have been safely collapsed into a single representative object without affecting the behavior of that program run. We report the results of applying this tool to benchmarks, including two widely used Web application servers. Many benchmarks exhibit significant amounts of object equivalence, and in most benchmarks our profiler identifies optimization opportunities clustered around a small number of allocation sites. We present a case study of using our profiler to find simple manual optimizations that reduce the average space used by live objects in two SpecJVM benchmarks by 47% and 38% respectively.


title: Relaxed MultiJava: balancing extensibility and modular typechecking

authors:
Todd D. Millstein
Mark Reay
Craig Chambers

abstract: We present the rationale, design, and implementation of Relaxed MultiJava (RMJ), a backward-compatible extension of Java that allows programmers to add new methods to existing classes and to write multimethods. Previous languages supporting these forms of extensibility either restrict their usage to a limited set of programming idioms that can be modularly typechecked (and modularly compiled) or simply forego modular typechecking altogether. In contrast, RMJ supports the new language features in a virtually unrestricted form while still providing mostly-modular static typechecking and fully-modular compilation. In some cases, the RMJ compiler will warn that the potential for a type error exists, but it will still complete compilation. In those cases, a custom class loader transparently performs load-time checking to verify that the potential error is never realized. RMJ's compiler and custom loader cooperate to keep load-time checking costs low. We report on qualitative and quantitative experience with our implementation of RMJ.


title: OOPAL: integrating array programming in object-oriented programming

authors:
Philippe Mougin
Stéphane Ducasse

abstract: Array programming shines in its ability to express computations at a high-level of abstraction, allowing one to manipulate and query whole sets of data at once. This paper presents the OPA model that enhances object-oriented programming with array programming features. The goal of OPA is to determine a minimum set of modifications that must be made to the traditional object model in order to take advantage of the possibilities of array programming. It is based on a minimal extension of method invocation and the definition of a kernel of methods implementing fundamental array programming operations. The OPA model presents a generalization of traditional message passing in the sense that a message can be send to an entire set of objects. The model is validated in FS, a new scripting language.


title: Mark-copy: fast copying GC with less space overhead

authors:
Narendran Sachindran
J. Eliot B. Moss

abstract: Copying garbage collectors have a number of advantages over non-copying collectors, including cheap allocation and avoiding fragmentation. However, in order to provide completeness (the guarantee to reclaim each garbage object eventually), standard copying collectors require space equal to twice the size of the maximum live data for a program. We present a mark-copy collection algorithm (MC) that extends generational copying collection and significantly reduces the heap space required to run a program. MC reduces space overhead by 75--85% compared with standard copying garbage collectors, increasing the range of applications that can use copying garbage collection. We show that when MC is given the same amount of space as a generational copying collector, it improves total execution time of Java benchmarks significantly in tight heaps, and by 5--10% in moderate size heaps. We also compare the performance of MC with a (non-generational) mark-sweep collector and a hybrid copying/mark-sweep generational collector. We find that MC can run in heaps comparable in size to the minimum heap space required by mark-sweep. We also find that for most benchmarks MC is significantly faster than mark-sweep in small and moderate size heaps. When compared with the hybrid collector, MC improves total execution time by about 5% for some benchmarks, partly by increasing the speed of execution of the application code.


title: Partial behavioral reflection: spatial and temporal selection of reification

authors:
Éric Tanter
Jacques Noyé
Denis Caromel
Pierre Cointe

abstract: Behavioral reflection is a powerful approach for adapting the behavior of running applications. In this paper we present and motivate partial behavioral reflection, an approach to more efficient and flexible behavioral reflection. We expose the spatial and temporal dimensions of such reflection, and propose a model of partial behavioral reflection based on the notion of hooksets. In the context of Java, we describe a reflective architecture offering appropriate interfaces for static and dynamic configuration of partial behavioral reflection at various levels, as well as Reflex, an open reflective extension for Java implementing this architecture. Reflex is the first extension that fully supports partial behavioral reflection in a portable manner, and that seamlessly integrates load-time and runtime behavioral reflection. The paper shows preliminary benchmarks and examples supporting the approach. The examples, dealing with the observer pattern and asynchronous communication via transparent futures, also show the interest of partial behavioral reflection as a tool for open dynamic Aspect-Oriented Programming.


title: Refactoring for generalization using type constraints

authors:
Frank Tip
Adam Kiezun
Dirk Bäumer

abstract: Refactoring is the process of applying behavior-preserving transformations (called "refactorings") in order to improve a program's design. Associated with a refactoring is a set of preconditions that must be satisfied to guarantee that program behavior is preserved, and a set of source code modifications. An important category of refactorings is concerned with generalization (e.g., Extract Interface for re-routing the access to a class via a newly created interface, and Pull Up Members for moving members into a superclass). For these refactorings, both the preconditions and the set of allowable source code modifications depend on interprocedural relationships between types of variables. We present an approach in which type constraints are used to verify the preconditions and to determine the allowable source code modifications for a number of generalization-related refactorings. This work is implemented in the standard distribution of Eclipse (see www.eclipse.org).


title: Lightweight confinement for featherweight Java

authors:
Tian Zhao
Jens Palsberg
Jan Vitek

abstract: Confinement properties impose a structure on object graphs which can be used to enforce encapsulation properties essential to certain program optimizations, modular reasoning, and software assurance. This paper formalizes the notion of confined type in the context of Featherweight Java. A static type system that mirrors the informal rules of Grothoff et al [17] is proven sound. The definition of confined types is extended to confined instantiation of generic classes. This allows for confined collection types in Java and for classes that can be confined post hoc. Confinement type rules are given for Generic Featherweight Java, and proven sound.


title: An efficient parallel heap compaction algorithm

authors:
Diab Abuaiadh
Yoav Ossia
Erez Petrank
Uri Silbershtein

abstract: We propose a heap compaction algorithm appropriate for modern computing environments. Our algorithm is targeted at SMP platforms. It demonstrates high scalability when running in parallel but is also extremely efficient when running single-threaded on a uniprocessor. Instead of using the standard forwarding pointer mechanism for updating pointers to moved objects, the algorithm saves information for a pack of objects. It then does a small computation to process this information and determine each object's new location. In addition, using a smart parallel moving strategy, the algorithm achieves (almost) perfect compaction in the lower addresses of the heap, whereas previous algorithms achieved parallelism by compacting within several predetermined segments.


title: Object-oriented units of measurement

authors:
Eric E. Allen
David Chase
Victor Luchangco
Jan-Willem Maessen
Guy L. Steele Jr.

abstract: Programs that manipulate physical quantities typically represent these quantities as raw numbers corresponding to the quantities' measurements in particular units (e.g., a length represented as a number of meters). This approach eliminates the possibility of catching errors resulting from adding or comparing quantities expressed in different units (as in the Mars Climate Orbiter error [11]), and does not support the safe comparison and addition of quantities of the same dimension. We show how to formulate dimensions and units as classes in a nominally typed object-oriented language through the use of statically typed metaclasses. Our formulation allows both parametric and inheritance poly-morphism with respect to both dimension and unit types. It also allows for integration of encapsulated measurement systems, dynamic conversion factors, declarations of scales (including nonlinear scales) with defined zeros, and nonconstant exponents on dimension types. We also show how to encapsulate most of the "magic machinery" that handles the algebraic nature of dimensions and units in a single meta-class that allows us to treat select static types as generators of a free abelian group.


title: A unified theory of garbage collection

authors:
David F. Bacon
Perry Cheng
V. T. Rajan

abstract: Tracing and reference counting are uniformly viewed as being fundamentally different approaches to garbage collection that possess very distinct performance properties. We have implemented high-performance collectors of both types, and in the process observed that the more we optimized them, the more similarly they behaved - that they seem to share some deep structure.


title: A practical type system and language for reference immutability

authors:
Adrian Birka
Michael D. Ernst

abstract: This paper describes a type system that is capable of expressing and enforcing immutability constraints. The specific constraint expressed is that the abstract state of the object to which an immutable reference refers cannot be modified using that reference. The abstract state is (part of) the transitively reachable state: that is, the state of the object and all state reachable from it by following references. The type system permits explicitly excluding fields or objects from the abstract state of an object. For a statically type-safe language, the type system guarantees reference immutability. If the language is extended with immutability downcasts, then run-time checks enforce the reference immutability constraints.


title: Mirrors: design principles for meta-level facilities of object-oriented programming languages

authors:
Gilad Bracha
David M. Ungar

abstract: We identify three design principles for reflection and metaprogramming facilities in object oriented programming languages. Encapsulation: meta-level facilities must encapsulate their implementation. Stratification: meta-level facilities must be separated from base-level functionality. Ontological correspondence: the ontology of meta-level facilities should correspond to the ontology of the language they manipulate. Traditional/mainstream reflective architectures do not follow these precepts. In contrast, reflective APIs built around the concept of mirrors are characterized by adherence to these three principles. Consequently, mirror-based architectures have significant advantages with respect to distribution, deployment and general purpose metaprogramming.

awards: Most Influential OOPSLA Paper (awarded 2014)


title: Concrete syntax for objects: domain-specific language embedding and assimilation without restrictions

authors:
Martin Bravenboer
Eelco Visser

abstract: Application programmer's interfaces give access to domain knowledge encapsulated in class libraries without providing the appropriate notation for expressing domain composition. Since object-oriented languages are designed for extensibility and reuse, the language constructs are often sufficient for expressing domain abstractions at the semantic level. However, they do not provide the right abstractions at the syntactic level. In this paper we describe MetaBorg, a method for providing concrete syntax for domain abstractions to application programmers. The method consists of embedding domain-specific languages in a general purpose host language and assimilating the embedded domain code into the surrounding host code. Instead of extending the implementation of the host language, the assimilation phase implements domain abstractions in terms of existing APIs leaving the host language undisturbed. Indeed, MetaBorg can be considered a method for promoting APIs to the language level. The method is supported by proven and available technology, i.e. the syntax definition formalism SDF and the program transformation language and toolset Stratego/XT. We illustrate the method with applications in three domains: code generation, XML generation, and user-interface construction.


title: Converting Java classes to use generics

authors:
Daniel von Dincklage
Amer Diwan

abstract: Generics offer significant software engineering benefits since they provide code reuse without compromising type safety. Thus generics will be added to the Java language in the next release. While this extension to Java will help programmers when they are writing new code, it will not help legacy code unless it is rewritten to use generics. In our experience, manually modifying existing programs to use generics is complex and can be error prone and labor intensive.


title: Converting java programs to use generic libraries

authors:
Alan Donovan
Adam Kiezun
Matthew S. Tschantz
Michael D. Ernst

abstract: Java 1.5 will include a type system (called JSR-14) that supports parametric polymorphism, or generic classes. This will bring many benefits to Java programmers, not least because current Java practice makes heavy use of logically-generic classes, including container classes.


title: Measuring the dynamic behaviour of AspectJ programs

authors:
Bruno Dufour
Christopher Goard
Laurie J. Hendren
Oege de Moor
Ganesh Sittampalam
Clark Verbrugge

abstract: This paper proposes and implements a rigorous method for studying the dynamic behaviour of AspectJ programs. As part of this methodology several new metrics specific to AspectJ programs are proposed and tools for collecting the relevant metrics are presented. The major tools consist of: (1) a modified version of the AspectJ compiler that tags bytecode instructions with an indication of the cause of their generation, such as a particular feature of AspectJ; and (2) a modified version of the *J dynamic metrics collection tool which is composed of a JVMPI-based trace generator and an analyzer which propagates tags and computes the proposed metrics. This dynamic propagation is essential, and thus this paper contributes not only new metrics, but also non-trivial ways of computing them.


title: Instrumentation of standard libraries in object-oriented languages: the twin class hierarchy approach

authors:
Michael Factor
Assaf Schuster
Konstantin Shagin

abstract: Code instrumentation is widely used for a range of purposes that include profiling, debugging, visualization, logging, and distributed computing. Due to their special status within the language infrastructure, the standard class libraries, also known as system classes provided by most contemporary object-oriented languages are difficult and sometimes impossible to instrument. If instrumented, the use of their rewritten versions within the instrumentation code is usually unavoidable. However, this is equivalent to `instrumenting the instrumentation', and thus may lead to erroneous results. Consequently, most systems avoid rewriting system classes. We present a novel instrumentation strategy that alleviates the above problems by renaming the instrumented classes. The proposed approach does not require any modifications to the language, compiler or runtime. It allows system classes to be instrumented both statically and dynamically. In fact, this is the first technique that enables dynamic instrumentation of Java system classes without modification of any runtime components. We demonstrate our approach by implementing two instrumentation-based systems: a memory profiler and a distributed runtime for Java.


title: Pluggable verification modules: an extensible protection mechanism for the JVM

abstract: Through the design and implementation of a JVM that supports Pluggable Verification Modules (PVMs), the idea of an extensible protection mechanism is entertained. Link-time bytecode verification becomes a pluggable service that can be readily replaced, reconfigured and augmented. Application-specific verification services can be safely introduced into the dynamic linking process of the JVM. This feature is enabled by the adoption of a previously proposed modular verification architecture, Proof Linking [23, 24], which decouples bytecode verification from the dynamic linking process, rendering the verifier a replaceable module. The PVM mechanism has been implemented in an open source JVM, the Aegis VM [21]. To evaluate the software engineering and security engineering benefits of this extensible protection mechanism, an augmented type system JAC (Java Access Control) [37] has been successfully implemented as a PVM.


title: Method-level phase behavior in java workloads

authors:
Andy Georges
Dries Buytaert
Lieven Eeckhout
Koen De Bosschere

abstract: Java workloads are becoming more and more prominent on various computing devices. Understanding the behavior of a Java workload which includes the interaction between the application and the virtual machine (VM), is thus of primary importance during performance analysis and optimization. Moreover, as contemporary software projects are increasing in complexity, automatic performance analysis techniques are indispensable. This paper proposes an off-line method-level phase analysis approach for Java workloads that consists of three steps. In the first step, the execution time is computed for each method invocation. Using an off-line tool, we subsequently analyze the dynamic call graph (that is annotated with the method invocations' execution times) to identify method-level phases. Finally, we measure performance characteristics for each of the selected phases. This is done using hardware performance monitors. As such, our approach allows for linking microprocessor-level information at the individual methods in the Java application's source code. This is extremely interesting information during performance analysis and optimization as programmers can use this information to optimize their code. We evaluate our approach in the Jikes RVM on an IA-32 platform using the SPECjvm98 and SPECjbb2000 benchmarks. This is done according to a number of important criteria: the overhead during profiling, the variability within and between the phases, its applicability in Java workload characterization (measuring performance characteristics of the various VM components) and application bottleneck identification.


title: Super and inner: together at last!

authors:
David S. Goldberg
Robert Bruce Findler
Matthew Flatt

abstract: In an object-oriented language, a derived class may declare a method with the same signature as a method in the base class. The meaning of the re-declaration depends on the language. Most commonly, the new declaration overrides the base declaration, perhaps completely replacing it, or perhaps using super to invoke the old implementation. Another possibility is that the base class always controls the method implementation, and the new declaration merely augments the method in the case that the base method calls inner. Each possibility has advantages and disadvantages. In this paper, we explain why programmers need both kinds of method redeclaration, and we present a language that integrates them. We also present a formal semantics for the new language, and we describe an implementation for MzScheme.


title: Recovering binary class relationships: putting icing on the UML cake

authors:
Yann-Gaël Guéhéneuc
Hervé Albin-Amiot

abstract: A discontinuity exists between object-oriented modeling and programming languages. This discontinuity arises from ambiguous concepts in modeling languages and a lack of corresponding concepts in programming languages. It is particularly acute for binary class relationships---association, aggregation, and composition. It hinders the traceability between software implementation and design, thus hampering software analysis. We propose consensual definitions of the binary class relationships with four minimal properties---exclusivity, invocation site, lifetime, and multiplicity. We describe algorithms to detect automatically these properties in source code and apply these on several frameworks. Thus, we bridge the gap between implementation and design for the binary class relationships, easing software analysis.


title: Finding your cronies: static analysis for dynamic object colocation

authors:
Samuel Z. Guyer
Kathryn S. McKinley

abstract: This paper introduces dynamic object colocation, an optimization to reduce copying costs in generational and other incremental garbage collectors by allocating connected objects together in the same space. Previous work indicates that connected objects belong together because they often have similar lifetimes. Generational collectors, however, allocate all new objects in a nursery space. If these objects are connected to data structures residing in the mature space, the collector must copy them. Our solution is a cooperative optimization that exploits compiler analysis to make runtime allocation decisions. The compiler analysis discovers potential object connectivity for newly allocated objects. It then replaces these allocations with calls to coalloc, which takes an extra parameter called the colocator object. At runtime, coalloc determines the location of the colocator and allocates the new object together with it in either the nursery or mature space. Unlike pretenuring, colocation makes precise per-object allocation decisions and does not require lifetime analysis or allocation site homogeneity. Experimental results for SPEC Java benchmarks using Jikes RVM show colocation can reduce garbage collection time by 50% to 75%, and total performance by up to 1%.


title: Vertical profiling: understanding the behavior of object-priented applications

authors:
Matthias Hauswirth
Peter F. Sweeney
Amer Diwan
Michael Hind

abstract: Object-oriented programming languages provide a rich set of features that provide significant software engineering benefits. The increased productivity provided by these features comes at a justifiable cost in a more sophisticated runtime system whose responsibility is to implement these features efficiently. However, the virtualization introduced by this sophistication provides a significant challenge to understanding complete system performance, not found in traditionally compiled languages, such as C or C++. Thus, understanding system performance of such a system requires profiling that spans all levels of the execution stack, such as the hardware, operating system, virtual machine, and application.


title: The garbage collection advantage: improving program locality

authors:
Xianglong Huang
Stephen M. Blackburn
Kathryn S. McKinley
J. Eliot B. Moss
Zhenlin Wang
Perry Cheng

abstract: As improvements in processor speed continue to outpace improvements in cache and memory speed, poor locality increasingly degrades performance. Because copying garbage collectors move objects, they have an opportunity to improve locality. However, no static copying order is guaranteed to match program traversal orders. This paper introduces online object reordering (OOR) which includes a new dynamic, online class analysis for Java that detects program traversal patterns and exploits them in a copying collector. OOR uses run-time method sampling that drives just-in-time (JIT) compilation. For each hot (frequently executed) method, OOR analysis identifies the hot field accesses. At garbage collection time, the OOR collector then copies referents of hot fields together with their parent. Enhancements include static analysis to exclude accesses in cold basic blocks, heuristics that decay heat to respond to phase changes, and a separate space for hot objects. The overhead of OOR is on average negligible and always less than 2% on Java benchmarks in Jikes RVM with MMTk. We compare program performance of OOR to static class-oblivious copying orders (e.g., breadth and depth first). Performance variation due to static orders is often low, but can be up to 25%. In contrast, OOR matches or improves upon the best static order since its history-based copying tunes memory layout to program traversal.


title: Practical predicate dispatch

abstract: Predicate dispatch is an object-oriented (OO) language mechanism for determining the method implementation to be invoked upon a message send. With predicate dispatch, each method implementation includes a predicate guard specifying the conditions under which the method should be invoked, and logical implication of predicates determines the method overriding relation. Predicate dispatch naturally unifies and generalizes several common forms of dynamic dispatch, including traditional OO dispatch, multimethod dispatch, and functional-style pattern matching. Unfortunately, prior languages supporting predicate dispatch have had several deficiencies that limit its utility in practice.


title: Decentralizing execution of composite web services

authors:
Mangala Gowri Nanda
Satish Chandra
Vivek Sarkar

abstract: Distributed enterprise applications today are increasingly being built from services available over the web. A unit of functionality in this framework is a web service, a software application that exposes a set of "typed'' connections that can be accessed over the web using standard protocols. These units can then be composed into a composite web service. BPEL (Business Process Execution Language) is a high-level distributed programming language for creating composite web services.


title: Scalable extensibility via nested inheritance

authors:
Nathaniel Nystrom
Stephen Chong
Andrew C. Myers

abstract: Inheritance is a useful mechanism for factoring and reusing code. However, it has limitations for building extensible systems. We describe nested inheritance, a mechanism that addresses some of the limitations of ordinary inheritance and other code reuse mechanisms. Using our experience with an extensible compiler framework, we show how nested inheritance can be used to construct highly extensible software frameworks. The essential aspects of nested inheritance are formalized in a simple object-oriented language with an operational semantics and type system. The type system of this language is sound, so no run-time type checking is required to implement it and no run-time type errors can occur. We describe our implementation of nested inheritance as an unobtrusive extension of the Java language, called Jx. Our prototype implementation translates Jx code to ordinary Java code, without duplicating inherited code.


title: Transparent proxies for java futures

authors:
Polyvios Pratikakis
Jaime Spacco
Michael W. Hicks

abstract: A proxy object is a surrogate or placeholder that controls access to another target object. Proxies can be used to support distributed programming, lazy or parallel evaluation, access control, and other simple forms of behavioral reflection. However, wrapper proxies (like futures or suspensions for yet-to-be-computed results) can require significant code changes to be used in statically-typed languages, while proxies more generally can inadvertently violate assumptions of transparency, resulting in subtle bugs.


title: Chianti: a tool for change impact analysis of java programs

authors:
Xiaoxia Ren
Fenil Shah
Frank Tip
Barbara G. Ryder
Ophelia C. Chesley

abstract: This paper reports on the design and implementation of Chianti, a change impact analysis tool for Java that is implemented in the context of the Eclipse environment. Chianti analyzes two versions of an application and decomposes their difference into a set of atomic changes. Change impact is then reported in terms of affected (regression or unit) tests whose execution behavior may have been modified by the applied changes. For each affected test, Chianti also determines a set of affecting changes that were responsible for the test's modified behavior. This latter step of isolating the changes that induce the failure of one specific test from those changes that only affect other tests can be used as a debugging technique in situations where a test fails unexpectedly after a long editing session. We evaluated Chianti on a year (2002) of CVS data from M. Ernst's Daikon system, and found that, on average, 52% of Daikon's unit tests are affected. Furthermore, each affected unit test, on average, is affected by only 3.95% of the atomic changes. These findings suggest that our change impact analysis is a promising technique for assisting developers with program understanding and debugging.


title: MC2: high-performance garbage collection for memory-constrained environments

authors:
Narendran Sachindran
J. Eliot B. Moss
Emery D. Berger

abstract: Java is becoming an important platform for memory-constrained consumer devices such as PDAs and cellular phones, because it provides safety and portability. Since Java uses garbage collection, efficient garbage collectors that run in constrained memory are essential. Typical collection techniques used on these devices are mark-sweep and mark-compact. Mark-sweep collectors can provide good throughput and pause times but suffer from fragmentation. Mark-compact collectors prevent fragmentation, have low space overheads, and provide good throughput. However, they can suffer from long pause times. Copying collectors can provide higher throughput than either of these techniques, but because of their high space overhead, they previously were unsuitable for memory-constrained devices. This paper presents MC2 (Memory-Constrained Copying), a copying generational garbage collector that meets the needs of memory-constrained devices with soft real-time requirements. MC2 has low space over-head and tight space bounds, prevents fragmentation, provides good throughput, and yields short pause times. These qualities make MC2 attractive for other environments, including desktops and servers.


title: Object-oriented encapsulation for dynamically typed languages

authors:
Nathanael Schärli
Andrew P. Black
Stéphane Ducasse

abstract: Encapsulation in object-oriented languages has traditionally been based on static type systems. As a consequence, dynamically-typed languages have only limited support for encapsulation. This is surprising, considering that encapsulation is one of the most fundamental and important concepts behind object-oriented programming and that it is essential for writing programs that are maintainable and reliable, and that remain robust as they evolve.


title: Refactoring class hierarchies with KABA

authors:
Mirko Streckenbach
Gregor Snelting

abstract: KABA is an innovative system for refactoring Java class hierar-chies. It uses the Snelting/Tip algorithm [13] in order to determine a behavior-preserving refactoring which is optimal with respect to a given set of client programs. KABA can be based on dynamic as well as static program analysis. The static variant will preserve program behavior for all possible input values; the dynamic version guarantees preservation of behavior for all runs in a given test suite. KABA offers automatic refactoring as well as manual refactoring using a dedicated editor.


title: Finding and preventing run-time error handling mistakes

authors:
Westley Weimer
George C. Necula

abstract: It is difficult to write programs that behave correctly in the presence of run-time errors. Existing programming language features often provide poor support for executing clean-up code and for restoring invariants in such exceptional situations. We present a dataflow analysis for finding a certain class of error-handling mistakes: those that arise from a failure to release resources or to clean up properly along all paths. Many real-world programs violate such resource safety policies because of incorrect error handling. Our flow-sensitive analysis keeps track of outstanding obligations along program paths and does a precise modeling of control flow in the presence of exceptions. Using it, we have found over 800 error handling mistakes almost 4 million lines of Java code. The analysis is unsound and produces false positives, but a few simple filtering rules suffice to remove them in practice. The remaining mistakes were manually verified. These mistakes cause sockets, files and database handles to be leaked along some paths. We present a characterization of the most common causes of those errors and discuss the limitations of exception handling, finalizers and destructors in addressing them. Based on those errors, we propose a programming language feature that keeps track of obligations at run time and ensures that they are discharged. Finally, we present case studies to demonstrate that this feature is natural, efficient, and can improve reliability; for example, retrofitting a 34kLOC program with it resulted in a 0.5% code size decrease, a surprising 17% speed increase (from correctly deallocating resources in the presence of exceptions), and more consistent behavior.


title: Resolving feature convolution in middleware systems

authors:
Charles Zhang
Hans-Arno Jacobsen

abstract: Middleware provides simplicity and uniformity for the development of distributed applications. However, the modularity of the architecture of middleware is starting to disintegrate and to become complicated due to the interaction of too many orthogonal concerns imposed from a wide range of application requirements. This is not due to bad design but rather due to the limitations of the conventional architectural decomposition methodologies. We introduce the principles of horizontal decomposition (HD) which addresses this problem with a mixed-paradigm middleware architecture. HD provides guidance for the use of conventional decomposition methods to implement the core functionalities of middleware and the use of aspect orientation to address its orthogonal properties. Our evaluation of the horizontal decomposition principles focuses on refactoring major middleware functionalities into aspects in order to modularize and isolate them from the core architecture. New versions of the middleware platform can be created through combining the core and the flexible selection of middleware aspects such as IDL data types, the oneway invocation style, the dynamic messaging style, and additional character encoding schemes. As a result, the primary functionality of the middleware is supported with a much simpler architecture and enhanced performance. Moreover, customization and configuration of the middleware for a wide-range of requirements becomes possible.


title: Formalising Java RMI with explicit code mobility

authors:
Alexander Joseph Ahern
Nobuko Yoshida

abstract: This paper presents a Java-like core language with primitives for object-oriented distribution and explicit code mobility. We apply our formulation to prove the correctness of several optimisations for distributed programs. Our language captures crucial but often hidden aspects of distributed object-oriented programming, including object serialisation, dynamic class downloading and remote method invocation. It is defined in terms of an operational semantics that concisely models the behaviour of distributed programs using machinery from calculi of mobile processes. Type safety is established using invariant properties for distributed runtime configurations. We argue that primitives for explicit code mobility offer a programmer fine-grained control of type-safe code distribution, which is crucial for improving the performance and safety of distributed object-oriented applications.


title: Adding trace matching with free variables to AspectJ

authors:
Chris Allan
Pavel Avgustinov
Aske Simon Christensen
Laurie J. Hendren
Sascha Kuzins
Ondrej Lhoták
Oege de Moor
Damien Sereni
Ganesh Sittampalam
Julian Tibble

abstract: An aspect observes the execution of a base program; when certain actions occur, the aspect runs some extra code of its own. In the AspectJ language, the observations that an aspect can make are confined to the current action: it is not possible to directly observe the history of a computation.Recently, there have been several interesting proposals for new history-based language features, most notably by Douence et al. and by Walker and Viggers. In this paper, we present a new history-based language feature called tracematches that enables the programmer to trigger the execution of extra code by specifying a regular pattern of events in a computation trace. We have fully designed and implemented tracematches as a seamless extension of AspectJ.A key innovation in our tracematch approach is the introduction of free variables in the matching patterns. This enhancement enables a whole new class of applications in which events can be matched not only by the event kind, but also by the values associated with the free variables. We provide several examples of applications enabled by this feature.After introducing and motivating the idea of tracematches via examples, we present a detailed semantics of our language design, and we derive an implementation from that semantics. The implementation has been realised as an extension of the abc compiler for AspectJ.


title: Improving virtual machine performance using a cross-run profile repository

authors:
Matthew Arnold
Adam Welc
V. T. Rajan

abstract: Virtual machines for languages such as the Java programming language make extensive use of online profiling and dynamic optimization to improve program performance. But despite the important role that profiling plays in achieving high performance, current virtual machines discard a program's profile data at the end of execution, wasting the opportunity to use past knowledge to improve future performance. In this paper, we present a fully automated architecture for exploiting cross-run profile data in virtual machines. Our work addresses a number of challenges that previously limited the practicality of such an approach.We apply this architecture to address the problem of selective optimization, and describe our implementation in IBM's J9 Java virtual machine. Our results demonstrate substantial performance improvements on a broad suite of Java programs, with the average performance ranging from 8.8% -- 16.6% depending on the execution scenario.


title: Refactoring support for class library migration

authors:
Ittai Balaban
Frank Tip
Robert M. Fuhrer

abstract: As object-oriented class libraries evolve, classes are occasionally deprecated in favor of others with roughly the same functionality. In Java's standard libraries, for example, class Hashtable has been superseded by HashMap, and Iterator is now preferred over Enumeration. Migrating client applications to use the new idioms is often desirable, but making the required changes to declarations and allocation sites can be quite labor-intensive. Moreover, migration becomes complicated---and sometimes impossible---if an application interacts with external components, if a legacy class is not completely equivalent to its replacement, or if multiple interdependent classes must be migrated simultaneously. We present an approach in which mappings between legacy classes and their replacements are specified by the programmer. Then, an analysis based on type constraints determines where declarations and allocation sites can be updated. The method was implemented in Eclipse, and evaluated on a number of Java applications. On average, our tool could migrate more than 90% of the references to legacy classes.


title: Classbox/J: controlling the scope of change in Java

authors:
Alexandre Bergel
Stéphane Ducasse
Oscar Nierstrasz

abstract: Unanticipated changes to complex software systems can introduce anomalies such as duplicated code, suboptimal inheritance relationships and a proliferation of run-time downcasts. Refactoring to eliminate these anomalies may not be an option, at least in certain stages of software evolution. Classboxes are modules that restrict the visibility of changes to selected clients only, thereby offering more freedom in the way unanticipated changes may be implemented, and thus reducing the need for convoluted design anomalies. In this paper we demonstrate how classboxes can be implemented in statically-typed languages like Java. We also present an extended case study of Swing, a Java GUI package built on top of AWT, and we document the ensuing anomalies that Swing introduces. We show how Classbox/J, a prototype implementation of classboxes for Java, is used to provide a cleaner implementation of Swing using local refinement rather than subclassing.


title: X10: an object-oriented approach to non-uniform cluster computing

authors:
Philippe Charles
Christian Grothoff
Vijay A. Saraswat
Christopher Donawa
Allan Kielstra
Kemal Ebcioglu
Christoph von Praun
Vivek Sarkar

abstract: It is now well established that the device scaling predicted by Moore's Law is no longer a viable option for increasing the clock frequency of future uniprocessor systems at the rate that had been sustained during the last two decades. As a result, future systems are rapidly moving from uniprocessor to multiprocessor configurations, so as to use parallelism instead of frequency scaling as the foundation for increased compute capacity. The dominant emerging multiprocessor structure for the future is a Non-Uniform Cluster Computing (NUCC) system with nodes that are built out of multi-core SMP chips with non-uniform memory hierarchies, and interconnected in horizontally scalable cluster configurations such as blade servers. Unlike previous generations of hardware evolution, this shift will have a major impact on existing software. Current OO language facilities for concurrent and distributed programming are inadequate for addressing the needs of NUCC systems because they do not support the notions of non-uniform data access within a node, or of tight coupling of distributed nodes.We have designed a modern object-oriented programming language, X10, for high performance, high productivity programming of NUCC systems. A member of the partitioned global address space family of languages, X10 highlights the explicit reification of locality in the form of places}; lightweight activities embodied in async, future, foreach, and ateach constructs; a construct for termination detection (finish); the use of lock-free synchronization (atomic blocks); and the manipulation of cluster-wide global data structures. We present an overview of the X10 programming model and language, experience with our reference implementation, and results from some initial productivity comparisons between the X10 and Java™ languages.

awards: Most Influential OOPSLA Paper (awarded 2015)


title: PolyD: a flexible dispatching framework

authors:
Antonio Cunei
Jan Vitek

abstract: The standard dispatching mechanisms built into programming languages are sometimes inadequate to the needs of the programmer. In the case of Java, the need for more flexibility has led to the development of a number of tools, including visitors and multi-method extensions, that each add some particular functionality, but lack the generality necessary to support user-defined dispatching mechanisms. In this paper we advocate a more modular approach to dispatching, and we present a tool, PolyD, that allows the programmer to design custom dispatching strategies and to parametrize many aspects of the dispatching process. PolyD exhibits excellent performance and compares well against existing tools.


title: Combining the robustness of checked exceptions with the flexibility of unchecked exceptions using anchored exception declarations

authors:
Marko van Dooren
Eric Steegmans

abstract: Ever since their invention 30 years ago, checked exceptions have been a point of much discussion. On the one hand, they increase the robustness of software by preventing the manifestation of unanticipated checked exceptions at run-time. On the other hand, they decrease the adaptability of software because they must be propagated explicitly, and must often be handled even if they cannot be signalled.We show that the problems with checked exceptions are caused by a lack of expressiveness of the exceptional return type of a method, which currently dictates a copy & paste style. We add the required expressiveness by introducing anchored exception declarations, which allow the exceptional behavior of a method to be declared relative to that of others. We present the formal semantics of anchored exception declarations, along with the necessary rules for ensuring compile-time safety, and give a proof of soundness. We show that anchored exception declarations do not violate the principle of information hiding when used properly, and provide a guideline for when to use them.We have implemented anchored exception declarations in Cappuccino, which is an extension to the ClassicJava programming language.


title: Subtext: uncovering the simplicity of programming

abstract: Representing programs as text strings makes programming harder then it has to be. The source text of a program is far removed from its behavior. Bridging this conceptual gulf is what makes programming so inhumanly difficult -- we are not compilers. Subtext is a new medium in which the representation of a program is the same thing as its execution. Like a spreadsheet, a program is visible and alive, constantly executing even as it is edited. Program edits are coherent semantic transformations.The essence of this new medium is copying. Programs are constructed by copying and executed by copy flow: the projection of changes through copies. The simple idea of copying develops into a rich theory of higher-order continual copying of trees. Notably absent are symbolic names, the workhorse of textual notation, replaced by immediately-bound explicit relationships. Subtext unifies traditionally distinct programming tools and concepts, and enables some novel ones. Ancestral structures are a new primitive data type that combines the features of lists and records, along with unproblematic multiple inheritance. Adaptive conditionals use first-class program edits to dynamically adapt behavior.A prototype implementation shows promise, but calls for much further research. Subtext suggests that we can make programming radically easier, if we are willing to be radical.


title: Micro patterns in Java code

authors:
Joseph Gil
Itay Maman

abstract: Micro patterns are similar to design patterns, except that micro patterns are stand at a lower, closer to the implementation, level of abstraction. Micro patterns are also unique in that they are mechanically recognizable, since each such pattern can be expressed as a formal condition on the structure of a class.This paper presents a catalog of 27 micro-patterns defined on Java classes and interfaces. The catalog captures a wide spectrum of common programming practices, including a particular and (intentionally restricted) use of inheritance, immutability, data management and wrapping, restricted creation, and emulation of procedural-, modular-, and even functional- programming paradigms with object oriented constructs. Together, the patterns present a set of prototypes after which a large portion of all Java classes and interfaces are modeled. We provide empirical indication that this portion is as high as 75%.A statistical analysis of occurrences of micro patterns in a large software corpus, spanning some 70,000 Java classes drawn from a rich set of application domains, shows, with high confidence level that the use of these patterns is not random. These results indicate consciousness and discernible design decisions, which are sustained in the software evolution. With high confidence level, we can also show that the use of these patterns is tied to the specification, or the purpose, that the software realizes.The traceability, abundance and the statistical significance of micro pattern occurrence raise the hope of using the classification of software into these patterns for a more founded appreciation of its design and code quality.


title: Relational queries over program traces

authors:
Simon Goldsmith
Robert O'Callahan
Alex Aiken

abstract: Instrumenting programs with code to monitor runtime behavior is a common technique for profiling and debugging. In practice, instrumentation is either inserted manually by programmers, or automatically by specialized tools that monitor particular properties. We propose Program Trace Query Language (PTQL), a language based on relational queries over program traces, in which programmers can write expressive, declarative queries about program behavior. We also describe our compiler, Partiqle. Given a PTQL query and a Java program, Partiqle instruments the program to execute the query on-line. We apply several PTQL queries to a set of benchmark programs, including the Apache Tomcat Web server. Our queries reveal significant performance bugs in the jack SpecJVM98 benchmark, in Tomcat, and in the IBM Java class library, as well as some correct though uncomfortably subtle code in the Xerces XML parser. We present performance measurements demonstrating that our prototype system has usable performance.


title: Fine-grained interoperability through mirrors and contracts

authors:
Kathryn E. Gray
Robert Bruce Findler
Matthew Flatt

abstract: As a value flows across the boundary between interoperating languages, it must be checked and converted to fit the types and representations of the target language. For simple forms of data, the checks and coercions can be immediate; for higher order data, such as functions and objects, some must be delayed until the value is used in a particular way. Typically, these coercions and checks are implemented by an ad-hoc mixture of wrappers, reflection, and dynamic predicates. We observe that 1) the wrapper and reflection operations fit the profile of mirrors, 2) the checks correspond to contracts, and 3) the timing and shape of mirror operations coincide with the timing and shape of contract operations. Based on these insights, we present a new model of interoperability that builds on the ideas of mirrors and contracts, and we describe an interoperable implementation of Java and Scheme that is guided by the model.


title: Lifting sequential graph algorithms for distributed-memory parallel computation

authors:
Douglas P. Gregor
Andrew Lumsdaine

abstract: This paper describes the process used to extend the Boost Graph Library (BGL) for parallel operation with distributed memory. The BGL consists of a rich set of generic graph algorithms and supporting data structures, but it was not originally designed with parallelism in mind. In this paper, we revisit the abstractions comprising the BGL in the context of distributed-memory parallelism, lifting away the implicit requirements of sequential execution and a single shared address space. We illustrate our approach by describing the process as applied to one of the core algorithms in the BGL, breadth-first search. The result is a generic algorithm that is unchanged from the sequential algorithm, requiring only the introduction of external (distributed) data structures for parallel execution. More importantly, the generic implementation retains its interface and semantics, such that other distributed algorithms can be built upon it, just as algorithms are layered in the sequential case. By characterizing these extensions as well as the extension process, we develop general principles and patterns for using (and reusing) generic, object-oriented parallel software libraries. We demonstrate that the resulting algorithm implementations are both efficient and scalable with performance results for several algorithms.


title: Automating vertical profiling

authors:
Matthias Hauswirth
Amer Diwan
Peter F. Sweeney
Michael C. Mozer

abstract: Last year at OOPSLA we presented a methodology, vertical profiling, for understanding the performance of object-oriented programs. The key insight behind this methodology is that modern programs run on top of many layers (virtual machine, middleware, etc) and thus we need to collect and combine information from all layers in order to understand system performance. Although our methodology was able to explain previously unexplained performance phenomena, it was extremely labor intensive. In this paper we describe and evaluate techniques for automating two significant activities of vertical profiling: trace alignment and correlation. Trace alignment aligns traces obtained from separate runs so that one can reason across the traces. We are not aware of any prior approach that effectively and automatically aligns traces. Correlation sifts through hundreds of metrics to find ones that have a bearing on a performance anomaly of interest. In prior work we found that statistical correlation was only sometimes effective. We have identified highly-effective approaches for both activities.For aligning traces we explore dynamic time warping, and for correlation we explore eight correlators based on statistical correlation, distance measures, and piecewise linear segmentation. Although we explore these activities in the context of vertical profiling, both activities are widely applicable in the performance analysis area.


title: Quantifying the performance of garbage collection vs. explicit memory management

authors:
Matthew Hertz
Emery D. Berger

abstract: Garbage collection yields numerous software engineering benefits, but its quantitative impact on performance remains elusive. One can compare the cost of conservative garbage collection to explicit memory management in C/C++ programs by linking in an appropriate collector. This kind of direct comparison is not possible for languages designed for garbage collection (e.g., Java), because programs in these languages naturally do not contain calls to free. Thus, the actual gap between the time and space performance of explicit memory management and precise, copying garbage collection remains unknown.We introduce a novel experimental methodology that lets us quantify the performance of precise garbage collection versus explicit memory management. Our system allows us to treat unaltered Java programs as if they used explicit memory management by relying on oracles to insert calls to free. These oracles are generated from profile information gathered in earlier application runs. By executing inside an architecturally-detailed simulator, this "oracular" memory manager eliminates the effects of consulting an oracle while measuring the costs of calling malloc and free. We evaluate two different oracles: a liveness-based oracle that aggressively frees objects immediately after their last use, and a reachability-based oracle that conservatively frees objects just after they are last reachable. These oracles span the range of possible placement of explicit deallocation calls.We compare explicit memory management to both copying and non-copying garbage collectors across a range of benchmarks using the oracular memory manager, and present real (non-simulated) runs that lend further validity to our results. These results quantify the time-space tradeoff of garbage collection: with five times as much memory, an Appel-style generational collector with a non-copying mature space matches the performance of reachability-based explicit memory management. With only three times as much memory, the collector runs on average 17% slower than explicit memory management. However, with only twice as much memory, garbage collection degrades performance by nearly 70%. When physical memory is scarce, paging causes garbage collection to run an order of magnitude slower than explicit memory management.


title: Associated types and constraint propagation for mainstream object-oriented generics

authors:
Jaakko Järvi
Jeremiah Willcock
Andrew Lumsdaine

abstract: Support for object-oriented programming has become an integral part of mainstream languages, and more recently generic programming has gained widespread acceptance as well. A natural question is how these two paradigms, and their underlying language mechanisms, should interact. One particular design option, that of using subtyping to constrain the type parameters of generic functions, has been chosen in the generics of Java and those planned for a future revision of C#.Certain shortcomings have previously been identified in using subtyping for constraining parametric polymorphism in the context of generic programming.To address these, we propose extending object-oriented interfaces and subtyping to include associated types and constraint propagation.Associated types are type members of interfaces and classes. Constraint propagation allows certain constraints on type parameters to be inferred from other constraints on those parameters and their use in base class type expressions.The paper demonstrates these extensions in the context of C# (with generics), describes a translation of the extended features to C#, and presents a formalism proving their safety. The formalism is applicable to other mainstream object-oriented languages supporting F-bounded polymorphism, such as Java.


title: Generalized algebraic data types and object-oriented programming

authors:
Andrew Kennedy
Claudio V. Russo

abstract: Generalized algebraic data types (GADTs) have received much attention recently in the functional programming community. They generalize the (type) parameterized algebraic datatypes (PADTs) of ML and Haskell by permitting value constructors to return specific, rather than parametric, typeinstantiations of their own datatype. GADTs have a number of applications, including strongly-typed evaluators, generic pretty-printing, generic traversals and queries, and typed LR parsing. We show that existing object-oriented programming languages such as Java and C ♯ can express GADT definitions, and a large class of GADT-manipulating programs, through the use of generics, subclassing, and virtual dispatch. However, some programs can be written only through the use of redundant runtime casts. Moreover, instantiationspecific, yet safe, operations on ordinary PADTs only admit indirect cast-free implementations, via higher-order encodings. We propose a generalization of the type constraint mechanisms of C ♯ and Java to both avoid the need for casts in GADT programs and higher-order contortions in PADT programs; we present a Visitor pattern for GADTs, and describe a refined switch construct as an alternative to virtual dispatch on datatypes. We formalize both extensions and prove type soundness.


title: Pluggable AOP: designing aspect mechanisms for third-party composition

authors:
Sergei Kojarski
David H. Lorenz

abstract: Studies of Aspect-Oriented Programming (AOP) usually focus on a language in which a specific aspect extension is integrated with a base language. Languages specified in this manner have a fixed, non-extensible AOP functionality. This paper argues the need for AOP to support the integration and use of multiple domain-specific aspect extensions together. We study the more general case of integrating a base language with a set of third-party aspect extensions for that language. We present a general mixin-based semantic framework for implementing dynamic aspect extensions in such a way that multiple, independently developed aspect mechanisms can be subject to third-party composition and work collaboratively. Principles governing the design of a collaborative aspect mechanism are aspectual effect exposure and implementation hiding.


title: Interaction-based programming with classages

authors:
Yu David Liu
Scott F. Smith

abstract: This paper presents Classages, a novel interaction-centric object-oriented language. Classes and objects in Classages are fully encapsulated, with explicit interfaces for all interactions they might be involved in. The design of Classages touches upon a wide range of language design topics, including encapsulation, object relationship representation, and object confinement. An encoding of Java's OO model in Classages is provided, showing how standard paradigms are supported. A prototype Classages compiler is described.


title: Incrementalization across object abstraction

authors:
Yanhong A. Liu
Scott D. Stoller
Michael Gorbovitski
Tom Rothamel
Yanni Ellen Liu

abstract: Object abstraction supports the separation of what operations are provided by systems and components from how the operations are implemented, and is essential in enabling the construction of complex systems from components. Unfortunately, clear and modular implementations have poor performance when expensive query operations are repeated, while efficient implementations that incrementally maintain these query results are much more difficult to develop and to understand, because the code blows up significantly, and is no longer clear or modular.This paper describes a powerful and systematic method that first allows the "what" of each component to be specified in a clear and modular fashion and implemented straightforwardly in an object-oriented language; then analyzes the queries and updates, across object abstraction, in the straightforward implementation; and finally derives the sophisticated and efficient "how" of each component by incrementally maintaining the results of repeated expensive queries with respect to updates to their parameters. Our implementation and experimental results for example applications in query optimization, role-based access control, etc. demonstrate the effectiveness and benefit of the method.


title: Finding application errors and security flaws using PQL: a program query language

authors:
Michael C. Martin
V. Benjamin Livshits
Monica S. Lam

abstract: A number of effective error detection tools have been built in recent years to check if a program conforms to certain design rules. An important class of design rules deals with sequences of events asso-ciated with a set of related objects. This paper presents a language called PQL (Program Query Language) that allows programmers to express such questions easily in an application-specific context. A query looks like a code excerpt corresponding to the shortest amount of code that would violate a design rule. Details of the tar-get application's precise implementation are abstracted away. The programmer may also specify actions to perform when a match is found, such as recording relevant information or even correcting an erroneous execution on the fly.We have developed both static and dynamic techniques to find solutions to PQL queries. Our static analyzer finds all potential matches conservatively using a context-sensitive, flow-insensitive, inclusion-based pointer alias analysis. Static results are also use-ful in reducing the number of instrumentation points for dynamic analysis. Our dynamic analyzer instruments the source program to catch all violations precisely as the program runs and to optionally perform user-specified actions.We have implemented the techniques described in this paper and found 206 errors in 6 large real-world open-source Java applica-tions containing a total of nearly 60,000 classes. These errors are important security flaws, resource leaks, and violations of consis-tency invariants. The combination of static and dynamic analysis proves effective at addressing a wide range of debugging and pro-gram comprehension queries. We have found that dynamic analysis is especially suitable for preventing errors such as security vulner-abilities at runtime.


title: Deriving object typestates in the presence of inter-object references

authors:
Mangala Gowri Nanda
Christian Grothoff
Satish Chandra

abstract: We are interested in static analysis of Java classes with the goal of discovering the preconditions under which a certain program point within a method may be reached, taking into account the effects of previous method calls on an object of that class. The information pertinent to this computation is represented as the object's typestate, which is a finite set of relevant predicates that abstract the object's actual state. The execution of a method depends on an object's current typestate as well as other input parameters; the object may transition to a different typestate during the method's execution.It is common for objects to contain references to other ob-jects. In such cases, an object's behavior may depend on, in addition to its own state, the state of objects it has a refer-ence to. The main contribution of this paper is to discover relevant object typestates, as well as transitions between typestates, in the presence of inter-object references. Our analysis first performs a combined predicate discovery and predicate abstraction to derive "boolean" versions of Java classes given as input. It then uses abstract interpretation to compute the typestate transitions caused by method calls. A novel aspect of this work is that a set of Java classes is analyzed in isolation, without any client program being pro-vided. To do this, the analysis simulates all possible client's actions via a synthetic heap, all of whose interesting config-urations are explored by our analysis.The information we compute can be put to use in several ways. It can be used in checking whether a given client code erroneously uses a set of Java classes in a way that can throw an exception. It can also be used in creating test drivers for Java classes in order to exercise all relevant code paths in the corresponding methods.


title: Parametric polymorphism for software component architectures

authors:
Cosmin E. Oancea
Stephen M. Watt

abstract: Parametric polymorphism has become a common feature of mainstream programming languages, but software component architectures have lagged behind and do not support it. We examine the problem of providing parametric polymorphism with components combined from different programming languages. We have investigated how to resolve different binding times and parametrization semantics in a range of representative languages and have identified a common ground that can be suitably mapped to different language bindings. We present a generic component architecture extension that provides support for parameterized components and that can be easily adapted to work on top of various software component architectures in use today (e.g., corba, dcom, jni). We have implemented and tested this architecture on top of corba. We also present Generic Interface Definition Language (gidl), an extension to corba-idl supporting generic types and we describe language bindings for C++, Java and Aldor. We explain our implementation of gidl, consisting of a gidl to idl compiler and tools for generating linkage code under the language bindings. We demonstrate how this architecture can be used to access C++'s stl and Aldor's BasicMath libraries in a multi-language environment and discuss our mappings in the context of automatic library interface generation.


title: Scalable component abstractions

authors:
Martin Odersky
Matthias Zenger

abstract: We identify three programming language abstractions for the construction of re-usable components: abstract type members, explicit selftypes and symmetric mixin composition. Together, these abstractions enable us to transform an arbitrary assembly of static program parts with hard references between them into a system of re-usable components. The transformation maintains the structure of the original system. We demonstrate this approach in two case studies, a subject/observer framework and a compiler front-end.


title: ArchMatE: from architectural styles to object-oriented models through exploratory tool support

authors:
J. Andrés Díaz Pace
Marcelo R. Campo

abstract: Given the difficulties of conventional object technologies to deal with quality-attribute concerns, software architectures appear as an interesting approach to manage them better. A problem to make this approach feasible is the gap between architectural and object models. Succeeding in bridging these two worlds implies that those design decisions about quality attributes made at the architectural level should be reflected at the object level. Nonetheless, a given architecture usually admits multiple, different materializations. Furthermore, any materialization requires considerable design background and experience from the developer. In this paper, we describe a tool approach, called ArchMatE, to assist developers in the exploration of object-oriented solutions for grounding specific architectural models. An important aspect of the approach is that the materializations are accomplished by means of quality-oriented strategies, so that those concerns prescribed by the original architecture are mostly preserved.


title: Using dependency models to manage complex software architecture

authors:
Neeraj Sangal
Ev Jordan
Vineet Sinha
Daniel Jackson

abstract: An approach to managing the architecture of large software systems is presented. Dependencies are extracted from the code by a conventional static analysis, and shown in a tabular form known as the 'Dependency Structure Matrix' (DSM). A variety of algorithms are available to help organize the matrix in a form that reflects the architecture and highlights patterns and problematic dependencies. A hierarchical structure obtained in part by such algorithms, and in part by input from the user, then becomes the basis for 'design rules' that capture the architect's intent about which dependencies are acceptable. The design rules are applied repeatedly as the system evolves, to identify violations, and keep the code and its architecture in conformance with one another. The analysis has been implemented in a tool called LDM which has been applied in several commercial projects; in this paper, a case study application to Haystack, an information retrieval system, is described.


title: Runtime specialization with optimistic heap analysis

authors:
Ajeet Shankar
S. Subramanya Sastry
Rastislav Bodík
James E. Smith

abstract: We describe a highly practical program specializer for Java programs. The specializer is powerful, because it specializes optimistically, using (potentially transient) constants in the heap; it is precise, because it specializes using data structures that are only partially invariant; it is deployable, because it is hidden in a JIT compiler and does not require any user annotations or offline preprocessing; it is simple, because it uses existing JIT compiler ingredients; and it is fast, because it specializes programs in under 1s.These properties are the result of (1) a new algorithm for selecting specializable code fragments, based on a notion of influence; (2) a precise store profile for identifying constant heap locations; and (3) an efficient invalidation mechanism for monitoring optimistic assumptions about heap constants. Our implementation of the specializer in the Jikes RVM has low overhead, selects specialization points that would be chosen manually, and produces speedups ranging from a factor of 1.2 to 6.4, comparable with annotation-guided specializers.


title: Demand-driven points-to analysis for Java

authors:
Manu Sridharan
Denis Gopan
Lexin Shan
Rastislav Bodík

abstract: We present a points-to analysis technique suitable for environments with small time and memory budgets, such as just-in-time (JIT) compilers and interactive development environments (IDEs). Our technique is demand-driven, performing only the work necessary to answer each query (a request for a variable's points-to information) issued by a client. In cases where even the demand-driven approach exceeds the time budget for a query, we employ early termination, i.e., stopping the analysis prematurely and returning an over-approximated result to the client. Our technique improves on previous demand-driven points-to analysis algorithms [17, 33] by achieving much higher precision under small time budgets and early termination.We formulate Andersen's analysis [5] for Java as a CFL-reachability problem [33]. This formulation shows that Andersen's analysis for Java is a balanced-parentheses problem, an insight that enables our new techniques. We exploit the balanced parentheses structure to approximate Andersen's analysis by regularizing the CFL-reachability problem, yielding an asymptotically cheaper algorithm. We also show how to regain most of the precision lost in the regular approximation as needed through refinement. Our evaluation shows that our regularization and refinement approach achieves nearly the precision of field-sensitive Andersen's analysis in time budgets as small as 2ms per query. Our technique can yield speedups of up to 16x over computing an exhaustive Andersen's analysis for some clients, with little to no precision loss.


title: Javari: adding reference immutability to Java

authors:
Matthew S. Tschantz
Michael D. Ernst

abstract: This paper describes a type system that is capable of expressing and enforcing immutability constraints. The specific constraint expressed is that the abstract state of the object to which an immutable reference refers cannot be modified using that reference. The abstract state is (part of) the transitively reachable state: that is, the state of the object and all state reachable from it by following references. The type system permits explicitly excluding fields from the abstract state of an object. For a statically type-safe language, the type system guarantees reference immutability. If the language is extended with immutability downcasts, then run-time checks enforce the reference immutability constraints.This research builds upon previous research in language support for reference immutability. Improvements that are new in this paper include distinguishing the notions of assignability and mutability; integration with Java 5's generic types and with multi-dimensional arrays; a mutability polymorphism approach to avoiding code duplication; type-safe support for reflection and serialization; and formal type rules and type soundness proof for a core calculus. Furthermore, it retains the valuable features of the previous dialect, including usability by humans (as evidenced by experience with 160,000 lines of Javari code) and interoperability with Java and existing JVMs.


title: A simple model of agile software processes - or - extreme programming annealed

abstract: Article Share on A simple model of agile software processes -- or -- extreme programming annealed Author: Glenn Vanderburg Plano, TX Plano, TXView Profile Authors Info & Claims OOPSLA '05: Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applicationsOctober 2005Pages 539–545https://doi.org/10.1145/1094811.1094854Published:12 October 2005Publication History 6citation3,363DownloadsMetricsTotal Citations6Total Downloads3,363Last 12 Months12Last 6 weeks1 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 SiteGet Access


title: Safe futures for Java

authors:
Adam Welc
Suresh Jagannathan
Antony L. Hosking

abstract: A future is a simple and elegant abstraction that allows concurrency to be expressed often through a relatively small rewrite of a sequential program. In the absence of side-effects, futures serve as benign annotations that mark potentially concurrent regions of code. Unfortunately, when computation relies heavily on mutation as is the case in Java, its meaning is less clear, and much of its intended simplicity lost.This paper explores the definition and implementation of safe futures for Java. One can think of safe futures as truly transparent annotations on method calls, which designate opportunities for concurrency. Serial programs can be made concurrent simply by replacing standard method calls with future invocations. Most significantly, even though some parts of the program are executed concurrently and may indeed operate on shared data, the semblance of serial execution is nonetheless preserved. Thus, program reasoning is simplified since data dependencies present in a sequential program are not violated in a version augmented with safe futures.Besides presenting a programming model and API for safe futures, we formalize the safety conditions that must be satisfied to ensure equivalence between a sequential Java program and its future-annotated counterpart. A detailed implementation study is also provided. Our implementation exploits techniques such as object versioning and task revocation to guarantee necessary safety conditions. We also present an extensive experimental evaluation of our implementation to quantify overheads and limitations. Our experiments indicate that for programs with modest mutation rates on shared data, applications can use futures to profitably exploit parallelism, without sacrificing safety.


title: Modeling architectural patterns using architectural primitives

authors:
Uwe Zdun
Paris Avgeriou

abstract: Architectural patterns are a key point in architectural documentation. Regrettably, there is poor support for modeling architectural patterns, because the pattern elements are not directly matched by elements in modeling languages, and, at the same time, patterns support an inherent variability that is hard to model using a single modeling solution. This paper proposes tackling this problem by finding and representing architectural primitives, as the participants in the solutions that patterns convey. In particular, we examine a number of architectural patterns to discover those primitive abstractions that are common among the patterns, and at the same time demonstrate a degree of variability in each pattern. These abstractions belong in the components and connectors architectural view, though more abstractions can be found in other views. We have selected UML 2 as the language for representing these primitive abstractions as extensions of the standard UML elements. The added value of this approach is twofold: it proposes a generic and extensible approach for modeling architectural patterns by means of architectural primitives; it demonstrates an initial set of primitives that participate in several well-known architectural patterns.


title: A framework for implementing pluggable type systems

authors:
Chris Andreae
James Noble
Shane Markstrum
Todd D. Millstein

abstract: Pluggable types have been proposed to support multiple type systems in the same programming language. We have designed and implemented JavaCOP, a program constraint system for implementing practical pluggable type systems for Java. JavaCOP enforces user-defined typing constraints written in a declarative and expressive rule language. We have validated our design by (re)implementing a range of type systems and program checkers. By using a program constraint system to implement pluggable types, programmers are able to check that their programs will operate correctly in restricted environments, adhere to strict programming rules, avoid null pointer errors or scoped memory exceptions, and meet style guidelines, while programming language researchers can easily experiment with novel type systems.


title: Understanding the shape of Java software

authors:
Gareth Baxter
Marcus R. Frean
James Noble
Mark Rickerby
Hayden Smith
Matt Visser
Hayden Melton
Ewan D. Tempero

abstract: Large amounts of Java software have been written since the language's escape into unsuspecting software ecology more than ten years ago. Surprisingly little is known about the structure of Java programs in the wild: about the way methods are grouped into classes and then into packages, the way packages relate to each other, or the way inheritance and composition are used to put these programs together. We present the results of the first in-depth study of the structure of Java programs. We have collected a number of Java programs and measured their key structural attributes. We have found evidence that some relationships follow power-laws, while others do not. We have also observed variations that seem related to some characteristic of the application itself. This study provides important information for researchers who can investigate how and why the structural relationships we find may have originated, what they portend, and how they can be managed.


title: The DaCapo benchmarks: java benchmarking development and analysis

authors:
Stephen M. Blackburn
Robin Garner
Chris Hoffmann
Asjad M. Khan
Kathryn S. McKinley
Rotem Bentzur
Amer Diwan
Daniel Feinberg
Daniel Frampton
Samuel Z. Guyer
Martin Hirzel
Antony L. Hosking
Maria Jump
Han Bok Lee
J. Eliot B. Moss
Aashish Phansalkar
Darko Stefanovic
Thomas VanDrunen
Daniel von Dincklage
Ben Wiedermann

abstract: Since benchmarks drive computer science research and industry product development, which ones we use and how we evaluate them are key questions for the community. Despite complex runtime tradeoffs due to dynamic compilation and garbage collection required for Java programs, many evaluations still use methodologies developed for C, C++, and Fortran. SPEC, the dominant purveyor of benchmarks, compounded this problem by institutionalizing these methodologies for their Java benchmark suite. This paper recommends benchmarking selection and evaluation methodologies, and introduces the DaCapo benchmarks, a set of open source, client-side Java benchmarks. We demonstrate that the complex interactions of (1) architecture, (2) compiler, (3) virtual machine, (4) memory management, and (5) application require more extensive evaluation than C, C++, and Fortran which stress (4) much less, and do not require (3). We use and introduce new value, time-series, and statistical metrics for static and dynamic properties such as code complexity, code size, heap composition, and pointer mutations. No benchmark suite is definitive, but these metrics show that DaCapo improves over SPEC Java in a variety of ways, including more complex code, richer object behaviors, and more demanding memory system requirements. This paper takes a step towards improving methodologies for choosing and evaluating benchmarks to foster innovation in system design and implementation for Java and other managed languages.

awards: Most Influential OOPSLA Paper (awarded 2016)


title: Adapting virtual machine techniques for seamless aspect support

authors:
Christoph Bockisch
Matthew Arnold
Tom Dinkelaker
Mira Mezini

abstract: Current approaches to compiling aspect-oriented programs are in-efficient. This inefficiency has negative effects on the productiv-ity of the development process and is especially prohibitive for dynamic aspect deployment. In this work, we present how well-known virtual machine techniques can be used with only slight modifications to support fast aspect deployment while retaining runtime performance. Our implementation accelerates dynamic as-pect deployment by several orders of magnitude relative to main-stream aspect-oriented environments. We also provide a detailed comparison of alternative implementations of execution environ-ments with support for dynamic aspect deployment.


title: Efficient control flow quantification

authors:
Christoph Bockisch
Sebastian Kanthak
Michael Haupt
Matthew Arnold
Mira Mezini

abstract: Aspect-oriented programming (AOP) is increasingly gaining in popularity. However, the focus of aspect-oriented language research has been mostly on language design issues; efficient implementation techniques have been less popular. As a result, the performance of certain AOP constructs is still poor. This is in particular true for constructs that rely on dynamic properties of the execution (e.g., the cflow construct).In this paper, we present efficient implementation techniques for cflow that exploit direct access to internal structures of the virtual machine running an application, such as the call stack, as well as the integration of these techniques into the just-in-time compiler code generation process.Our results show that AOP has the potential to make programs that need to define control flow-dependent behavior not only more modular but also more efficient. By making means for control flow-dependent behavior part of the language, AOP opens the possibility of applying sophisticated compiler optimizations that are out of reach for application programmers.


title: Declarative, formal, and extensible syntax definition for aspectJ

authors:
Martin Bravenboer
Éric Tanter
Eelco Visser

abstract: A Case for Scannerless Generalized-LR Parsing Aspect-Oriented Programming (AOP) is attracting attention from both research and industry, as illustrated by the ever-growing popularity of AspectJ, the de facto standard AOP extension of Java. From a compiler construction perspective, AspectJ is interesting as it is a typical example of a compositional language, i.e. a language composed of a number of separate languages with different syntactical styles: in addition to plain Java, AspectJ includes a language for defining pointcuts and one for defining advices. Language composition represents a non-trivial challenge for conventional parsing techniques. First, combining several languages with different lexical syntax leads to considerable complexity in the lexical states to be processed. Second, as new language features for AOP are being explored, many research proposals are concerned with further extending the AspectJ language, resulting in a need for an extensible syntax definition. This paper shows how scannerless parsing elegantly addresses the issues encountered by conventional techniques when parsing AspectJ. We present the design of a modular, extensible, and formal definition of the lexical and context-free aspects of the AspectJ syntax in the Syntax Definition Formalism SDF, which is implemented by a scannerless, generalized-LR parser (SGLR). We introduce grammar mixins as a novel application of SDF’s modularity features, which allows the declarative definition of different keyword policies and combination of extensions. We illustrate the modular extensibility of our definition with syntax extensions taken from current research on aspect languages. Finally, benchmarks show the reasonable performance of scannerless generalized-LR parsing for this grammar.


title: Method-specific dynamic compilation using logistic regression

authors:
John Cavazos
Michael F. P. O'Boyle

abstract: Determining the best set of optimizations to apply to a program has been a long standing problem for compiler writers. To reduce the complexity of this task, existing approaches typically apply the same set of optimizations to all procedures within a program, without regard to their particular structure. This paper develops a new method-specific approach that automatically selects the best optimizations on a per method basis within a dynamic compiler. Our approach uses the machine learning technique of logistic regression to automatically derive a predictive model that determines which optimizations to apply based on the features of a method. This technique is implemented in the Jikes RVM Java JIT compiler. Using this approach we reduce the average total execution time of the SPECjvm98 benchmarks by 29%. When the same heuristic is applied to the DaCapo+ benchmark suite, we obtain an average 33% reduction over the default level O2 setting.


title: A flow-based approach for variant parametric types

authors:
Wei-Ngan Chin
Florin Craciun
Siau-Cheng Khoo
Corneliu Popeea


title: JTL: the Java tools language

authors:
Tal Cohen
Joseph Gil
Itay Maman

abstract: We present an overview of JTL (the Java Tools Language, pronounced "Gee-tel"), a novel language for querying JAVA [8] programs. JTL was designed to serve the development of source code software tools for JAVA, and as a small language which to aid programming language extensions to JAVA. Applications include definition of pointcuts for aspect-oriented programming, fixing type constraints for generic programming, specification of encapsulation policies, definition of micro-patterns, etc. We argue that the JTL expression of each of these is systematic, concise, intuitive and general.JTL relies on a simply-typed relational database for program representation, rather than an abstract syntax tree. The underlying semantics of the language is restricted to queries formulated in First Order Predicate Logic augmented with transitive closure (FOPL).Special effort was taken to ensure terse, yet readable expression of logical conditions. The JTL pattern public abstract class, for example, matches all abstract classes which are publicly accessible, while class (public clone();) matches all classes in which method clone is public. To this end, JTL relies on a DATALOG-like syntax and semantics, enriched with quantifiers and pattern matching which all but entirely eliminate the need for recursive calls.JTL's query analyzer gives special attention to the fragility of the "closed world assumption" in examining JAVA software, and determines whether a query relies on such an assumption.The performance of the JTL interpreter is comparable to that of JQuery after it generated its database cache, and at least an order of magnitude faster when the cache has to be rebuilt.


title: Efficient software model checking of data structure properties

authors:
Paul T. Darga
Chandrasekhar Boyapati

abstract: This paper presents novel language and analysis techniques that significantly speed up software model checking of data structure properties. Consider checking a red-black tree implementation. Traditional software model checkers systematically generate all red-black tree states (within some given bounds) and check every red-black tree operation (such as insert, delete, or lookup) on every red-black tree state. Our key idea is as follows. As our checker checks a red-black tree operation o on a red-black tree state s, it uses program analysis techniques to identify other red-black tree states s'1, s'2, ..., s'k on which the operation o behaves similarly. Our analyses guarantee that if o executes correctly on s, then o will execute correctly on every s'i. Our checker therefore does not need to check o on any s'i once it checks o on s. It thus safely prunes those state transitions from its search space, while still achieving complete test coverage within the bounded domain. Our preliminary results show orders of magnitude improvement over previous approaches. We believe our techniques can make model checking significantly faster, and thus enable checking of much larger programs and complex program properties than currently possible.


title: Uniform proxies for Java

abstract: The proxy abstraction has a longlasting tradition in object settings. From design pattern to inherent language support, from remote method invocations to simple forms of behavioral reflection - incarnations as well as applications of proxies are innumerable.Since version 1.3, Java supports the concept of dynamic proxy. Such an object conforms to a set of types specified by the program and can be used wherever an expression of any of these types is expected, yet reifies invocations performed on it. Dynamic proxies have been applied to implement paradigms as diverse as behavioral reflection, structural conformance, or multi-methods. Alas, these proxies are only available "for interfaces". The case of creating dynamic proxies for a set of types including a class type has not been considered, meaning that it is currently not possible to create a dynamic proxy mimicking an instance of a given class. This weakness strongly limits any application of dynamic proxies.In this paper we unfold the current support for dynamic proxies in Java, assessing it in the light of a set of generic criteria for proxy implementations. We present an approach to supporting dynamic proxies "for classes" in Java, consisting in transformations performed on classes at load-time, including a generic scheme for enforcing encapsulation upon field accesses. These transformations seemlessly extend the scope of the current support for dynamic proxies. We discuss the precise benefits and costs of our extension in terms of the criteria introduced, and illustrate the usefulness of uniformly available proxies by implementing future method invocations both safely and transparently.


title: Design fragments make using frameworks easier

authors:
George Fairbanks
David Garlan
William L. Scherlis

abstract: Object oriented frameworks impose additional burdens on programmers that libraries did not, such as requiring the programmer to understand the method callback sequence, respecting behavior constraints within these methods, and devising solutions within a constrained solution space. To overcome these burdens, we express the repeated patterns of engagement with the framework as a design fragment. We analyzed the 20 demo applets provided by Sun and created a representative catalog of design fragments of conventional best practice. By evaluating 36 applets pulled from the internet we show that these design fragments are common, many applets copied the structure of the Sun demos, and that creation of a catalog of design fragments is practical. Design fragments give programmers immediate benefit through tool-based conformance assurance and long-term benefit through expression of design intent.


title: Conscientious software

authors:
Richard P. Gabriel
Ron Goldman

abstract: Software needs to grow up and become responsible for itself and its own future by participating in its own installation and customization, maintaining its own health, and adapting itself to new circumstances, new users, and new uses. To create such software will require us to change some of our underlying assumptions about how we write programs. A promising approach seems to be to separate software that does the work (allopoietic)from software that keeps the system alive (autopoietic).