The Artima Developer Community
Sponsored Link

Pattern Centric Blog
Simplyfing Java Generics by Eliminating Wildcards
by Howard Lovatt
January 11, 2008
Summary
Many people have written that generics in Java are too complicated, this blog examines a simplification — the elimination of wildcards.

Advertisement

Background

In his recent Javapolis presentation Joshua Bloch cited the following generic examples as overly complicated:

  Enum<E extends Enum<E>> { ... }

  <T extends Object & Comparable<? super T>> T Collections.max(Collection<? extends T>) { ... }

  public <V extends Wrapper<? extends Comparable<T>>>
    Comparator<V> comparator() { ... }

  error: equalTo(Box<capture of ?>) in Box<capture of ?> cannot be applied to (Box<capture of ?>)
    equal = unknownBox.equalTo(unknownBox)

  Arrays.asList(String.class, Integer.class) // Warning!

Joshua also used the following two quotes from the web:

“I am completely and totally humbled. Laid low. I realize now that I am simply not smart at all. I made the mistake of thinking that I could understand generics. I simply cannot. I just can't. This is really depressing. It is the first time that I've ever not been able to understand something related to computers, in any domain, anywhere, period.”
“I'm the lead architect here, have a PhD in physics, and have been working daily in Java for 10 years and know it pretty well. The other guy is a very senior enterprise developer (wrote an email system that sends 600 million emails/year with almost no maintenance). If we can't get [generics], it's highly unlikely that the ‘average’ developer will ever in our lifetimes be able to figure this stuff out.”

Joshua, talking about closures, also said:

"We simply cannot afford another wildcards"

The examples that Joshua chose mainly involved wildcards and he also directly said they were a problem and it is possible to eliminate wildcards from Java — perhaps we should!

Running Example

In functional programming a common data structure is the immutable list. An immutable list provides a good example to demonstrate the pros and cons of wildcards:

public class ImmutableList<T> {
  public ImmutableList<T> prepend( final T newHead ) {
    return new ListBody<T>( newHead, this );
  }

  public T head() { throw new IllegalStateException(); }

  public ImmutableList<T> tail() { throw new IllegalStateException(); }

  public boolean isEmpty() { return true; }

  // equals, hashCode, toString, etc.

  private static class ListBody<T> extends ImmutableList<T> {
    final T head;

    final ImmutableList<T> tail;

    ListBody( final T head, final ImmutableList<T> tail  ) {
      this.head = head;
      this.tail = tail;
    }

    @Override public T head() { return head; }

    @Override public ImmutableList<T> tail() { return tail; }

    @Override public boolean isEmpty() { return false; }
  }
}

The list is constructed by prepending elements to an empty list and lists are processed recursively using the head and tail methods. However the type system is quite restrictive, e.g. the following will not sum a list of Doubles:

  static double sum( final ImmutableList<Number> list ) {
    if ( list.isEmpty() ) { return 0.0; }
    return list.head().doubleValue() + sum( list.tail() );
  }

The problem is that a ImmutableList<Number> is not a ImmutableList<Double> even though Double is a Number, i.e. generic parameters without wildcards are not variant and therefore require exactly the same types (not sub-types, not super types). A second problem is that if you have ImmutableList<Integer> and prepend to it a Double then it would be nice if prepend returned a ImmutableList<Number> since Number is the superclass of both Integer and Double.

Wildcards

Wildcards in Java provide a solution to both problems, first generic functions:

  static double sum( final ImmutableList<? extends Number> list ) {
    if ( list.isEmpty() ) { return 0.0; }
    return list.head().doubleValue() + sum( list.tail() );
  }

and second for prepend, make prepend a static method rather than an instance method and modify the immutable list to accept sub-classes of its generic type:

public class ListWildcards<T> {
  public T head() { throw new IllegalStateException(); }

  public ListWildcards<? extends T> tail() { throw new IllegalStateException(); }

  public static <T> ListWildcards<T> prepend( final ListWildcards<? extends T> list, final T newHead ) {
    return new ListBody<T>( newHead, list );
  }

  public boolean isEmpty() { return true; }

  private static class ListBody<T> extends ListWildcards<T> {
    final T head;

    final ListWildcards<? extends T> tail;

    ListBody( final T head, final ListWildcards<? extends T> tail    ) {
      this.head = head;
      this.tail = tail;
    }

    @Override public T head() { return head; }

    @Override public ListWildcards<? extends T> tail() { return tail; }

    @Override public boolean isEmpty() { return false; }
  }
}

The solution works, but as already noted it is quite complicated.

Scala and Fortress

Other languages notable Scala and Fortress have adopted an alternative to wildcards in variable/field/argument declarations, they allow the type parameters of a class to be marked with wildcards. Assume this technique was adopted in Java:

public class ListScalaStyle<? extends T> {
  public T head() { throw new IllegalStateException(); }

  public ListScalaStyle<T> tail() { throw new IllegalStateException(); }

  public <U super T> ListScalaStyle<U> prepend( final U newHead ) {
    return new ListBody<U>( newHead, this );
  }

  public boolean isEmpty() { return true; }

  private static class ListBody<? extends T> extends ListScalaStyle<T> {
    final T head;

    final ListScalaStyle<T> tail;

    ListBody( final T head, final ListScalaStyle<T> tail    ) {
      this.head = head;
      this.tail = tail;
    }

    @Override public T head() { return head; }

    @Override public ListScalaStyle<T> tail() { return tail; }

    @Override public boolean isEmpty() { return false; }
  }
}

The changes above also allow sum to be written as well as solving the prepend problem. A similar example to the above list example is in the Artima Scala Book (the book uses Queue rather than List). This is definitely easier to follow than wildcards, but still tricky. Also the system doesn't solve all problems, consider:

    final ListScalaStyle<Integer> iList = new ListScalaStyle<Integer>();
    final ListScalaStyle<Number> nList = iList.prepend( (Number)2.0 ); // OK
    final ListScalaStyle<Integer> iList2 = nList.tail(); // Error, still a Number list

The Java solution also fails this test, yet if you are arguing that it is worthwhile to support a prepend that returns the super-type list then surely tail should return the sub-type list! They are after all the mirror operations of each other.

Since the Scala/Fortress compilers check your declaration of generic parameters it might be possible to do away with the wildcard notation and have the compiler infer the wildcards. Another, simpler, alternative is given in the next section.

Remove Wildcards

Since wildcards in either the Scala/Fortress form or the Java form have problems and are both tricky (particularly the Java form). An alternative is to do without wildcards and make generic parameters co-variant by default like arrays are. If generic parameters behaved like arrays then the original example would work with the original sum . However prepend wouldn't return super-type lists and tail (like all systems) wouldn't return sub-type lists. Without wildcards you can get ArrayStoreExceptions at runtime, just like you can with arrays. However ArrayStoreExceptions are rare in my experience.

This suggestion of deprecating wildcards would break code that used wildcards and this incompatibility could be managed with a source statement. Therefore I would suggest dropping wildcards and making generic parameters co-variant by default since this is simple (KISS) and powerful. What do you think?

Talk Back!

Have an opinion? Readers have already posted 33 comments about this weblog entry. Why not add yours?

RSS Feed

If you'd like to be notified whenever Howard Lovatt adds a new entry to his weblog, subscribe to his RSS feed.

About the Blogger

Dr. Howard Lovatt is a senior scientist with CSIRO, an Australian government owned research organization, and is the creator of the Pattern Enforcing Compiler (PEC) for Java. PEC is an extended Java compiler that allows Software Design Patterns to be declared and hence checked by the compiler. PEC forms the basis of Howard's 2nd PhD, his first concerned the design of Switched Reluctance Motors.

This weblog entry is Copyright © 2008 Howard Lovatt. All rights reserved.

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us