Neal Gafter's blog

A couple of comments on Defender Methods

2010-08-26T15:18:00.001-07:00

Brian Goetz has posted version 3 of his proposal "Defender Methods", which is a way of adding methods to existing interfaces without breaking binary compatibility. Generally speaking, I think the idea is sound but I think there are some problems with the proposal in its current form. I would normally post my comments on the proposal to the lambda-dev mailing list, which ensures that any IP embedded in my comments are formally submitted to Oracle's ownership. However, Oracle's recent lawsuit against Google has made it clear that, even though I am a contributor to openjdk7, I do not have a license to Oracle's patents that are necessarily infringed by the use of the openjdk7 source base. This is a very confusing position for the organizer of an open-source effort to take. Rather than continuing to contribute IP directly to the project, I'll post my comments here and contribute them to Oracle once it is clear that I've been granted a license to the patents necessary to use openjdk7.

The latest version of the proposal has added a section on "Binary compatibility" (section 11), but that section fails to address the one binary compatibility issue raised previously: what are the binary compatibility implications of changing the default for a defender method? Since the defender method's default is an implementation detail, such a change should be binary (and source) compatible, but the resolution mechanism (section 3) makes it binary incompatible. The proposal doesn't provide compile-time semantics for invoking an extension method or compile-time rules for when a given class declaration is legal. At the very least there should be rules to ensure that sources that compile cleanly together do not trigger a VM error at runtime due to an ambiguous method invocation. The most natural change of the compile-time rules to match the given runtime resolution rules would make changing the defender method's default a source incompatible change as well (because it could introduce an ambiguity). I believe this undermines the justification for having defender methods out-of-line (section 2). Moreover, the separation forces API designers to create vestigial public API elements (the static extension methods).

These issues can be addressed by (a) having defender method bodies written inline, and (b) rejecting non-abstract class declarations where some defender method does not have a unique default.

I suspect the proposed implementation mechanisms (sections 7 and 8) will be far too expensive compared to existing virtual method calls. For the Interface.super calls (section 7), my suggestion is to extend the VM specification of invokespecial.

A Syntax Option for Project Lambda (Closures for Java)

2010-02-13T16:52:00.000-08:00

It was noted recently on the Project Lambda mailing list that allowing arrays of function type would undermine the type system. The reason for this is a combination of Java's covariant arrays, the natural subtypes among function types (they are covariant on return type and contravariant on argument types), exception checking, and the erasure implementation of generics. We certainly can't remove covariant arrays or checked exceptions, and removing the subtype relationship among function types really reduces their utility. Unfortunately, it is almost certainly too late to reify generics too. Although you can't have an array of function type, there is no problem having, for example, an ArrayList of a function type. So while we might prefer not to have this restriction, it won't be much of a problem in practice.

There are many ways in which arrays of function type would undermine the type system, but to give you some flavor of the problem, the following is a method written assuming that arrays of function type are allowed. This method must fail in some way - either fail to compile, or throw a ClassCastException, or an ArrayStoreException, or something. In all of the implementations being considered, this method would throw IOException, even though that isn't declared in the throws clause of the method. We have undermined Java's exception checking without even a cast!

public void main(String[] args) {
    #void()[] arrayOfFunction = new #void()[1];
    Object[] objectArray = arrayOfFunction;
    objectArray[0] = #(){ throw new IOException(); };
    arrayOfFunction[0].(); // invoke the function out of the array
}

The realization that supporting arrays of function type would introduce a loophole in the type system makes it possible to consider some very nice syntax options that were previously eliminated because there was no syntactic way to write an array of function type. But if we disallow arrays of function type, those options can be considered.

My favorite of the alternatives is based on this grammar

FunctionType:

( TypeList_opt Throws_opt ) -> ResultType

Expression:

LambdaExpression

LambdaExpression:

( FormalParameterList_opt ) -> Expression

A function type is written with the argument types between parentheses, then a right arrow (dash greater-than), and then the result type.

The most important distinction between this proposal and the existing draft specification is that this proposal places the result type after the argument types, instead of before. The benefits of its simplicity compared to the current specification are most obvious when you combine function types and lambdas with other features.

Here is a simple example to show how the two proposals look. The example is currying. The following method takes as a parameter a function of two arguments, and returns a function of one argument that returns a function of one argument. Applying the resulting function to one value, and then the result of that to another value, should have the same effect as applying the original function to both values. To make it interesting, we make the argument and result types generic, and we allow the function to throw an exception.

Using the currently proposed syntax for Project Lambda, the code would look something like this:

static <T,U,V,X extends Throwable>
##V(U)(throws X)(T) curry(#V(T,U)(throws X) function) {
   return #(T t)(#(U u)(function.(t,u)));
}

On the other hand, with the proposal described above it looks something like this:

static <T,U,V,X extends Throwable>
(T)->(U throws X)->V curry((T,U throws X)->V function) {
   return (T t)->(U u)->function.(t,u);
}

I've intentionally selected an example that uses the new features heavily, so either may take a few moments of studying to understand. But I claim the latter is much easier to follow than the former, even once you've become familiar with the syntax.

You can easily write a function that yields an array as its result

()->int[] arrayLambda = ()->new int[]{1, 2, 3};

With this proposed syntax there is no way to write an array of functions. But that is exactly what we concluded could not be made to work within the type system anyway.

JDK API search in Google Toolbar

2009-03-10T08:16:00.000-07:00

For those of you who use the Google Toolbar, the following links will add a Java API search button to your toolbar. I've found this to be a very handy way to locate the javadoc for the platform.

Add Java SE 6 API search box to Google Toolbar

Add OpenJDK API search box to Google Toolbar

Language Parity: Closures and the Java VM

2009-02-13T07:34:00.000-08:00

A video of my talk at the September 2008 JVM Language Summit has been posted. It's a discussion of how Java SE is tilted toward supporting the Java language at the expense of other languages, and what we might do about it.

Java Closures Prototype Feature-Complete

2008-08-07T23:08:00.000-07:00

I'm pleased to announce that the Java Closures prototype now supports all of the features of its specification!

The complete source code, released under GPLv2, is in the project's openjdk repository. A binary build, suitable for use with an existing JDK6, is at http://www.javac.info/closures.tar.gz. Other related documents are on the website http://www.javac.info/

Although there is room for performance tuning, the prototype supports the full Closures (v0.5) specification. Based on your feedback, there are some changes in the prototype suitable for a future update of the specification:

Renamed Unreachable to Nothing

We adopt the name used by Scala to represent the same concept.

Removed support for the type null

We used null as a placeholder for an exception type when none can be thrown. The type Nothing now serves that purpose; null is no longer supported as the name of a type.

Overhauled restricted versus unrestricted

In the specification, an interface is considered restricted if it extends a marker interface. Unfortunately, the specification only provides a syntax for function type interfaces that are unrestricted. We modified the syntax so that a function type written using the => token designates a restricted function type, while one written using the newly introduced ==> token represents an unrestricted function type. This allows programmers to easily write APIs that restrict (or don't restrict) the operations of closure expressions passed as parameters.

Refined restrictions

We modified the distinction between restricted and unrestricted closures. As before, it is not legal to convert an unrestricted closure to a restricted interface type, nor is it legal to break, continue, or return from inside a restricted closure to a target outside the closure. However, a restricted closure is allowed to refer to a non-final local variable from an enclosing scope. In this case a warning is given unless one of the following conditions holds:

The variable is not the target of any assignment, or

The variable is annotated @Shared

It is possible to suppress the warning by annotating some enclosing construct @SuppressWarnings("shared").

Relaxed the closure conversion

In response to user feedback, we've relaxed the relationship between a closure parameter's type and the target interface's parameter type. Rather than requiring them to be of the same type, they are now allowed to be related by an assignment conversion, including boxing or unboxing.

for-qualified method declarations

The for keyword on a method declaration, meant to introduce a control abstraction method that works like a loop, is now treated syntactically like a modifier rather than appearing immediately before the method name. This helps make the declaration site more similar to the use site.

Added support for method references

We added extensive support for treating a reference to a method as a closure using a newly introduced token #. The syntax is borrowed from the FCM proposal. The semantics are as follows:

A method reference written as
Primary # Identifier ( TypeList )
where the Primary designates an expression (as opposed to a type) is treated the same as a closure
{ Type x0, Type x1 ... => tmp.Identifier(x0, x1 ...) }
or
{ Type x0, Type x1 ... => tmp.Identifier(x0, x1 ...); }
Where tmp is a temporary value that holds the computed value of the primary expression. The former translation is used when the resolved method has a non-void return type, while the latter is used when the resolved method has a void return type.
If the primary resolves to a type, then this is translated to
{ Type x0, Type x1 ... => Primary.Identifier(x0, x1 ...) }
or
{ Type x0, Type x1 ... => Primary.Identifier(x0, x1 ...); }
when the resolved method is static, or
{ Primary x, Type x0, Type x1 ... => x.Identifier(x0, x1 ...) }
or
{ Primary x, Type x0, Type x1 ... => x.Identifier(x0, x1 ...); }
when the resolved method is an instance method.
In addition, optional explicit type arguments, between angle brackets, may be placed immediately after the # token. These are used directly in the translated method invocation to resolve the method to be invoked.

Implemented a classfile format for the for qualifier

We've impleemnted a class file representation of the for qualifier to support separate compilation.

Closures: Control Abstraction, Method References, Puzzler Solution

2008-03-17T00:37:00.000-07:00

Closures: Control Abstraction, Method References, Puzzler Solution

The Java Closures prototype now supports control abstraction and implements restricted closures and function types. The syntax has changed slightly. Also, as hinted in the draft JSR proposal, there is now support for eta abstraction, which is called method reference in Stephen Colebourne's FCM proposal. We haven't updated the specification, so this will serve as a brief tutorial on the changes until we do. I don't know if this will be the syntax we will end up with, but it will do for now. Finally, we look at solutions to the closure puzzler in my previous post.

Control Abstraction

The first thing you'll notice when using the new prototype is that the compiler gives a warning when a closure uses a local variable from an enclosing scope:

Example.java:4: warning: [shared] captured variable i not annotated @Shared
        Runnable r = { => System.out.println(i); };
                                             ^

There are a few ways to make this warning go away:

declare the variable final; or
annotate the variable @Shared; or
make sure the variable is not the target of any assignment expression; or
put @SuppressWarnings("shared") on an enclosing method or class; or
use an unrestricted closure, by using the ==> token instead of the => token (when possible).

The => token builds a restricted closure that triggers this warning. Restricted closures also do not allow a break or continue statement to a target outside the closure, nor a return statement from the enclosing method. You will rarely want to write an unrestricted closure; many (but not all) of the things you need to do with an unrestricted closure can be expressed more clearly with a control invocation statement instead.

You're not allowed to assign an unrestricted closure to a restricted interface. A number of existing JDK interfaces, such as java.lang.Runnable, have been modified to be restricted.

Error: cannot assign an unrestricted closure to a restricted interface type
        Runnable r = { ==> System.out.println(i); };
                       ^

In the less common case that you're writing a method intended to be used as a control API, you can write a function type with the (new) ==> token to designate an unrestricted function (interface) type. Let's do that to write a method, with, that will automatically close a stream for us. The idea is to be able to replace this code

FileInputStream input = new FileInputStream(fileName);
try {
    // use input
} finally {
    try {
        input.close();
    } catch (IOException ex) {
        logger.log(Level.SEVERE, ex.getMessage(), ex);
    }
}

with this

with (FileInputStream input : new FileInputStream(fileName)) {
    // use input
}

which is an invocation of the following method

public static void with(FileInputStream t, {FileInputStream==>void} block) {
    try {
        block.invoke(t);
    } finally {
        try {
            t.close();
        } catch (IOException ex) {
            logger.log(Level.SEVERE, ex.getMessage(), ex);
        }
    }
}

This is among the simplest control APIs, but it has some limitations:

It works with the type FileInputStream, but not any other Closeable types
It does not support exception transparency
It does not support completion transparency

Completing the API by repairing these defects is left as an exercise to the reader. A solution will be discussed in my JavaOne talk Closures Cookbook.

Method References

A natural companion to closures is a way to refer to an existing method instead of writing a closure that accepts the same arguments and just invokes the method. This is sometimes known as eta abstraction or method references. We expect closures in their final form to include support for this convenient feature, which is why it is called out in the draft JSR proposal. The latest version of the prototype supports this, with a syntax based on javadoc conventions. Here are a few examples:

{ int => Integer } integerValue = Integer#valueOf(int);
{ Integer => String } integerString = Integer#toString();
{ int, int => int } min = Math#min(int, int);
{ String => void } println = System.out#println(String);
{ => String } three = new Integer(3)#toString();
{ Collection<String> => String } max = Collections#max(Collection<String>);
{ => Collection<String> } makeEmpty = Collections#<String>emptySet();
Runnable printEmptyLine = System.out#println();

Writing code as a method is sometimes more convenient than writing it as a closure:

void doTask() {
    // a complex task to be done in the background
}


Executor ex = ...;
ex.execute(this#doTask());

Puzzler Solution

A couple of weeks ago we looked at a Java puzzler involving closures, and a number of people discussed the underlying issue. My favorite is David's post "Color-flavor locking breaks chiral symmetry". Lessons include not exposing public fields (accessors are better) and being careful to avoid cyclic initialization dependencies.

The enum language feature provides support for one solution to the puzzle: specialize each instance of the enums.

import java.util.*;

enum Color {
    BROWN {
        public Flavor flavor() {
            return Flavor.CHOCOLATE;
        }
    },
    RED {
        public Flavor flavor() {
            return Flavor.STRAWBERRY;
        }
    },
    WHITE {
        public Flavor flavor() {
            return Flavor.VANILLA;
        }
    };
    abstract Flavor flavor();
}

enum Flavor {
    CHOCOLATE {
        public Color color() {
            return Color.BROWN;
        }
    },
    STRAWBERRY {
        public Color color() {
            return Color.RED;
        }
    },
    VANILLA {
        public Color color() {
            return Color.WHITE;
        }
    };
    abstract Color color();

}

class Neapolitan {

    static <T,U> List<U> map(List<T> list, {T=>U} transform) {
        List<U> result = new ArrayList<U>(list.size());
        for (T t : list) {
            result.add(transform.invoke(t));
        }
        return result;
    }

    public static void main(String[] args) {
        List<Color> colors = map(Arrays.asList(Flavor.values()), { Flavor f => f.color() });
        System.out.println(colors.equals(Arrays.asList(Color.values())));

        List<Flavor> flavors = map(Arrays.asList(Color.values()), { Color c => c.flavor() });
        System.out.println(flavors.equals(Arrays.asList(Flavor.values())));
    }
}

Another elegant solution, due to 5er_levart, uses closures:

enum Color {
    BROWN({=>Flavor.CHOCOLATE}),
    RED({=>Flavor.STRAWBERRY}),
    WHITE({=>Flavor.VANILLA});

    private final {=>Flavor} flavor;

    public Flavor flavor() { return flavor.invoke(); }

    Color({=>Flavor} flavor) {
        this.flavor = flavor;
    }
}

enum Flavor {
    CHOCOLATE({=>Color.BROWN}),
    STRAWBERRY({=>Color.RED}),
    VANILLA({=>Color.WHITE});

    private final {=>Color} color;

    public Color color() { return color.invoke(); }

    Flavor({=>Color} color) {
        this.color = color;
    }
}

In both solutions the idea is to compute the value lazily, a key technique to break dependency cycles.

Closures Puzzler: Neapolitan Ice Cream

2008-02-05T09:21:00.000-08:00

People experience the world in different ways, using different senses. Some people view the world primarily through sight. Do you see what I mean? Some through sound. Do you hear me? Some experience the world only after thought and reflection. Do you know what I mean? Some point out "smells" in code as a way of criticizing its design. This puzzle explores the question of whether people experiencing the same thing through different senses are really experiencing the same thing at all. What is the program's output, and why?

This puzzle uses Java Closures, so if you want to try it you should download the prototype here. You can download the puzzle sources here. Comments on this blog post will not be posted to avoid spoiling the puzzle.

import java.util.*;

enum Color {
    BROWN(Flavor.CHOCOLATE),
    RED(Flavor.STRAWBERRY),
    WHITE(Flavor.VANILLA);
    final Flavor flavor;
    Color(Flavor flavor) {
        this.flavor = flavor;
    }
}

enum Flavor {
    CHOCOLATE(Color.BROWN),
    STRAWBERRY(Color.RED),
    VANILLA(Color.WHITE);
    final Color color;
    Flavor(Color color) {
        this.color = color;
    }
}

class Neapolitan {

    static <T,U> List<U> map(List<T> list, {T=>U} transform) {
        List<U> result = new ArrayList<U>(list.size());
        for (T t : list) {
            result.add(transform.invoke(t));
        }
        return result;
    }

    public static void main(String[] args) {
        List<Color> colors = map(Arrays.asList(Flavor.values()), { Flavor f => f.color });
        System.out.println(colors.equals(Arrays.asList(Color.values())));

        List<Flavor> flavors = map(Arrays.asList(Color.values()), { Color c => c.flavor });
        System.out.println(flavors.equals(Arrays.asList(Flavor.values())));
    }
}

Is the Java Language Dying?

2008-01-11T17:16:00.001-08:00

We tend to think of programming languages in two categories: "living languages" in which we should seriously consider developing new code, and "legacy languages" that we mainly use, if at all, because we have to maintain an existing code base. The act of classifying a language into one or the other category helps us decide what, if anything, we might consider doing to change the language. If a language is primarily a legacy language, changes should be aimed at making it easier to maintain and modify existing bodies of code. A living language, on the other hand, also benefits from changes that make it easier to design, develop, and maintain new code. Living languages evolve to reduce accidental complexity.

"What does a high-level language accomplish? It frees a program from much of its accidental complexity. An abstract program consists of conceptual constructs: operations, datatypes, sequences, and communication. The concrete machine program is concerned with bits, registers, conditions, branches, channels, disks, and such. To the extent that the high-level language embodies the constructs wanted in the abstract program and avoids all lower ones, it eliminates a whole level of complexity that was never inherent in the program at all." -No Silver Bullet - Fred Brooks

Programs written in legacy languages tend to exhibit a high degree of accidental complexity [Code's Worst Enemy, Steve Yegge] [Mr. Yegge meets Mr. Brooks, Brian C Cunningham]. Early in the life of a language, the complexity of programs written in that language may appear to be essential, but as we learn more about software engineering and programming languages, we find patterns of complexity appearing in the code that can be eliminated by improved languages.

A good example of this is garbage collection. In C and C++, memory management is a pervasive concern. Smart pointers and destructors help, but they do not significantly reduce the complexity of memory management. In languages with garbage collection, most of the complexity of memory management is assumed by the implementation of the language. Most languages that have been introduced in the past ten years support garbage collection.

Another example is concurrency. The threads-and-locks-and-semaphores primitives of Java enable parallel programming, but require that programmers express concurrency at a fairly low level. This has been "good enough" for some time, as most programs are not deployed on highly concurrent hardware. But that is changing [The Free Lunch Is Over, Herb Sutter]. Libraries such as java.util.concurrent and Doug Lea's fork-join framework help somewhat, but in many cases they introduce complexities of their own. Other languages that support closures, such as Scala make fork-join-like libraries much easier to use. Scala supports control abstraction [Crowl and LeBlanc], which allows the libraries to manage much of the complexity associated with concurrency [Debasish Ghosh]. Support for the Actors model [Haller and Odersky], for example, can be expressed cleanly as a library in Scala

Besides raising the level of abstraction of concurrent code, control abstraction also raises the level of abstraction for sequential code by eliminating whole categories of boilerplate, which can instead be moved into common library code. This kind of boilerplate cannot be significantly reduced by adding one or two custom statements to the language, because such built-in forms necessarily make assumptions about the use cases that narrow their applicability. For example, ARM blocks don't document how they handle exceptions arising from the close() method. One example in the proposal suggests they are silently swallowed at runtime, which may work for many cases involving I/O streams, but another example given is a transactional API, in which ignoring such exceptions is precisely wrong. Without a specification for the syntax and semantics, the reader is welcome to imagine the most favorable treatment of each use case. But an attempt to reconcile these and other conflicting requirements may show the approach cannot be salvaged. Perhaps that is why no progress has been made since mid 2006.

What about Java? Is it a living language, or a legacy language like Cobol? This question underlies much of the debate about how to move the Java programming language forward, if at all. Carl Quinn asked at the December 14, 2007, JavaPolis Future of Computing Panel (to be published on http://www.parleys.com): "How can we address the issue of evolving the [Java] platform, language, and libraries without breaking things?"

Neal Gafter: "If you don't want to change the meaning of anything ever, you have no choice but to not do anything. The trick is to minimize the effect of the changes while enabling as much as possible. I think there's still a lot of room for adding functionality without breaking existing stuff..."

Josh Bloch: "My view of what really happens is a little bit morbid. I think that languages and platforms age by getting larger and clunkier until they fall over of their own weight and die very very slowly, like over ... well, they're all still alive (though not many are programming Cobol anymore). I think it's a great thing, I really love it. I think it's marvelous. It's the cycle of birth, and growth, and death. I remember James saying to me [...] eight years ago 'It's really great when you get to hit the reset button every once and a while.'"

Josh may well be right. If so, we should place Java on life support and move our development to new languages such as Scala. The fork-join framework itself is an example of higher-order functional programming, which Josh argues is a style that we should neither encourage nor support in Java. Is it really time to move on?

Personally, I believe rumors of Java's demise are greatly exaggerated. We should think of Java as a living language, and strive to eliminate much of the accidental complexity of Java programs. I believe it is worth adding support for closures and control abstraction, to reduce such complexity of both the sequential and concurrent aspects of our programs. At the same time, for completely new code bases, we should also consider (and continue to develop) newer languages such as Scala, which benefit from the lessons of Java.

What flavor of closures?

2007-12-13T07:48:00.000-08:00

I just attended Josh Bloch's presentation at JavaPolis, where he asks the community whether they want Java to support function types, or if they'd prefer that people write these things the way they do today. His examples are carefully selected from the most twisted of the test suite. Compiler test suites are a good place to find the most twisted but unrealistic uses of any given language feature. I thought it would be interesting to look at the question in the context of a real API. You probably know my opinion, but just to be clear, here is an excerpt from Doug Lea's fork-join framework

/**
 * An object with a function accepting pairs of objects, one of
 * type T and one of type U, returning those of type V
 */
interface Combiner<T,U,V> {
  V combine(T t, U u);
}
class ParallelArray<T> {
  /**
   * Returns a ParallelArray containing results of applying
   * combine(thisElement, otherElement) for each element.
   */
  <U,V> ParallelArray<V> combine(
    ParallelArray<U> other,
    Combiner<? super T, ? super U, ? extends V> combiner) { ... }
}

And the equivalent code ported to use the features of the closures spec:

class ParallelArray<T> {
  /**
   * Returns a ParallelArray containing results of applying
   * combine(thisElement, otherElement) for each element.
   */
  <U,V> ParallelArray<V> combine(
    ParallelArray<U> other,
    { T, U => V } combiner) { ... }
}

The question Josh asks is this: which version of this API would you prefer see?

The point he makes is that function types enable (he says "encourage") an "exotic" style of programming - functional programming - which should be discouraged, otherwise the entire platform will become infected with unreadable code. Although functional programming is just as possible with or without function types - they are just shorthand for interface types, after all - Josh prefers the language provide syntactic vinegar for these techniques.

Part of his talk was about the problems of being able to use nonlocal return by default in a closure. See my previous blog post for a description of how this theoretical problem won't exist in the next version of the spec, and doesn't exist in the prototype today.

Finally, Josh showed that if you want to use something like eachEntry to loop over a map, and you want to be able to use primitive types for the loop variables, autoboxing doesn't work and you'd have to define 81 different versions of the eachEntry method (one for each possible primitive type in each position). That's true, just as it's true that you'd have to define 81 different versions of the Map API if you want to be able to handle primitives in them. If it turns out to be a good idea to make autoboxing work for the incoming arguments to a closure, that is a small tweak to the closure conversion. These kinds of issues can be addressed in a JSR.

Josh's vision for an alternative is Concise Instance Creation Expressions along with adding a moderate number of new statement forms.

Restricted Closures

2007-12-03T23:16:00.000-08:00

Note: this discusses a feature of the Closures specification that was published back in February, but which is likely to change in an upcoming revision.

The Closures for Java specification, version 0.5, contains a special marker interface java.lang.RestrictedFunction. When a closure is converted to an interface that extends RestrictedFunction, this prevents the closure from doing certain operations. Specifically, it prevents accessing mutated local variables from an enclosing scope, or using a break, continue, or return to a target outside the closure. The idea is that APIs that are intended to be used in a concurrent setting would want to receive restricted rather than unrestricted closures to prevent programmers from shooting themselves in the foot.

Two weeks ago Mark Mahieu contacted me regarding his experience with the closures version of the fork-join framework. Because I had ported that API before I had implemented any of the operations that would be restricted, and before RestrictedFunction itself, I had simply not provided any restrictions at all. Mark was wondering how to do it:

I hadn't looked at the jsr166y javadoc before you linked to it on your blog, so I had the chance to compare the two versions on equal terms, and I can honestly say that I found the closures version of the API to be much more approachable at first blush. I also suspect that the majority of the Java programmers I work with would feel the same way, once comfortable with function type syntax.

One thing I did wonder was whether a method like ParallelArray.combine() could be declared as:
public <U,V,C extends {T,U=>V} & RestrictedFunction> ParallelArray<V> combine(ParallelArray<U> other, C combiner) { ... }
but my reading of the specification suggests that the type C won't be a valid target for closure conversion. Maybe I'm being greedy, but in certain cases (jsr166y being a good example) I'd ideally want both the clarity provided by using function types in place of a multitude of interfaces, and the compile-time checking afforded by RestrictedFunction. Having said that, I think the additional type parameter above negates those gains in clarity somewhat, even if it were an option.

I responded, describing what I had been planning to do in the next minor update of the spec:

I expect to make that work. However, I hope it won't be necessary. I expect to support function types like
{T,U=>V}&RestrictedFunction
directly. For example
public <U,V> ParallelArray<V> combine(ParallelArray<U> other, {T,U=>V}&RestrictedFunction combiner) { ... }
You will be allowed to intersect a function type with non-generic marker interfaces such as RestrictedFunction, Serializable, etc. Unfortunately, I will have to rev the spec to support this.

Since that time I've been discussing this issue with a number of people. Some, who believe that the concurrent use cases are primary, or who believe that "Mort" programmers will blithely copy-and-paste code from anonymous inner classes (which have different semantics) into closures, suggest that the default is backwards: closures and function types should be restricted unless specific action is taken to make them otherwise. Reversing the sense of the marker interface doesn't work (it violates subtype substitutability), but there may be other ways to accomplish it. On the other hand, there are others who believe the synchronous use cases, such as control APIs, are primary (even when used in a concurrent setting), and prefer not to see the language cluttered with support for the restictions at all. Instead, they would prefer that any such restrictions take the form of warnings (which the programmer might suppress or ask javac to escalate to errors). I have sympathy for both camps.

Another possibility would be to produce a warning whenever you use a nonlocal transfer at all and do away with RestrictedFunction. The way to suppress the warning would be with a @SuppressWarning("nonlocal-transfer") annotation. Could we make it an error instead of a warning? This may make the interface easier to read, but it doesn't give the API designer any way to express a preference. It may make control APIs painful to use.

Finally, it would be possible to use a different syntax for restricted and unrestricted function types and closures. For example, one using the => token would be restricted, not allowing nonlocal transfers. One using a different token such as ==> or #> would be unrestricted, allowing nonlocal transfers. The idea is that if you want an unrestricted closure, you'd have to use the slightly more awkward syntax, and the receiving type must also be of the unrestricted variety. The control invocation syntax would be defined in terms of the unrestricted form. This enables API designers to express a preference for whether or not clients would be allowed to write unrestricted closures (and therefore, whether or not they would be allowed to use the control invocation syntax).

This can be made to work using only concepts already in the spec. The unrestricted form of a function type would be defined as an interface type as in the current spec. The restricted form would be the same but with RestrictedFunction mixed in. With this approach there is no need for the explicit "&" conjunction-type syntax for function types.

Closures Prototype Update and Extension Methods

2007-11-20T19:20:00.000-08:00

Closures Prototype Update

The Closures for Java prototype now allows a closure to access mutated local variables from an enclosing scope. You can download the prototype here. You can also download the sources for the rewritten parts of Doug Lea's fork-join library, ported to use function types. It is a good example of how APIs can be affected by these language changes. Personally, I find the API simplifications to be quite compelling. If you're on the fence about function types, I recommend you have a look. Any feedback you may have is most welcome!

I mentioned previously that I'm working on a number of smaller language features, which hopefully will be considered for JDK7. For now, I'd like to talk about just one of them.

Extension Methods

Once an API has been published, you can't add methods to it without breaking backward compatibility. That's because implementations of the old version of the interface don't provide an implementation of any new methods. You can use abstract classes instead of interfaces, and only add concrete methods in the future. Unfortunately, that limits you to single inheritance.

One way API designers work around this limitation is to add new functionality to an interface by writing static utility functions. For example, java.util.Collection.sort acts as an extension of java.util.List. But such methods are less convenient to use, and code written using them is more difficult to read.

Extension methods enable programmers to provide additional methods that clients of an interface can elect use as if they are members of the interface. Todd Millstain's Expanders are the most full-featured version of this feature. The simplest version of this feature that I advocate would be to enable statically-imported methods to be used as if members of their first argument type. For example:


    import static java.util.Collections.sort;
    ...
    List<String> list = ...;
    list.sort();

Extension methods are completely orthogonal to closures, but they enable a number of typical functional-style programming patterns to be expressed more directly in Java using extension methods that accept closures.

Java Closures: first prototype

2007-10-28T17:05:00.000-07:00

I've finally had some time to make progress on a prototype of closures. If you want to see what an API looks like, you can compare Doug Lea's jsr166y fork-join framework to the same API ported to use the language features of the prototype.

If you want to try it, you can download an executable version of the prototype here. Make sure a JDK6 version of java and javac are on your path. This is binary-licensed under the JRL, but if a JSR is created I expect to license it under GPLv2. There are a few small test cases included.

This prototype supports

the BGGA function type syntax
closure literals
the closure conversion
the null type, disjunctive types, and exception transparency
definite assignment
Unreachable and completion transparency.
Catching multiple exceptions at once like catch(X1|X2 ex) { ...
[not closely related to closures but the implementation was simple once closures are there]

This prototype does not yet support

a closure using a mutated variable from the enclosing scope
nonlocal control-flow (break, return, and continue)
the control invocation statement and loop abstractions

I'm intentionally distributing it before these features are available. The idea is that people can try this version, and compare it to the next version with these features working.

Separately, I'm working on a set of smaller language extensions for JDK7, some of which interact very nicely with Closures. For example, "extension methods" enable you to have the effect of adding methods to existing interfaces (e.g. adding "each", "filter", etc to Collection) without breaking backward compatibility. I'll write more about these over the next few days.

This is still rough around the edges, but any feedback you have is most welcome.

Internal Versus External Iterators

2007-07-31T00:27:00.000-07:00

In the "Gang Of Four" Patterns book's discussion of the Iterator pattern, we read (page 260):

Who controls the iteration? A fundamental issue is deciding which party controls the iteration, the iterator or the client that uses the iterator. When the client controls the iteration, the iterator is called an external iterator (C++ and Java), and when the iterator controls it, the iterator is an internal iterator (Lisp and functional languages). Clients that use an external iterator must advance the traversal and request the next element explicitly from the iterator. In contrast, the client hands an internal iterator an operation to perform, and the iterator applies that operation to every element in the aggregate.

External iterators are more flexible than internal iterators. It's easy to compare two collections for equality with an external iterator, for example, but it's practically impossible with internal iterators. Internal iterators are especially weak in a language like C++ that does not provide anonymous functions, closures, or continuations like Smalltalk and CLOS. But on the other hand, internal iterators are easier to use, because they define the iteration logic for you.

To make this very concrete, one might define a collection-like interface using external iterators like this:

public interface ExternalIterable<T> {
    ExternalIterator<T> iterator();
}
public interface ExternalIterator<T> {
    T next();
    boolean hasNext();
}

On the other hand, using internal iterators one might define an interface something like this:

public interface InternalIterable<T> {
    void iterate(Function<T> closure);
}
public interface Function<T> {
    void invoke(T t);
}

Languages with well-integrated support for closures (such as Scala, Smalltalk, and Ruby) usually provide support for looping over their collections using internal iterators - they are, after all, easier to use in most cases - while other object-oriented languages (such as C++, Java, and C#) tend to use external iterators. Without well-integrated language support for closures, internal iterators would be too painful to use effectively. For that reason, the Java collection framework uses external iterators. But once we have closures in the language, wouldn't it be worth reversing that decision?

The answer is no, and it isn't just because it would be an incompatible change to an existing interface. As discussed above, external iterators are more flexible for some clients. The simpler code that clients can write using internal iterators is already achieved in many clients (of external iterators) due to the previous addition of the for-each loop in JDK5. For the remaining clients, simple library methods can bridge the gap between internal and external iterators. See, for example, the "eachEntry" method for iterating over the entries of a map, discussed in my earlier postings on closures. To see how easy the conversion is, here is the code to convert from an external iterator to an internal one:

    public <T> InternalIterable<T> internalize(final ExternalIterable<T> ext) {
        return new InternalIterable<T>() {
            public void iterate(Function<T> closure) {
                for (ExternalIterator<T> it = ext.iterator(); it.hasNext(); ) {
                    closure.invoke(it.next());
                }
            }
        };
    }

Iteration using internal iterators is often much easier to implement, because the iterator implementation doesn't have to explicitly store and manage the state of the iteration. Much of the complexity in the implementation of the iterators for Java's HashMap and TreeMap (and their Set cousins) would simply vanish if the iterators were internal. For that reason, it is interesting to see if it is possible to have the iterator implemented internally, but exposed to the client externally, by writing a utility method that converts between the two iterable interfaces. This is the reverse of the conversion above. How easy this is to implement depends on the features of your programming language.

C# provides a "yield return" construct that helps provide the convenience of implementing internal iterators and the flexibility of using external iterators. But it is not quite powerful enough to bridge the gap between them. See notes from Cyrus Najmabadi's attempt to do so. Neither are simple (local) byte-code rewriting systems such as Aviad Ben Dov's Yielder Framework for Java. You can do it using continuations, coroutines, or fibers. But Java doesn't have them.

You can solve the problem in Java by resorting to the use of a separate thread to simulate coroutines. The result is messy and expensive, as each converted external iterator requires its own thread. Here is my implementation; can you do better?

Constructor Type Inference

2007-07-05T22:40:00.000-07:00

One of the ideas for improving the Java Programming Language is "type inference" on variable declarations. The idea is to simplify a pattern of code that now appears in programs due to generics:

Map<String,List<Thing>> map = new HashMap<String,List<Thing>>();

surely we shouldn't have to give the same type parameters twice? The simplest proposal to relieve this redundancy allows

map := new HashMap<String,List<Thing>>();

This introduces the new colon-equals token and the declaration-assignment statement. The variable appearing on the left-hand-side of the statement is implicitly defined by this statement, and its type is the type of the expression on the right-hand-side. I don't like this proposal. It both goes too far and not far enough.

It goes too far in that it allows the programmer to elide the type in a variable declaration. The type in a variable declaration is valuable documentation that helps the reader understand the program, and this proposal reduces the readability of programs by allowing it to be elided. Worse, it assigns the wrong type to the variable. Following Effective Java (first edition, item 34), the type of a declared variable should be an interface type. This statement form forces the variable to be of the (likely more specific) type of the right-hand-side. Consequently, the programmer may inadvertently depend on features of the concrete implementation class when using the variable. That would make it more difficult to modify the program later by selecting a different implementation type.

This syntax doesn't go far enough because the verbosity of creating generic classes is worth eliminating in other contexts as well. Programmers today work around the verbosity by providing static factory methods corresponding to constructors:

static <K,V> HashMap<K,V> makeHashMap() {
    return new HashMap<K,V>();
}

This addresses the immediate problem:

Map<String,List<String>> map = makeHashMap();

Unfortunately, this idiom replaces one form of boilerplate (in variable initialization) with another: trivial static factories. A generic class is typically created more than once, so adding a single static factory can simplify the code at every creation site. But with language support, we can do better.

I propose a new form of class instance creation expression:

Map<String,List<Thing>> map = new HashMap<>();

Using empty type parameters on a class instance creation expression asks the language/compiler to perform type inference, selecting appropriate type parameters exactly as it would in the invocation of the equivalent trivial static factory.

Type inference today works on the right-hand-side of an assignment. I also propose that we enable this new form to be used in more situations by improving type inference for expressions appearing in other contexts:

the argument of a method call
the receiver of a method call
the argument of a constructor
the argument of an alternate constructor invocation

This would enable generic methods to be invoked in these contexts without providing explicit type parameters.

Removing Language Features?

2007-05-26T10:07:00.000-07:00

As a language grows by the addition of features, it necessarily gets more complex. After all, you can't remove existing language features because existing programs use those features, but each additional feature adds complexity. Right?

Fellow Googler Matt Shulman asked me a question about the Closures for Java specification. He observed that much of the complexity arises because of support for checked exceptions in the spec. Things like throws type parameters, disjunctive types, and throws clauses on function interfaces would be unnecessary without checked exceptions. Matt asked me if we had considered if things would be simpler without all that. At first I misunderstood his question to be referring to just the Closures specification, so I answered that the facility wouldn't fit into the language as well without support for checked exceptions.

Matt clarified that he was asking not just about removing support for checked exceptions from the Closures spec, but from the entire programming language.

There has been an ongoing debate on the utility of checked exceptions. Many people are critical of Java's checked exceptions, characterizing them as a failed experiment in software engineering. In practice, checked exceptions can result in API complexity, and programs appear to be cluttered with exception handling code just to satisfy the compiler. Some people believe checked exceptions are a good language feature but are misused, even in the JDK. With the "experts" being such poor role models, how can we expect ordinary Java programmers to do better?

We did a Google search to see how many people have written in support of checked exceptions and how many people don't like them. The discussion seems to be lopsided against checked exceptions, but on the other hand that may be due to the fact that checked exceptions are the status quo.

This isn't a question I had thought much about. I believe the language could be simplified by treating all exception types as unchecked without breaking existing programs. This could also result in a simplification of future language extensions and APIs. But would the language and platform be better off without checked exceptions?

A Limitation of Super Type Tokens

2007-05-20T19:01:00.000-07:00

Watching Josh Bloch's presentation at JavaOne about new topics in the second edition of Effective Java makes me want to go out and get my own copy. Unfortunately, he's not scheduled to have the new edition in print until later this year.

There was a coincidental adjacency between two slides in Josh's talk that made me think a bit more about the idea of Super Type Tokens. The last slide of his discussion of generics gave a complete implementation of the mind-expanding Typesafe Heterogenous Containers (THC) pattern using Super Type Tokens:

import java.lang.reflect.*;

public abstract class TypeRef<T> {
    private final Type type;
    protected TypeRef() {
        ParameterizedType superclass = (ParameterizedType)
            getClass().getGenericSuperclass();
        type = superclass.getActualTypeArguments()[0];
    }
    @Override public boolean equals (Object o) {
        return o instanceof TypeRef &&
            ((TypeRef)o).type.equals(type);
    }
    @Override public int hashCode() {
        return type.hashCode();
    }
}

public class Favorites2 {
    private Map<TypeRef<?>, Object> favorites =
        new HashMap< TypeRef<?> , Object>();
    public <T> void setFavorite(TypeRef<T> type, T thing) {
        favorites.put(type, thing);
    }
    @SuppressWarning("unchecked")
    public <T> T getFavorite(TypeRef<T> type) {
        return (T) favorites.get(type);
    }
    public static void main(String[] args) {
        Favorites2 f = new Favorites2();
        List<String> stooges = Arrays.asList(
            "Larry", "Moe", "Curly");
        f.setFavorite(new TypeRef<List<String>>(){}, stooges);
        List<String> ls = f.getFavorite(
            new TypeRef<List<String>>(){});
    }
}

But on the very next slide, the very first bullet of the summary of his presentation reminds us

Don't ignore compiler warnings.

This was referring to Josh's advice earlier in the presentation not to ignore or suppress unchecked compiler warnings without trying to understand them. Ideally, you should only suppress these warnings when you have good reason to believe that the code is type-safe, even though you might not be able to convince the compiler of that fact.

The method Favorites2.getFavorite, above, is annotated to suppress a warning from the compiler. Without that annotation, the compiler complains about the cast to the type T, a type parameter. Is this code demonstrably type safe? Is it possible to cause this cast to fail using code that is otherwise completely type safe? Unfortunately, the cast is not safe:

class Oops {
    static Favorites2 f = new Favorites2();

    static <T> List<T> favoriteList() {
        TypeRef<List<T>> ref = new TypeRef<List<T>>(){};
        List<T> result = f.getFavorite(ref);
        if (result == null) {
            result = new ArrayList<T>();
            f.setFavorite(ref, result);
        }
        return result;
    }

    public static void main(String[] args) {
        List<String> ls = favoriteList();
        List<Integer> li = favoriteList();
        li.add(1);
        for (String s : ls) System.out.println(s);
    }
}

This program compiles without warning, but it exposes the loopole in the type system created by the cast to T in Favorites2.getFavorite. The compiler's warning does, after all, tell us about a weakness in the type safety of the program.

The issue is a subtle one: TypeRef treats two types as the same when the underlying java.lang.reflect.Type objects are equal. A given java.lang.reflect.Type object represents a particular static type appearing in the source, but if it is a type variable it can represent a different dynamic type from one point in the program's execution to another. The program Oops exploits that mismatch.

The Super Type Token pattern can be redeemed by disallowing the use of type variables anywhere in the Type object it stores. That can be enforced at runtime (but not at compile time) in the constructor.

Perhaps a better solution would be to reify generics (i.e., "erase erasure") in the language, making all this nonsense unnecessary.

A Consensus Closures JSR Proposal

2007-04-27T09:12:00.000-07:00

I had set aside work on the closures prototype for a couple of months to write a JSR proposal that represents a consensus among the folks thinking about this area. You can find it at http://www.javac.info/consensus-closures-jsr.html. One of the things I learned is that unanimous agreement is rarely possible. There are those who feel that nothing should be done to the Java programming language, and such people will not be swayed by simple but powerful additions. Our latest JSR proposal comes as close to achieving consensus as I believe possible. All but one of the authors of the three widely-discussed closures proposals have agreed to support it.

The purpose of the JSR proposal is to define the problems to be solved and circumscribe the permitted solution space. It doesn't mandate a particular solution, though it does offer the Closures for Java specification as an example of a solution to many (but not all) of the problems. This should not be surprising, as that spec was written specifically in an attempt to satisfy the requirements. Still, the spec is a work in progress.

So what is next? I hope we'll have some active discussion at JavaOne about where to go from here.

Closures for Organizing Your Code

2007-03-29T02:09:00.000-07:00

Much of the discussion of Closures in Java has been about they way they affect public APIs. But there is another aspect that is just as important: the way closures affect private APIs between parts of your program. Closures often enable a tremendous simplification of a program design compared to what would be required in their absence. The following describes my implementation of a graph algorithm for computing the Jeffersonians of a graph using algorithm K from Knuth's The Art of Computer Programming, volume 4B, section 7.5.7.

As you may be aware the set of Jeffersonians of a graph is best computed using a complex recursive algorithm. Although recursive algorithms can be translated into algorithms without using recursion (Java without recursion remains Turing-complete), the recursive version of the algorithm is much shorter and easier to understand. We're lucky to be living in an age in which virtually all programming languages support recursion. Though details of the implementation are not important, my implementation went something like this:

public Collection<Jeffersonian> findAllJeffersonians(Graph g) {
    Collection<Jeffersonian> result = new ArrayList<Jeffersonian>();
    findAllJeffersoniansInternal(g, result);
    return result;
}

The idea is that the recursive part of the algorithm can pass around the collection into which the result will be placed, and every Jeffersonian that is found will be placed into the collection:

private void findAllJeffersoniansInternal(
        Graph g, Collection<Jeffersonian> result) {
    // complex recursive algorithm here
    Jeffersonian found = ...;
    result.add(found);
    // more complex recursion here
}

One pot of coffee and an all-nighter later I had this working like a charm. The next day my tech lead asked me to add an API element that determines whether or not a graph has a Jeffersonian or not. That was easy:

public boolean hasJeffersonian(Graph g) {
    return findAllJeffersonians(g).size() != 0;
}

This didn't pass code review. The problem is that this new method is to be used in the inner loop of Google's über-secret application that will take over the world. Never mind that. The problem is performance. Determining whether or not a graph has a Jeffersonian can be done in linear time, but enumerating all of them requires quadratic time (or worse). But my implementation does it the hard way. By then it was Friday afternoon and I really wanted to head home for a glass of wine, so I did what any self-loathing software engineer would do: I cut and pasted the complex recursive code in findAllJeffersoniansInternal into hasJeffersonianInternal and added a boolean return value (true when a Jeffersonian was found). Then I added logic to short-circuit the rest of the algorithm once a Jeffersonian had been found at any step. The code was messy but workable, and I had it passing tests in less than an hour. The code duplication left me somewhat uncomfortable, but the two methods were different enough that merging them would have been hard. I considered adding a second flag so I could have one body of code to do both versions, but I decided to leave that refactoring until Monday.

Something very strange happened over the weekend, though. On Monday my pointy-haired boss told me there was both good news and bad news, and asked which I wanted first. Knowing how these jokes work (the second one always trumps the first) I asked for the bad news first. The bad news was that my machine had crashed, losing all of my work from Friday. Including my implementation of hasJeffersonian. The good news was that my machine had been replaced with a brand new one, a fast new 40-core workstation, and it came with JDK7 preinstalled. I had been using JDK6 before, so I was eager to try the new Java language features.

Taking a fresh look at the problem of writing hasJeffersonian, I decided to refactor the original program to pass a closure instead of a collection:

public Collection<Jeffersonian> findAllJeffersonians(Graph g) {
    Collection<Jeffersonian> result = new ArrayList<Jeffersonian>();
    findAllJeffersoniansInternal(g, { Jeffersonian j => result.add(j); });
    return result;
}

private void findAllJeffersoniansInternal(
        Graph g, {Jeffersonian => void} foundJeffersonian) {
    // complex recursive algorithm here
    Jeffersonian found = ...;
    foundJeffersonian.invoke(found);
    // more complex recursion here
}

Then I realized I could use the nicer syntax allowed for passing a closure to a method:

public Collection<Jeffersonian> findAllJeffersonians(Graph g) {
    Collection<Jeffersonian> result = new ArrayList<Jeffersonian>();
    findAllJeffersoniansInternal(Jeffersonian j : g) {
        result.add(j);
    }
    return result;
}

Solving the second problem was then trivial:

public boolean hasJeffersonian(Graph g) {
    findAllJeffersoniansInternal(Jeffersonian j : g) {
        return true;
    }
    return false;
}

That was the entire implementation. I had a strange sense of elation, but I couldn't quite tell why. I could no longer remember why the problem was so messy on Friday. This refactoring seemed trivial, and this code was so clear. What made it so hard before?

Then I woke up. It's 2007, not 2009. JDK7 is barely a gleam in the eye of Sun. My machine is only dual-core. Consensus on closures is elusive. As far as I can tell, there isn't any such thing as a graph's Jeffersonian, or a Google plan to take over the world. It's Monday morning, and I have to figure out how to merge two almost-copies of a big recursive algorithm.

But on the bright side, my boss is a really nice guy.

A Compact Object Comparator

2007-03-16T16:39:00.000-07:00

Every now and then a problem arises where the right solution would be to impose an arbitrary total ordering on a collection of objects. The simplest example of this is when you need to sychronize on more than one object, all at the same time, to maintain some consistency condition across those objects. Using Closures, you might invoke a utility method like this:

Locks.withLocks(lock1, lock2) {
    // code protected by both locks
}

To avoid deadlock, every piece of code that locks the same set of locks should do so in the same order. Rather than forcing all callers of the withLocks method to worry about getting them in the right order, the implementation of withLocks can sort the incoming locks. Then the caller can just pass the locks in arbitrary order, knowing that they will be locked "in the right order". It doesn't actually matter what order we sort them in, as long as we always get the same order for the same objects. The implementation of withLocks can use Collections.sort to sort the incoming locks, but java.util.concurrent.locks.Lock is not naturally comparable, so we need to pass an appropriate comparator to sort. We need a java.util.Comparator<Lock>, but a java.util.Comparator<Object> would work just as well. Let's specify, and then implement, a suitable comparator. Here is what we need:

/**
 * Returns a comparator that imposes a complete order on all objects.
 * Each invocation of this method may yield a distinct comparator,
 * or may yield the same comparator.
 */
public Comparator<Object> totalOrder() { ... }

How are we going to do this? One idea is to create an assignment of long values to each object, as needed. That would look something like this:

public Comparator<Object> totalOrder() { return new TotalOrder(); }
private class TotalOrder implements Comparator<Object> {
    long nextNonce = 1;
    Map<Object,Long> codes = new IdentityHashMap<Object,Long>();
    public int compare(Object o1, Object o2) {
        Long l1 = getNonce(o1);
        Long l2 = getNonce(o2);
        return l1.compareTo(l2);
    }
    synchronized Long getNonce(Object o) {
        Long nonce = codes.get(o);
        if (nonce == null) {
            nonce = nextNonce++;
            codes.put(o, nonce);
        }
        return nonce;
    }
}

There are two major problems with this approach. First, it causes object retention. Objects whose space would otherwise be recovered by the garbage collector are retained because they are reachable as keys in the codes map. We can't fix this by simply using a WeakHashMap; without the identity semantics of IdentityHashMap the technique doesn't work. We really need WeakIdentityHashMap for this, but no such class exists in the JDK yet. Fortunately, "crazy" Bob Lee has come to the rescue with an implementation of this concept inside the recently open-sourced Guice dependency injection framework. I think this belongs in the JDK, and now is the time to propose it for JDK7.

The other problem with this implementation is that this utility takes up too much space. In general, every time you call the compare method one or two objects might be created and added to the map.

Another idea for implementing this utility is to sort the objects based on their identity hash code. Identity hash codes are well distributed, almost like random numbers. That is naturally thread-safe, and would look something like this:

private class TotalOrder implements Comparator<Object> {
    public int compare(Object o1, Object o2) {
        if (o1==o2) return 0;
        int i1 = System.identityHashCode(o1);
        int i2 = System.identityHashCode(o2);
        return (i1<i2) ? -1 : (i1==i2) ? 0 : 1;
    }
}

This is much more compact than the previous approach. But because identity has codes are not guaranteed to be unique, it occasionally treats two distinct objects as equal.

We can get the best of both worlds - a space-efficient comparator and a complete order - by combining the two approaches:

private class TotalOrder implements Comparator<Object> {
    long nextNonce = 1;
    Map<Object,Long> codes = new IdentityHashMap<Object,Long>();
    synchronized Long getNonce(Object o) {
        Long nonce = codes.get(o);
        if (nonce == null) {
            nonce = nextNonce++;
            codes.put(o, nonce);
        }
        return nonce;
    }
    public int compare(Object o1, Object o2) {
        if (o1==o2) return 0;
        int i1 = System.identityHashCode(o1);
        int i2 = System.identityHashCode(o2);
        if (i1 != i2) return (i1<i2) ? -1 : 1;
        Long l1 = getNonce(o1);
        Long l2 = getNonce(o2);
        return l1.compareTo(l2);
    }
}

By the way, if you haven't already checked it out, see "crazy" Bob Lee's Guice dependency injection framework. We use it extensively at Google. By really taking advantage of recent language features such as generics and annotations, the Guice framework is very flexible and yet much simpler than existing frameworks. Throw away your XML and write your Java code in Java!

thanks to "crazy" Bob Lee for contributing the Guice framework, and for reviewing this essay.

On The Expressive Power of Programming Languages

2007-03-08T08:05:00.000-08:00

There are at least three separate proposals recently put forward in the space of "Closures for Java." Among the criteria for evaluating the proposals, I'd like to discuss two: conciseness (possibly phrased as convenience) of code using the construct, and expressiveness. Conciseness is pretty obvious, and you can compare the proposals on this measure by writing snippets of code that do basically the same thing as each other, but written using existing constructs and then each of the proposed constructs. How many characters, or tokens, does it take to write the code? By the measure of conciseness, shorter is better.

Unfortunately, the authors of the various proposals don't appear to be using a common meaning for "expressiveness" or "expressive power." Consequently, we often end up talking at cross-purposes when comparing the proposals. Some people appear to treat "expressiveness" and "conciseness" as synonyms, but to me these have completely different meanings. Expressiveness is a bit harder to measure, but in some ways more important at this stage of the discussion. See Matthias Felleisen's, On the Expressive Power of Programming Languages, 3rd European Symposium on Programming, Copenhagen, Denmark, 1990, http://citeseer.ist.psu.edu/felleisen90expressive.html, for one attempt to formally capture the meaning of expressiveness.

In my mind, a language construct is expressive if it enables you to write (and use) an API that can't be written (and used) without the construct. In the context of the Closures for Java proposed language extension, control abstraction APIs are the kind of thing that don't seem to be supported by the competing proposals. You don't see the proposals compared side-by-side on this measure because this is something only supported by one proposal. Programmers who have become accustomed to programming with closures find them very useful for factoring out common code in ways that are not currently possible in Java. See, for example, http://www.joelonsoftware.com/items/2006/08/01.html, http://ivan.truemesh.com/archives/000637.html, http://www.talios.com/dear_java_i_need_closure.htm, and http://blog.moertel.com/articles/2005/08/30/closures-and-the-professional-programmer. These kinds of uses might not occur to you if you're mainly a Java programmer, because Java doesn't reward you for thinking this way. But this is another example of expressive power.

I'm not particularly attached to one syntax or another for closures. I don't mean to say that syntax isn't important. Anyone who knows the story of variance and wildcards knows how much I value a good surface syntax. Our proposal describes a particular syntax not because we believe it is the best possible syntax, but because it is hard to write a specific proposal without some syntax. Ultimately, I hope the closures issue becomes a JSR and the expert group takes its time to decide what surface syntax is best. But I believe that the expressiveness of the Closures for Java proposal is the most important reason to consider doing anything in this space at all. If it is just a matter of a slightly more concise syntax, I'm not sure it is worth the trouble.

Java Closures versus MouseListener

2007-03-05T21:24:00.000-08:00

The Closures for Java proposal simplifies the code for many purposes where anonymous class instance creation expressions are currently used. When the anonymous class's supertype is an interface with a single abstract method, a closure can be used directly. But if the supertype is a class, like java.util.TimerTask, or has more than one method, like java.awt.event.MouseListener, then you can't use a closure directly. You can still use an anonymous inner class directly, as always, but there are ways of using closures that may be more convenient. For TimerTask, a client can be written this way

void printHelloAfterDelay(java.util.Timer timer, long delay) {
    timer.schedule(TimerTask.of({ => System.out.println("Hello"); }), delay);
}

if we add the following utility method to TimerTask:

public TimerTask of(final Runnable block) {
    class ClosureTimerTask extends TimerTask {
        public void run() { block.run(); }
    }
    return new ClosureTimerTask();
}

Similarly, Peter von der Ahé showed me how to use the builder pattern, along with closures, to simplify handling mouse events:

void addSomeActions(java.awt.Component foo) {
    foo.addMouseListener(new MouseListenerBuilder() 
        .setMouseClicked({ MouseEvent e => System.out.println("Mouse clicked"); })
        .setMouseReleased({ MouseEvent e => System.out.println("Mouse released"); })
        .setMouseEntered({ MouseEvent e => System.out.println("Mouse entered " + e.getComponent()); }));
}

The implementation of MouseListenerBuilder is left as an exercise to the reader.

Closures Spec Update (v0.5)

2007-02-05T10:33:00.000-08:00

This post discusses a draft proposal for adding support for closures to the Java programming language for the Dolphin (JDK 7) release. It was carefully designed to interoperate with the current idiom of one-method interfaces. The latest version of the proposal and a prototype can be found at http://www.javac.info/.

We've just updated the Closures for Java specification, bringing it to v0.5. There are two significant changes:

We've dropped the nominal version of the specification. We are no longer maintaining parallel versions of the specification (with and without function types) because the most significant concerns regarding function types were resolved in earlier revisions of the spec.
We added support for user-defined looping APIs. I wrote about this in October 2006, but did not integrate that into the spec until now.

There is now a two-hour version of my Closures for Java talk on video. It is the same as the one-hour version but with questions and answers both during and after the talk.

A Definition of Closures

2007-01-28T14:11:00.000-08:00

There has been some confusion over our proposal to add closures to the Java Programming Language. After all, doesn't Java already have closures in the form of anonymous inner classes? What is the point of adding something to the language that it already has? To some there appears to be a lot in the proposal that has nothing to do with closures, including the control invocation syntax, null as a type, Unreachable, throws type parameters, function interface types, and "nonlocal" returns. In my Javapolis talk I tried to give an explanation for why these features are in the proposal from the practical point of view of what kinds of things would be possible that were not formerly possible. But that begs the question: why do we call it "Closures" for Java? In this blog post I'll try to show how the definition of closures relates to the features of the proposal, and identify which features of the proposal do (and which do not) result from the definition.

Before discussing the definition of closures, it helps to understand the historical context in which the term was introduced.

Lisp was created in the late 1950's by John McCarthy and others at M.I.T. One feature of the language was function-valued expressions, signified by lambda. The name "lambda" was borrowed from a mathematical formalism known as the lambda calculus. Although Lisp was not based on an effort to model that formalism, lambda plays approximately the same role in Lisp as it does in the lambda calculus: lambda is the syntax for a function-valued expression. McCarthy's intent was that Lisp should be designed to be implemented very efficiently, ideally compiled. That desire for efficiency influenced the design of the language.

Lisp used something called dynamic scoping. Logically, in a dynamically scoped language, when a variable reference is evaluated the runtime looks up the call stack until it finds a scope in which a variable of that name is defined. But as a practical matter variable references in a dynamically scoped language can be resolved in constant time simply by maintaining a value cell for each variable name; that value cell caches the variable's current definition. Dynamic scoping is easy to implement in an interpreter or compiler. Some very clever people had found ways to not only take advantage of dynamic scoping, but had developed what would now be thought of as programming patterns that depended deeply on it. But it was soon discovered that dynamic scoping suffered subtle problems, something the Lisp community called the FUNARG problem.

Now we fast-forward to the mid 1970's. On the radio you would hear¹ Elton John, Emerson Lake & Palmer, Joni Mitchell, The Captain and Tennille, John Denver, Paul Simon, Paul McCartney and Wings, ABBA, David Bowie, Janis Ian, Aerosmith, Fleetwood Mac, Heart, and Queen. A number of popular Lisp dialects were in use including InterLisp, MacLisp, UCI-Lisp, Stanford Lisp 1.6, and U. Utah's Standard Lisp. All of them were dynamically scoped. It was in this context that Guy Steele and Gerald Jay Sussman developed Scheme, a very simple Lisp dialect.

One thing about Scheme was different². Scheme was lexically scoped, like the lambda calculus and most mathematical notations, which means that a variable reference binds to the lexically enclosing definition for that name that was active at the time the enclosing lambda form was evaluated. To explain the semantics in terms of the implementation, evaluating a lambda expression was said to produce a closure. This is a function value represented as an object that contains references to the current bindings for all the variables used inside the lambda expression but defined outside it. These are called the free variables. When this closure object, or function, is applied to arguments later, the variable bindings that had been captured in the closure are used to give meaning to the free variables appearing in the code. The term closure describes more than just the abstract language construct, it also describes its implementation.

To many in the Lisp community at the time, it didn't make sense to adopt a Lisp dialect with closures. Not only would it undermine common programming techniques but it would obviously be much less efficient. For a short time these issues were debated, and Guy Steele wrote a series of papers entitled Lambda the Ultimate _____ (where _____ is Imperative, Declarative, GOTO, or Opcode) to help explain the power of lexically scoped lambda (closures). Fast forward only a few years and the debate was largely settled: lexical scoping is Right and dynamic scoping is Wrong and we've all learned our lesson. Since that time the word closure is used to mean lexically scoped anonymous function, but the connotation is that it is possible to get the semantics wrong for any number of reasons, including bugs and concerns about implementation efficiency. It also hints that we should let the language design drive the implementation, not the other way around. Virtually every programming language, whether or not it has something like lambda and anonymous function values, uses lexical rather than dynamic scoping. The basic definition of a closure, however, shows its Lisp roots:

A closure is a function that captures the bindings of free variables in its lexical context.

Around this time, Smalltalk was introduced. Smalltalk is the most pure and simple of the object-oriented languages: everything is an object. Object-oriented languages add a twist to lexical scoping. Rather than binding all names in the lexical scope, free variables appearing in methods are bound in the scope of the object that the method is a member of. In other words, names in a method are bound to members of the "current" object. The current object is accessible by the name "self". Another small but interesting detail is that you can return early from a method in Smalltalk using the syntax "^expression". We'll return (no pun intended) to the significance of this fact later.

Methods aren't the only kind of code abstraction in Smalltalk. There is also an expression form for writing a block expression, which is essentially a lambda. Early dialects had limitations on them, but most modern Smalltalks do not. They are a true analog to Scheme's lambda. Free variables in a Smalltalk block are bound in the enclosing scope, which is typically the scope of some enclosing method. The result of evaluating a block expression is a closure, and like everything else it is an object. In this case the object has a method that you use to invoke the code of the block.

Anonymous functions (closures) were not blindly introduced into Smalltalk just because it seemed like a neat idea, or because they had worked out well in another language. Rather they were integrated fully and carefully into the language. Anonymous functions can properly be integrated into even an existing language, but there is an advantage when adding them early. As Guy Steele's papers demonstrated, they are so powerful that they subsume other language features. If you add them early, you might save yourself the trouble of adding language features that can instead be added as libraries. Smalltalk provides few control constructs directly in the language. Even the conditional "if" is provided as a library method and invoked using blocks.

Two things distinguish blocks in Smalltalk from Scheme's lambda. First, the meaning of "self" within a block refers to whatever meaning it had in the enclosing context. Specifically, it doesn't refer to the closure object itself. Second, the syntax for returning from a method, "^expression", returns from the enclosing method; it doesn't return from the method representing the closure invocation. These two details are a natural consequence of the fact that, while Scheme has only one lexically scoped language construct (variable bindings), Smalltalk has three lexically scoped language constructs: name bindings (like Scheme), the referent of the return syntax, and the meaning of "self". The definition of closures above mentioned only "the bindings of free variables", but that is because the definition was written for the language Scheme, and name (variable) binding is the only lexically scoped construct in Scheme. Common Lisp also has "return" and "goto", and these too are captured lexically in a closure. In order to realize the full power of closures, described in Guy Steele's lambda papers, they must capture all lexically scoped language constructs. Generalizing the definition of closure to cover other languages would require using more language-neutral terminology: instead of "bindings of free variables" we would have something like "lexically scoped semantic language constructs." However, that obscures the origins of the term.

Fast forward more than 25 years, and we're once again listening to some of the same music we listened to in the late 1970's. We are now considering adding closures to Java, a significantly more complex language than either Scheme or Smalltalk. We're not considering them because they seem like a neat idea, or because they worked out well in other languages, or because we're bored. Rather we're considering them: because of the power and flexibility they will add to the programmer's arsenal; because of the improved readability we expect from programs that use closures instead of the existing alternatives; and because of a number of other recently proposed language extensions that will be unnecessary if closures are added. In order to get the full power of closures, they should capture all lexically scoped semantic language constructs. What are the lexically scoped language constructs in Java?

The meaning of variable names.
The meaning of method names.
The meaning of type names.
The meaning of this.
The meaning of names defined as statement labels.
The referent of an unlabelled break statement.
The referent of an unlabelled continue statement.
The set of checked exceptions declared or caught.
The referent of a return statement.
The definite assignment state of variables.
The definite unassignment state of variables.
The reachability state of the code³.

In addition, Java has one other significant difference from either Scheme or Smalltalk: Java is statically typed. That means that each expression has a type at compile-time. So if we add closures, we need to have some appropriate type for a closure. Since a closure is an anonymous function, it is natural to consider adding function types to the language. But this is not a mandate. As you can see by the two variations of our closures proposal (the nominal and the functional versions) we believe it is possible to add closures without adding function types with a limited loss of functionality (higher-order programming becomes impractical). Our proposal for closures addresses every item on this checklist. There are additional features of our proposal (the control invocation syntax and the closure conversion) that don't relate directly to the definition of closures, but which make them integrate very nicely with existing language features. And there are additional features not mentioned in the spec (such as proper tail recursion) that would be helpful to realize the full potential of closures.

What about anonymous inner classes? It turns out that they don't pass muster on any item on this checklist. Let's set aside the fact that local variables from enclosing scopes must be final to be used inside an anonymous class. The problem is that variable names are simply not resolved in the correct scope. They are resolved in the scope of the anonymous class that you're creating, not the enclosing scope. If you're creating an instance of an interface then it's probably not too much of a problem because most interfaces don't have any (constant) variable definitions. But anonymous inner classes fail every other item on this checklist as well, most of them fatally. Most alternative proposals don't actually address any of the items on this list, and so fail to provide the power of closures any more than existing language constructs.

Setting aside all the programming language theory, don't anonymous inner classes provide, in practice, all of the advantages of closures? I believe I've already shown that the answer is no. It is certainly true that for any program you can write using closures, you can write a roughly equivalent program using anonymous inner classes. That's because the Java programming language is Turing-complete. But you will probably find yourself resorting to a significant and awkward refactoring of the code that has nothing to do with the purpose of the code. In fact, you can write a roughly equivalent program using assembly language if you have the stomach for such an effort. On the other hand, true closures increase the power of a language by adding to the kinds of abstractions you can express.

Acknowledgments: my thanks to Gilad Bracha, John Rose, and Guy Steele for filling me in on and fact-checking the terminology and relevant history. Any remaining historical fantasies are my own.

¹ This is Guy Steele's impression of the late 1970's music era [personal communication].

² Scheme was the first lexically scoped Lisp, but certainly not the first lexically scoped programming language. Algol60, for example, was lexically scoped. See also Landin's The Next 700 Programming Languages.

³ Arguably part of the lexical semantics or not, reachability state is valuable to capture in practice.

Video Interview at Javapolis

2007-01-19T14:46:00.000-08:00

Ted Neward interviewed me at Javapolis last month, and the video has just been posted:

Who's your friend? (frog on my shoulder)
Who are you and what do you do?
What are you presenting at Javapolis?
Why are Closures for Java important?
What are the differences between the two Closures proposals?
What kinds of problems is your proposal trying to solve?
Is Java becoming too complex?
Did Generics add complexity to the Java language?
Can OpenJDK lead to a fragmentation of the Java platform?
How does it feel to have your code now splashed out in the open?
What should I learn to be able to change the Java compiler?

You can jump to any section of the interview, or just skip the whole thing.

Primate Parts

2007-01-16T18:44:00.000-08:00

Recently Chris Lamb and friends wrote about their experience adding a feature to javac, a pastime slightly more popular than it used to be now that javac's sources have been opened under the GPL. And he found something strange:

"Anyway, it turns out that the javacc [sic] code is messy. Really really messy. But it’s the source of great amusement though, not only from the scary amount of no-op casts, misleading indenting and undocumented functions, but the lexical token for the ‘@‘ symbol is ‘MONKEYS_AT‘. No, we have no idea either."

I responded with a conditional promise to tell him the story:

"Actually, the indentation is consistent if you have your tabs set at 8 spaces, where God intended them.

"There’s a story behind MONKEYS_AT, and if you know it this little piece of code is a funny inside joke. But if you want me to tell you, you’ll have to take back your assertion that javac’s code is messy and tell me that it’s a work of art."

Chris quickly buckled to the pressure, responding by email:

"Yes, it is true - when set it to 8 spaces, it seems to look a bit
better. What I mean to say is, it's now a work of art and any blemishes
are my fault. :)

"Anyway, yes, my friends and I would really like to know this story
behind the naming of the token though -- we found it at about 3AM whilst
hacking on the javac code and it put us off our stride somewhat. ^_^"

Here's the formerly untold story of MONKEYS_AT.

During the development of the JDK5 language features, the Sun team had regular meetings with a team from Denmark that was designing and implementing the variance feature (since renamed wildcards, which is a longer and more interesting story). You can find the team member names in the paper describing the work. The Danish team was led by Mads Torgersen, and we all enjoyed a number of evenings chatting over beer. During one such session, I was discussing the work I was doing to implement annotations, and I mentioned that, unlike the "#" character that seems to have many names, there don't seem to be any alternative names for the "@" character. Mads told us that in Denmark, there are a number of names for this character, including the archaic "monkey's ass", which refers to the similarity in appearance of this character to the rear end of a monkey. We all thought this was hilarious, but perhaps a bit too risque to put in corporate-developed and publicly-visible sources. But it was just too funny to leave out. Thus I came up with the pun MONKEYS_AT. To this day that little inside joke in the sources reminds me of the team and the time we spent together.

Mads, by the way, is the one on the left. ;-)

There you have it: a disinterested observer, inclined to believe otherwise, comes to appreciate the beauty and humor of javac.

MethodNamesInPieces

2007-01-09T09:32:00.000-08:00

In Smalltalk, the name of a method being invoked is interleaved with the arguments passed to the method. Consequently it is difficult to confuse the order of arguments. In Java, on the other hand, when you invoke a method that accepts three integers it is easy to get the order wrong. The compiler has no way to detect the problem, so APIs must be carefully designed with the artificial constraint that one should avoid "too many" arguments of "compatible" types. In the context of closures, Smalltalk's syntax allows "built-in" statement forms such as if-then-else to be expressed as an ordinary method call. When we were putting together the original version of the closures proposal James Gosling suggested this idea to support do-while and if-else style syntax of user-defined control abstraction methods, something that was mentioned in the further ideas section. We placed this issue on the back burner once we found a nice syntax that works for many of the control-invocation use cases, but a recently submitted comment by Stefan Schulz on my blog reminded me of this issue. His use case is that he'd like to be able to write an API that allows him to refactor this

public String toString() {
    StringBuilder sb = new StringBuilder("[");
    boolean first = true;
    for (String s : someCollection) {
     if (first) {
            first = false;
        } else {
            sb.append(", ");
        }
        sb.append(s);
    }
    return sb.append("]").toString();
}

into this

public String toString() {
    StringBuilder sb = new StringBuilder("[");
    for each(String s : someCollection) {
        sb.append(s);
    } inBetween {
        sb.append(", ");
    }
    return sb.append("]").toString();
}

Presumably, the API method would be defined something like this:

<T> void for each(Iterable<T> it, {T=>void} body) inBetween({=>void} between) {
    boolean first = true;
    for (T t : it) {
     if (first) {
            first = false;
        } else {
            between.invoke();
        }
        body.invoke();
    }
}

A related advantage of the Smalltalk syntax is that operator overloading comes almost for free. If operator overloading is on the table for JDK7, perhaps we can kill two birds with one stone, by making the name before the first argument optional:

static BigDecimal (BigDecimal left) plus (BigDecimal right) {
    return left.add(right);
}
static BigDecimal (BigDecimal left) times (BigDecimal right) {
    return left.multiply(right);
}

This would allow you to write code like this:

static BigDecimal f(BigDecimal x, BigDecimal y, BigDecimal z) {
    return (x) plus ((y) times (z));
}

It's probably a small step from here to allowing arbitrary symbols as operator names and eliding some parens. I don't think anything is required in the VM, as we can encode these method names using some non-identifier character in the VM signature. For example, the above methods could be translated in the VM to methods with the names "each~~inBetween", "~plus", and "~times" (the number of tilde characters is the number of arguments before "parts" of the name in the method signature).

There are difficult syntax issues (for example, the each-inBetween example can also be parsed as two separate statements) and I'm not sure I would recommend any of this, but I wanted to share the idea.

Closures Talk and Spec Update

2006-12-18T20:19:00.000-08:00

My 2006 JavaPolis talk Closures for Java has now been published - slides synchronized with a soundtrack - and can be viewed online at the new Javapolis website, Parleys.com. If you're still wondering why all the fuss about closures, I recommend you listen to the talk.

We've also just published an update to the specification, version 0.4 . The specification seems to be setling down quite a bit, as the changes are minor:

The throws clause of a function type is now placed between the curly braces.
The description of function types has been rewritten to emphasize more clearly that function types are interface types rather than a separate extension to the type system.
The closure conversion can now convert a closure that has no result expression to an interface type whose function returns java.lang.Void. This change helps support completion transparency. A completion transparent method is one written such that the compiler can infer that an invocation completes normally iff the closure passed to it completes normally.
Some examples have been modified to be completion transparent.
null is now a subtype of Unreachable, and a number of small related changes. Thanks to Rémi Forax for pointing out the issues.

I hope the talk, which is less technical than the specification, makes it easier for you to evaluate the proposal and compare it to the alternatives.

Javapolis 2006

2006-12-15T12:36:00.000-08:00

I'm on my way back from Javapolis 2006, unfortunately missing the third day of the conference. One of the innovations this year was a bank of ten whiteboards where people brainstormed about the future of the Java language and platform. I had a camera with me but I realized too late that I should have taken snapshots of the contents of all those boards before I left. I hope someone else will. The only snapshots I took were the vote tallies that I discuss below.

There were three issues discussed on those boards that I'd like to share with you.

Closures

The first board contained a discussion of closures, including an informal vote of people "in favor of" and "against" adding support for closures. I gave a talk about closures yesterday afternoon, which explained the goals and design criteria, showed how they fit quite smoothly into the existing language and APIs, and more importantly explained in detail why anonymous instance creation expressions do not solve the problems closures were designed to solve. Before my talk about closures, the vote was about 55% in favor and 45% against. After my talk the vote was 71% in favor and 29% against. I don't think any "against" votes were added to the tally after my talk. There was also a BOF (Birds-Of-a-Feather) session in the evening discussing closures. Of the 20 or so attendees none admitted being against adding closures. I'm sure the fact that the BOF was scheduled opposite a free showing of Casino Royale didn't help, but I had hoped to hear from opponents more about their concerns. We discussed a number of issues and concerns, most of which had been discussed on my blog at one time or another.

One issue that I discussed with a few individuals earlier and then at the BOF was the idea of adding a statement whose purpose is to yield a result from the surrounding closure, which you could use instead of or in addition to providing a result as the last expression in the closure. It turns out that adding this feature make closures no longer suitable for expressing control abstractions. In other words, adding this feature to the language would make closures less useful! This is a very counterintuitive result. I first understood the issue by analyzing the construct using Tennent's Correspondence Principle, but it is much easier for most people to understand when the result is presented as specific examples that fail to work as expected. For now I'll leave this as an exercise to the reader, but I'll probably write more about it later. Incidentally, I believe the folks who designed Groovy got closures wrong for exactly this reason.

There was a video made of my talk that will be posted to the Javapolis website. Ted Neward also interviewed me on video, and Bill Venners interviewed me on audio. As soon as these are available on the web I'll blog pointers to them.

Native XML Support

Mark Reinhold gave a talk on adding native (i.e. language-level) support for XML into Java. Though they were not presented as such, some people prefer to think of the proposal as separable into a language extension part and an API part. The proposed APIs appear to be an improvement over the existing alternatives. However, the language extension for writing XML literals appears to be only marginally more convenient than the XML construction techniques provided by libraries in JDOM. I personally would like to see the new APIs pursued but XML creation provided in the JDOM way. Mark took a vote by show of hands on how people felt about the two issues, but I couldn't see the tally. There was also an informal tally about adding native XML support on one of the whiteboards. The result was 29% in favor and 71% against.

Constructor Invocation for Generics

Another much-discussed issue appeared on one of the whiteboards: the verbosity of creating instances of generic types. This is typical:

Map<Pair<String,Integer>,Node> map = new HashMap<Pair<String,Integer>,Node>();

The problem here is that the type parameters have to be repeated twice. One common "workaround" to this problem is to always create your generic objects using static factories, but the language should not force you to do that. A number of different syntax forms have been suggested for fixing this:

var map = new HashMap<Pair<String,Integer>,Node>();

This unfortuately requires the addition of a new keyword. Another:

final map = new HashMap<Pair<String,Integer>,Node>();

This reuses an existing keyword, but at the same time it also makes the variable final. Another variation on this idea:

map := new HashMap<Pair<String,Integer>,Node>();

In my opinion these three forms all suffer the same flaw: they place the type parameters in the wrong place. Since the variable is to be used later in the program, the programmer presumably wants control over its type and the reader wants the type to be clear from the variable declaration. In this case you probably want the variable to be a Map and not a HashMap. An idea that addresses my concern is:

Map<Pair<String,Integer>,Node> map = new HashMap();

Unfortunately, this is currently legal syntax that creates a raw HashMap. I don't know if it is possible to change the meaning of this construct without breaking backward compatibility. Another possibility:

Map<Pair<String,Integer>,Node> map = new HashMap<>();

You can see clearly by the presence of the empty angle brackets that the type parameters have been omitted where the compiler is asked to infer them. Of the alternatives, this is my favorite. I don't think it will be too hard to implement in javac using the same techniques that work for static factories of generic types.

Type Literals

2006-12-05T14:24:00.000-08:00

Yesterday I wrote about super type tokens, which is an API that acts like class literals but with two advantages over class literals: they work with generic types, and they provide full generic type information. The disadvantages are that they are more verbose than class literals, and (being a different type than java.lang.Class) they are incompatible with APIs that use type tokens. It turns out that it is possible to get the best of both worlds by adding super type tokens to the language. I would call the resulting construct type literals.

The basic idea would be to retrofit java.lang.reflect.Type with generics, in the same way that java.lang.Class was retrofitted with generics in JDK5. Then the type of List<String>.class would be Type<List<String>>, and the structure of the resulting object would contain all of the generic type information that a Type is capable of expressing. The code generated by javac could very well use the trick outlined in my previous blog post, though I expect there are much more efficient ways of doing it. You would then be able to write

Type<List<String>> x = List<String>.class;

The "type literal" on the right is currently a syntax error, but this language extension would give meaning to the syntax. How does this fit with the existing meaning of class literals? Very nicely. The type java.lang.Class already extends java.lang.reflect.Type, so a class literal of type Class<String> could be assigned to a variable of type Type<String>. In other words, the following would be legal:

Type<String> x = String.class;

Adding support for type literals to the language and retrofitting java.lang.reflect.Type would simplify the use of the THC pattern with generic types and make existing type-token-based APIs interoperate nicely with the pattern.

Super Type Tokens

2006-12-04T13:04:00.000-08:00

When we added generics to Java in JDK5, I changed the class java.lang.Class to become a generic type. For example, the type of String.class is now Class<String>. Gilad Bracha coined the term type tokens for this. My intent was to enable a particular style of API, which Joshua Bloch calls the THC, or Typesafe Heterogenous Container pattern. For some examples of where this is used see the APIs for annotations:

public <A extends Annotation> A java.lang.Class.getAnnotation(Class<A> annotationClass)

My earliest use of this feature (like my earliest use of all recent Java language features) appears in the compiler for the Java programming language (javac), in this case as a utility called Context, and you can find the code in the open source version. It was a utility that allowed the compiler to be written as a bunch of separate classes that all refer to each other, and solved the hard problem of getting all the parts created in an order such that they can be initialized with references to each other. The utility is also used to replace pieces of the compiler, for example to make related tools like javadoc and apt, the Annotation Processing Tool, and for testing. Today I would describe the utility as a simple dependency injection framework, but that wasn't a popular buzzword at the time.

Here is a simple but complete example of an API that uses type tokens in the THC pattern, from Josh's 2006 JavaOne talk:

public class Favorites {
    private Map<Class<?>, Object> favorites =
        new HashMap<Class<?>, Object>();
    public <T> void setFavorite(Class<T> klass, T thing) {
        favorites.put(klass, thing);
    }
    public <T> T getFavorite(Class<T> klass) {
        return klass.cast(favorites.get(klass));
    }
    public static void main(String[] args) {
        Favorites f = new Favorites();
        f.setFavorite(String.class, "Java");
        f.setFavorite(Integer.class, 0xcafebabe);
        String s = f.getFavorite(String.class);
        int i = f.getFavorite(Integer.class);
    }
}

A Favorites object acts as a typesafe map from type tokens to instances of the type. The main program in this snippet adds a favorite String and a favorite Integer, which are later taken out. The interesting thing about this pattern is that a single Favorites object can be used to hold things of many (i.e. heterogenous) types but in a typesafe way, in contrast to the usual kind of map in which the values are all of the same static type (i.e. homogenous). When you get your favorite String, it is of type String and you don't have to cast it.

There is a limitation to this pattern. Erasure rears its ugly head:

Favorites:15: illegal start of expression
f.setFavorite(List<String>.class, Collections.emptyList());
                          ^

You can't add your favorite List<String> to a Favorites because you simply can't make a type token for a generic type. This design limitation is one that a number of people have been running into lately, most recently Ted Neward. "Crazy" Bob Lee also asked me how to solve a related problem in a dependency injection framework he is developing. The short answer is that you can't do it using type tokens.

On Friday I realized you can solve these problems without using type tokens at all, using a library. I wish I had realized this three years ago; perhaps there was no need to put support for type tokens directly in the language. I call the new idea super type tokens. In its simplest form it looks like this:

public abstract class TypeReference<T> {}

The abstract qualifier is intentional. It forces clients to subclass this in order to create a new instance of TypeReference. You make a super type token for List<String> like this:

TypeReference<List<String>> x = new TypeReference<List<String>>() {};

Not quite as convenient as writing List<String>.class, but this isn't too bad. It turns out that you can use a super type token to do nearly everything you can do with a type token, and more. The object that is created on the right-hand-side is an anonymous class, and using reflection you can get its interface type, including generic type parameters. Josh calls this pattern "Gafter's Gadget". Bob Lee elaborated on this idea as follows:

import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.ArrayList;
import java.util.List;

/**
 * References a generic type.
 *
 * @author crazybob@google.com (Bob Lee)
 */
public abstract class TypeReference<T> {

    private final Type type;
    private volatile Constructor<?> constructor;

    protected TypeReference() {
        Type superclass = getClass().getGenericSuperclass();
        if (superclass instanceof Class) {
            throw new RuntimeException("Missing type parameter.");
        }
        this.type = ((ParameterizedType) superclass).getActualTypeArguments()[0];
    }

    /**
     * Instantiates a new instance of {@code T} using the default, no-arg
     * constructor.
     */
    @SuppressWarnings("unchecked")
    public T newInstance()
            throws NoSuchMethodException, IllegalAccessException,
                   InvocationTargetException, InstantiationException {
        if (constructor == null) {
            Class<?> rawType = type instanceof Class<?>
                ? (Class<?>) type
                : (Class<?>) ((ParameterizedType) type).getRawType();
            constructor = rawType.getConstructor();
        }
        return (T) constructor.newInstance();
    }

    /**
     * Gets the referenced type.
     */
    public Type getType() {
        return this.type;
    }

    public static void main(String[] args) throws Exception {
        List<String> l1 = new TypeReference<ArrayList<String>>() {}.newInstance();
        List l2 = new TypeReference<ArrayList>() {}.newInstance();
    }
}

This pattern can be used to solve Ted Neward's problem, and most problems where you would otherwise use type tokens but you need to support generic types as well as reifiable types. Although this isn't much more than a generic factory interface, the automatic hook into the rich generic reflection system is more than you can get with simple class literals. With a few more bells and whistles (toString, hashCode, equals, etc) I think this is a worthy candidate for inclusion in the JDK.

Linear Time Sort Puzzler

2006-11-22T12:17:00.000-08:00

Interviewing for an engineering position at Google can be grueling and humbling. You get less than an hour with each interviewer, and may get one technical problem after another to solve. If you have performance anxiety you may have a hard time focusing on the problem. The best approach, if you can do it, is to think of the interview as a technically challenging but friendly brainstorming session. If you get hired, that's what your life will be like.

My friend, Jim Davis, told me about someone he interviewed earlier this week. The candidate thought the interview wasn't going well and hoped to impress Jim by sharing an idea he had: a new algorithm for sorting in linear time. It isn't a sort based exclusively on comparisons; it can be proven that any such sort must perform O(n log n) comparisons. It isn't a bucket sort, which is a standard algorithm for this problem (assuming certain characteristics of the input set). But the candidate's algorithm helped Jim understand the candidate's capabilities.

The algorithm works like this: you start by making a linear scan through the n numbers to be sorted and note the largest and smallest of the elements. Using that, you compute a linear function f(x) that will map the smallest input element to zero and the largest to n. Then, for each input element x_i, you fork a task that waits f(x_i) milliseconds and then outputs x_i. After n milliseconds the output contains the input elements in sorted order.

There may be problems when two tasks attempt to output their data at nearly the same time, but let's ignore that for a moment and assume an "ideal" system. If you have a truly concurrent computer, this may run in O(n) time using O(n) processors, thereby consuming a total of O(n²) processing time. There are far better concurrent sorting algorithms around. Much more interesting is the idea of running this algorithm on a sequential computer with a non-preemptive scheduler. The non-preemptive scheduler avoids the problem of two tasks producing data at the same time. The scheduler can also ensure that the tasks run in their proper order, even if the running time of some tasks causes others to start slightly "too late".

Jim explained the problem with the algorithm, concluding "so you've reduced the problem of sorting in linear time to a different linear time sorting algorithm." After Jim explained this remark, the candidate replied "well, the idea isn't really very well thought out." Here is the puzzle: what was Jim talking about?

A Thread Pool Puzzler

2006-11-20T21:04:00.000-08:00

I participated in the design and development of a couple of concurrency libraries for shared-memory multiprocessors long before such machines were popular. So when I started using java.util.concurrent I was already somewhat comfortable with the concepts. But when I used it more intensely for production work in the Google Calendar server, I ran into a couple of "gotcha" situations. I'd like to tell you about one in particular, in part because it might help you avoid the problem yourself, and in part because I believe this issue exposes some missing functionality in the concurrency framework.

Many parallel programming problems can be expressed using fork-join parallelism, in which tasks spawn, or "fork", a number of subtasks that can be executed in parallel. The caller then waits for these subtasks to complete by "join"ing with them. Consider the following sequential program. It is an abstract model of some larger program that has three logical layers.

class Program {
    static final int N = 3;
    public static void main(String[] args) {
        doSomeWork();
        loopNtimes(N, new Runnable() {
                public void run() { doLayerOne(); }
            });
        System.out.println();
    }

    static void doLayerOne() {
        doSomeWork();
        loopNtimes(N, new Runnable() {
                public void run() { doLayerTwo(); }
            });
    }

    static void doLayerTwo() {
        doSomeWork();
        loopNtimes(N, new Runnable() {
                public void run() { doLayerThree(); }
            });
    }

    static void doLayerThree() {
        doSomeWork();
    }
    static void loopNtimes(int n, Runnable runnable) {
        for (int i=0; i<n; i++) runnable.run();
    }
    static void doSomeWork() {
        System.out.print(".");
        try { Thread.sleep(500L); } catch (InterruptedException _) {}
    }
}

This program prints 40 dots, taking a half second for each one. It runs to completion in about 20 seconds. Let's rewrite the loops as concurrent (instead of sequential) loops, using an idiom recommended by Martin Buchholz. To do that we replace the method loopNtimes with the following:

    static ExecutorService threadPool = Executors.newCachedThreadPool();
      static void loopNtimes(int n, Runnable runnable) {
        Collection<Callable<Object>> c = new ArrayList<Callable<Object>>();
        for (int i=0; i<n; i++) c.add(Executors.callable(runnable));
        Collection<Future<Object>> futures = null;
        try { futures = threadPool.invokeAll(c); } catch (InterruptedException _) {}
        if (futures != null) for (Future<Object> f : futures) {
            try { f.get(); }
            catch (InterruptedException ex) {}
            catch (ExecutionException ex) {
                ex.printStackTrace();
                System.exit(1);
            }
        }
    }

This requires a couple of other minor changes to the program (two import statements and System.exit(0) at the end of main), but the program now runs in two seconds instead of twenty. So far so good, but if N is larger, say a hundred, this program fails. It throws OutOfMemoryError becuase it tries to allocate too many threads. My first attempt to fix this replaced the thread pool by one containing a fixed number of threads:

    static ExecutorService threadPool = Executors.newFixedThreadPool(100);

This version of the program works and runs in 2 seconds. But why should we use 100 threads? If we imagine that the Thread.sleep statements represent computationally intensive parts of the program, it might make more sense to have a number of threads approximately the same as the number of physical processors. I'm running this on a machine with an Intel Cetrino Duo processor, which acts roughly like 2 processors. Let's be generous, however, and make ten threads. So we modify this version of the program by changing 100 to 10. That won't be as fast as the version with 100 threads, but just how fast will it be?

If you haven't guessed the punch line by now, I'll tell you: with ten threads in the pool the program prints 11 periods and then deadlocks! If you use a debugger to examine the state of the program to figure out what's going on, you'll find the main thread waiting for invokeAll, three threads in doLayerOne waiting for invokeAll, seven threads in doLayerTwo waiting for invokeAll, and there are no threads left to do any of the work of calling doLayerThree. This is a classic thread starvation deadlock.

If you're just trying out this program to see what happens, you might be slightly annoyed and finally give up and hit control-C to quit the Java program, but when our program (Google Calendar) encounters this kind of problem our customers get annoyed, give up, and sign up for a competitor like Yahoo Calendar or 30Boxes. Hey, don't click those links; trust me, you really want Google Calendar. My point is that we can't leave this to chance.

What can or should we do about this problem? The first idea is to change the 10 back into 100, but those numbers are pulled out of thin air. Without analyzing the behavior and interaction of all the places where the thread pool is used, understanding the dynamic performance of the application under real loads, and placing bounds on the number of tasks that will be used at each level in the program's hierarchy, it is difficult or impossible to pick a number that will always avoid this kind of deadlock. Another idea is to use unbounded thread pools, but as we've seen under high load situations those can cause an explosion in the number of threads, resulting in the program failing by running out of memory.

What we did to address this issue is avoid the single monolithic thread pool altogether. Instead, we use a separate thread pool at every level in the hierarchy. In terms of this example, we would have a thread pool for use in main, one for use in doLayerOne, and one for use in doLayerTwo. Every subsystem that requires concurrency gets its own personal thread pool. That way every layer that uses concurrency is guaranteed to make progress when it has work to do, so this kind of deadlock cannot occur. But there is a cost to this as well: balancing the sizes of these thread pools is a black art. During operation we have hundreds of threads, most of which are sitting around doing nothing. Besides being a waste of resources, the generous surplus of "extra" threads make debugging more difficult than it should be. If the system doesn't break down so neatly into layers (perhaps because there are recursive loops in the call cycle of the subsystems) then even this solution can break down and result in thread starvation.

The situation is not entirely hopeless. In my opinion, this kind of thread starvation should never occur because there is always one thread that can contribute processing power toward execution the subtasks: the thread that is waiting for the subtasks to complete. Here's the implementation of invokeAll as it appears in the JDK:

    public <T> List<Future<T>> invokeAll(Collection<Callable<T>> tasks)
        throws InterruptedException {
        if (tasks == null)
            throw new NullPointerException();
        List<Future<T>> futures = new ArrayList<Future<T>>(tasks.size());
        boolean done = false;
        try {
            for (Callable<T> t : tasks) {
                FutureTask<T> f = new FutureTask<T>(t);
                futures.add(f);
                execute(f);
            }
            for (Future<T> f : futures) {
                if (!f.isDone()) {
                    try { 
                        f.get(); 
                    } catch(CancellationException ignore) {
                    } catch(ExecutionException ignore) {
                    }
                }
            }
            done = true;
            return futures;
        } finally {
            if (!done)
                for (Future<T> f : futures) 
                    f.cancel(true);
        }
    }

This code does not use the current thread to do any of the work of invoking the callables. Below is a slightly modified version (I've added a line to the original and refactored it to make it a static method that we can put in the program) that uses the current thread to do any work that another thread hasn't already started. I've highlighted the newly added code:

    public static <T> List<Future<T>> invokeAll(
            ExecutorService threadPool, Collection<Callable<T>> tasks)
        throws InterruptedException {
        if (tasks == null)
            throw new NullPointerException();
        List<Future<T>> futures = new ArrayList<Future<T>>(tasks.size());
        boolean done = false;
        try {
            for (Callable<T> t : tasks) {
                FutureTask<T> f = new FutureTask<T>(t);
                futures.add(f);
                threadPool.execute(f);
            }
            // force unstarted futures to execute using the current thread
            for (Future<T> f : futures) ((FutureTask)f).run();
            for (Future<T> f : futures) {
                if (!f.isDone()) {
                    try { 
                        f.get(); 
                    } catch(CancellationException ignore) {
                    } catch(ExecutionException ignore) {
                    }
                }
            }
            done = true;
            return futures;
        } finally {
            if (!done)
                for (Future<T> f : futures) 
                    f.cancel(true);
        }
    }

Using this version of invokeAll, the program does not experience thread starvation. If the thread pool is reduced in size to just one thread, the program runs to completion in about 11 seconds, because two threads are contributing to doing the work (the main thread and the thread from the pool).

I discussed this issue with Doug Lea, and he warned me that selecting tasks for efficient scheduling in a fork-join concurrency framework is not trivial; the standard solution is to have a double-ended queue for each worker task where it enqueues its subtasks. The worker removes the most recently generated task from this queue for itself to process, thereby simulating a depth-first execution strategy in the single-thread case. When a worker finds itself without any work to do, it steals work from the other end of the queue of another task. That is, it should steal one of the least-recently created (course-grained) subtasks. In addition, it is beneficial to have a mechanism to avoid the queue altogether for the bottom of the call chain. Doug told me that this strategy was pioneered by the Cilk work, but I first learned about this strategy 10 years earlier reading WorkCrews: An Abstraction for Controlling Parallelism by Mark T. Vandervoorde and Eric S. Roberts. My implementation provides exactly this behavior but with a much simpler implementation. The invocation of run executes one of the tasks most recently generated by the current thread. When a thread has no more work to do, it removes work from the queue of the underlying ExecutorService, which is a FIFO queue, and so it takes the least-recently generated task of all workers. On the other hand, because this implementation shares a single queue among all worker threads, there may be additional synchronization overhead compared to the WorkCrews/Cilk solution.

It is possible to use the existing concurrency utilities to work around the problem, if you don't mind the task scheduling being far from optimal. You can do that by setting CallerRuns policy on a ThreadPoolExecutor, and using a synchronous queue:

static ThreadPoolExecutor threadPool =
  new ThreadPoolExecutor(0, 10, 60L, TimeUnit.SECONDS,
                         new SynchronousQueue<Runnable>());
static {
    threadPool.setRejectedExecutionHandler(
        new ThreadPoolExecutor.CallerRunsPolicy());
}

Doug explained to me that the earlier public-domain version of the concurrency utilities had a full implementation of a framework for fork-join parallelism, but they didn't get included in JDK5:

"... The vast majority of such usages are nicest to support as "loop parallelism" utilities. And it is not so much that utilities based on FJ tasks are inconvenient to use that has kept them out, but instead uncertainty about basic APIs until closures are settled. All of the methods for aggregate operations on collections and arrays (applyToAll, map, reduce, mapReduce, findAny, findAll, etc) require function-type arguments (perhaps along with some sort of purity annotation as might be introduced via JSR305) that, depending on how things work out otherwise, would need to be introduced more generally."

Did you think I would get through an entire blog post without mentioning Closures?

Closures Esoterica: completion transparency

2006-11-13T22:50:00.000-08:00

The Closures for Java draft specifiation (currently at v0.3) is the product of a lot of work. Everything in the spec has been discussed and scrutinized before being placed into the specification, and is there for a reason. From your point of view, you have seen snapshots of our specification, with very little explanation of why things are the way they are. Changes from one revision to another may seem arbitrary. I am not writing detailed notes on the progress and evolution of the specification and its prototype, because there is too much to explain and too little time would be left for me to work on the specification and prototype. I am, after all, working on this on my own time. I suspect few people would care for that level of detail anyway. Much of the work on the specification takes place during face-to-face meetings, after which I update the specification to reflect our decisions. Some issues get resolved through email discussions. We've been keeping an eye on the comments on this blog, various message boards, mailing lists, and elsewhere for input, and meeting with interested folks, and that has been a very useful part of the process. Thank you for your help!

I'm preparing the next revision of the specification, and we just resolved an issue by email. Unless you know what the issue is, the change in the upcoming version of the specification will appear totally arbitrary. Because the issue was resolved by email, I have a nice record of the problem and its resolution. Here is an edited excerpt of the the start of our discussion:

We'd like programmers to be able to define their own control constructs. One thing that would make this easier would be if programmer-defined control constructs act like built-in ones for the purposes of handling reachability of statements (and "can complete normally"). That's why we added the bottom type java.lang.Unreachable to the specification. But just having that isn't enough. Watch as I try to define a withLock method that is completion transparent.

First, ignoring reachability, the library writer might define
<throws E> void withLock(Lock lock, {=>void throws E} block) throws E { ... }
this achieves exception transparency, but not completion transparency. If the block returns a value, this would work:
<T, throws E> T withLock(Lock lock, {=>T throws E} block) throws E { ... }
this works because a closure that can't complete normally can be converted, via the closure conversion, to {=>Unreachable}. In practice, any specific invocation of withLock will either have a block that doesn't return anything (i.e. =>void) or can't complete normally (i.e. =>Unreachable}. You might think, therefore, that the library writer need only write these two overloaded methods to achieve completion transparency, and let overload resolution take care of the rest.

Unfortunately it isn't that simple. With these two methods, an invocation of withLock using a closure that can't complete normally can be an invocation of either of these methods. That's because the closure conversion can convert a closure that results in Unreachable to an interface whose method returns void. Since both are applicable, the compiler must select the most specific. Neither of these methods is more specific than the other (the closures are unrelated, given our scheme of mapping function types to interfaces), so the invocation is ambiguous.

I don't propose that we mess with the specification for "most specific". I'm afraid that would be a disaster, though maybe you can reassure me that it isn't. Instead, I propose that the closure conversion be allowed to convert a closure that results in void to an interface whose method's return type is java.lang.Void. The generated code would naturally return a null value. Then the library writer would write only the second version, above, and it would work both for the void-returning case and the Unreachable-returning case. I think being able to write control abstractions as a single method (instead of two overloadings) is a significant advantage. Additionally, this API is more flexible because it can be used by programmers to pass a value back through from the closure to the caller.

We discussed this issue and found the proposed resolution our best option. The next version of the proposal will include in the closure conversion a provision allowing conversion of a closure that returns void to an interface type whose method returns java.lang.Void. You can see hints in this email thread that the syntax of a function type has changed slightly (the throws clause has moved inside the curly braces), and that a function type is now specified to be an interface type, rather than having its own type rules. The specification is getting simpler, which is definitely a move in the right direction!

Reified Generics for Java

2006-11-05T15:22:00.000-08:00

Many people are unsatisfied with the restrictions caused by the way generics are implemented in Java. Specifically, they are unhappy that generic type parameters are not reified: they are not available at runtime. Generics are implemented using erasure, in which generic type parameters are simply removed at runtime. That doesn't render generics useless, because you get typechecking at compile-time based on the generic type parameters, and also because the compiler inserts casts in the code (so that you don't have to) based on the type parameters.

Generics are implemented using erasure as a response to the design requirement that they support migration compatibility: it should be possible to add generic type parameters to existing classes without breaking source or binary compatibility with existing clients. I wrote about this two years ago. Migration compatibility is exploited widely in JDK5; all of the collection classes and interfaces use generics, yet existing code using collections continues to work. Without migration compatibility, the collection APIs could not be retrofitted use generics; we would probably have added a separate, new set of collection APIs that use generics. That was the approach used by C# when generics were introduced, but Java did not take this approach because of the huge amount of pre-existing Java code using collections.

While solving one set of problems, erasure adds a set of its own problems. For a type parameter T, you can't write a class literal T.class. You can't use instanceof to test if an object is of type T. And you can't create an array of T. But it gets worse. You also can't write class literals for generic types like List<String>.class, or test if an object is an instanceof List<String>, or create an array of List<String>. The implementation of generics using erasure also causes Java to have unchecked operations, which are operations that would normally check something at runtime but can't do so because not enough information is available. For example, a cast to the type List<String> is an unchecked cast, because the generated code checks that the object is a List but doesn't check whether it is the right kind of list.

It isn't too late to add reified generics to Java. There are two basic approaches. The first uses the language as it exists today but adds the generic type information at runtime. In the ideal world, we wait until every bit of Java code in the world has been modified to use generics safely, and then go through a transition in which we start recording type parameters at runtime by using a new javac and VM. There are two main difficulties with this approach. First, it is not compatible. It is not source compatible because you would no longer be allowed to use raw types (i.e., it is impractical to wait until all code has been generified); it is not binary compatible because new clients would invoke new kinds of constructors for generic classes that also record the type parameters, but existing classes do not have those constructors. (A hybrid approach is being investigated in which the system records type parameters only when they are available, but I haven't yet seen a workable proposal along these lines.) The second problem is more insidious: lots of existing code uses generics but uses them in an unsafe way. For example, I have seen code that creates an ArrayList<Object>, but later casts it to a List<String> where the author knows that it only contains objects of type String. I would not be surprised to find such code in the JDK. Such code must fail at runtime when generics are reified, so some existing (but working) code would be broken.

The other approach modifies the language so that the declaration of a generic parameter distinguishes reified type parameters from erased ones. It is a pure extension of the language. The existing syntax for generics would continue to designate generics by type erasure, but a newly introduced syntax would be used to declare reified type parameters. Perhaps something like this:

class NewCollection<class E> extends Collection<E> { ... }
class NewList<class E> extends NewCollection<E>, List<E> { ... }

The rules for these reified type parameters are straightforward. When using a reified generic class, the type argument has to be a reified type. You would not be allowed to create a NewCollection in its raw form. Code that uses only reified types would never get an unchecked warning from the compiler, because the compiler can always generate the correct checking code. If you have a reference of type Collection that refers to a NewCollection<String>, you would get a runtime error if you attempt to put anything other than a String into it. In this sense reified collections are like java.util.Collections.checkedCollection, only better because the element type can itself be generic and the guarantees are stronger. You can even create an array of E inside an implementation of this type. But there is a disadvantage: the strategy requires a new set of reified Collections APIs parallel to the existing erasure-based ones. This is why C# introduced new collections APIs when they introduced generics.

As the above declaration illustrates, the new reified collection interfaces could be extensions of the existing collection interfaces. Consequently, existing APIs that receive old collections can be passed new collections. For example, you could pass a NewCollection<String> to an API that is declared to receive a Collection<String>. In addition, the new reified collection classes (that is, the implementations) could be extensions of the existing collection classes. That allows the implementation of the old and new collection classes to be shared, and provides a nice migration path. Existing APIs that return old collections can be modified to return new collections. Over time, most libraries can be migrated to use the new APIs without breaking backward compatibility (though it would break unsafe clients). In this way we can have a more gradual migration than would be possible with the first approach.

I don't mean to trivialize the work involved: this requires a significant revision of the VM and language specifications and a significant effort from the teams who implement VMs, java compilers (i.e. javac and Hotspot), and the core JDK libraries. From the programmer's point of view, however, the language change is small and mostly involves removing restrictions.

Approaching the problem this way has a secondary benefit. Because the new reified collection interfaces don't exist yet, it is possible for methods to be added to them when they are introduced. Perhaps sorting methods belong in NewList? If reified generics are added at the same time as (or after) closures, a number of useful methods could be added to take advantage of closures. Filters, mappers, reducers, and visitors are just some of the ideas.

Closures for Java (v0.3)

2006-10-22T08:58:00.000-07:00

We've just completed a major revision and simplification of the Closures for Java specification. Rather than post the specification on this blog, it is on its own web page, here. There are two versions of the specification: one with function types and one without. There is a pulldown menu at the top of the specification that makes it display only the text relevant to the version of the specification you want to see. Keeping the specification in this form will allow us to more easily maintain the two parallel specifications so we can compare them and delay a decision on this issue until later. These specifications are the starting point for our prototype.

There are two significant changes in this revision. First, there is a completely new syntax for closures and function types. Using the new syntax, with functon types, you can write

{int,int => int} plus = {int x, int y => x+y};

As you can see, we're proposing to add the new "arrow" token => to the syntax. Just to be perfectly clear, this code declares a variable of function type

{int,int => int}

which is a function that takes two ints and yields an int. The variable is named "plus" and it is assigned the closure value

{int x, int y => x+y}

which is a closure that receives two ints (named x and y) and yields their sum.

The second major change has to do with the treatment of "restricted" closures. We've done away with the "synchronized" parameters from the previous revision of the specification. Instead, you can inherit from a marker interface to restrict the closure conversion. If you don't use the marker interface, then closures are not restricted when converted to that type.

Another important change is to the meaning of a function type. It is now defined to be a system-provided interface type, and it is provided in a way that gives the required subtype relations among function types. That means that in order to invoke a value of function type, instead of simply placing arguments in parens after the function value, you use its "invoke" method. This significantly simplifies the name lookup rules for variables of function type. In fact, now there are no special rules at all.

As always, your feedback and ideas are welcome.

Concurrent Loops Using Java Closures

2006-10-13T10:31:00.000-07:00

The java.util.concurrent package has very nice support for writing concurrent loops. I used it recently to improve the performance of some code in the Google Calendar Server. In the Calendar Server, we have a class representing an event on a calendar. The following method on an event computed the set of attendees to the event. The old code looked something like this:

public Collection<Principal> getAttendees() {
    List<Principal> result = new ArrayList<Principal>();
    for (EventResponse r : getResponses()) {
        if (r.mayAttend()) {
            result.add(r.getAttendee());
        }
    }
    return result;
}

The problem with this code, it turned out, was that getAttendee() has to talk to a remote server to look up the Principal in a database, and although the remote server is very fast, it is far enough away that there is some latency. Since this loop is sequential, when there are many responses it spends most of its time waiting for a response from the remote server, over and over again. Consequently the call to getAttendees() was very slow for events with many attendees. One solution to this kind of problem would be to send a single batch request, and that is probably the best long-term solution to the problem, but the server in this case doesn't yet know how to handle batch requests. So our fix to the immediate performance problem was to use java.util.concurrent and make the requests in parallel; this did speed things up significantly:

public Collection<Principal> getAttendees() {
    final List<Principal> result = new ArrayList<Principal>();
    CompletionService<Void> ecs =
        new ExecutorCompletionService<Void>(threadPool);
    for (final EventResponse r : getResponses()) {
        ecs.submit(new Callable<Void>() {
            public Void call() {
                if (r.mayAttend()) {
                    try {
                        Principal attendee = r.getAttendee();
                      synchronized (result) {
                          result.add(attendee);
                        }
                  } catch (Throwable ex) {
                        LOGGER.log(Level.SEVERE, "Uncaught Exception", ex);
                    }
                }
                return null;
            }
        });
    }
    // wait for the tasks to complete
    for (final EventResponse r : getResponses()) {
        try {
            /*discard*/ ecs.take().get();
        } catch (InterruptedException ex) {
            throw new AssertionError(ex); // shouldn't happen
        } catch (ExecutionException ex) {
            LOGGER.log(Level.SEVERE, "Uncaught Exception", ex);
        }
    }
    return result;
}

When I find code like this I have a few reactions. First, my eyes glaze over at the complexity. Then, if I'm interested, I look carefully at the code to try to understand it. After all, I'm likely to want to do something like this again someday. Finally, I bookmark it so I can add it to my bag of tricks.
I don't think writing a concurrent loop should have to be so complex. Here is what I would like to have written:

public Collection<Principal> getAttendees() {
    List<Principal> result = new ArrayList<Principal>();
    for eachConcurrently(EventResponse r : getResponses(), threadPool) {
        if (r.mayAttend()) {
            Principal attendee = r.getAttendee();
            synchronized (result) {
              result.add(attendee);
            }
        }
    }
    return result;
}

You might think that in order to do this kind of thing we would need to add a concurrent looping statement to the language. Actually, it is possible to add the concurrent looping construct as a library method if you have closures in the language! It isn't trivial to write, but that's why we have people like Doug Lea in the world. An API like this "for eachConcurrently" thing should be written once by an expert and placed into the JDK for everyone to use.

What should happen if you use continue, break, or return within the body of this loop, or throw an exception? The continue case is easy: it just completes execution of that one iteration, and the other iterations proceed on their merry way. The semantics of break are a bit subtle, but obvious once you realize this is supposed to act like a loop: it completes the current iteration and cancels any other iterations that have not completed, and control returns to the caller of for eachConcurrently. Handling a return statement is similar: it cancels any uncompleted iterations and returns from the enclosing method, which in this case would be getAttendees. Finally, any exception that propagates out of a loop iteration cancels uncompleted iterations and propagates from the loop.

p.s.: Martin Buchholz offered the follow improved version of the code using java.util.concurrent:

public Collection<Principal> getAttendees() {
final Collection<Principal> result
= new ConcurrentLinkedQueue<Principal>();

    final Collection<Callable<Object>> tasks
      = new ArrayList<Callable<Object>>();
    for (final EventResponse r : getResponses())
      tasks.add(Executors.callable(new Runnable() { public void run() {
      try {
      if (r.mayAttend())
      result.add(r.getAttendee());
      } catch (Throwable ex) {
      LOGGER.log(Level.SEVERE, "Uncaught Exception", ex);
      }}}));
    try {
      threadpool.invokeAll(tasks);
    } catch (InterruptedException ex) {}
    return new ArrayList<Principal>(result);
}

Iterative control abstraction: user-defined loops

2006-10-02T21:39:00.000-07:00

A couple of people have written about using Java closures to write methods that act as looping constructs. For example, iterating through a map is currently an ugly exercise in boilerplate:

Droid seekDroid(Map<String,Droid> map) {
    for (Map.Entry<String,Droid> entry : map.entrySet()) {
        String droidName = entry.getKey();
        Droid droid = entry.getValue();
        if (droid.isSought()) {
            System.out.printf("'%s' is the droid we seek.%n", droidName);
            return droid;
        }
    }
}

It has been proposed that we add looping methods to Collection and Map that take advantage of closures, but it would be incompatible to add methods to an existing interface. We can accomplish the same thing using static methods. With one small additional twist to the closures proposal, we could make it even easier to write a method that iterates over maps. Here is what we want our client to look like:

import static java.util.Collections.eachEntry;
...
Droid seekDroid(Map<String,Droid> map) {
    for eachEntry(String droidName, Droid droid : map) {
        if (droid.isSought()) {
            System.out.printf("'%s' is the droid we seek.%n", droidName);
            return droid;
        }
    }
}

To enable this, the following would be added to java.util.Collections:

public interface Block2<K,V,throws E> {
    void invoke(K k, V v) throws E;
}
public static <K,V,throws E>
void for eachEntry(Map<K,V> map, Block2<K,V,E> block) throws E {
    for (Map.Entry<K,V> entry : map.entrySet()) {
        block.invoke(entry.getKey(), entry.getValue());
    }
}

Notice the "for" qualifier on the declaration of eachEntry, and the for keyword on its invocation. Methods defined this way and then invoked using the control abstraction syntax would require the use of the for keyword on the invocation. The compiler arranges such control abstractions to act like loops, by properly interpreting break and continue statements within the body of the closure. Although this example doesn't use break or continue statements, the mere presence of the for keyword on the invocation helps the reader understand the code. In this way user-defined control constructs could be written that appear and act as loops.

Failure of Imagination in Language Design

2006-09-17T06:37:00.000-07:00

Failure of imagination - that is, failure to make language constructs orthogonal because you aren't quite sure how people will need to use them together - is one of the most common and severe errors you can make in programming language design. It is an error that is often impossible to correct after the fact. There is an approach to programming language design that you can take to maximize your opportunities to err in this way: consider the interactions of individual language features and decide on a case-by-case basis if the interaction will be allowed or not (or even what the semantics should be) based on whether or not you can find use cases and which semantics best fit those use cases.

This is an approach favored by expert API designers, because the domain of API design is best suited to this approach and these designers expect their expertise to carry from one domain to the other. In an API, the components of the API fit together in particular and well-defined patterns due to the typing and subtyping relationships between the elements; the job of the API designer is to ensure that the patterns you can build with the API elements satisfy a set of use cases.

In a programming language, on the other hand, the elements that are used to assemble programs are ideally orthogonal and independent. Programmers can assemble the elements in arbitrary ways, often unexpected but surprisingly useful ways. The "patterns" movement for example records some of these ideas by creating a common terminology for newly discovered ways of assembling programs from primitives.

To be sure, use cases also play a very important role in language design, but that role is a completely different one than the kind of role that they play in API design. In API design, satisfying the requirements of the use cases is a sufficient condition for completeness. In language design, it is a necessary condition.

Nominal Closures for Java (version 0.2)

2006-09-13T21:33:00.000-07:00

This post describes a draft proposal for adding support for closures to the Java programming language for the Dolphin (JDK 7) release. It was carefully designed to interoperate with the current idiom of one-method interfaces. The latest version of the proposal and a prototype can be found at http://www.javac.info/.

This revision of the closures proposal eliminates function types, introduces the Unreachable type, and gives related reachability rules. A closure's "return" type is now called its result type. The abbreviated invocation syntax now takes any statement, not just a block, to make nesting work nicely.

Gilad Bracha, Neal Gafter, James Gosling, Peter von der Ahé

Modern programming languages provide a mixture of primitives for composing programs. C#, Javascript, Ruby, Scala, and Smalltalk (to name just a few) have direct language support for delayed-execution blocks of code, called closures. A proposal for closures is working its way through the C++ standards committees as well. Closures provide a natural way to express some kinds of abstraction that are currently quite awkward to express in Java. For programming in the small, closures allow one to abstract an algorithm over a piece of code; that is, they allow one to more easily extract the common parts of two almost-identical pieces of code. For programming in the large, closures support APIs that express an algorithm abstracted over some computational aspect of the algorithm. This proposal outlines a specification of closures for Java without introducing function types.

1. Closure Literals

We introduce a syntactic form for constructing a closure value:

Expression3
Closure
Closure
FormalParameters { BlockStatements_opt Expression_opt }

Example

We can write a closure that adds two to its argument like this:

interface IntFunction {
 int invoke(int i);
}
IntFunction plus2 = (int x){ x+2 };

2. The type of a closure

A closure literal has a "closure type" that exists transiently at compile time. It is converted to some object type at compile-time; See Closure Conversion for details. It is a compile-time error if a closure is not subject to a closure conversion.

The type of a closure is inferred from its form as follows:

The argument types of a closure are the types of the declared arguments.

If the body of the closure ends with an expression, the result type of the closure is the type of that expression; otherwise if the closure can complete normally, the result type is void; otherwise the result type is Unreachable.

The set of thrown types of a closure are those checked exception types thrown by the body.

Example

The following illustrates a closure being assigned to a variable of a compatible object type.

interface VoidIntBlock<throws E> {
 void invoke(int i) throws E;
}
VoidIntBlock<InterruptedException> sleeper = (int t) { Thread.sleep(t); };

3. `synchronized` parameters

We allow the qualifier synchronized to be used on formal method arguments. When a closure is passed to such a parameter, the closure conversion (see Closure Conversion) is allowed to close over its context: the closure may use non-final local variables from enclosing scopes, and may use control-transfer statements such as break, continue, and return that transfer control outside of the body of the closure. An overriding method declaration may only add (i.e. may not remove) the synchronized qualfier to formal parameters compared to a method it overrides; an abstract method that overrides one whose parameter is declared synchronized must itself declare the parameter synchronized. If a closure is passed to a parameter that is not declared synchronized, then the only local variables from enclosing scopes it may access are those that are marked final.

Note: this qualifier is necessary to enable API writers to distinguish synchronous from asynchronous receivers of closures. For compatibility with existing APIs, most of which are asynchronous, the default is not allowing closing over the context. The constraint on overriders preserves the substitutability of subtypes: if a closure is allowed when passed to the superclass method, it must be allowed when passed to the subclass method. A consequence of the overriding constraint is that no existing overridable method can be retrofitted to accept synchronous closures without breaking source compatibility. Static methods such as AccessController.doPrivileged can be retrofitted. The synchronized keyword isn't an ideal choice, but it is the best we've found so far.

Names that are in scope where a closure is defined may be referenced within the closure. It is a compile-time error to access a local variable declared outside the closure from within a closure unless the closure is passed to a parameter that is declared synchronized or the variable was declared final.

Note: a local variable that is referenced within a closure is in scope in the body of the closure. Consequently the lifetime of objects referenced by such variables may extend beyond the time that the block containing the local declaration completes.

4. Closure conversion

A closure literal may be assigned to a variable or parameter of any compatible object type by the closure conversion:

There is a closure conversion from every closure of type T to every interface type that has a single method m with signature U such that T is compatible with U. A closure of type T is compatible with a method U iff all of the following hold:

Either
- The result type of T is either the same as the return type of U or
- There is an assignment conversion from the result type of T to the return type of U; or
- the result type of T is Unreachable.
T and U have the same number of arguments.
For each corresponding argument position in the argument list of T and U, both argument types are the same.
Every exception type in the throws of T is a subtype of some exception type in the throws of U.

If the closure is not passed to a parameter that was declared synchronized then

it is a compile-time error if the closure being converted contains a break, continue or return statement whose execution would result in a transfer of control outside the closure
it is a compile-time error if the closure being converted refers to a non-final local variable or parameter declared in an enclosing scope.

The closure conversion to a non-synchronized parameter applies only to closures that obey the same restrictions that apply to local and anonymous classes. The motivation for this is to help catch inadvertent use of non-local control flow in situations where it would be inappropriate. Examples would be when the closure is passed to another thread, or stored in a data structure to be invoked at a later time when the method invocation in which the closure originated no longer exists.

Note: The closure conversion occurs at compile-time, not at runtime. This enables javac to allocate only one object, rather than both a closure and an anonymous class instance.

We are considering an additional qualifier on non-final local variables that allows a closure to access the variable.

Example

We can use the existing Executor framework to run a closure in the background:

 void sayHello(java.util.concurrent.Executor ex) {
 ex.execute((){ System.out.println("hello"); });
 }

5. Exception type parameters

To support exception transparency, we add a new type of generic formal type argument to receive a set of thrown types. [This deserves a more formal treatment] What follows is an example of how the proposal would be used to write an exception-transparent version of a method that locks and then unlocks a java.util.concurrent.Lock, before and after a user-provided block of code:

interface Block<throws E> {
 void invoke() throws E;
}
public static <throws E extends Exception>
void withLock(Lock lock, Block<E> block) throws E {
 try {
 lock.lock();
 block.invoke();
 } finally {
 lock.unlock();
 }
}

This can be used as follows:

withLock(lock, (){
 System.out.println("hello");
});

This uses a newly introduced form of generic type parameter. The type parameters E are declared to be used in throws clauses. If the extends clause is omitted, a type parameter declared with the throws keyword is considered to extend Exception (instead of Object, which is the default for other type parameters). This type parameter accepts multiple exception types. For example, if you invoke it with a block that can throw IOException or NumberFormatException the type parameter E would be IOException|NumberFormatException. In those rare cases that you want to use explicit type parameters with multiple thrown types, the keyword throws is required in the invocation, like this:

Locks.<throws IOException|NumberFormatException>withLock(lock) {
 whatever();
}

You can think of this kind of type parameter accepting disjunction, "or" types. That is to allow it to match the exception signature of a closure that throws any number of different checked exceptions. If the block throws no exceptions, the type parameter would be the type null.

Type parameters declared this way can be used only in a throws clause or as a type argument to a generic method, interface, or class whose type argument was declared this way too.

6. Non-local control flow

One purpose for closures is to allow a programmer to refactor common code into a shared utility, with the difference between the use sites being abstracted into a closure. The code to be abstracted sometimes contains a break, continue, or return statement. This need not be an obstacle to the transformation. A break or continue statement appearing within a closure may transfer to any matching enclosing statement provided the target of the transfer is in the same innermost ClassBody.

A return statement always returns from the nearest enclosing method or constructor.

If a break statement is executed that would transfer control out of a statement that is no longer executing, or is executing in another thread, the VM throws a new unchecked exception, UnmatchedNonlocalTransfer. Similarly, an UnmatchedNonlocalTransfer is thrown when a continue statement attempts to complete a loop iteration that is not executing in the current thread. Finally, an UnmatchedNonlocalTransfer is thrown when a return statement is executed if the method invocation to which the return statement would transfer control is not on the stack of the current thread.

7. Definite assignment

The body of a closure may not assign to a final variable declared outside the closure.

A closure expression does not affect the DA/DU status of any variables it names.

8. The type `Unreachable`

We add the non-instantiable type java.lang.Unreachable, corresponding to the standard type-theoretic bottom. Values of this type appear only at points in the program that are formally unreachable. This is necessary to allow transparency for closures that do not return normally. Unreachable is a subtype of every type (even primitive types). No other type is a subtype of Unreachable. It is a compile-time error to convert null to Unreachable. It is an error to cast to the type Unreachable.

Example

The following illustrates a closure being assigned to a variable of the correct type.

interface NullaryFunction<T, throws E> {
 T invoke() throws E;
}
NullaryFunction<Unreachable,null> thrower = () { throw new AssertionError(); };

8. Unreachable statements

An expression statement in which the expression is of type Unreachable cannot complete normally.

10. Abbreviated invocation syntax.

A new invocation statement syntax is added to make closures usable for control abstraction:

AbbreviatedInvocationStatement
Primary ( ExpressionList ) Statement
AbbreviatedInvocationStatement
Primary ( Formals ) Statement
AbbreviatedInvocationStatement
Primary ( Formals : ExpressionList ) Statement

This syntax is a shorthand for the following statement:

Primary ( ExpressionList, ( Formals ) { Statement } );

This syntax makes some kinds of closure-receiving APIs more convenient to use to compose statements.

Note: There is some question of the correct order in the rewriting. On the one hand, the closure seems most natural in the last position when not using the abbreviated syntax. On the other hand, that doesn't work well with varargs methods. Which is best remains an open issue.

We could use the shorthand to write our previous example this way

withLock(lock) {
 System.out.println("hello");
}

This is not an expression form for a very good reason: it looks like a statement, and we expect it to be used most commonly as a statement for the purpose of writing APIs that abstract patterns of control. If it were an expression form, an invocation like this would require a trailing semicolon after the close curly brace of a controlled block. Forgetting the semicolon would probably be a common source of error. The convenience of this abbreviated syntax is evident for both synchronous (e.g. withLock) and asynchronous (e.g. Executor.execute) use cases. Another example of its use would be a an API that closes a java.io.Closeable after a user-supplied block of code:

class OneArgBlock<T, throws E> {
    void invoke(T t) throws E;
}
<T extends java.io.Closeable, throws E>
void closeAtEnd(OneArgBlock<? super T,E> block, T t) throws E {
    try {
        block.invoke();
    } finally {
        try { t.close(); } catch (IOException ex) {}
    }
}

We could use the shorthand with this API to close a number of streams at the end of a block of code:

closeAtEnd(FileReader in : makeReader()) closeAtEnd(FileWriter out : makeWriter()) {
 // code using in and out
}

Acknowledgments

The authors would like to thank the following people whose discussions and insight have helped us craft, refine, and improve this proposal:

Lars Bak, Cedric Beust, Joshua Bloch, Martin Buchholz, Danny Coward, Erik Ernst, Christian Plesner Hansen, Kohsuke Kawaguchi, Doug Lea, "crazy" Bob Lee, Martin Odersky, Tim Peierls, John Rose, Ken Russell, Mads Torgersen, Jan Vitek, and Dave Yost.

Closures for Java (version 0.1)

2006-09-07T21:29:00.000-07:00

This revision of the proposal drops local functions and the special nonlocal return syntax, adds support for generic type parameters that can be used to represent thrown exceptions, and has only one form of closure literal. It also adds an abbreviated invocation statement that supports very convenient control abstraction. Soon I'll present a parallel proposal based on interfaces (that is, without function types) and contrast the two proposals.

Gilad Bracha, Neal Gafter, James Gosling, Peter von der Ahé

Modern programming languages provide a mixture of primitives for composing programs. C#, Javascript, Ruby, Scala, and Smalltalk (to name just a few) have direct language support for function types and inline function-valued expression, called closures. A proposal for closures is working its way through the C++ standards committees as well. Function types provide a natural way to express some kinds of abstraction that are currently quite awkward to express in Java. For programming in the small, closures allow one to abstract an algorithm over a piece of code; that is, they allow one to more easily extract the common parts of two almost-identical pieces of code. For programming in the large, closures support APIs that express an algorithm abstracted over some computational aspect of the algorithm. We propose to add function types and closures to Java. We anticipate that the additional expressiveness of the language will simplify the use of existing APIs and enable new kinds of APIs that are currently too awkward to express using the best current idiom: interfaces and anonymous classes.

1. Function Types

We introduce a new syntactic form:

Type
Type ( TypeList_opt ) FunctionThrows_opt
FunctionThrows
throws ThrowsTypeList

ThrowsTypeList
Type
ThrowsTypeList
ThrowsTypeList VBAR Type
VBAR
|

These syntactic forms designate function types. A function type is a kind of reference type. A function type consists of a return type, a list of argument types, and a set of thrown exception types.

2. Namespaces and name lookup

The Java programming language currently maintains a strict separation between expression names and method names. These two separate namespaces allow a programmer to use the same name for a variable and for methods. Variables of closure type necessarily blur the distinction between these two namespaces, because they can be used in an expression and they can be invoked.

When searching a scope for a method name, if no methods exist with the given name then variables of the given name that are of function type are considered candidates. If more than one exists (for example, function-typed variable declarations are inherited from separate supertypes), the reference is considered ambiguous.

We allow a function to be invoked from an arbitrary (for example, parenthesized) expression:

Primary
Primary Arguments

3. Closure Literals

We also introduce a syntactic form for constructing a value of function type:

Expression3
Closure
Closure
FormalParameters { BlockStatements_opt Expression_opt }

Example

We can write a function that adds two to its argument like this:

    int(int) plus2 = (int x){ x+2 };

4. The type of a closure

The type of a closure is inferred from its form as follows:

The argument types of a closure are the types of the declared arguments.

If the body of the closure ends with an expression, the return type of the closure is the type of that expression; otherwise if the closure can complete normally, the return type is void; otherwise the return type is null.

The set of thrown types of a closure are those checked exception types thrown by the body.

Example

The following illustrates a closure being assigned to a variable with precisely the type of the closure.

void(int) throws InterruptedException sleeper = (int t) { Thread.sleep(t); };

5. Subtyping

A function type T is a subtype of function type U iff all of the following hold:

Either
- The return type of T is either the same as the return type of U or
- Both return types are reference types and the return type of T is a subtype of the return type of U, or
- the return type of U is void.
T and U have the same number of declared arguments.
For each corresponding argument position in the argument list of T and U, either both argument types are the same or both are reference types and the type of the argument to U is a subtype of the corresponding argument to T.
Every exception type in the throws of T is a subtype of some exception type in the throws of U.

6. Exception checking

The invocation of a function throws every checked exception type in the function's type.

7. Reflection

A function type inherits all the non-private methods from Object. The following methods are added to java.lang.Class to support function types:

  public final class java.lang.Class ... {
      public boolean isFunction();
      public java.lang.reflect.FunctionType functionType();
      public Object invokeFunction(Object function, Object ... args)
         throws IllegalArgumentException | InvocationTargetException;
  }
  public interface java.lang.reflect.FunctionType {
      public Type returnType();
      public Type[] argumentTypes();
      public Type[] throwsTypes();
  }

Note: unlike java.lang.reflect.Method.invoke, Class.invokeFunction cannot throw IllegalAccessException, because there is no access control to enforce; the function value designates a closure, which does not have access modifiers. Access to function values is controlled at compile-time by their scope, and at runtime by controlling the function value.

8. The type of `null`

We add support for null and the type of null in function types. We introduce a meaning for the keyword null as a type name; it designates the type of the expression null. A class literal for the type of null is null.class. These are necessary to allow reflection, type inference, and closure literals to work for functions that do not return normally. We also add the non-instantiable class java.lang.Null as a placeholder, and its static member field TYPE as a synonym for null.class.

9. Referencing names from the enclosing scope

Names that are in scope where a closure is defined may be referenced within the closure. We do not propose a rule that requires referenced variables be final, as is currently required for anonymous class instances.

Note: a local variable that is referenced within a closure is in scope in the body of the closure. Consequently the lifetime of objects referenced by such variables may extend beyond the time that the block containing the local declaration completes.

10. Non-local control flow

A return statement always returns from the nearest enclosing method or constructor.

If a break statement is executed that would transfer control out of a statement that is no longer executing, or is executing in another thread, the VM throws a new unchecked exception, UnmatchedNonlocalTransfer. (I suspect we can come up with a better name). Similarly, an UnmatchedNonlocalTransfer is thrown when a continue statement attempts to complete a loop iteration that is not executing in the current thread. Finally, an UnmatchedNonlocalTransfer is thrown when a NamedReturnStatement attempts to return from a function or method invocation that is not pending in the current thread. Likewise, an UnmatchedNonlocalTransfer is thrown when a return statement is executed if the method invocation to which the return statement would transfer control is not on the stack of the current thread.

11. Closure conversion

We propose the following closure conversion, to be applied only in those contexts where boxing currently occurs:

There is a closure conversion from every closure of type T to every interface type that has a single method with signature U such that T is a subtype of the function type corresponding to U.

It is a compile-time error if the closure being converted contains a break, continue or return statement whose execution could result in a transfer of control outside the closure. It is a compile-time error if the closure being converted refers to a non-final local variable or parameter declared in an enclosing scope.

We will want to generalize this rule slightly to allow the conversion when boxing or unboxing of the return type is required, e.g. to allow assigning a closure that returns int to an interface whose method returns Integer or vice versa.

Note: the closure conversion is applied only to closures (i.e. function literals), not to arbitrary expressions of function type. This enables javac to allocate only one object, rather than both a closure and an anonymous class instance. The conversion avoids hidden overhead at runtime. As a practical matter, javac will automatically generate code equivalent to our original client, creating an anonymous class instance in which the body of the lone method corresponds to the body of the closure.

Closure conversion applies only to closures that obey the same restrictions that apply to local and anonymous classes. The motivation for this is to help catch inadvertent use of non-local control flow in situations where it would be inappropriate. Examples would be when the closure is passed to another thread, or stored in a data structure to be invoked at a later time when the method invocation in which the closure originated no longer exists.

Examples

We can use the existing Executor framework to run a closure in the background:

  void sayHello(java.util.concurrent.Executor ex) {
      ex.execute((){ System.out.println("hello"); });
  }

Here is a definition of an API that locks and then unlocks a java.util.concurrent.Lock, before and after a user-provided block of code:

public static <E extends Exception>
void withLock(Lock lock, void() throws E block) throws E {
    try {
        lock.lock();
        block();
    } finally {
        lock.unlock();
    }
}

This can be used as follows:

withLock(lock, (){
    System.out.println("hello");
});

You might find this syntax a bit tedious. Not to worry - see below.

12. Abbreviated invocation syntax.

A new invocation statement syntax is added to make closures usable for control abstraction:

AbbreviatedInvocationStatement
Primary ( ExpressionList ) Block
AbbreviatedInvocationStatement
Primary ( Formals ) Block
AbbreviatedInvocationStatement
Primary ( Formals : ExpressionList ) Block

This syntax is a shorthand for the following statement:

Primary ( ExpressionList, ( Formals ) Block );

Note that this syntax is only a convenience to make some kinds of closure-receiving APIs more convenient to use to compose statements.

We could use the shorthand to write our previous example this way

withLock(lock) {
    System.out.println("hello");
}

This is not an expression form for a very good reason: it looks like a statement, and we expect it to be used most commonly as a statement for the purpose of writing APIs that abstract patterns of control. If it were an expression form, an invocation like this would require a trailing semicolon after the close curly brace. Forgetting the semicolon would probably be a common source of error. The convenience of this abbreviated syntax is evident for both synchronous (e.g. withLock) and asynchronous (e.g. Executor.execute) use cases.

13. Definite assignment

The body of a closure may not assign to a final variable declared outside the closure.

A closure expression does not affect the DA/DU status of any variables it names.

14. Exception type parameters

To support exception transparency, we add a new type of generic formal type argument to receive a set of thrown types. [This deserves a more formal treatment] What follows is an example of how the proposal would be used to write an exception-transparent version of the withLock() example we've been using. The syntax is quite tentative at this point (ideas are welcome).

public static <throws E extends Exception>
void withLock(Lock lock, void() throws E block) throws E {
    try {
        lock.lock();
        block();
    } finally {
        lock.unlock();
    }
}

This method uses a newly introduced form of generic type parameter. The type parameter E is declared to be used in throws clauses. If the extends clause is omitted, a type parameter declared with the throws keyword is considered to extend Exception (instead of Object, which is the default for other type parameters). This type parameter accepts multiple exception types. For example, if you invoke it with a block that can throw IOException or NumberFormatException the type parameter E would be IOException|NumberFormatException. In those rare cases that you want to use explicit type parameters, the keyword throws is required in the invocation, like this:

Locks.<throws IOException|NumberFormatException>withLock(lock) {
    whatever();
}

Type parameters declared this way can be used only in a throws clause or as a type argument to a generic method, interface, or class whose type argument was declared this way too.

15. Implementing a Function Type

A programmer may write a class that implements a function type. The implementation is written as a public method with the keyword do in place of the method's identifier. For example

class MyBlock implements void() {
    public void do() {
        // implementation of the function
    }
}

In this way programmers can, for example, create implementations of function types that are serializable.

Acknowledgments

The authors would like to thank the following people whose discussions and insight have helped us craft, refine, and improve this proposal:

Lars Bak, Cedric Beust, Joshua Bloch, Martin Buchholz, Danny Coward, Erik Ernst, Christian Plesner Hansen, Doug Lea, "crazy" Bob Lee, Martin Odersky, Tim Peierls, John Rose, Ken Russell, Mads Torgersen, Jan Vitek, and Dave Yost.

The Debate over Closures for Java

2006-09-06T21:00:00.000-07:00

We've been continuing work on the closures proposal. I'd like to give you some feedback on what I think about the debate. Tomorrow I'll post an updated proposal, and the next day I'll outline an alternative version of the proposal that avoids function types and contrast it with the current draft; some people think that might be a better approach, though we have some doubts that I'll explain.

Our publication of the draft closures proposal resulted in a great deal of debate and excitement. Even if we end up doing nothing, I think that is very healthy. These kind of things rarely get debated in such public forums. We've been listening to the debate as it rages (on scores of blogs and message boards, and the occasional email), and we're trying to adjust our thinking accordingly. My next post will be an updated version of the proposal, and the following will be an extended discussion of one alternative direction we're considering that addresses some concerns.

There are a few different kinds of feedback we've received, both positive and negative. To those whose feedback has been mostly positive: you've been no help whatsoever. Just kidding. Seriously, thanks for the support. We don't think things are perfect yet, and maybe they will never even be good enough to put anything like closures in the Java programming language. We need to figure out what, if anything, to change to make it better, so your criticism is welcome. If you can quantify precisely how much more fun Java will be to program in, that would help too.

To those with mainly negative or mixed feedback, I'd like to try to classify some of the most common concerns and give general, blanket responses. Please don't take these to mean we're dismissing your concerns. On the contrary, we expect the proposal to evolve, and your concerns are a primary source of information on how the proposal needs to evolve. This classification doesn't cover all the constructive criticism we've received or all the issues we know we need to address, and there is a great deal of overlap between these topics.

Closures don't buy you anything beyond what you can accomplish with inner classes. That just isn't true. See my previous blog post about use cases. Interfaces and inner classes solve the asynchronous use cases just fine, mostly, but they don't touch the synchronous use cases. I don't mean to imply that they can't be extended to cover both sets of use cases, but inner classes in their current form don't do it.

The addition of function types to the language is too much of a price to pay for closures. We have a few reactions to this. First, you're likely to be surprised how much you actually get with closures, and how little it actually costs you in complexity. While it might be possible to get closures without function types - see the alternative proposal for one stab at that approach - what you lose doing things that way is not trivial.

The structural typing of function types doesn't feel right in Java, which normally does its typing via programmer-defined named types. Actually, function types dovetail nicely with interfaces due to the closure conversion. The structural typing you get with closures is much like you would get using generic interfaces and using wildcards heavily in your code, except much simpler.

The proposal introduces a second way to do things that folks already do with interfaces. The concern here is that the language should provide strong guidance on how to do any particular kind of thing, and Java has already chosen to pass snippets of code around as objects that implement interfaces, typically via anonymous classes. Moreover, some existing APIs might look silly doing things the "wrong" way once a new way is introduced. I don't think this concern holds water because virtually all of the existing APIs in the JDK that I'm aware of are best written using interfaces rather than function types. I've heard the debate regarding the JDK notification APIs (for example, in swing) and what to do about them. I think they should be left alone.

Ordinary Java programmers won't be able to understand this stuff. Many folks who say this don't make it clear which parts of the proposal they find most troubling, or perhaps they don't see the proposal as decomposable into troubling and acceptable parts. The Closures for Java draft specification was written to be more like a specification than a tutorial. It is not a suitable thing to read to learn the language construct, any more than reading the Java Language Specification is a suitable way to learn object-oriented programming. Rather you would learn the feature by examples of gradually increasing complexity. I haven't provided that, and I apologize. I've tried to remedy that in my later blog posts but I'm afraid I'm not very good at that kind of writing.

If you believe that closures are inherently a difficult concept for programmers to understand, or some kind of language "trickery", I suspect you probably haven't done much coding in a language that supports them (see Steve Yegge's blog post Language Trickery and EJB, and Curtis Poe's article Sapir-Whorf is not a Klingon). In practice they are pretty straightforward and obvious. Things are complex with anonymous inner classes, and any tutorial would need to explain them as well. I will present an alternative spec in a few days that does away with function types entirely, syntax and all; with that change the spec may seem simpler than the previous one, but I believe as a practical matter it will be harder to use. Also gone are local functions from our proposal entirely. Those who identified function types as the main problem might be satisfied with the version of the proposal lacking function types. But if you have a hard time understanding anonymous inner classes, closures won't make things any easier as we can't remove anything from the language. There also needs to be a prototype implementation that people can actually use to get a feel for what closures can do. I eagerly await an open-source javac on which we can prototype this.

How much more expressive does the language become given the complexity of the additions? The gist of this concern is that adding closures seems to increase the complexity of the language substantially. Is the additional expressiveness worth the additional complexity? The best result would that we end up with an expressive but simple programming langauge. The question is: how much more expressive can you get with minimal changes to the language? We believe that closures adds significantly to the expressiveness of Java in an area that the language is severly lacking. The asynchronous use cases are handled just fine today, but the synchronous use cases like control abstraction and some kinds of functional programming idioms are very difficult.

Are you just doing this to compete with C#/Ruby/Javascript or add the latest experimental/research language feature? Closures have been an idea simmering in the background since the earliest days of Java, and it is the subject of repeated RFEs. Closures predate Java by many years. Closures were in Simula (the original object-oriented language), Lisp, and Smalltalk. They really do make some things easy that are difficult or impossible to express without them. Anonymous inner classes were a half-measure that made some use cases easier, but left some use cases unaddressed. Competition from other languages has shaped the political landscape and the programmer mindset to make closures more acceptable than they were before, so the time is ripe to propose them.

Values of function type can't be made serializable. Agreed, a problem in the previous spec. We intend that you should be allowed to "implement" function types so that you can make them serializable.

I can't stand the syntax. We've heard this before about things that people ended up loving once they started using them. We're open to alternatives. The alternative of just using anonymous class instance creation expressions doesn't work. Closures are not just shorthand for making an anonymous class, because names appearing inside the closure are resolved in the context of the enclosing scope instead of in the context of the anonymous class being created. Perhaps there is a better way of writing a function type. Perhaps we can improve the syntax for writing a closure - but it does require its own distinct syntax in order to get the expressive power. Your suggestions and ideas are welcome.

The synchronous and asynchronous use cases are so different that they deserve completely different syntax. I'm not sure about this argument. First, in the proposal the two kinds of APIs do use completely different syntaxes: one uses function types and the other uses interfaces. A closure means precisely the same thing (if it is allowed) whether used in one kind of API or the other. Any difference in meaning is because of what the API elects to do with the closure (for example, invoke it or not invoke it). Therefore, to understand a use of a closure, you need to consult the documentation or specification of the method it is passed to. In this respect a closure is no different than a value of any other type. I suspect I don't fully understand this concern, and we'll keep listening.

Closures will be implemented using the JVM invokedynamic bytecode; won't that hurt performance? The short answer is: no, not necessarily, and there are alternative implementation strategies that use existing instructions.

Compatibility with the existing language demands an inelegant/kludgy design for closures. Frankly, I don't believe it. I believe that the Java language in JDK7 can have closures AND seem to have been designed with them from the beginning, with virtually all existing APIs using the most appropriate idiom. Some minor syntactic challenges remain: closures would probably better be written with a new keyword (lambda? fun?), but can't due to backward compatibility; a related issue is the difficulty of using "," or "|" in the syntax for disjunction types for type parameters representing thrown exception types. I believe we are likely to converge on a syntax that feels quite natural once people start trying to use it.

A related argument compares the Java programming language to a delicious Oreo® Cookie: you can add syntactic sugar to its outside and still have a nice Oreo cookie, but if you disturb its delicious design center it just won't be the same anymore. Implicit in this argument is a warning (or veiled threat) that hordes of Java programmers will abandon the platform if anything so horrible is done to the language. I think this line of reasoning is overly melodramatic. In fact, I believe the addition of closures will attract a number of programmers who have previously had no choice but to seek alternative languages due to limitations of Java.

Closures are too powerful; programmers should not have the freedom to effectively define their own control constructs, because they will write programs that are too hard to understand. Instead, the argument goes, we should add new statements to the language for each of the important use cases we know about and leave it at that. The gist of this concern is that while the Java programming language today lends itself to easily understood programs, the addition of closures will result in a language in which readers of programs have no firm ground to stand on, and will not be able to tell what a program means. I've only heard this concern raised by a small number of people and our response (thanks to James Gosling) is: by the same logic we shouldn't allow programmers to write their own methods either. If you're reading a program with invocations of unfamiliar methods, you may have to consult the documentation of those methods to understand what the code does; if the code is well-written the name of the method will give you a good hint. This is true whether or not the method receives a closure as an argument. Related to this argument is the concern that the addition of closures will make it possible to write programs that are really hard to understand, but in reality poor programs can be written in any language. This line of reasoning is made by those who consider themselves advocates of the B&D (Bondage and Discipline) school of language design, but I would characterize it as the S&M (Sadism and Masochism) school. The subtext is that we should not trust ordinary programmers with anything so expressive as closures.

Closures should work with classes that have a single abstract method, like java.util.TimerTask, in addition to single-method interfaces. OK, sure, that sounds like a good idea.

There have also been proponents of various other languages like Smalltalk, Ruby, and Javascript noting with smug amusement that the Java folks (or some of them, anyway) finally "get" closures. To them I say "Pfffft!"

Control abstraction

2006-09-05T23:58:00.000-07:00

All of the examples of synchronous use cases for closures that I've shown so far fall into the general category of control abstraction. The idea is that you have a common pattern appearing in your code, and you want to abstract the common parts while allowing the caller to provide the parts that differ. You can think of these use cases as satisfying a desire to extend the set of statements available in the language. Java is already pretty good at data abstraction, but not so good for control abstraction.

Thanks to a blogger whom I can't identify, I have another simple use case for closures of the synchronous variety (still control abstraction, though). I would love to be able to use this in the implementation of my project, Google Calendar to simplify the code in hundreds of places.

Many places throughout our code we have this pattern appearing:

 
void someOperation() throws SomeException { 
    long t0 = System.nanoTime(); 
    boolean success = false; 
    try { 
        someOperationInternal(); // may fail, throwing SomeException 
        success = true; 
    } finally { 
        long elapsed = System.nanoTime() - t0; 
        logElapsedTime("someOperation", success, elapsed); 
    } 
}

The presence of this code helps us with realtime (i.e. elapsed time) performance measurement, but it clutters up our code and tends to obscure the logic of the application. We would prefer to write a timeOperation method once, thereby enabling us to write the above code as follows:

 
void someOperation() throws SomeException { 
    timeOperation("someOperation", (){ 
        someOperationInternal(); // may fail, throwing SomeException 
    }); 
}

Or, better yet, (presuming the language supports the abbreviated invocation syntax that I'll describe in a future post)

 
void someOperation() throws SomeException { 
    timeOperation("someOperation") { 
        someOperationInternal(); // may fail, throwing SomeException 
    } 
}

The timeOperation method can be written (once) as follows:

 
<E extends Exception> 
void timeOperation(String operationName, void() throws E block) throws E { 
    long t0 = System.nanoTime(); 
    boolean success = false; 
    try { 
        block(); 
        success = true; 
    } finally { 
        long elapsed = System.nanoTime() - t0; 
        logElapsedTime(operationName, success, elapsed); 
    } 
}

This is the best way I've seen to remove this kind of redundant code that is currently repeated hundreds of times throughout our application. This example should help illustrate why closures will help make code much easier to read. Certainly timing support could instead be done with an additional extension to the Java language: a new statement for timing blocks of code. Do you also add a new statement for closing your streams at the end of a block, and one for locking and unlocking your java.util.concurrent locks around a block of code? Once you start down that path, where does it all end? We'd prefer to give ordinary programmers the ability to write these kinds of methods (and perhaps place some of them into the JDK) rather than adding a series of language extensions to address particular use cases.

Besides control abstraction, there are also important synchronous use cases for closures inspired by functional programming idioms with a very different feel, and I'll blog about that separately.

Use cases for closures

2006-08-25T12:20:00.000-07:00

Some people have been reacting to this proposal as if it represents Sun's plans for the future of the language. At this stage it is just some ideas being drawn up to address a number of requirements in a clean and uniform framework. Other people are working on alternative proposals, and I expect you'll see those soon. It is too early to place bets on what, if anything, Sun will do in this space for JDK7.

With the insights described in my last blog entry, we no longer need two separate syntactic forms for closures. We also don't need the "labelled" nonlocal return statement. We're updating the draft spec with this and other changes, making it more precise, and adding a bit of rationale. I hope to augment the brief rationale that will appear in the draft with further explanation here.

Closures, Inner Classes, and Concurrency

Our "solution" to concurrency issues in the original version of the proposal was quite unsatisfying. Part of the problem was that we could see no way to satisfy the requirements of that community while preserving some of the most useful features of closures and without violating the language design principles. Since then, we've been reexamining the issue, and I think we've found a very tidy solution.

Asynchronous use cases

To understand the solution, it is useful to characterize the use cases for closures into two very distinct categories. The first category, which I'll call asynchronous, are those in which the user-privided code is not called immediately by the API, but rather is saved to be executed from another thread or at a later time. This includes asynchronous notification frameworks, the concurrency framework's executors, and timer tasks. Generally speaking these fall into a pattern in which the caller of the API controls what will be done, but the API controls when it will be done. These kinds of Java APIs are widespread in practice, and are often expressed using single-method interfaces or abstract classes. Because the code passed into the API is invoked when its context no longer exists, it is generally inappropriate to allow nonlocal control-flow. Because it may be invoked from another thread, it is often inappropriate to allow such code to access mutable local state.

The closure proposal attempts to address this category of use case by providing the closure conversion, which converts the user-written chunk of code into an anonymous inner class.

To make this very concrete, let's see how this would affect they way you can submit a task to a java.util.concurrent.Executor. The way you'd write it today (and this way of writing it will always be available) is this:

void sayHelloInAnotherThread(Executor ex) {
    ex.execute(new Runnable() {
        public void run() {
            System.out.println("hello");
        }
    });
}

Now, that's not too bad, but using closures you can write the following, without any change to the executor APIs:

void sayHelloInAnotherThread(Executor ex) {
    ex.execute(() {
        System.out.println("hello");
    });
}

This is a little better, though not necessarily enough by itself to justify closures. This works because although Executor.execute takes a Runnable as an argument, and we wrote a closure, the closure conversion converts it to a Runnable. Essentially, the closure conversion builds an anonymous instance of Runnable whose run method just invokes the closure. The closure conversion is implemented at compile-time, generating exactly the same code as in the first case, so there is no runtime overhead.

If we adopt an alternative invocation syntax that we're working on to allow an abbreviated form of invocation statement for methods involving closures (we're still working on the specification), you would be able to write it something like this:

void sayHelloInAnotherThread(Executor ex) {
    ex.execute() {
        System.out.println("hello");
    }
}

If this syntax doesn't mean anything to you, just imagine that the block appearing at the end of the invocation of ex.execute is turned into a closure and then passed as the last argment (the only one, in this case) to execute. That's basically what the abbreviated invocation syntax does.

This is a significant improvement compared to what you have to write today. You could think of these uses cases as a shorthand for creating anonymous class instances. The analogy isn't exact, as certain details necessarily differ to get the langauge construct to be well defined. Most importantly, the binding of the names inside the block of code have to be based on the scope in which the code appears, which in this case is the method sayHelloInAnotherThread, not in the scope of the anonymous class that will be created. Why? Well, if the meaning of a name appearing in a block of code changes when you use it in code passed in to method like this, then it would be a fruitful source of Java Programming Puzzles. That is especially true if the scope from which the names are inherited isn't even mentioned in the code. It gets worse when you consider that the method name to which the closure is being passed might be overloaded, so you can't tell when you're typechecking the block which interface you are building.

Some people believe that what you can do with interfaces and classes is enough, and would prefer to see no more (and possibly less) than some abbreviated syntax for writing anonymous class creation expressions. The most significant difference between that approach and closures appears in the other category of use cases.

Synchronous use cases

The other category I'll call the synchronous use cases, in which the closures you pass to an API element are invoked by your own thread strictly before that API element returns control to you. There aren't many of these APIs appearing in the JDK, usually because such APIs are rather awkward to write. Anonymous class instances sometimes satisfy the requirement for this category of use cases, and when they don't programmers resort to various contortions to get their job done, or simply leave the job half done. Let's see how far we can get, though, using only interfaces for this category. I'll give a single example, again motivated by the concurrency framework.

The Java synchronized statement is convenient and easy to use, but for many purposes has been superceded by the Lock interface in the concurrency framework. Here is how you currently use a Lock to synchronize a snippet of code:


void sayHelloWhileHoldingLock(Lock lock) {
    lock.lock();
    try {
        System.out.println("hello");
    } finally {
        lock.unlock();
    }
}

This syntax is tedious and distracting. One would prefer to write something like

void sayHelloWhileHoldingLock(Lock lock) {
    withLock(lock) {
        System.out.println("hello");
    }
}

Let's try to write this using only interfaces and classes, and perhaps taking advantage of the syntactic abbreviation that we might think of as being implemented by translation into inner classes. The first thing we'll need is an interface that represents the block of code that we're passing in. java.lang.Runnable might just do it. So our first try at writing this method might look something like this:

void withLock(Lock lock, Runnable runnable) {
    lock.lock();
    try {
        runnable.run();
    } finally {
        lock.unlock();
    }
}

This works for some uses. It allows us to write the sayHelloWhileHoldingLock method, above. So far so good. What happens if we try to write other clients using this?

Suppose we have the following method that uses old-style locks, and we want to refactor it to using a java.util.concurrent lock.

void callBigHonkingWhileHoldingLock(Object lock) throws CheckedException {
    synchronized (lock) {
        bigHonkingMethod(); // throws CheckedException
    }
}

The refactored version would presumably look something like this:

void callBigHonkingWhileHoldingLock(Lock lock) throws CheckedException {
    withLock (lock) {
        bigHonkingMethod(); // throws CheckedException
    }
}

It would be nice if this just worked, but it doesn't quite. The reason is that the run method of Runnable isn't declared to throw any exception types, and specifically it doesn't throw CheckedException. If we make something almost like Runnable but in which the run method throws Exception, that doesn't quite work either because the implementation of withLock would have to declare that it throws Exception too, and we aren't catching it in callBigHonkingWhileHoldingLock.

The immediate problem is that the withLock method doesn't provide exception transparency, which means that the method throws the same exception type as the method passed in to it. In order to get that, we'd have to make a version of Runnable that can also throw some unspecified exception type. We can do that with generics:

class RunnableWithException<E extends Exception> {
    public void run() throws E;
}

now we can make the withLock method exception-transparent:

<E> void withLock(Lock lock, RunnableWithException<E> runnable) throws E {
    lock.lock();
    try {
        runnable.run();
    } finally {
        lock.unlock();
    }
}

Assuming the closure conversion can automatically figure out that it should be creating an instance of RunnableWithException<CheckedException>, which it should, this works just fine.

Things are a bit more complicated when the thing you're running can throw two checked exception types; you really want to write a version of withLock that doesn't care how many exceptions are thrown in the block, they are all just propogated out. Let's take it as a given that the generic type system can be extended to do that (I don't think it's too difficult). Now we have a version of withLock that is completely exception-transparent, and can be invoked on a block of code that throws any set of exception types, which will have to be declared or caught by the caller of withLock. So far so good.

Let's take another slightly more complex example of a method that we might want to refactor to use the new locks:


boolean containsFred(Object lock, List<String> c) throws CheckedException {
    synchronized (lock) {
        for (String s : c) {
            if (s.toLowerCase().equals("fred")) return true;
        }
    }
    return false;
}

The refactored version would presumably look something like this:

boolean containsFred(lock lock, List<String> c) throws CheckedException {
    withLock (lock) {
        for (String s : c) {
            if (s.toLowerCase().equals("fred")) return true;
        }
        return false;
    }
}

But this won't compile. The first problem is that the variable c isn't final, but it is being accessed within an inner class. We can easily fix that in this case by making c final because the variable isn't assigned anywhere. If the variable were assigned somewhere (but not in the block), we could create a final local variable to hold a copy of the variable's value where it is used, and use that other variable inside the block.

There is a worse problem: the return true statement inside the block is returning from the RunnableWithException.run method, not containsFred but the run method returns void. We could solve that, perhaps, by making a new version of Runnable-like interface that returns a boolean. Or better yet perhaps we could add another generic type parameter to indicate the return type of the interface's method, and have the withLock method return the value to its caller that was returned by the block.

So far so good... well, not quite as good as one would hope, because the refactoring isn't straightforward and requires serious thought from the programmer. Did you notice that the final return statement had to move inside the block? But Java programmers generally speaking are smart people, and they can work out how to do this. I'm sure they enjoy (as much as I do) spending their time puzzling out how to coerce the language into doing what they want.

Next let's try to refactor the following method to use new locks:

int countBeforeFred(Object lock, List<String> c) throws CheckedException {
    synchronized (lock) {
        int count = 0;
        for (String s : c) {
            if (s.toLowerCase().equals("fred")) return count;
            count++;
        }
    }
    reportMissingFred(c);
}

Performing a straightforward refactoring of this code to use a method like withLock runs into a number of problems. Let's look at the snippet of code that would become the body of the method RunnableWithExceptionAndReturn.run

{
    int count = 0;
    for (String s : c) {
        if (s.toLowerCase().equals("fred")) return count;
        count++;
    }
}

This can't possibly be the body of any method: it returns a value in the middle of a loop, but it also falls off the end of its execution. In order to refactor this method to use something like withLock, we have to start reorganizing the code to avoid these problems. We could move reportMissingFred(c); into the synchronized block, but that changes the behavior of the program. Another idea is to use a boolean state value that is returned to the caller in addition to the count, to tell the caller whether or not the block fell off the end, but where would we put it? We can't make it a local variable in countBeforeFred because the block can only use final variables. Perhaps we could use a ThreadLocal. We could put a length-one final boolean array in the local scope of countBeforeFred, and keep the boolean value in element zero.

If the body of the countBeforeFred were much more complicated in its control structure at all, for example containing a break from inside the block to outside it, this kind of refactoring might become prohibitively complex. Realistically, we would just give up and stop trying to use withLock at all, effectively inling it. After all, it is only a few lines of locking code, and it's an idiom that programmers should be expected to learn, right? The idiom is even documented in the javadoc of the Lock interface.

We've only touched the surface, though. The method withLock is perhaps simple enough that you won't mind having to inline it except in the simplest of circumstances when it does you the least good. You might feel some discomfort at repeating code, especially such boilerplate code, but there really isn't any good alternative, and after all it really isn't that much code.

However, some synchronous APIs are naturally more complex, and it doesn't take much more complexity in the API before it simply doesn't make sense for the caller to repeat code from the implementation of the API to avoid these problems. Consider, for example, an API that automatically closes your streams for you. Instead of writing

{
    Stream s = null;
    try {
        s = openStream();
        yourCodeHere();
    } finally {
        try {
            if (s != null) s.close();
        } catch (IOException ex) {}
    }
}

You would write an invocation of a library method closeAtEnd to get the same effect:

{
    closeAtEnd(Stream s : openStream()) {
        yourCodeHere();
    }
}

You would probably go to much greater lengths to avoid inlining the API method closeAtEnd than withLock, but the same problems are are unavoidable. These are just two specific examples of particular APIs of the synchronous closure variety; if the API implementation is much more complicated, or contains details in its implementation that callers should not be aware of, the problem becomes acute because by-hand inlining is no longer an option. If you've ever used java.security.AccessController.doPrivileged, for example, you know the pain.

While we've shown how to achieve exception transparency, we haven't quite achieved control transparency, which means that control constructs like break, continue, and return have the same meaning when enclosed by a closure. The idea is that you should be able to wrap a block of code in an invocation of withLock, closeAtEnd, or any other API that takes a block of code, and the meaning of the control constructs appearing in that code should be the same. Ideally, the only difference is that the block is executed while a lock is held, or a stream is closed after the block, or more generally whatever is specified and implemented by the API. You should be able to break from the block to get out of a loop or switch statement that might enclose the invocation of withLock or closeAtEnd. We've looked at examples where return is problematic, but the same problems occur for other control constructs. Similarly, and for the same reasons, in synchronous APIs you want to be able to refer to and modify local variables in the enclosing scope; because the block is executed synchronously and by the same thread, there are no more concurrency issues than there are for an ordinary block statement.

If you believe that these two methods - closeAtEnd and withLock - are the only synchronous APIs worth having, now or ever, you might be tempted to add some very specific language features to Java to get precisely the desired functionality, and dismiss the rest of our closure proposal. We believe that would be a mistake, because we believe that synchronous closures would greatly simplify the lives of programmers. There are not many APIs of this sort today, mainly because they can't be made to work very well with the language in its current state.

The problem to be solved for synchronous closures is that the programmer should not have to transform or contort his code at all in order to wrap it in a closure to pass it to one of these APIs.

Bridging the Chasm

We're left with two seemingly irreconcilable sets of requirements. Asynchronous closures should not be allowed to refer to local variables in the enclosing scope, do not support nonlocal control-flow, do not require exception transparency, and generally speaking are done today using interfaces or abstract classes. Synchronous closures, on the other hand, should be allowed to refer to locals in enclosing scopes, should support nonlocal control-flow, and may require exception transparency, but generally speaking don't appear in the Java APIs because they are not expressible. These use cases would seem to have so little in common that one might not expect a single language construct to satisfy both sets of requirements. But we believe a small modification to the currently published proposal, in addition to the change described in my previous blog post, satisfies both sets of requirements. This is a very tidy result, because having a single uniform language feature is very much preferable to having two.

The change is very simple, but the change is not to the specification of function types or closure expressions, it is to the specification of the closure conversion, which allows you to write a closure - a block of code - where a one-method interface is expected. We add the additional restrictions that a closure to which the closure conversion is applied must not reference any non-final local variables from enclosing scopes, and must not use break, continue, or return to transfer control out of the closure, or the program is in error. These are the same restrictions you have now with anonymous inner classes.

How does this solve both sets of problems? Well, first consider the asynchronous use cases. These are expressed using interfaces, and therefore in order to use these APIs with the closure syntax, the block must be subjected to the closure conversion. Consequently, if there is any use of a nonlocal non-final variable, the compiler must reject the program. Similarly, the compiler must reject the program if there is nonlocal control-flow. The things that you will be able to do are essentially the same as what you can do today, but with a much simpler syntax and clearer semantics.

However, APIs for the synchronous use cases have largely not been written yet, so they can be written using the new function types. A closure is an expression of function type, so the closure conversion is not required, and its restrictions do not apply. Consequently, the block is allowed to use nonlocal non-final variables, and can use nonlocal control-flow. The block has essentially the same meaning as it would if it were not wrapped by a closure. In the rare cases that an existing API is expressed using an interface but is a synchronous use case - for example java.security.PrivilegedExceptionAction - the library writer can write a small utility method that converts a closure to an implementation of the interface, enabling the client to take advantage of the full generality of the feature. To implement withLock using closures, with full exception- and control-transparency, the JDK authors could write this:

<E extrends Exception>
public static void withLock(Lock lock, void()throws E block) throws E {
    lock.lock();
    try {
        block();
    } finally {
        lock.unlock();
    }
}

The method closeAtEnd is similarly straightforward.

Once you have support for synchronous closures, however, there are many opportunities for the addition of extremely useful APIs to the JDK as library methods, such as withLock, closeAtEnd, and a method that simplifies the use of java.security.AccessController.doPrivileged. More importantly, synchronous closures enable Java programmers - not the JDK authors, but ordinary Java programmers - to freely refactor and abstract over pieces of their code in simple ways that are not currently possible for seemingly arbitrary reasons.

Refactoring

This isn't just about writing and reading programs, it is about refactoring programs too. Your ability to factor common code by moving it into a separate "routine" is currently limited by how the block passed by the caller can interact with the caller. Closures, and synchronous closures in particular, simply remove that limit. When a program is in need of a small refactoring, you are free to factor just the code in common, rather than revisiting the design of the basic data structures and organization of your application. That was the point of my post What's the Point of Closures. Some people missed the point, and thought the program was merely flawed from the beginning and should have been rewritten. Yes, it was flawed, as are most programs in the real world. Not every programmer can get everything right the first time, or can rewrite thousands of lines to solve a localized issue. The whole point of such examples of refactoring is that the original program is flawed in some way. If the program were not flawed then refactoring might not be required. The refactorings supported by closures enable the programmer to get everything right in the end by small refinements to the program, step by step.

And more...

I believe that the additional expressiveness of the language with closures will enable people to discover and use new and powerful kinds of design patterns to organize their code in ways not possible today, making things simple that currently seem complex. I have some more ideas in this direction, which I'll write about at another time when I've had more sleep.

Tennent's Correspondence Principle and Returning From a Closure

2006-08-23T08:22:00.000-07:00

I just had a very productive meeting with coauthors of the closure proposal. I think we made a lot of progress addressing most of the specific concerns people have with the proposal (with the exception of subjective comments like "I don't think you should do this kind of thing to Java").

One issue in particular has been nagging us, and in spite of Gilad's insistence that we comply with Tennent's Correspondence and Abstraction Principles (described in detail in the now out-of-print book Principles of Programming Languages by R.D.Tennent), Gilad reluctantly admitted before we published the first draft that there doesn't seem to be a way of doing that for returning from a closure without introducing inconsistencies with the rest of the language. In the end we discovered that there is indeed a way to do it, and it seems to be rather cleaner than any of the alternatives.

Setting aside the technical details of Tennent's approach, the principle applies directly to the closure construct. A closure can be used to abstract over an expression or a statement. The principle dictates that an expression or statement, when wrapped in a closure and then immediately invoked, ought to have the same meaning as it did before being wrapped in a closure. Any change in semantics when wrapping code in a closure is likely a flaw in the language.

To put this more concretely, an expression

expr

should have the same meaning as the expression that wraps it in a closure and then evaluates it:

(():expr}()

And a block statement

{ stmt; ... }

ought to have the same meaning as creating and invoking a closure that wraps the statement:

((){ stmt; ... })()

Tennent's principles are very powerful because violations of them tend to show up in the language as flaws, irregularities, unnecessary restrictions, unexpected interactions or complications, and so on. While exploring the language design space for closures, every time we were tempted to violate them we found that there were very real and unpleasant consequences; they are very powerful tools for detecting bad smells in a programming language design. The principles apply no less when extending an existing programming language, because what you are doing in that case is designing the next version of a language. We discovered that when a bad smell is detected by these principles, it is often straightforward to illustrate specific problems. The problems we identified also arise in many supposedly "simpler" proposals that attempt to provide merely a shorthand notation for construcing anonymous class instances. I'll show two specific issues that we identified based on bad smells, examples of the real problems caused, and how we solved them.

The meaning of `this`

Before we look at the question of how to return from a closure, and to help understand how the principles are applied, let's look at the application of Tennent's principles to the question of the meaning of this within a closure. One possibility would be that it designates the closure object itself. That might be useful if you want to define a recursive closure, as you now have a convenient way of invoking yourself. An alternative is that it designates the anonymous class instance that is created if the closure conversion is applied. That seems natural if you like to think of the closure expression as a shorthand for creating an anonymous class.

Unfortunately, both of these alternatives get you into trouble, and we can show specific ways that the language no longer fits together when you take these approaches. The former approach, for example, doesn't allow you to analyze the types of expressions appearing within the closure, because the closure type depends on the type of the returned expression, but the returned expression might use "this", and so may depend on the type of the closure. The latter approach has a similar chicken-and-egg problem, because the type of interface you're creating may depend on the types within the closure, but the types within the closure depend on the type of the interface you're creating.

To see the problem more simply, one issue is that the expression this no longer designates the same thing when wrapped by a closure. In order to abstract (i.e., wrap a closure around) a piece of code that uses this or uses any names that are inherited from Object, you would have to systematically rewrite those names to qualify them in some way to ensure that they refer to the appropriate object. In other words, you'd have to change every this to EnclosingClassName.this and every toString() to EnclosingClassName.this.toString(). To be most useful as an abstraction facility, programmers should be free to wrap a piece of code in a closure without worrying that its semantics will change subtly. To satisfy Tennent's Correspondence Principle, a closure should introduce into the scope of the closure no names that are not explicitly declared by the user - that is, only the closure's parameters.

Returning from a closure

The principle also applies to the problem of returning from a closure. The current draft proposal suggests that we use the existing return syntax for returning from a closure, but that violates the principles; you can detect the bad smell by observing that this statement

{ if (...) return; }

doesn't mean the same thing as this:

(){ if (...) return; } ()

The former returns to the enclosing method (not shown), while the latter returns from the closure, effectively doing nothing.

One idea, desribed in the further ideas section of the draft spec, is to introduce a new syntax for returning from a closure, and reserve the return statement for returning from a method, function, or constructor. We toyed with the statement syntax

^ expression;

Setting aside aesthetics, this seems to satisfy the requirements, because this isn't legal syntax outside a closure. Existing code does not have statements of this form, so wrapping such code could not change its meaning. However, on further reflection we realized that this syntax and all of the other new kinds of return statements that we considered have the same flaw as using return: while existing code doesn't use this new statement form, once we introduce it into the language we should expect people to start using it in new code. And once they do, any code that includes this statement cannot be wrapped in a closure without changing its meaning. Once we identified the bad smell this way, it wasn't hard to come up with realistic examples where it gets in the way of using the language.

Having eliminated any form of return statement, what are you left with? Referring back to Tennent's principles is instructive: you should be able to replace an expression expr with

(){ expr } ()

This is the proposed syntax for returning a value from a closure. It is simpler than the existing spec because no rules are needed to infer the return type; it is the type of the expression. Of course, we will want to allow a list of statements instead of an expression to allow the construct to close over statements (in which case the closure returns void), and allow a list of statements to precede a trailing expression (in which case the final expression is the result of the closure). An expression without a trailing semicolon isn't a legal statement form, so there is no confusion with any existing constructs. This nicely satisfies Tennent's principles. My only regret is that there is no single way to both designate the returned value and return from a closure before its end, which would be slightly more consistent with Java's existing control constructs.

And more...

We made progress on a number of issues:

We know how to address concerns about how the closure conversion will interact with APIs like concurrency and asynchronous notification systems where the closure isn't just called by the current thread; in those APIs you don't want to allow nonlocal control-flow or capturing nonfinal variables.
We think we can add support for type inference of exception types to allow writing APIs in which the set of exceptions from a block (closure) that is passed in to the API can propogate out of the API while being strongly type-checked.
We think it should be possible to write a class that "implements" a function type, as suggested by "crazy" Bob Lee, so that you can define a custom toString() to make debugging easier or make the implementation serializable.
We started looking at a number of specific use cases that have been suggested, such as a library that allows you to execute a block of code while holding a java.util.concurrent.locks.Lock, unlocking it at the end, or a library that closes your streams (or other Closable things) after your block of code is finished.
We've also made progress on detailing the set of implementation techniques that might be used to implement the facility.

I'll blog about these later.

What's the point of Closures?

2006-08-19T17:50:00.000-07:00

A number of people have asked me: What's the point of closures? Can't you accomplish pretty much the same thing with the existing language constructs? What does it really buy you?

If you haven't programmed using closures, and you've gotten used to the Java idioms for the past ten years, it might be hard to see what closures really buy you. This is my attempt to give you a glimpse of that, by way of an extended example.

The problem

Suppose you are working with an application that maintains a list of documents, and for each individual in some set a list of document annotations. For the sake of this example, suppose the two lists are parallel. That is, if you take the list of annotations from an individual, the values correspond elementwise with the elements of the document list. To make this more concrete:

class Document { ... }
class DocAnnotation { ... }
class Person { ... }
class Documents {
    static List<Document> allDocuments();
}
class Persons {
    static Set<Person> allPersons();
    static Person GEORGE_W_BUSH = ...;
}
class DocAnnotations {
    static Map<Person,List<DocAnnotation>> allAnnotations = ...;
}

Now, you might ask a question such as: Has George Bush annotated any documents mentioning Iraq as secret. In this hypothetical application, you might code that up something like this:

boolean bushMarkedAnyIraqDocsSecret() {
    Iterator<Document> docI = Documents.allDocuments().iterator();
    Iterator<DocAnnotation> annI =
        DocAnnotations.allAnnotations.get(GEORGE_W_BUSH).iterator();
    while (docI.hasNext() && annI.hasNext()) {
        Document doc = docI.next();
        DocAnnotation docAnn = annI.next();
        if (doc.mentions("Iraq") && docAnn.marked("secret")) {
            return true;
        }
    }
    return false;
}

We could abstract this over what we're looking for in the document, who'se annotations we're looking for, and what kind of annotation we're looking for:

boolean personAnnotatedOnKeyword(Person person, String ann, String key) {
    Iterator<Document> docI = Documents.allDocuments().iterator();
    Iterator<DocAnnotation> annI =
        DocAnnotations.allAnnotations.get(person).iterator();
    while (docI.hasNext() && annI.hasNext()) {
        Document doc = docI.next();
        DocAnnotation docAnn = annI.next();
        if (doc.mentions(key) && docAnn.marked(ann)) {
            return true;
        }
    }
    return false;
}

It is possible that abstracting in this way allowes us to avoid repeating this loop throughout the code, if the code frequently needs to ask this kind of question. Abstracting common code is good because, among other things, it allows us to reduce the number of things we need to change when we refactor code. For example, if we were to change the representation of a person's annotations to be a Map<Document,DocAnnotation> instead of List<DocAnnotation>, or make a DocAnnotation contain a reference to the Document, we would have to change this kind of loop everywhere it appears. So having a single place where the loop is written is a good thing, as there are fewer places in the code that depend on the exact representation of the data.

Abstracting the loop in JDK5

The next step is to try to abstract the loop itself. Java provides some convenient looping constructs, including the recently introduced for-each loop with its Iterable interface. We can use that, but we need to introduce a type over which we're iterating:

class DocAndAnnotation {
    final Document doc;
    final DocAnnotation docAnn;
    DocAndAnnotation(Document doc, DocAnnotation docAnn) {
        this.doc = doc;
        this.docAnn = docAnn;
    }
}

Now we can provide looping support by writing the loop only once in the code like this

Collection<DocAndAnnotation> docsWithAnnotations(Person person) {
    Iterator<Document> docI = Documents.allDocuments().iterator();
    Iterator<DocAnnotation> annI =
        DocAnnotations.allAnnotations.get(person).iterator();
    List<DocAndAnnotation> result =
        new ArrayList<DocAndAnnotation>();
    while (docI.hasNext() && annI.hasNext()) {
        Document doc = docI.next();
        DocAnnotation docAnn = annI.next();
        result.add(new DocAndAnnotation(doc, docAnn));
    }
    return result;
}

This allows us to write the original loop like this:

boolean personAnnotatedOnKeyword(Person person, String ann, String key) {
    for (DocAndAnnotation docAndAnn : docsWithAnnotations(person)) {
        if (docWithAnn.doc.mentions(key) && docWithAnn.docAnn.marked(ann)) {
            return true;
        }
    }
    return false;
}

So far so good, but this solution has an unfortunate feature: it constructs the entire list even if the answer can be found by looking at only the first annotated document. We can do slightly better by constructing a lazy iterator instead of an eager list. We do that by rewriting docsWithAnnotations as follows:

Iterable<DocAndAnnotation> docsWithAnnotations(Person person) {
    final Iterator<Document> docI =
        Documents.allDocuments().iterator();
    final Iterator<DocAnnotation> annI =
        DocAnnotations.allAnnotations.get(person).iterator();
    return new Iterable<DocAndAnnotation>() {
        public Iterator<DocAndAnnotation> iterator() {
            return new Iterator<DocAndAnnotation>() {
                public boolean hasNext() {
                    return docI.hasNext() && annI.hasNext();
                }
                public DocAndAnnotation next() {
                    return new DocAndAnnotation(docI.next(), annI.next());
                }
                public void remove() {
                    throw new UnsupportedOperationException();
                }
            };
        }
    };
}

Now, without changing personAnnotatedOnKeyword, the same loop works without the overhead of building the entire List<DocAndAnnotation>.

This program does, however, produce a large number of small, transient garbage objects. The Iterator, Iterable, and DocAndAnnotation objects are all short-lived and simply exist to convey data from one part of the program to another. This is not necessarily a problem; HotSpot has a number of garbage-collection algorithms that are good at allocating and reclaiming short-lived objects. But in some applications it could contribute toward a performance bottleneck.

Can the looping code be refactored to avoid all these small allocations? The answer is yes, and there is a standard idiom for doing that in Java. The idea is to turn the control structure of the loop inside-out. Rather than having the personAnnotatedOnKeyword perform the iteration, we have a library method perform the iteration and pass the values to a snippet of code provided by personAnnotatedOnKeyword. That would look something like this:

interface WithDocumentAndAnnotation {
    void doIt(Document doc, DocAnnotation docAnn);
}
void docsWithAnnotations(
        Person person, WithDocumentAndAnnotation body) {
    Iterator<Document> docI = Documents.allDocuments().iterator();
    Iterator<DocAnnotation> annI =
        DocAnnotations.allAnnotations.get(person).iterator();
    while (docI.hasNext() && annI.hasNext()) {
        Document doc = docI.next();
        DocAnnotation docAnn = annI.next();
        body.doIt(doc, docAnn);
    }
}

A client can now iterate through a person's annotations by providing a snippet of code in the form of a class that implements the interface:

boolean personAnnotatedOnKeyword(
        Person person, final String ann, final String key) {
    class MyBody implements WithDocumentAndAnnotation {
        boolean result = false;
        public void doIt(Document doc, DocAnnotation docAnn) {
            if (doc.mentions(key) && docAnn.marked(ann)) {
                result = true;
            }
        }
    }
    MyBody body = new MyBody();
    docsWithAnnotations(person, body);
    return body.result;
}

This solves the transient memory allocation problem (if it even was a problem), but this version of the program again unnnecessarily iterates through all of the documents even if it needs to iterate through only a few to compute its result. We can fix that by modifying the WithDocumentAndAnnotation interface's method to return a boolean, which indicates whether or not iteration should continue or whether the loop should abort. This may enable many of the old clients of the docsWithAnnotations method to migrate to the new API, but it may not satisfy the needs of all of them. Presumably we could modify the interface further as we discovered different patterns of control-flow used by clients that iterate through documents and their annotations. We leave the details as an exercise to the reader.

Abstracting the loop with Closures

Closures provide a somewhat more convenient way to abstract the loop:

void docsWithAnnotations(Person person, void(Document,DocAnnotation) block) {
    Iterator<Document> docI = Documents.allDocuments().iterator();
    Iterator<DocAnnotation> annI =
        DocAnnotations.allAnnotations.get(person).iterator();
    while (docI.hasNext() && annI.hasNext()) {
        Document doc = docI.next();
        DocAnnotation docAnn = annI.next();
        block(doc, docAnn);
    }
}

This looks almost the same as our last version using JDK5, except that it does not require the introduction of the WithDocumentAndAnnotation interface. Let's see what the client looks like:


boolean personAnnotatedOnKeyword(
        Person person, final String ann, final String key) {
    docsWithAnnotations(person, (Document doc, DocAnnotation docAnn) {
        if (doc.mentions(key) && docAnn.marked(ann)) {
            return personAnnotatedOnKeyword: true;
        }
    });
    return false;
}

That's it. If we adopt the modifications to the proposal suggested in the Further Ideas section, the client would look something like this:

boolean personAnnotatedOnKeyword(
        Person person, final String ann, final String key) {
    docsWithAnnotations(person) (Document doc, DocAnnotation docAnn) {
        if (doc.mentions(key) && docAnn.marked(ann)) {
            return true;
        }
    }
    return false;
}

The only transient objects created in this version are the closure object itself and the two iterators used in the implementation of docsWithAnnotations. As you can see, the caller of docsWithAnnotations can use control-flow operations like return without the implementation of docsWithAnnotations having to anticipate what kinds of control-flow will be required.

Now, in the interest of full disclosure I should mention that the return statement within the closure is likely to be implemented under the covers using exceptions. That's one more transient object we should count. As for the performance of using an exception in this way, I'm told by HotSpot engineers that an exception used this way is largely optimized away by the VM if found in performance-critical code. The most expensive part of exception handling by far is capturing the stack trace when creating the exception, and we would want to create exceptions for this purpose without stack traces.

That really is it. All of the design iterations we went through to handle variations on this problem in JDK5 simply don't arise as issues. That's the beauty of closures: they allow you to easily abstract away aspects of code that would otherwise require complex contortions.

A slight update on my current feelings about the draft spec. I think we are likely to drop the special syntax for a nonlocal return, and have a different syntax for returning from a closure. This is hinted at in the Further Ideas section. "return" would mean return from the enclosing method or function, and if you're inside a closure you would write a statement something like "^ expression;" to return a value from the closure. Most value-returning closures are unlikely to need this syntax, since they can often be expressed using the "(args) : expression" form.

Closures for Java

2006-08-18T07:30:00.000-07:00

I'm co-author of a draft proposal for adding support for closures to the Java programming language for the Dolphin (JDK 7) release. It was carefully designed to interoperate with the current idiom of one-method interfaces. An abbreviated version of the original proposal is reproduced below. The latest version of the proposal and a prototype can be found at http://www.javac.info/.

Gilad Bracha, Neal Gafter, James Gosling, Peter von der Ahé

Modern programming languages provide a mixture of primitives for composing programs. C#, Javascript, Ruby, Scala, and Smalltalk (to name just a few) have direct language support for function types and inline function-valued expression, called closures. A proposal for closures is working its way through the C++ standards committees as well. Function types provide a natural way to express some kinds of abstraction that are currently quite awkward to express in Java. For programming in the small, closures allow one to abstract an algorithm over a piece of code; that is, they allow one to more easily extract the common parts of two almost-identical pieces of code. For programming in the large, closures support APIs that express an algorithm abstracted over some computational aspect of the algorithm. We propose to add function types and closures to Java. We anticipate that the additional expressiveness of the language will simplify the use of existing APIs and enable new kinds of APIs that are currently too awkward to express using the best current idiom: interfaces and anonymous classes.

Function Types

We introduce a new syntactic form:

Type: Type ( TypeList ) { throws ThrowsTypeList }
ThrowsTypeList: Type
ThrowsTypeList: ThrowsTypeList VBAR Type
VBAR: |

Note: the existing syntax for the throws clause in a method declaration uses a comma to separate elements of the ThrowsTypeList. For backward compatibility we continue to allow commas to separate these elements in method and function declarations, but in function types we require the use of the '|' (vertical-bar) character as aseparator to resolve a true ambiguity that would arise when a function type is used in a type list. For uniformity of syntax, we also allow the vertical-bar as a separator in the throws clause of method and function definitions, and as a matter of style we recommend that new code prefer the vertical-bar.

Local Functions

In addition to function types, we introduce local functions, which are one way to introduce a name with function type:

BlockStatement: LocalFunctionDeclarationStatement
LocalFunctionDeclarationStatement: Type Identifier FormalParameters { throws ThrowsTypeList } Block

A local function declaration has the effect of declaring a final variable of function type. Local functions may not be declared with a variable argument list. Local functions may invoke themselves recursively.

Note: this syntax omits annotations, which should be allowed on local functions.

Example

Combining these forms, we can write a simple function and assign it to a local function variable:

 public static void main(String[] args) {
     int plus2(int x) { return x+2; }
     int(int) plus2b = plus2;
     System.out.println(plus2b(2));
 }

Namespaces and name lookup

The Java programming language currently maintains a strict separation between expression names and method names. These two separate namespaces allow a programmer to use the same name for a variable and for methods. Local functions and closure variables necessarily blur the distinction between these two namespaces: local functions may be used as expression values; contrariwise, variables of function type may be invoked.

A local function declaration introduces the declared name as a variable name. When searching a scope for a method name, if no methods exist with the given name then local functions and variables of the given name that are of function type are considered candidates. If more than one exists (for example, function-typed variable declarations are inherited from separate supertypes), the reference is considered ambiguous; local functions do not overload.

When searching a scope for an expression name, local functions are treated as variables. Function names and values can therefore be used like other values in a program, and can be applied using the existing invocation syntax. In addition, we allow a function to be invoked from an arbitrary (for example, parenthesized) expression:

Primary: Primary Arguments

Anonymous Functions (Closures)

We also introduce a syntactic form for constructing a function value without declaring a local function (precedence is tentative):

Expression3: Closure
Closure: FormalParameters Block
Closure: FormalParameters : Expression3

Example

We can rewrite the assignment to plus2b in the previous example using an anonymous function:

    int(int) plus2b = (int x) {return x+2; };

Or, using the short form,

    int(int) plus2b = (int x) : x+2;

The type of a closure

The type of a closure is inferred from its form as follows:

The argument types of a closure are the types of the declared arguments.

For the short form of a closure, the return type is the type of the expression following the colon. For a long form of a closure, if the body contains no return statement and the body cannot complete normally, the return type is the type of null. Otherwise if the body contains no return statement or the form of return statements are without a value, the return type is void

Otherwise, consider the set of types appearing in the return statements within the body. These types are combined from left to right using the rules of the conditional operator (JLS3 15.25) to compute a single unique type, which is the return type of the closure.

The set of thrown types of a closure are those checked exception types thrown by the body.

Example

The following illustrates a closure being assigned to a variable with precisely the type of the closure.

    void(int) throws InterruptedException closure =
  (int t) { Thread.sleep(t); }

Subtyping

A function type T is a subtype of function type U iff all of the following hold:

Either
- The return type of T is either the same as the return type of U or
- Both return types are reference types and the return type of T is a subtype of the return type of U, or
- the return type of U is void.
T and U have the same number of declared arguments.
For each corresponding argument position in the argument list of T and U, either both argument types are the same or both are reference types and the type of the argument to U is a subtype of the corresponding argument to T.
Every exception type in the throws of T is a subtype of some exception type in the throws of U.

Exception handling

The invocation of a function throws every checked exception type in the function's type.

It is a compile-time error if the body of a function can throw a checked exception type that is not a subtype of some member of the throws clause of the function.

Reflection

A function type inherits all the non-private methods from Object. The following methods are added to java.lang.Class to support function types:

    public final class java.lang.Class<T> ... {
        public boolean isFunction();
        public java.lang.reflect.FunctionType functionType();
        public Object invokeFunction(Object function, Object ... args)
           throws IllegalArgumentException | InvocationTargetException;
    }
    public interface java.lang.reflect.FunctionType {
        public Type returnType();
        public Type[] argumentTypes();
        public Type[] throwsTypes();
    }

Note: unlike java.lang.reflect.Method.invoke, Class.invokeFunction cannot throw IllegalAccessException, because there is no access control to enforce; the function value designates either an anonymous or local function, neither of which allows access modifiers in its declaration. Access to function values is controlled at compile-time by their scope, and at runtime by controlling the function value.

The type of `null`

Referencing names from the enclosing scope

Names that are in scope where a function or closure is defined may be referenced within the closure. We do not propose a rule that requires referenced variables be final, as is currently required for anonymous class instances. The constraint on anonymous class instances is also relaxed to allow them to reference any local variable in scope.

Note: Some who see concurrency constructs being the closure construct's primary use prefer to either require such referenced variables be final, or that such variables be explicitly declared for sharing, perhaps by requiring them be declared volatile. We reject this proposal for a few reasons. First, concurrency has no special role in the need for closures in the Java programming language; the proposal punishes other users of the feature for the convenience of these few. Second, the proposal is non-parallel with the closest existing parallel structure: classes. There is no constraint that a method may only access, for example, volatile fields of itself or other objects or enclosing classes. If compatibility allowed us to add such a rule to Java at this time, such a rule would obviously inconvenience most programmers for very little benefit. Third, marking such variables volatile, with all the semantic meaning implied by volatile, is neither necessary nor sufficient to ensure (and hardly assists!) appropriate use in a multithreaded environment.

Non-local transfer

One purpose for closures is to allow a programmer to refactor common code into a shared utility, with the difference between the use sites being abstracted into a local function or closure. The code to be abstracted sometimes contains a break, continue, or return statement. This need not be an obstacle to the transformation. A break or continue statement appearing within a closure or local function may transfer to any matching enclosing statement provided the target of the transfer is in the same innermost ClassBody.

Because the return statement within a block of code is given new meaning when transformed by being surrounded by a closure, a different syntactic construct is required to return from an enclosing function or method. The following new form of the return statement may be used within a closure or local function to return from any enclosing (named) local function or method, provided the target of the transfer is in the same innermost ClassBody:

NamedReturnStatement: return Identifier : ;
NamedReturnStatement: return Identifier : Expression ;

No syntax is provided to return from a lexically enclosing closure. If such non-local return is required, the code should be rewritten using a local function (i.e. introducing a name) in place of the closure.

If a break statement is executed that would transfer control out of a statement that is no longer executing, or is executing in another thread, the VM throws a new unchecked exception, UnmatchedNonlocalTransfer. (I suspect we can come up with a better name). Similarly, an UnmatchedNonlocalTransfer is thrown when a continue statement attempts to complete a loop iteration that is not executing in the current thread. Finally, an UnmatchedNonlocalTransfer is thrown when a NamedReturnStatement attempts to return from a function or method invocation that is not pending in the current thread.

Closure conversion

We propose the following closure conversion, to be applied only in those contexts where boxing currently occurs:

There is a closure conversion from every closure of type T to every interface type that has a single method with signature U such that T is a subtype of the function type corresponding to U.

Note: The current Java idiom for capturing a snippet of code requires the use of a one-method interface to represent the function type and an anonymous class instance to represent the closure:

        public interface Runnable {
           void run();
        }
        public interface API {
           void doRun(Runnable runnable);
        }
        public class Client {
            void doit(API api) {
                api.doRun(new Runnable(){
                   public void run() {
                       snippetOfCode();
                   }
                });
            }
        }

Had function types been available when this API was written, it might have been written like this:

        public interface API {
            void doRun(void() func);
        }

And the client like this:

        public class Client {
            void doit(API api) {
                api.doRun(() {snippetOfCode(); });
            }
        }

Unfortunately, compatibility prevents us from changing existing APIs. One possibility is to introduce a boxing utility method somewhere in the libraries:

        Runnable runnable(final void() func) {
            return new Runnable() {
                public void run() { func(); }
            };
        }

Allowing the client to write this:

        public class Client {
            void doit(API api) {
                api.doRun(runnable(() {snippetOfCode(); }));
            }
        }

This may be nearly good enough from the point of view of how concise the usage is, but it has one more serious drawback: every creation of a Runnable this way requires that two objects be allocated instead of one (one for the closure and one for the Runnable), and every invocation of a method constructed this way requires an extra invocation. For some applications -- for example, micro-concurrency -- this overhead may be too high to allow the use of the closure syntax with existing APIs. Moreover, the VM-level optimizations required to generate adequate code for this kind of construct are difficult and unlikely to be widely implemented soon.

The closure conversion is applied only to closures (i.e. function literals), not to arbitrary expressions of function type. This enables javac to allocate only one object, rather than both a closure and an anonymous class instance. The conversion avoids any hidden overhead at runtime. As a practical matter, javac will automatically generate code equivalent to our original client, creating an anonymous class instance in which the body of the lone method corresponds to the body of the closure.

Example

We can use the existing Executor framework to run a closure in the background:

 void sayHello(java.util.concurrent.Executor ex) {
     ex.execute((){ System.out.println("hello"); });
 }

Further ideas

We are considering allowing omission of the argument list in a closure when there are no arguments. Further, we could support a sugar for calls to functions whose last argument is a zero argument closure:

 void foo(T1 p1, ..., Tn pn, R() pn+1) {...}

could be called as

 T1 a1; ... Tn an;
 foo(a1, ..., an){...};

where the call is translated to

 foo(a1, ..., an, {...});

In the special case where there is only one argument to foo, we also would allow

 foo{...}

for example

 void sayHello(java.util.concurrent.Executor ex) {
     ex.execute { System.out.println("hello"); }
 }

We are also experimenting with generalizing this to support an invocation syntax that interleaves parts of the method name and its arguments, which would allow more general user-defined control structures that look like if, if-else, do-while, and so on.

This doesn't play well with the return statement being given a new meaning within a closure; it returns from the closure instead of the enclosing method/function. Perhaps the return from a closure should be given a different syntax:

 ^ expression;

With this, we probably no longer need the nonlocal return statement.

Acknowledgments

The authors would like to thank the following people whose discussions and insight have helped us craft, refine, and improve this proposal:

Lars Bak, Cédric Beust, Joshua Bloch, Martin Buchholz, Danny Coward, Erik Ernst, Christian Plesner Hansen, Doug Lea, "crazy" Bob Lee, Martin Odersky, Tim Peierls, John Rose, Ken Russell, Mads Torgersen, Jan Vitek, and Dave Yost.

Peripheral Motion Illusions

2005-02-17T23:15:00.000-08:00

We've been struggling with what to do for the cover art of Java Puzzlers, and some brainstorming brought us to the idea something like the amazing optical illusions of professor Akiyoshi Kitaoka. They are absolutely mind-blowing. At first you'll think they are animated GIF images, but I assure you the pictures move when printed on paper too! Professor Kitaoka has two books in print, and plans to publish English translations soon. In the U.S. you can get the Japanese books from the Kinokuniya bookstore.

I installed Macromedia Freehand FX on my Mac and was able to reproduce some of his more stunnning illusions, and then tried creating some of my own. Like this one.

"Java Puzzlers" is coming

2005-02-10T13:23:00.000-08:00

Amazon is listing my forthcoming book (with Joshua Bloch) for preordering: Java Puzzlers. We're having lots of fun getting the material into book form, and the reviewers seems to be very happy with the chapters so far. Here's what one of them had to say:

I laughed, I cried, I threw up ... my hands in admiration.
-Tim Peierls

Puzzling Through Erasure: answer section

2004-09-23T13:06:00.000-07:00

Erasure is the technique that Java 5 uses to implement generics. Basically, the javac compiler performs its type-checking and then erases, or removes, the generic type information from the runtime representation. Reification, on the other hand, is the opposite. A generics implementation based on reification retains the type parameters at runtime as first-class entities, which allows it to perform certain type-based language and reflective operations on type parameters. Sun chose to implement generics using erasure. C# implements generics using reification. A number of questions about erasure and reification have been raised in the context of the new version of the Java language, and misunderstanding and misinformation abounds. I hope this note will help illuminate the issues.

Why did Sun go with an erasure scheme to implement generics, rather than reifying type parameters as is done in C#? This is perhaps one of the least understood aspects of the Java generics design, but it is a natural conseqence of the design goals of the language extension. The goal was to provide backwards compatibility of both source and object code, and also migration compatibility. The meaning of backwards compatibility is pretty obvious: you want existing source and class files to continue to be legal and continue to mean what they meant before. Although the definition of backwards compatibility is clear, it is actually very hard to change the language without violating it.

The other design constraint is migration compatibility, and this is a big one. I'll explain it by way of an example.

Migration Compatibility

Migration compatibility is the first constraint among the requirements (in section 2.5) for jsr14's design for a generic extension to java:

C1) Upward compatibility with existing code. Pre-existing code must work on the new system. This implies not only upward compatibility of the class file format, but also interoperability of old applications with parameterized versions of pre-existing libraries, in particular those used in the platform library and in standard extensions.

Consider the following software vendors: Company A sells a Java library for manipulating Audio. Company B sells a Java library for controlling electronic Bugles (I think this product would be called Boogie Woogie Boy). Company C sells a software product that is an electronic Bugle which is built on the libraries from A and B. C's customers would normally license all three products.

Along comes JDK5, and these companies naturally want to migrate to generics. Companies A and B are in the comfortable position of being at the bottom of this software stack, and can immediately begin developing new versions of their APIs and libraries that take advantage of the new language features. Being a new release of the product, Company A would naturally also add new features. Their new API is called A2. Customers who require library A, for example because they have not modified their source to take advantage of generics yet, can still license it.

Company B, similarly, ships two libraries B and B2.

What does company C do? First, they cannot migrate to the new version of these libraries until the new libraries are available. And once they are available, C will want to migrate, for two reasons. First, it improves their software development process to use the improved language features. Second, their future customers might license the new (rather than the old) libraries A2 and B2. So company C provides two versions of their product, the old version C based on A and B, and C2 based on A2 and B2.

Shortly after releasing C2 (and settling the inevitable trademark infringement lawsuit with Coca Cola) Company C discovers that it has left a huge number of its customers out in the cold. These are customers who have licensed the new version of one of the libraries A or B, but not new versions of both. Neither of C's products will work with these combinations. So Company C promptly provides C2a and C2b, two new versions of their product for this subset of customers.

Things only get worse as we move up the software stack. First, it will be a very long time before everyone can migrate fully to the new APIs. Second, as a library writer you either require your customers to use the latest version of everything and deprecate your old APIs, or you support an astronomical number of variations of the underlying layers. If you're in the enviable position of controlling the entire software stack then this is no big deal -- except perhaps to your customers. Sun is not in that position and this situation is clearly unacceptable.

This is where migration compatibility comes in. Migration compatibility requires that the generic version of an API be compatible with the old version, in the sense that existing clients will continue to compile (for source) and run (for binaries). This requirement constrains the design space significantly.

In a system that support migration compatibility, Companies A and B can independently retrofit their libraries with generics, and their customers will be able to use the new library without modifying their source code, even without recompiling it. But those customers only gain the benefit of generics in those libraries when they begin placing type parameters on the generic types. But Companies A and B can now ship a single version of their library.

We do not know how to satisfy this constraint in a system that also provides reification, that is, runtime access to type parameters. This is not for lack of trying. In fact, we've explored the design space enough to conjecture that it simply can't be done. The details of that exploration are very interesting but far beyond the scope of this note. Bruce Eckel's injection idea is often proposed as a starting point, as is NextGen. Neither supports migration compatibility.

Backwards compatibility is hard

I mentioned earlier that even though the phrase "backwards compatibility" is easier to understand than migration compatibility, it is not easy to extend the language without breaking compatibility. Let's take, for example, Bruce's suggestion that some future version of Java would begin reifying type parameters and stop using erasure. His idea is that constructor invocations for generic classes would pass one or more extra parameters - type information for the instantiation's type parameters - which would be stored in the instance.

Setting aside the some very difficult implementation and performance issues (do you really want every linked list node to double in size? How do you implement instanceof for generic interfaces? How do you implement array store checks?), this isn't really backward compatible. The fundamental problem is that existing Java 5 class files don't follow that convention, and so won't interoperate with new code. Existing code that instantiates Foo<String> doesn't in fact pass the extra parameter. Existing subclasses of Foo don't pass such data on to the superclass constructor. Existing implementations of a Foo<T> interface don't expect to receive that extra parameter in the constructor.

I would also like to address some other misconceptions Bruce Eckel's two latest blog entries here and here.

Why can't I "new T()"?

For a type parameter T, the reason you can't do a "new T()" is because not every type has a no-arg constructor. I know Bruce is a big fan of what he calls "latent typing", and he would prefer to get such errors at runtime. But Java is a statically typed language, for better or worse, and you simply can't invoke a no-arg constructor on a type that isn't statically known to have one. It's also true that due to erasure there would be no way to generate this code, but for this construct that is beside the point.

What is the point of type parameters if they are erased

Static type checking! To belabor the point, if you're someone who prefers what Bruce calls latent typing, then you care about what you can do with a type at runtime more than the compile-time utility. If that's the case, any extension to the static type system is ho-hum uninteresting and not worth the brain cycles needed to understand it.

But for those of us who want to rely on the compiler to help us get our programs statically correct and prefer our errors be reported early, generics are a huge win. Generics can save you a great deal of work and mental energy that used to be necessary mediating untyped collections with a program that works with concrete types.

How do I create an array of T?

There are two answers - a cheat that isn't typesafe but works in many situations, and a correct answer. Bruce found the cheat, and it's unfortunate that it is widely being copied as the "correct" way to do things. At the risk of sending the wrong message, the cheat is as follows:

 T[] a = (T[]) new Object[N]; // Bad style!

When you do this sort of thing the compiler will rightfully complain. After all, an Object array isn't a T array unless T happens to be Object. You shouldn't ignore this compiler warning. In fact, what you've written here is very dangerous. If you have a method in the API that returns a T[] and you return this value, and you have a client for which T==String who tries to store it into a variable of type String[], you will get a ClassCastException at runtime.

But wait, you say, this kind of thing appears in the Collections implementation! So it must be the approved, accepted, proper approach. No. Mea culpa. I was lazy. It would have been better for me to use an Object array inside the collection, and add a cast (yes, to T) everywhere necessary when an element is removed from the array. In general, this cast is elided by javac and moved into the non-generic client, both by virtue of compiling by erasure. But you still get a complaint from the compiler on each cast. This warning is unavoidable, because at runtime existing clients simply do not provide enough type information to do the cast correctly. That's not due to erasure, it's due to language evolution.

But that's not the correct solution. The correction solution requires that you design your API to be aware of generics (unfortunately not possible when retrofitting an exising class) and relies on using the idea of a type token, which I introduced along with the generification of the core APIs. See section 8 of Gilad Bracha's Generics Tutorial for more details, as well as the checked collection wrappers in JDK5 for a straightforward example. If you're designing an API in which you really, really wish that type parameters were not erased, you can achieve almost the same effect as follows:

  class Generic<T> {
    final private Class<T> tClass;
    public Generic(Class<T> tClass) {
      this.tClass = tClass;
    }
  }

Now you can instantiate using reflection (tClass.newInstance()), create arrays (Array.newInstance), cast (Class.cast), and do instanceof tests (Class.isInstance), though with a slightly different syntax than you might prefer.

This technique allows you to get the effect of what Bruce calls "type injection", almost undoing the erasure yourself. Why do I say "almost"? I'll leave that as a puzzle for you to think about. One hint: just as you feared, it has something to do with erasure.

Why can't I put bounds on an instantiation?

What would it mean? If you were able to make a new List<? extends Foo>(), then you could place into that list a Foo or any subclass of Foo. But a sublcass of Foo is also a Foo, so you could also use a List<Foo> for the same purpose. In short, new List<? extends Foo>() would mean the same thing as new List<Foo>().

To look at it another way, consider method parameters. You can put a type on a method's value parameter, where the parameter's name is defined, but not on an argument to a method call, which is an expression. The same is true of type parameters and arguments: you can put a bound on the type parameter, where its name is defined, but not on the type argument.

Why do you say that C# breaks compatibility with their generics system?

The short answer is: I don't.

Microsoft is essentially deprecating the old collections classes by introducing a new, preferred set of generic collections classes. They are creating the kinds of problems described in the Company A-B-C scenario, only it might just be less of a problem for them because they control so much more of the software stack. I do not claim that they break backward compatibility. In fact, generally speaking I prefer reification when it doesn't conflict with the design goals. The other disadvantage (besides abandoning migration compatibility) that I see in the C# approach is that it is hard to reconcile with both the bipartite type system and wildcards, though perhaps that problem could be solved.

You might not agree with migration compatibility as a goal for the generics extension to Java. That would have been very useful feedback in 1999 when jsr14 was formed, and in fact the issue was discussed at great length at the time. Whatever your feelings, I hope you agree that now, a month before the product ships, is a poor time to reconsider the most fundamental design goals that were set five years earlier for the product and on which the existing design and implementation depends deeply.

Neal Gafter's blog

A couple of comments on Defender Methods

A Syntax Option for Project Lambda (Closures for Java)

JDK API search in Google Toolbar

Language Parity: Closures and the Java VM

Java Closures Prototype Feature-Complete

Closures: Control Abstraction, Method References, Puzzler Solution

Closures: Control Abstraction, Method References, Puzzler Solution

Control Abstraction

Method References

Puzzler Solution

Closures Puzzler: Neapolitan Ice Cream

Is the Java Language Dying?

What flavor of closures?

Restricted Closures

Closures Prototype Update and Extension Methods

Closures Prototype Update

Extension Methods

Java Closures: first prototype

Internal Versus External Iterators

Constructor Type Inference

Removing Language Features?

A Limitation of Super Type Tokens

A Consensus Closures JSR Proposal

Closures for Organizing Your Code

A Compact Object Comparator

On The Expressive Power of Programming Languages

Java Closures versus MouseListener

Closures Spec Update (v0.5)

A Definition of Closures

Video Interview at Javapolis

Primate Parts

MethodNamesInPieces

Closures Talk and Spec Update

Javapolis 2006

Closures

Native XML Support

Constructor Invocation for Generics

Type Literals

Super Type Tokens

Linear Time Sort Puzzler

A Thread Pool Puzzler

Closures Esoterica: completion transparency

Reified Generics for Java

Closures for Java (v0.3)

Concurrent Loops Using Java Closures

Iterative control abstraction: user-defined loops

Failure of Imagination in Language Design

Nominal Closures for Java (version 0.2)

1. Closure Literals

Example

2. The type of a closure

Example

3. synchronized parameters

4. Closure conversion

Example

5. Exception type parameters

6. Non-local control flow

7. Definite assignment

8. The type Unreachable

Example

8. Unreachable statements

10. Abbreviated invocation syntax.

Acknowledgments

Closures for Java (version 0.1)

1. Function Types

2. Namespaces and name lookup

3. Closure Literals

Example

4. The type of a closure

Example

5. Subtyping

6. Exception checking

7. Reflection

8. The type of null

9. Referencing names from the enclosing scope

10. Non-local control flow

11. Closure conversion

Examples

12. Abbreviated invocation syntax.

3. `synchronized` parameters

8. The type `Unreachable`

8. The type of `null`

The meaning of `this`

The type of `null`