Skip to main content

2008 | Buch

ECOOP 2008 – Object-Oriented Programming

22nd European Conference Paphos, Cyprus, July 7-11, 2008 Proceedings

insite
SUCHEN

Über dieses Buch

It is a pleasure to present the proceedings of the 22nd European Conference on Object-Oriented Programming (ECOOP 2008) held in Paphos, Cyprus. The conference continues to serve a broad object-oriented community with a tech- cal program spanning theory and practice and a healthy mix of industrial and academic participants. This year a strong workshop and tutorial program c- plementedthemaintechnicaltrack.Wehad13workshopsand8tutorials,aswell as the co-located Dynamic Language Symposium (DLS). Finally, the program was rounded out with a keynote by Rachid Guerraoui and a banquet speech by James Noble. As in previous years, two Dahl-Nygaard awards were selected by AITO, and for the ?rst time, the ECOOP Program Committee gave a best paper award. Theproceedingsinclude27papersselectedfrom138submissions.Thepapers werereviewed in a single-blind process with three to ?ve reviews per paper. P- liminaryversionsofthereviewsweremadeavailabletotheauthorsaweekbefore the PC meeting to allow for short (500 words or less) author responses. The - sponses were discussed at the PC meeting and were instrumental in reaching decisions. The PC discussions followed Oscar Nierstrasz’Champion pattern. PC papers had ?ve reviews and were held at a higher standard.

Inhaltsverzeichnis

Frontmatter

Keynote

The Return of Transactions
Abstract
Major chip manufacturers have recently shifted their focus from speeding individual processors to multiplying them on the same chip and shipping multicore architectures. Boosting the performance of programs will thus necessarily go through parallelizing them. This is not trivial and the average programmer will badly need abstractions for synchronizing concurrent accesses to shared memory objects. The transaction abstraction looks promising for this purpose and there is a lot of interest around its use in modern parallel programming. This talk will investigate whether the ”return” of the old transaction idea brings any interesting research question, especially for the programming language community.
Rachid Guerraoui

Session I

A Model for Java with Wildcards
Abstract
Wildcards are a complex and subtle part of the Java type system, present since version 5.0. Although there have been various formalisations and partial type soundness results concerning wildcards, to the best of our knowledge, no system that includes all the key aspects of Java wildcards has been proven type sound. This paper establishes that Java wildcards are type sound. We describe a new formal model based on explicit existential types whose pack and unpack operations are handled implicitly, and prove it type sound. Moreover, we specify a translation from a subset of Java to our formal model, and discuss how several interesting aspects of the Java type system are handled.
Nicholas Cameron, Sophia Drossopoulou, Erik Ernst
On Validity of Program Transformations in the Java Memory Model
Abstract
We analyse the validity of several common program transformations in multi-threaded Java, as defined by the Memory Model section of the Java Language Specification. The main design goal of the Java Memory Model (JMM) was to allow as many optimisations as possible. However, we find that commonly used optimisations, such as common subexpression elimination, can introduce new behaviours and so are invalid for Java. In this paper, we describe several kinds of transformations and explain the problems with a number of counterexamples. More positively, we also examine some valid transformations, and prove their validity. Our study contributes to the understanding of the JMM, and has the practical impact of revealing some cases where the Sun Hotspot JVM does not comply with the Java Memory Model.
Jaroslav Ševčík, David Aspinall
Safe Cross-Language Inheritance
Abstract
Inheritance is a standard means for reuse and for interfacing with external libraries. In a multi-language software product, extending a class written in a statically-typed language with a dynamically-typed class can require a significant number of manual indirections and other error-prone complications. Building on our previous interoperability work, we introduce a technique that allows safe, easy inheritance across languages. We demonstrate our technique for cross-language inheritance with a statically-typed object calculus and a dynamically-typed object calculus, where a statically-typed class can extend a dynamically-typed one and vice versa. We provide a proof sketch of soundness, as well as a guarantee that dynamic type errors do not arise due to statically-typed expressions.
Kathryn E. Gray

Session II

Liquid Metal: Object-Oriented Programming Across the Hardware/Software Boundary
Abstract
The paradigm shift in processor design from monolithic processors to multicore has renewed interest in programming models that facilitate parallelism. While multicores are here today, the future is likely to witness architectures that use reconfigurable fabrics (FPGAs) as coprocessors. FPGAs provide an unmatched ability to tailor their circuitry per application, leading to better performance at lower power. Unfortunately, the skills required to program FPGAs are beyond the expertise of skilled software programmers. This paper shows how to bridge the gap between programming software vs. hardware. We introduce Lime, a new Object-Oriented language that can be compiled for the JVM or into a synthesizable hardware description language. Lime extends Java with features that provide a way to carry OO concepts into efficient hardware. We detail an end-to-end system from the language down to hardware synthesis and demonstrate a Lime program running on both a conventional processor and in an FPGA.
Shan Shan Huang, Amir Hormati, David F. Bacon, Rodric Rabbah
Kilim: Isolation-Typed Actors for Java
(A Million Actors, Safe Zero-Copy Communication)
Abstract
This paper describes Kilim, a framework that employs a combination of techniques to help create robust, massively concurrent systems in mainstream languages such as Java: (i) ultra-lightweight, cooperatively-scheduled threads (actors), (ii) a message-passing framework (no shared memory, no locks) and (iii) isolation-aware messaging.
Isolation is achieved by controlling the shape and ownership of mutable messages – they must not have internal aliases and can only be owned by a single actor at a time. We demonstrate a static analysis built around isolation type qualifiers to enforce these constraints.
Kilim comfortably scales to handle hundreds of thousands of actors and messages on modest hardware. It is fast as well – task-switching is 1000x faster than Java threads and 60x faster than other lightweight tasking frameworks, and message-passing is 3x faster than Erlang (currently the gold standard for concurrency-oriented programming).
Sriram Srinivasan, Alan Mycroft
A Uniform Transactional Execution Environment for Java
Abstract
Transactional memory (TM) has recently emerged as an effective tool for extracting fine-grain parallelism from declarative critical sections. In order to make STM systems practical, significant effort has been made to integrate transactions into existing programming languages. Unfortunately, existing approaches fail to provide a simple implementation that permits lock-based and transaction-based abstractions to coexist seamlessly. Because of the fundamental semantic differences between locks and transactions, legacy applications or libraries written using locks can not be transparently used within atomic regions. To address these shortcomings, we implement a uniform transactional execution environment for Java programs in which transactions can be integrated with more traditional concurrency control constructs. Programmers can run arbitrary programs that utilize traditional mutual-exclusion-based programming techniques, execute new programs written with explicit transactional constructs, and freely combine abstractions that use both coding styles.
Lukasz Ziarek, Adam Welc, Ali-Reza Adl-Tabatabai, Vijay Menon, Tatiana Shpeisman, Suresh Jagannathan

Session III

Ptolemy: A Language with Quantified, Typed Events
Abstract
Implicit invocation (II) and aspect-oriented (AO) languages provide related but distinct mechanisms for separation of concerns. II languages have explicitly announced events that run registered observer methods. AO languages have implicitly announced events that run method-like but more powerful advice. A limitation of II languages is their inability to refer to a large set of events succinctly. They also lack the expressive power of AO advice. Limitations of AO languages include potentially fragile dependence on syntactic structure that may hurt maintainability, and limits on the available set of implicit events and the reflective contextual information available. Quantified, typed events, as implemented in our language Ptolemy, solve all these problems. This paper describes Ptolemy and explores its advantages relative to both II and AO languages.
Hridesh Rajan, Gary T. Leavens
Prototyping and Composing Aspect Languages
Using an Aspect Interpreter Framework
Abstract
Domain specific aspect languages (DSALs) are becoming more popular because they can be designed to represent recurring concerns in a way that is optimized for a specific domain. However, the design and implementation of even a limited domain-specific aspect language can be a tedious job. To address this, we propose a framework that offers a fast way to prototype implementations of domain specific aspect languages. A particular goal of the framework is to be general enough to support a wide range of aspect language concepts, such that existing language concepts can be easily used, and new language concepts can be quickly created.
We briefly introduce the framework and its underlying model, as well as the workflow used when implementing DSALs. Subsequently, we show mappings of several domain specific aspect languages to demonstrate the framework. Since in our approach the DSALs are mapped to a common model, the framework provides an integrating platform allowing us to compose programs that use aspects written in multiple DSALs. The framework also provides explicit mechanisms to specify composition of advices written in multiple DSALs.
Wilke Havinga, Lodewijk Bergmans, Mehmet Aksit
Assessing the Impact of Aspects on Exception Flows: An Exploratory Study
Abstract
Exception handling mechanisms are intended to support the development of robust software. However, the implementation of such mechanisms with aspect-oriented (AO) programming might lead to error-prone scenarios. As aspects extend or replace existing functionality at specific join points in the code execution, aspects’ behavior may bring new exceptions, which can flow through the program execution in unexpected ways. This paper presents a systematic study that assesses the error proneness of AOP mechanisms on exception flows of evolving programs. The analysis was based on the object-oriented and the aspect-oriented versions of three medium-sized systems from different application domains. Our findings show that exception handling code in AO systems is error-prone, since all versions analyzed presented an increase in the number of uncaught exceptions and exceptions caught by the wrong handler. The causes of such problems are characterized and presented as a catalogue of bug patterns.
Roberta Coelho, Awais Rashid, Alessandro Garcia, Fabiano Ferrari, Nélio Cacho, Uirá Kulesza, Arndt von Staa, Carlos Lucena

Session IV

UpgradeJ: Incremental Typechecking for Class Upgrades
Abstract
One of the problems facing developers is the constant evolution of components that are used to build applications. This evolution is typical of any multi-person or multi-site software project. How can we program in this environment? More precisely, how can language design address such evolution? In this paper we attack two significant issues that arise from constant component evolution: we propose language-level extensions that permit multiple, co-existing versions of classes and the ability to dynamically upgrade from one version of a class to another, whilst still maintaining type safety guarantees and requiring only lightweight extensions to the runtime infrastructure. We show how our extensions, whilst intuitive, provide a great deal of power by giving a number of examples. Given the subtlety of the problem, we formalize a core fragment of our language and prove a number of important safety properties.
Gavin Bierman, Matthew Parkinson, James Noble
Integrating Nominal and Structural Subtyping
Abstract
Nominal and structural subtyping each have their own strengths and weaknesses. Nominal subtyping allows programmers to explicitly express design intent, and, when types are associated with run time tags, enables run-time type tests and external method dispatch. On the other hand, structural subtyping is flexible and compositional, allowing unanticipated reuse. To date, nearly all object-oriented languages fully support one subtyping paradigm or the other.
In this paper, we describe a core calculus for a language that integrates the key aspects of nominal and structural subtyping in a unified framework. We have also merged the flexibility of structural subtyping with statically typechecked external methods, a novel combination. We prove type safety for this language and illustrate its practical utility through examples that are not easily expressed in other languages. Our work provides a clean foundation for the design of future languages that enjoy the benefits of both nominal and structural subtyping.
Donna Malayeri, Jonathan Aldrich
Flow Analysis of Code Customizations
Abstract
Inconsistency between metadata and code customizations is a major concern in modern, configurable enterprise systems. The increasing reliance on metadata, in the form of XML files, and code customizations, in the form of Java files, has led to a hybrid development platform. The expected consistency requirements between metadata and code should be checked but often are not, so current tools offer surprisingly poor development support. In this paper, we adapt classical data flow analyses to detect inconsistencies and provide better static guarantees. We provide a formalization of the consistency requirements and a set of adapted analyses for a concrete case study. Our work is implemented in a fast and efficient prototype in the form of an Eclipse plugin. We validate our work by testing this prototype on actual production code; preliminary results show that this approach is worthwhile. We found a significant number of previously undetected consistency errors and have received very positive feedback from the developer community in the case study.
Anders Hessellund, Peter Sestoft

Session V

Online Phase-Adaptive Data Layout Selection
Abstract
Good data layouts improve cache and TLB performance of object-oriented software, but unfortunately, selecting an optimal data layout a priori is NP-hard. This paper introduces layout auditing, a technique that selects the best among a set of layouts online (while the program is running). Layout auditing randomly applies different layouts over time and observes their performance. As it becomes confident about which layout performs best, it selects that layout with higher probability. But if a phase shift causes a different layout to perform better, layout auditing learns the new best layout. We implemented our technique in a product Java virtual machine, using copying generational garbage collection to produce different layouts, and tested it on 20 long-running benchmarks and 4 hardware platforms. Given any combination of benchmark and platform, layout auditing consistently performs close to the best layout for that combination, without requiring offline training.
Chengliang Zhang, Martin Hirzel
MTM2: Scalable Memory Management for Multi-tasking Managed Runtime Environments
Abstract
Multi-tasking, managed runtime environments (MREs) for modern type-safe, object-oriented programming languages enable isolated, concurrent execution of multiple applications within a single operating system process. Multi-tasking MREs can potentially extract high-performance on desktop and hand-held systems through aggressive sharing of classes and compiled code, and by exploiting high-level dynamic program information.
We investigate the performance of a state-of-the-art multi-taking MRE for concurrent program execution. We find that due to limited support for multi-tasking and performance isolation in the memory management subsystem, multi-tasking performs poorly compared to a production-quality, single-tasking MRE. We present MTM 2: a comprehensive memory management system for concurrent multi-tasking. MTM 2 facilitates performance isolation and efficient heap space usage through on-demand allocation of application-private regions. MTM 2 mitigates fragmentation using a novel hybrid garbage collector that combines mark-sweep with opportunistic copying. Our evaluation shows that MTM 2 improves overall performance, scalability, and footprint for concurrent workloads over state-of-the-art, multi- and single-tasking MREs.
Sunil Soman, Chandra Krintz, Laurent Daynès
Externalizing Java Server Concurrency with CAL
Abstract
One of the most important design decisions about a server program is regarding its concurrency mechanisms. However, good concurrency models for general-purpose server programs are increasingly difficult to conceive as the runtime conditions are hard to predict. In this work, we advocate that the concurrency code is to be decoupled from server programs. To enable such separation, we propose and evaluate CAL, — the Concurrency Aspect Library. CAL provides uniform concurrency programming abstractions and mediates the intrinsic differences among concurrency models. Through CAL, a server program is not tied to any particular concurrency model and framework. CAL can be configured without modifications to use concurrency frameworks of fundamentally different natures. The concurrency code based on CAL is simpler and looks closer to the design. Leveraging the customizability of CAL, we show that a commercial middleware server, refactored to use CAL, outperforms its original version by as much as 10 times.
Charles Zhang, Hans-Arno Jacobsen

Session VI

Regional Logic for Local Reasoning about Global Invariants
Abstract
Shared mutable objects pose grave challenges in reasoning, especially for data abstraction and modularity. This paper presents a novel logic for error-avoiding partial correctness of programs featuring shared mutable objects. Using a first order assertion language, the logic provides heap-local reasoning about mutation and separation, via ghost fields and variables of type ‘region’ (finite sets of object references). A new form of modifies clause specifies write, read, and allocation effects using region expressions; this supports effect masking and a frame rule that allows a command to read state on which the framed predicate depends. Soundness is proved using a standard program semantics. The logic facilitates heap-local reasoning about object invariants: disciplines such as ownership are expressible but not hard-wired in the logic.
Anindya Banerjee, David A. Naumann, Stan Rosenberg
A Unified Framework for Verification Techniques for Object Invariants
Abstract
Object invariants define the consistency of objects. They have subtle semantics because of call-backs, multi-object invariants and subclassing. Several visible-state verification techniques for object invariants have been proposed. It is difficult to compare these techniques and ascertain their soundness because of differences in restrictions on programs and invariants, in the use of advanced type systems (e.g. ownership types), in the meaning of invariants, and in proof obligations.
We develop a unified framework for such techniques. We distil seven parameters that characterise a verification technique, and identify sufficient conditions on these parameters which guarantee soundness. We instantiate our framework with three verification techniques from the literature, and use it to assess soundness and compare expressiveness.
S. Drossopoulou, A. Francalanza, P. Müller, A. J. Summers
Extensible Universes for Object-Oriented Data Models
Abstract
We present a datatype package that enables the shallow embedding technique to object-oriented specification and programming languages. This datatype package incrementally compiles an object-oriented data model to a theory containing object-universes, constructors, accessors functions, coercions between dynamic and static types, characteristic sets, their relations reflecting inheritance, and the necessary class invariants. The package is conservative, i.e., all properties are derived entirely from axiomatic definitions. As an application, we use the package for an object-oriented core-language called imp++, for which correctness of a Hoare-Logic with respect to an operational semantics is proven.
Achim D. Brucker, Burkhart Wolff

Session VII

Programming with Live Distributed Objects
Abstract
A component revolution is underway, bringing developers improved productivity and opportunities for code reuse. However, whereas existing tools work well for builders of desktop applications and client-server structured systems, support for other styles of distributed computing has lagged. In this paper, we propose a new programming paradigm and a platform, in which instances of distributed protocols are modeled as “live distributed objects”. Live objects can represent both protocols and higher-level components. They look and feel much like ordinary objects, but can maintain shared state and synchronization across multiple machines within a network. Live objects can be composed in a type-safe manner to build sophisticated distributed applications using a simple, intuitive drag and drop interface, very often without writing any code or having to understand the intricacies of the underlying distributed algorithms.
Krzysztof Ostrowski, Ken Birman, Danny Dolev, Jong Hoon Ahnn
Bristlecone: A Language for Robust Software Systems
Abstract
We present Bristlecone, a programming language for robust software systems. Bristlecone applications have two components: a high-level organization description that specifies how the application’s conceptual operations interact, and a low-level operational description that specifies the sequence of instructions that comprise an individual conceptual operation. Bristlecone uses the high-level organization description to recover the software system from an error to a consistent state and to reason how to safely continue the software system’s execution after the error.
We have implemented a compiler and runtime for Bristlecone.We have evaluated this implementation on three benchmark applications: a web crawler, a web server, and a multi-room chat server. We developed both a Bristlecone version and a Java version of each benchmark application. We used injected failures to evaluate the robustness of each version of the application. We found that the Bristlecone versions of the benchmark applications more successfully survived the injected failures.
Brian Demsky, Alokika Dash
Session-Based Distributed Programming in Java
Abstract
This paper demonstrates the impact of integrating session types and object-oriented programming, through their implementation in Java. Session types provide high-level abstraction for structuring a series of interactions in a concise syntax, and ensure type-safe communications between distributed peers. We present the first full implementation of a language and runtime for session-based distributed programming featuring asynchronous message passing, delegation, and session subtyping and interleaving, combined with class downloading and failure handling. The compilation-runtime framework of our language effectively maps session abstraction onto underlying transports and guarantees communication safety through static and dynamic session type checking. We have implemented two alternative mechanisms for performing distributed session delegation and prove their correctness. Benchmark results show session abstraction can be realised with low runtime overhead.
Raymond Hu, Nobuko Yoshida, Kohei Honda

Session VIII

ReCrash: Making Software Failures Reproducible by Preserving Object States
Abstract
It is very hard to fix a software failure without being able to reproduce it. However, reproducing a failure is often difficult and time-consuming. This paper proposes a novel technique, ReCrash, that generates multiple unit tests that reproduce a given program failure. During every execution of the target program, ReCrash stores partial copies of method arguments in memory. If the program fails (e.g., crashes), ReCrash uses the saved information to create unit tests reproducing the failure.
We present ReCrashJ, an implementation of ReCrash for Java. ReCrashJ reproduced real crashes from Javac, SVNKit, Eclipsec, and BST. ReCrashJ is efficient, incurring 13%–64% performance overhead. If this overhead is unacceptable, then ReCrashJ has another mode that has negligible overhead until a crash occurs and 0%–1.7% overhead until the crash occurs for a second time, at which point the test cases are generated.
Shay Artzi, Sunghun Kim, Michael D. Ernst
An Extensible State Machine Pattern for Interactive Applications
Abstract
The state design pattern is the standard object-oriented programming idiom for implementing the state machine logic of interactive applications. While this pattern provides a number of advantages, it does not easily support the creation of extended state machines in subclasses. We describe the extensible state design pattern, which augments the traditional state pattern with a few additional constraints that allow subclasses to easily add both new states and new events. Further, we observe that delimited continuations, a well-known construct from functional programming languages, supports state refinement in subclasses as well as the modular expression of control flow in the presence of interaction. We illustrate our pattern in the context of Java, leveraging its generics to obviate the need for dynamic typecasts and employing a small library that implements delimited continuations. We have used our pattern to simplify and modularize a widely used application written by others.
Brian Chin, Todd Millstein
Practical Object-Oriented Back-in-Time Debugging
Abstract
Back-in-time debuggers are extremely useful tools for identifying the causes of bugs. Unfortunately the “omniscient” approaches that try to remember all previous states are impractical because they consume too much space or they are far too slow. Several approaches rely on heuristics to limit these penalties, but they ultimately end up throwing out too much relevant information. In this paper we propose a practical approach that attempts to keep track of only the relevant data. In contrast to other approaches, we keep object history information together with the regular objects in the application memory. Although seemingly counter-intuitive, this approach has the effect that data not reachable from current application objects (and hence, no longer relevant) is garbage collected. We describe the technical details of our approach, and we present benchmarks that demonstrate that memory consumption stays within practical bounds. Furthermore, the performance penalty is significantly less than with other approaches.
Adrian Lienhard, Tudor Gîrba, Oscar Nierstrasz

Session IX

Inference of Reference Immutability
Abstract
Javari is an extension of Java that supports reference immutability constraints. Programmers write readonly type qualifiers and other constraints, and the Javari typechecker detects mutation errors (incorrect side effects) or verifies their absence. While case studies have demonstrated the practicality and value of Javari, a barrier to usability remains. A Javari program will not typecheck unless all the references in the APIs of libraries it uses are annotated with Javari type qualifiers. Manually converting existing Java libraries to Javari is tedious and error-prone.
We present an algorithm for inferring reference immutability in Javari. The flow-insensitive and context-sensitive algorithm is sound and produces a set of qualifiers that typecheck in Javari. The algorithm is precise in that it infers the most readonly qualifiers possible; adding any additional readonly qualifiers will cause the program to not typecheck. We have implemented the algorithm in a tool, Javarifier, that infers the Javari type qualifiers over a set of class files.
Javarifier automatically converts Java libraries to Javari. Additionally, Javarifier eases the task of converting legacy programs to Javari by inferring the mutability of every reference in a program. In case studies, Javarifier correctly inferred mutability over Java programs of up to 110 KLOC.
Jaime Quinonez, Matthew S. Tschantz, Michael D. Ernst
Computing Stack Maps with Interfaces
Abstract
Lightweight bytecode verification uses stack maps to annotate Java bytecode programs with type information in order to reduce the verification to type checking. This paper describes an improved bytecode analyser together with algorithms for optimizing the stack maps generated. The analyser is simplified in its treatment of base values (keeping only the necessary information to ensure memory safety) and enriched in its representation of interface types, using the Dedekind-MacNeille completion technique. The computed interface information allows to remove the dynamic checks at interface method invocations. We prove the memory safety property guaranteed by the bytecode verifier using an operational semantics whose distinguishing feature is the use of untagged 32-bit values. For bytecode typable without sets of types we show how to prune the fix-point to obtain a stack map that can be checked without computing with sets of interfaces i.e., lightweight verification is not made more complex or costly. Experiments on three substantial test suites show that stack maps can be computed and correctly pruned by an optimized (but incomplete) pruning algorithm.
Frédéric Besson, Thomas Jensen, Tiphaine Turpin
How Do Java Programs Use Inheritance? An Empirical Study of Inheritance in Java Software
Abstract
Inheritance is a crucial part of object-oriented programming, but its use in practice, and the resulting large-scale inheritance structures in programs, remain poorly understood. Previous studies of inheritance have been relatively small and have generally not considered issues such as Java’s distinction between classes and interfaces, nor have they considered the use of external libraries.
In this paper we present the first substantial empirical study of the large-scale use of inheritance in a contemporary OO programming language. We present a suite of structured metrics for quantifying inheritance in Java programs. We present the results of performing a corpus analysis using those metrics to over 90 applications consisting of over 100,000 separate classes and interfaces. Our analysis finds higher use of inheritance than anticipated, variation in the use of inheritance between interfaces and classes, and differences between inheritance within application types compared with inheritance from external libraries.
Ewan Tempero, James Noble, Hayden Melton
Backmatter
Metadaten
Titel
ECOOP 2008 – Object-Oriented Programming
herausgegeben von
Jan Vitek
Copyright-Jahr
2008
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-70592-5
Print ISBN
978-3-540-70591-8
DOI
https://doi.org/10.1007/978-3-540-70592-5