Making the future safe for the past:
Adding Genericity to the Java Programming Language
Gilad Bracha, Martin Odersky, David Stoutamire and Philip Wadler
Object-Oriented Programming Systems, Languages, and Applications
(OOPSLA '98), Vancouver, Canada, October 1998.
We present GJ, a design that extends the Java programming language with generic types and methods. These are both explained and implemented by translation into the unextended language. The translation closely mimics the way generics are emulated by programmers: it erases all type parameters, maps type variables to their bounds, and inserts casts where needed. Some subtleties of the translation are caused by the handling of overriding.
GJ increases expressiveness and safety: code utilizing generic libraries is no longer buried under a plethora of casts, and the corresponding casts inserted by the translation are guaranteed to not fail.
GJ is designed to be fully backwards compatible with the current Java language, which simplifies the transition from non-generic to generic programming. In particular, one can retrofit existing library classes with generic interfaces without changing their code.
An implementation of GJ has been written in GJ, and is freely available on the web.
Portable, Modular Expression of Locality
David Stoutamire
Ph.D. Thesis, University of California at Berkeley, 1997.
It is difficult to achieve high performance while programming in the large. In particular, maintaining locality hinders portability and modularity. Existing methodologies are not sufficient: explicit communication and coding for locality require the programmer to violate encapsulation and compositionality of software modules, while automated compiler analysis remains unreliable.
This thesis presents a performance model that makes thread and object locality explicit. Zones form a runtime hierarchy that reflects the intended clustering of threads and objects, which are dynamically mapped onto hardware units such as processor clusters, pages, or cache lines. This conceptual indirection allows programmers to reason in the abstract about locality without committing to the hardware of a specific memory system. Zones complement conventional coding for locality and may be added to existing code to improve performance without affecting correctness.
The integration of zones into the Sather language is described, including an implementation of memory management customized to parameters of the memory system.
Iteration Abstraction in Sather
Stephan Murer, Stephen Omohundro, David Stoutamire and Clemens Szyperski
Transactions on Programming Languages and Systems, Vol. 18, No. 1, Jan 1996 p. 1-15.
Sather extends the notion of an iterator in a powerful new way. We argue that iteration abstractions belong in class interfaces on an equal footing with routines. Sather iterators were derived from CLU iterators but are much more flexible and better suited for object-oriented programming. We retain the property that iterators are structured, i.e. strictly bound to a controlling structured statement. We motivate and describe the construct along with several simple examples. We compare it with iteration based on CLU iterators, cursors, riders, streams, series, generators, coroutines, blocks, closures, and lambda expressions. Finally, we describe experiences with iterators in the Sather compiler and libraries.
Other publications:
Using Value Semantic Abstractions to Guide Strongly Typed Library Design
This report addresses typing problems that arise when modelling simple
mathematical entities in strongly typed languages such as Sather, which
are eliminated by a proper distinction between mutable and immutable
abstractions. We discuss the reasons why our intuition leads us astray,
and provide a solution using statically type-safe specialization through
constrained overloading. We also discuss the type relationships between
mutable and immutable classes and the notion of freezing objects.
Portable, Modular Expression of Locality
It is difficult to achieve high performance while programming in the
large. In particular, maintaining locality hinders portability and
modularity. Existing methodologies are not sufficient: explicit
communication and coding for locality require the programmer to
violate encapsulation and compositionality of software modules, while
automated compiler analysis remains unreliable.
This thesis presents a performance model that makes thread and object
locality explicit. Zones form a runtime hierarchy that
reflects the intended clustering of threads and objects, which are
dynamically mapped onto hardware units such as processor clusters,
pages, or cache lines. This conceptual indirection allows programmers
to reason in the abstract about locality without committing to the
hardware of a specific memory system. Zones complement conventional
coding for locality and may be added to existing code to improve
performance without affecting correctness.
The integration of zones into the Sather language is described,
including an implementation of memory management customized
to parameters of the memory system.
Type-Safety and Overloading in Sather
Method overloading is a form of statically resolved multi-methods
which may be used to express specialization in a type hierarchy. The
design of the overloading rule in Sather is constrained by the
presence of multiple subtyping and the ability to add supertyping
edges to the type graph after the fact. We describe the design of
overloading rules which permit method specialization while allowing
separate type checking, i.e., existing code cannot be broken by the
after the fact addition of supertyping edges.
An Analysis of the Divergence of Two Sather Dialects
Sather is an object oriented language designed to be
simple, efficient, safe, and non-proprietary. It was
originally envisioned as a ``cleaned-up'' version of
Eiffel, addressing perceived failures in simplicity and
efficiency. The first public implementation (Sather 0)
was first released to the public by ICSI in 1991.
Shortly after, a compiler group at the University of
Karlsruhe created the first native code compiler.
A major effort then began to redesign the language to
correct shortcomings in Sather 0 and to make Sather
suitable for general-purpose, large scale programming.
In part because each compiler group was building a
compiler for a moving design target, the two parallel
efforts resulted in two dialects, Sather 1 and Sather
K. This report analyzes the essential causes of the
differences, which result from differences in each
group's goals.
Killing Threads Considered Dangerous
The parallel Sather (pSather) group continues its efforts to make parallel
OO programming safe, efficient and relatively easy. Since the last POOMA
meeting we have learned many lessons, some of which seem to be of general
interest. All Sather releases since 1.0.6 in May 1995 have included
pSather. The latest version runs on Solaris SMPs, networks of these linked
by Myrinet or TCP/IP, and the Meiko CS-2. It is currently being used in a
parallel computing course at Berkeley and for ICSI projects.
The talk briefly introduces the key features of pSather and the new
modifications. These include disjunctive locks, visitor/ mutator
protection and iterator yields from within a lock statement.
One of the most interesting lessons of the last year has been a major
revision of how thread termination is handled. There was a "gate.clear"
command that terminated all threads attached to a gate, regardless of
their state. We eventually convinced ourselves that there is no way to do
this that guarantees correct semantics. Meanwhile, we had been discussing
whether it was worth adding disjunctive locks to the language. It turns
out that disjunctive locks cleanly handle all the cases in which we were
using asynchronous thread termination.
The Sather 1.1 Specification
This document is a concise specification of Sather
1.1. Sather is an object oriented language designed to
be simple, efficient, safe, flexible and non-proprietary.
Sather has parameterized classes,
object-oriented dispatch, statically-checked strong
(contravariant) typing, separate implementation and
type inheritance, multiple inheritance, garbage
collection, iteration abstraction, closures, exception
handling, assertions, preconditions, post conditions,
and class invariants.
This 1.1 specification significantly polishes and
improves the 1.0 language specification with an
introduction, index, and examples. New constructs
include `out' arguments, less restrictive overloading,
and improved external language interfaces.
Sather Revisited: A High-Performance Free Alternative to C++
Sather is an object-oriented language first introduced in
1991. Since then, considerable practical experience has been
obtained with the language by the hundreds of users making up
the Sather community. Sather offers many safety and
convenience features to help programmers avoid common errors
and reuse code. Some of these were discussed in a previous
Computers in Physics article; they include strong typing,
garbage collection, object-oriented dispatch, multiple
inheritance and parameterized classes. Here we mention other
advantages that have come to maturity since then, including
iteration abstraction and parallel and distributed language
extensions.
The Sather 1.0 Specification
This document is a concise specification of Sather 1.0. Sather
is an object oriented language designed to be simple,
efficient, safe, flexible and non-proprietary. Sather has
parameterized classes, object-oriented dispatch,
statically-checked strong (contravariant) typing, separate
implementation and type inheritance, multiple inheritance,
garbage collection, iteration abstraction, higher-order
routines and iters, exception handling, assertions,
preconditions, postconditions, and class invariants. The ICSI
compiler supported this 1.0 specification from 1994 through
much of 1995.
The pSather 1.0 Manual
This document describes pSather 1.0, the parallel and
distributed extension to Sather 1.0 (see ICSI tech
report TR-95-057). pSather adds support for threads,
synchronization, communication, and placement of
objects and threads. The ICSI compiler supported this
1.0 specification through much of 1995.
CNS-1 Architecture Specification
The Connectionist Network Supercomputer, or CNS-1, is a
multi-year effort to incorporate recent advances in VLSI
design and application-specific computer architecture
for the realization of a massively parallel machine.
Application targets for the CNS-1 include connectionist
networks in the areas of speech recognition, language
modeling, vision, and hardware simulation for VLSI.
This technical report presents the background and
motivation for high-level design decisions, along with
descriptions of several hardware and software elements.
The document represents a "snapshot" of the design, which
is expected to be operational in 1995.
Machine Learning, Game Play, and Go
The game of go is an ideal problem domain for exploring machine
learning: it is easy to define and there are many human
experts, yet existing programs have failed to emulate their
level of play to date. Existing literature on go playing
programs and applications of machine learning to games are
surveyed. An error function based on a database of master
games is defined which is used to formulate the learning of go
as an optimization problem. A classification technique called
pattern preference is presented which is able to
automatically derive patterns representative of good moves; a
hashing technique allows pattern preference to run efficiently
on conventional hardware with graceful degradation as memory
size decreases.
Machine Learning Applied to Go
The game of go is an ideal problem domain for exploring machine
learning; it is easy to define and there exist many skilled
human experts, yet existing programs have failed to emulate
their level of play to date. Existing techniques used by
computers to play go are surveyed. An error function is
defined which is used by several classifications techniques and
genetic algorithms to automatically derive patterns
representative of good moves.
Benedict Gomes, David Stoutamire, Boris Weissman and Jerome Feldman
International Computer Science Institute TR-97-061.
David Stoutamire
International Computer Science Institute TR-97-056.
Benedict Gomes, David Stoutamire and Boris Weissman
International Computer Science Institute TR-97-055.
David Stoutamire, Wolf Zimmermann, and Martin Trapp
International Computer Science Institute TR-96-037.
Claudio Fleiner, Jerry Feldman and David Stoutamire
Conference on Parallel and Object Oriented Methods and Applications
(POOMA), Santa Fe, 1996
David Stoutamire and Stephen Omohundro
International Computer Science Institute TR-96-012.
David Stoutamire and Matt Kennel
Computers in Physics, Vol. 9, No. 5, Sep/Oct 1995 p. 519-524.
Stephen Omohundro and David Stoutamire
International Computer Science Institute TR-95-057.
David Stoutamire
International Computer Science Institute TR-95-058.
Krste Asanovic, James Beck, Tim Callahan, Jerry Feldman,
Bertrand Irissou, Brian Kingsbury, Phil Kohn, John Lazzaro,
Nelson Morgan, David Stoutamire and John Wawrzynek
International Computer Science Institute TR-93-021.
David Stoutamire
Center for Automation and Intelligent Systems Research TR 91-128,
Case Western Reserve University.
David Stoutamire
M.S. thesis, Case Western Reserve University, 1991.