Papers and Other Publications

mostly harmless

Documents are posted here to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. These works may not be reposted without the explicit permission of the copyright holder.

The definitive versions of all published papers appearing here are those that actually appeared in print. In some cases, the versions presented here may differ in minor ways. When citing any published papers provided here, please reference the published versions.

(This statement of fair use is derived from one posted by The Laboratory for Empirically-based Software Quality Research and Development at the University of Nebraska, Lincoln.)

SPLICE: Self-paced learning in an inverted classroom environment

Matt Boutell and Curtis Clifton 2011. Poster presented at SIGCSE ‘11: the 42st ACM technical symposium on computer science education.

Full text: BoutellClifton11aa.pdf

Abstract: Learning to program is hard for many students. Practice with an expert coach is key to overcoming this challenge. However, finding time for this is an issue because presenting concepts, showing examples, and modeling problem solving reduce the time available for mentored practice. Pace is also an issue because some students arrive with confidence and prior experience and are thus bored, while other students labor and become overwhelmed.

To address these problems in CS1, we created on-line videos for a C programming unit to present concepts, show examples, and model problem solving. As a result, our students spend every class session entirely in active learning activities with expert coaching, receive more individual attention, and set their own pace.

Early and often: Bringing more parallelism into undergraduate Computer Science curricula

Richard Brown, Elizabeth Shoop, Joel Adams, Curtis Clifton, Mark Gardner, and Michael Haupt 2010. Position paper for the Second Workshop on Curricula in Concurrency and Parallelism.

Full text: BrownShoopAdams10ba.pdf

Abstract: In view of recent industry shifts towards both multi-core processors and applications of distributed computing through techniques such as map-reduce, the question naturally arises: how can Computer Science (CS) undergraduate programs respond with curricular changes to prepare their students for the future of computation, in which parallelism and concurrency will be a necessity, not an option? Up to now, the innovations in hardware parallelism that have driven advances in processor design have been transparent to programmers and programming environments. This is no longer the case. As hardware designers turn to ever increasing numbers of cores, software designers must explicitly turn to parallelism (and concurrency – for convenience, we will use the term parallelism to include both) to take advantage of these cores. If not, the steady advances in performance that software designers formerly received for free will cease.

Strategies for Preparing Computer Science Students for the Multicore World

R. Brown and E. Shoop and J. Adams and C. Clifton and M. Gardner and M. Haupt and P. Hinsbeeck. In 2010 ITiCSE Working Group Reports, 2010. ACM Press.

Full text: BrownShoopAdams10aa.pdf

Abstract: Multicore computers have become standard, and the number of cores per computer is rising rapidly. How does the new demand for understanding of parallel computing impact computer science education? In this paper, we examine several aspects of this question: (i) What parallelism body of knowledge do today’s students need to learn? (ii) How might these concepts and practices be incorporated into the computer science curriculum? (iii) What resources will support computer science educators, including non-specialists, to teach parallel computing? (iv) What systemic obstacles impede this change, and how might they be overcome? We address these concerns as an initial framework for responding to the urgent challenge of injecting parallelism into computer science curricula.

PyTetris

Delvin Defoe, Matt Boutell, and Curtis Clifton 2010. To appear in CCSC:Midwest 2010 Nifty Tools and Assignments.

Abstract: Students work in teams of two or three to implement the Tetris video game. We provide a series of unit tests to help students write correct logic, and give them a basic GUI. They write the logic for the piece movements and enhance their game by adding advanced features.

CFG Experimenter: An Animated Parser-Generator Programming Project for Learning Compiler Algorithms

Curtis Clifton and Brian T. Kelley 2010. Poster presented at SIGCSE ‘10: the 41st ACM technical symposium on computer science education.

Full text: CliftonKelley10ab.pdf

Abstract: Many students learn best from concrete examples. Generating concrete examples of the algorithms used in ll(1) and lr(1) parsing can be tedious for instructors and students. CFG Experimenter is a tool for generating such examples, but beyond that, it is also scaffolding for a programming project where students learn the algorithms by implementing them. CFG Experimenter includes algorithms for calculating first and follow sets, canonical collections of lr(1) items, action and goto tables, and determining whether a context-free grammar is ll(1) or lr(1) parseable. CFG Experimenter can also animate ll(1) and lr(1) parsing, and allows students to “scrub through” the animation to check their understanding. Whether used as a programming project for students, or simply as a tool for instructors and students to generate and check examples, CFG Experimenter helps students better understand the algorithms used by most common parser-generators.

JML Reference Manual

Gary T. Leavens, Erik Poll, Curtis Clifton, Yoonsik Cheon, Clyde Ruby, David R. Cok, Peter Muller, Joseph Kiniry, Patrice Chalin, and Daniel M. Zimmerman 2009. Department of Electrical Engineering and Computer Science, University of Central Florida.

FOAL 2009 Proceedings: Foundations of Aspect-Oriented Languages Workshop at AOSD 2009

C. Clifton and S. Katz and G. T. Leavens and M. Mezini, editors. Charlottesville, Virginia, USA, 2009. ACM International Conference Proceedings Series, ACM Press.

Full text: FOAL09a.pdf

Concurrency in the Curriculum: Demands and Challenges

Curtis Clifton 2009. Position paper for the First Workshop on Curricula in Concurrency and Parallelism, OOPSLA 2009.

Full text: Clifton09aa.pdf

Abstract: This position paper describes my background as a practitioner and educator. It outlines some ideas on the general directions for curricular change to address concurrency and parallelism. Finally, the paper identifies a key challenge in making this transition.

Introducing PyLighter: Dynamic Code Highlighter

M. G. Boland and C. Clifton. In Fortieth SIGCSE Technical Symposium on Computer Science Education, pp. 489-493, 2009. .

Full text: BolandClifton09aa.pdf

Abstract: Like a screenplay, a program is both a static artifact and instructions for a dynamic performance. This duality can keep laypeople from appreciating the complexity of software systems and can be a stumbling block for novice programmers. PyLighter lets laypeople and novice programmers perceive the relationship between static Python code and its execution. PyLighter works with everything from simple console applications to arcade-style games, and because PyLighter is easy to adopt and use, instructors can integrate it into any Python-based introductory course without changing the rest of their syllabus.

FOAL 2008 Proceedings: Foundations of Aspect-Oriented Languages Workshop at AOSD 2008

C. Clifton and S. Katz and G. T. Leavens and M. Mezini, editors. Brussels, Belgium, 2008. ACM International Conference Proceedings Series, ACM Press.

Full text: FOAL08a.pdf

FOAL 2007 Proceedings: Foundations of Aspect-Oriented Languages Workshop at AOSD 2007

C. Clifton and G. T. Leavens and M. Mezini, editors. Vancouver, BC, Canada, 2007. ACM International Conference Proceedings Series, ACM Press.

Full text: FOAL07.pdf

MAO: Ownership and Effects for More Effective Reasoning About Aspects

C. Clifton and G. T. Leavens and J. Noble. In ECOOP 2007 – Object-Oriented Programming, pp. 451–475, 2007. Springer.

Full text: CliftonLeavensNoble07a.pdf

Abstract: Aspect-oriented advice increases the number of places one must consider during reasoning, since advice may affect all method calls and field accesses. MAO, a new variant of AspectJ, demonstrates how to simplify reasoning by allowing programmers, if they choose, to declare limits on the control and heap effects of advice. Heap effects, such as assignment to object fields, are specified using concern domains — declared partitions of the heap. By declaring the concern domains affected by methods and advice, programmers can separate objects owned by the base program and by various aspects. When desired, programmers can also use such concern domain annotations to check that advice cannot interfere with the base program or with other aspects. Besides allowing programmers to declare how concerns interact in a program, concern domains also support a simple kind of semantic pointcut. These features make reasoning about control and heap effects easier.

Multiple Concerns in Aspect-Oriented Language Design: A Language Engineering Approach to Balancing Benefits, with Examples

G. T. Leavens and C. Clifton. Technical Report 07-01, Iowa State University, 2007. Appeared in SPLAT 2007–Software Engineering Properties of Language and Aspect Technologies workshop.

Full text: LeavensClifton07.pdf

Abstract: Some in the aspect-oriented community view a programming language as aspect-oriented only if it allows programmers to perfectly eliminate scattering and tangling. That is, languages that do not allow programmers to have maximal quantification and perfect obliviousness are not viewed as aspect-oriented. On the other hand, some detractors of aspect-oriented software development view maximal quantification and perfect obliviousness as causing problems, such as difficulties in reasoning or maintenance. Both views ignore good language design and engineering practice, which suggests trying to simultaneously optimize for several goals. That is, designers of aspect-oriented languages that are intended for wide use should be prepared to compromise quantification and obliviousness to some (small) extent, if doing so helps programmers solve other problems. Indeed, balancing competing requirements is an essential part of engineering. Simultaneously optimizing for several language design goals becomes possible when one views these goals, such as minimizing scattering and tangling, not as all-or-nothing predicates, but as measures on a continuous scale. Since most language design goals will only be partially met, it seems best to call them “concerns.”

Subverting the Fundamentals Sequence: Using Version Control to Enhance Course Management

C. Clifton and L. C. Kaczmarczyk and M. Mrozek. In Thirty-eighth SIGCSE Technical Symposium on Computer Science Education, pp. 86–90, 2007. ACM Press.

Full text: CliftonKaczmarczykMrozek07a.pdf

Abstract: Instructors of introductory courses face many challenges, not the least of which is dealing with a large volume of course materials and students with differing backgrounds. There are often too many administrative demands to have as much time for creative pedagogy as one would like. Team pro jects, and complex realistic pro jects in general, increase psychic demands, and conflicting schedules make creative collaboration with other instructors impossible. In order to address these issues, we need to find ways to increase effective handling of course development, to free up time for creative pedagogical efforts. This paper reports on an exploratory pro ject in which two instructors and an undergrad- uate teaching assistant used the Subversion version control system to collaborate remotely on developing and running two CS1 classes. We focus on the ease and efficiency of course management using Subversion, providing a new perspective on how version control can enhance teaching.

FOAL 2006 Proceedings: Foundations of Aspect-Oriented Languages Workshop at AOSD 2006

C. Clifton and R. Lämmel and G. T. Leavens, editors. Bonn, Germany, 2006. Iowa State University, Dept. of Computer Science.

Full text: FOAL06.pdf

A Type Notation for Scheme

G. T. Leavens and C. Clifton and B. Dorn. Technical Report 05-18a, Iowa State University, 2006. Available by anonymous ftp from ftp.cs.iastate.edu.

Full text: Leavens-Clifton-Dorn06.pdf

Abstract: The Typedscm dialect of Scheme is a variant on the Scheme dialect used in the book Essentials of Programming Languages [Friedman-Wand-Haynes01]. Typedscm adds facilities for declaring types in a Scheme-inspired notation. For example, one can write (deftype add1 (-> (number) number)) (define add1 (lambda (n) (+ n 1))) Typedscm allows for both type checking and type inference; that is, type declarations can be omitted in many cases. For example, Typedscm would infer the type of add1 even if the deftype declaration above were not given.

MultiJava: Design Rationale, Compiler Implementation, and Applications

C. Clifton and T. Millstein and G. T. Leavens and C. Chambers. ACM Trans. on Prog. Lang. and Systems, 28(3):517-575, 2006.

Full text: Clifton-etal06.pdf

Abstract: MultiJava is a conservative extension of the Java programming language that adds symmetric multiple dispatch and open classes. Among other benefits, multiple dispatch provides a solution to the binary method problem. Open classes provide a solution to the extensibility problem of ob ject-oriented programming languages, allowing the modular addition of both new types and new operations to an existing type hierarchy. This paper illustrates and motivates the design of MultiJava and describes its modular static typechecking and modular compilation strategies. Although MultiJava extends Java, the key ideas of the language design are applicable to other ob ject-oriented languages, such as C# and C++, and even, with some modifications, to functional languages such as ML.

This paper also discusses the variety of application domains in which MultiJava has been successfully used by others, including pervasive computing, graphical user interfaces, and compilers. MultiJava allows users to express desired programming idioms in a way that is declarative and supports static typechecking, in contrast to the tedious and type-unsafe workarounds required in Java. MultiJava also provides opportunities for new kinds of extensibility that are not easily available in Java.

MiniMAO1: An Imperative Core Language for Studying Aspect-Oriented Reasoning

C. Clifton and G. T. Leavens. Science of Computer Programming, 63(3):321-374, 2006.

Full text: CliftonLeavens06b.pdf

Abstract: This paper describes MiniMAO1 , a core aspect-oriented language. Unlike previous aspect-oriented calculi and core languages, MiniMAO1 allows around advice to change the target object of an advised operation before proceeding. MiniMAO1 accurately models the ways AspectJ allows changing the target object, e.g., at call join points. Practical uses for changing the target object using advice include proxies and other wrapper objects. MiniMAO1 was designed to serve as a core language for studying modular specification and verification in the aspect-oriented paradigm. To this end MiniMAO1  —  has an imperative, reference-based semantics,  —  models the control-flow effects of changing target object bindings with advice, and  —  has a safe static type system. The first two features make MiniMAO1 suitable for the study of aspect-oriented mechanisms, such as those found in AspectJ. These features are important for studying the interaction of aspect-oriented language features with modular specification and verification. A statically type-safe language is also import for such research. AspectJ does not have a safe static type system. To achieve static type safety MiniMAO1 uses a slightly different form of proceed and advice binding than in AspectJ. These changes are sufficient for static type safety, but we do not claim that they are necessary; a less restrictive type system might suffice. This paper gives an operational semantics, type system, and proof of soundness for MiniMAO1 .

MiniMAO: Investigating the Semantics of Proceed

C. Clifton and G. T. Leavens. In FOAL 2005 Proceedings: Foundations of Aspect-Oriented Languages Workshop at AOSD 2005, pp. 51-61, 2005. Iowa State University, Dept. of Computer Science.

Full text: CliftonLeavens06c.pdf

Abstract: This paper describes the semantics of MiniMAO1, a core aspect-oriented calculus. Unlike previous aspect-oriented calculi, it allows around advice to change the target object of an advised operation before proceeding. MiniMAO1 accurately models the ways AspectJ allows changing the target object, e.g., at call join points. Practical uses for changing the target object using advice include proxies and other wrapper objects.

In addition to accurate modeling of bindings for around advice, MiniMAO1 has several other features that make it suitable for the study of aspect-oriented mechanisms, such as those found in AspectJ. Like AspectJ, the calculus consists of an imperative, object-oriented base language plus aspect-oriented extensions. MiniMAO1 has a sound static type system, facilitated by a slightly different form of proceed than in AspectJ. abstract

Lessons from the JML Project

G. T. Leavens and C. Clifton. In Verified Software: Theories, Tools, Experiments, Zurich, Switzerland, 2005. Springer-Verlag. To appear. Also ISU TR 05-12a, July 2005

Full text: Leavens-Clifton05a.pdf

Abstract: To have impact, a grand challenge should provide a way for diverse research to be integrated in a synergistic fashion. Synergy in the JML project comes from a shared specification language, and thus holds several lessons for the verifying compiler grand challenge. An important lesson is that the project should focus considerable resources on specification language design, which still contains many open research problems. Another important lesson is that, to support such a specification language, the project needs to involve groups doing research on extensible compilers and integrated development environments.

A design discipline and language features for modular reasoning in aspect-oriented programs

C. Clifton. Ph.D. thesis, Iowa State University, 2005. Also available as ISU TR 05-15.

Full text: Clifton05a.pdf

Abstract: Aspect-oriented programming lets programmers modularize concerns that are orthogonal to the main decomposition of a program. To do this, aspect-oriented programming includes modules called aspects that may modify the behavior, or advise, code in the main decomposition. Aspect-oriented programming also allows aspects to declaratively specify what code should be advised. This means that a whole-program search is required to find all the aspects that might advise a given piece of code. The problems this causes are somewhat analogous to overriding methods and polymorphic method dispatch in traditional object-oriented programming. In object-oriented programming, the discipline of behavioral subtyping permits reasoning about polymorphic methods even when overriding methods remain unseen. The discipline gives guidance to the author of an overriding method: the overriding method must satisfy the specification of the overridden, superclass method. If the author follows the discipline, then other programmers can reason about a method invocation based on the specification of the superclass method, even if an unseen overriding method might actually be executed. This dissertation describes an analogous discipline for aspect-oriented programming. The basic premise is that modular reasoning about aspect-oriented programs requires shared responsibility between the aspect author and the client programmer, whose code might be advised by the aspect. To mediate this sharing, this dissertation proposes that aspects be categorized into two sorts: “spectators” and “assistants”. Spectators are statically restricted to not modify the behavior of the code that they advise. Because of their restricted behavior, spectators may remain unseen by the client programmer. The burden is on the aspect programmer to ensure that spectators satisfy their restrictions. Unlike spectators, assistants are not restricted in their behavior. The burden of reasoning about their effects falls to the client programmer. To do this, the client programmer must be able to identify all applicable assistants. Thus, assistants must be explicitly accepted by the advised code. This discipline allows modular reasoning, permits the use of existing aspect-oriented idioms, and appears to be practical and statically verifiable. A formal study demonstrates that the restrictions on spectators may be statically checked.

How the Design of JML Accommodates Both Runtime Assertion Checking and Formal Verification

G. T. Leavens and Y. Cheon and C. Clifton and C. Ruby and D. R. Cok. Science of Computer Programming, 55(1-3):185-208, 2005.

Full text: Leavens-etal05.pdf

Abstract: Specifications that are used in detailed design and in the documentation of existing code are primarily written and read by programmers. However, most formal specification languages either make heavy use of symbolic mathematical operators, which discourages use by programmers, or limit assertions to expressions of the underlying programming language, which makes it difficult to write exact specifications. Moreover, using assertions that are expressions in the underlying programming language can cause problems both in runtime assertion checking and in formal verification, because such expressions can potentially contain side effects. The Java Modeling Language, JML, avoids these problems. It uses a side-effect free subset of Java’s expressions to which are added a few mathematical operators (such as the quantifiers \forall and \exists). JML also hides mathematical abstractions, such as sets and sequences, within a library of Java classes. The goal is to allow JML to serve as a common notation for both formal verification and runtime assertion checking; this gives users the benefit of several tools without the cost of changing notations.

FOAL 2005 Proceedings: Foundations of Aspect-Oriented Languages Workshop at AOSD 2005

C. Clifton and R. Lämmel and G. T. Leavens, editors. Chicago, Illinois, USA, 2005. Iowa State University, Dept. of Computer Science.

Full text: FOAL05.pdf

FOAL 2004 Proceedings: Foundations of Aspect-Oriented Languages Workshop at AOSD 2004

C. Clifton and R. Lämmel and G. T. Leavens, editors. Lancaster, UK, 2004. Iowa State University, Dept. of Computer Science.

Full text: FOAL04.pdf

Obliviousness, Modular Reasoning, and the Behavioral Subtyping Analogy

C. Clifton and G. T. Leavens. Technical Report 03-01a, Iowa State University, 2003. Appeared in SPLAT–Software Engineering Properties of Language and Aspect Technologies 2003.

Full text: Clifton-Leavens03.pdf

Abstract: The obliviousness property of AspectJ conflicts with the ability to reason about an AspectJ program in a modular fashion. This makes debugging and maintenance difficult. In ob ject-oriented programming, the discipline of behavioral subtyping allows one to reason about programs modularly, despite the somewhat oblivious nature of dynamic binding; however, it is not clear what discipline would help AspectJ programmers obtain modular reasoning. We describe this problem in detail, and sketch a solution that allows programmers to tell both “superimposition” and “evolution” stories in their AspectJ programs.

How the Design of JML Accommodates Both Runtime Assertion Checking and Formal Verification

G. T. Leavens and Y. Cheon and C. Clifton and C. Ruby and D. R. Cok. In Formal Methods for Components and Objects: First International Symposium, FMCO 2002, Lieden, The Netherlands, November 2002, Revised Lectures, 2003. Springer-Verlag.

Full text: Leavens-etal03a.pdf

Abstract: Specifications that are used in detailed design and in the documentation of existing code are primarily written and read by programmers. However, most formal specification languages either make heavy use of symbolic mathematical operators, which discourages use by programmers, or limit assertions to expressions of the underlying programming language, which makes it difficult to write complete specifications. Moreover, using assertions that are expressions in the underlying programming language can cause problems both in runtime assertion checking and in formal verification, because such expressions can potentially contain side effects. The Java Modeling Language, JML, avoids these problems. It uses a side-effect free subset of Java’s expressions to which are added a few mathematical operators (such as the quantifiers \forall and \exists). JML also hides mathematical abstractions, such as sets and sequences, within a library of Java classes. The goal is to allow JML to serve as a common notation for both formal verification and runtime assertion checking; this gives users the benefit of several tools without the cost of changing notations.

Obliviousness, Modular Reasoning, and the Behavioral Subtyping Analogy

C. Clifton and G. T. Leavens. Technical Report 03-15, Iowa State University, 2003.

Full text: Clifton-Leavens03a.pdf

Abstract: The obliviousness property of AspectJ-like languages conflicts with the ability to reason about programs in a modular fashion. This can make debugging and maintenance difficult. In ob ject-oriented programming, the discipline of behavioral subtyping allows one to reason about programs modularly, despite the oblivious nature of dynamic binding; however, it is not clear what discipline would help programmers in AspectJ-like languages obtain modular reasoning. Behavioral subtyping was born out of the stories programmers were telling in their ob ject-oriented programs and how they reasoned about them. Programmers use AspectJ-like languages to tell what we call “superimposition” and “adaptation” stories. Thus, a discipline of modular reasoning for an AspectJ-like language must account for both sorts of stories. We describe the modular reasoning problem for AspectJ-like languages. We do not yet have a solution, but concisely articulate the issues involved.

Formal Definition of the Parameterized Aspect Calculus

C. Clifton and G. T. Leavens and M. Wand. Technical Report 03-12b, Iowa State University, 2003.

Full text: Clifton-Leavens-Wand03.pdf

Abstract: This paper gives the formal definition of the parameterized aspect calculus, or \sigma_asp. The \sigma_asp calculus is a core calculus for the formal study of aspect-oriented programming languages. The calculus consists of a base language, taken from Abadi and Cardelli’s object calculus, and point cut description language. The calculus is parameterized to accept a variety of point cut description languages, simplifying the study of a variety of aspect-oriented language features. The calculus exposes a rich join point model on the base language, granting great flexibility to point cut description languages.

Parameterized Aspect Calculus: A Core Calculus for the Direct Study of Aspect-Oriented Languages

C. Clifton and G. T. Leavens and M. Wand. Technical Report 03-13, Iowa State University, 2003.

Full text: Clifton-Leavens-Wand03a.pdf

Abstract: Formal study of aspect-oriented languages is difficult because current theoretical models provide a range of features that is too limited and rely on encodings using lower-level abstractions, which involve a cumbersome level of indirection. We present a calculus, based on Abadi and Cardelli’s object calculus, that explicitly models a base language and a variety of point cut description languages. This explicit modeling makes clear the aspect-oriented features of the calculus by removing the indirection of some existing models. We demonstrate the generality of our calculus by presenting models for AspectJ’s open classes and advice, and HyperJ’s compositions, and sketching a model for DemeterJ’s adaptive methods.

Observers and Assistants: A Proposal for Modular Aspect-Oriented Reasoning

C. Clifton and G. T. Leavens. In FOAL 2002 Proceedings: Foundations of Aspect-Oriented Languages Workshop at AOSD 2002, pp. 33-44, 2002. Iowa State University, Dept. of Computer Science.

Full text: Clifton-Leavens02a.pdf

Abstract: In general, aspect-oriented programs require a whole-program analysis to understand the semantics of a single method invocation. This property can make reasoning difficult, impeding maintenance efforts, contrary to a stated goal of aspect-oriented programming. We propose some simple modifications to AspectJ that permit modular reasoning. This eliminates the need for whole-program analysis and makes code easier to understand and maintain.

Spectators and Assistants: Enabling Modular Aspect-Oriented Reasoning

C. Clifton and G. T. Leavens. Technical Report 02-10, Iowa State University, 2002.

Full text: Clifton-Leavens02b.pdf

Abstract: In current aspect-oriented languages, separate compilation and modular reasoning are not possible. This detracts from comprehensibility and impedes maintenance efforts. We describe language features that would allow aspect-oriented languages to provide separate compilation and modular reasoning. We demonstrate that existing programs written in AspectJ can be easily rewritten using these features.

MultiJava: Design, implementation, and evaluation of a Java-compatible language supporting modular open classes and symmetric multiple dispatch

C. Clifton. Masters thesis, Iowa State University, 2001.

Full text: Clifton01.pdf

Abstract: This paper describes the design, implementation, and evaluation of MultiJava, a backward-compatible extension to The Java Programming Language that supports open classes and symmetric multiple dispatch. An open class is one to which new methods can be added without editing the class directly. Multiple dispatch allows the method invoked by a message send to depend on the run-time types of any subset of the argument objects. MultiJava is the first full-scale programming language to support these features while retaining modular static typechecking and compilation.

The paper defines the notions of modular editing, typechecking, and compilation, and describes two problems, the augmenting method problem and the binary method problem, that heretofore had not been solved in a modular way. We describe the architecture and key implementation details of our MultiJava compiler, mjc. mjc is open-source and is freely available for downloading. We present an evaluation of MultiJava that demonstrates the ease of extending code written in the language. We also provide empirical results for the performance of MultiJava versus the previous partial solutions to the augmenting method and binary method problems. These results demonstrate that MultiJava’s performance is comparable to that of the partial solutions, while the language provides full solutions to the problems.

MultiJava: Modular Open Classes and Symmetric Multiple Dispatch for Java

C. Clifton and G. T. Leavens and C. Chambers and T. Millstein. In OOPSLA 2000 Conference on Object-Oriented Programming, Systems, Languages, and Applications, pp. 130-145, 2000. ACM Press.

Full text: Clifton-etal00.pdf

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