The Artima Developer Community
Sponsored Link

Weblogs Forum
Simplyfing Java Generics by Eliminating Wildcards

33 replies on 3 pages. Most recent reply: Jul 19, 2008 10:16 PM by Howard Lovatt

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 33 replies on 3 pages [ 1 2 3 | » ]
Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Simplyfing Java Generics by Eliminating Wildcards (View in Weblogs)
Posted: Jan 11, 2008 3:29 AM
Reply to this message Reply
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?


Raoul Duke

Posts: 127
Nickname: raoulduke
Registered: Apr, 2006

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 11, 2008 9:21 PM
Reply to this message Reply
Generics can be hard, subclassing / subtyping can be hard, co/contra-variance can be hard (http://lambda-the-ultimate.org/node/2593), etc. so I can undersand wanting to KISS.

But, anything which introduces more chance for runtime exceptions vs. static error checking is not really a step forward, in my mind.

I'm not smart enough to tell anybody how to KISS while keeping good static checking and appropriate generic-style polymorphism, but I bet somebody out there in the programming language theory world knows the best if not outright right way to go?

Carson Gross

Posts: 153
Nickname: cgross
Registered: Oct, 2006

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 12, 2008 7:54 AM
Reply to this message Reply
I bet somebody out there in the programming language theory world knows the best if not outright right way to go

Nope, they don't. Wildcards are *from* those guys.

It turns out that being really, really typesafe is hard, and often gets in the way of other language goals. All programming language design consists of trading off one feature against another so that you get the maximum total benefit at the minimum total cost.

My conclusion on the matter, and I know *everyone* is panting for it, is that java arrays are The Right Thing. This is as shocking to me as it is to you. So, for example, List<String> should be a subtype of List<Object>. I understand all to well that this isn't type safe, but it *is* simple and everyone can understand the rule. My observation is that ArrayStoreExceptions are extremely rare. Furthermore, you can now do after-the-fact covariant subtyping of classes with collections with this rul.

What I mean by that is that if A has a method getThings() that returns List<A> on it, you can create a subtype B of A and covariantly override getThings() to return List<B> without modifying getThings() in A to return <? extends A>. Yes, it isn't type safe, but that cost is worth the simplicity of the model.

Again, I'm surprised I've come to this conclusion. Along with all the other programming language wannabes, I used to make fun of java because of the way array assignability works. Now I'm not so sure.

As a side note, just to be clear, I think you still need type *constraints* so that developers can properly constrain type variables in API design. That is, you still need to be able to say class MyClass<A extends List> { ... }.

Cheers,
Carson

Sean Fritz

Posts: 2
Nickname: seanfritz
Registered: Dec, 2005

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 12, 2008 9:18 AM
Reply to this message Reply
I'm one of those PL community guys that gets generics (no I don't particularly like them either).

I think the best way to put this is, generics is the best solution to the problem they solve. That problem is, how do you add typesafe first class type parameters to a strictly strongly typed language without relaxing any type safety such that all checks can be done statically at compile time (except a the few situations [dynamic casts mostly] where it's impossible to check at compile time).

Quite simply, OOP and type theory is really hard. It looks easy on the surface, because you don't have to understand much about types to make a huge mess of a inheritance heirarchy. However, when you go to write a language to *match* that, or any other, type heirarchy it becomes impossible to not be exposed to the complexity of types.

If you want everything to be explicit, as the Java community says it does, then you're going to end up with really hard generics. There is no way around it.

Larry Maccherone

Posts: 1
Nickname: lmaccheron
Registered: Jan, 2008

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 12, 2008 6:55 PM
Reply to this message Reply
I'm fairly new to generic so I could be mistaken but I think the D programming language does exactly what you are describing:

http://www.digitalmars.com/d/template.html

It doesn't seem to have a wildcard but it does allow you to specify type restrictions.

I've just started playing with generics in java and I've already been burned several times. In fact, I almost gave up at one point and went back to a non-generic approach but I plowed ahead and now have a little understanding of the warts. I teach classes to professional software developers and I agree that the vast majority of them will not be able to write their own generic code. However, I think developers can learn enough to correctly use a library of generic code.

To me, the bigger problem is that by grafting generics onto the language after the fact, you end up with all of these edge cases that drive folks crazy when they are trying to learn something new. I spent most of my time on this issue:

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5004321

The above bug "fix" actually breaks my code in a way very similar to what jcsahnwaldt describes in the comments. The proposed fix to the fix that broke my code is:

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6184881

This is nuts!!! No "normal" programmer is going to wade through this mess to figure it out. I'm certain that the introduction of closures will be just as messy. I wonder if the D folks avoided this because they didn't have to maintain backward compatibility with anything when they introduced generics. I wonder if the new ECMAScript 4 will suffer from backward compatibility kruft.

Paul Beckford

Posts: 51
Nickname: phaedrus
Registered: Feb, 2007

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 13, 2008 6:12 AM
Reply to this message Reply
> Generics can be hard, subclassing / subtyping can be hard,
> co/contra-variance can be hard
> (http://lambda-the-ultimate.org/node/2593), etc. so I can
> undersand wanting to KISS.
>
> But, anything which introduces more chance for runtime
> exceptions vs. static error checking is not really a step
> forward, in my mind.
>
> I'm not smart enough to tell anybody how to KISS while
> keeping good static checking and appropriate generic-style
> polymorphism, but I bet somebody out there in the
> programming language theory world knows the best if not
> outright right way to go?

I'm still using Java 1.4, and I think this over emphasis on static error checking misses the whole point. OO programming is about hiding implementation and in so doing reducing coupling. This is the opposite to Generics. If you are worried about errors then why not program using TDD/BDD? Behavior specifications are a lot more expressive and a lot more likely to catch bugs.

Paul.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 13, 2008 8:41 PM
Reply to this message Reply
> I'm fairly new to generic so I could be mistaken but I
> think the D programming language does exactly what you
> are describing:
>
> http://www.digitalmars.com/d/template.html

I don't know D and the page reference didn't give any complicated examples, e.g. a complicated example might be something like the list example in the original blog. So I can't say. If you use D then I would interested to see what happens if you code the list example.

> ... I spent most of my time on
> this issue:
>
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5004321
>
> The above bug "fix" actually breaks my code in a way very
> similar to what jcsahnwaldt describes in the comments.
> The proposed fix to the fix that broke my code is:
>
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6184881

I think the elimination of wildcards is in line with the fix (6184881). This bug report is asking for co-variant typing, ? extends ArrayList<?>, and that is what I am proposing.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 13, 2008 8:44 PM
Reply to this message Reply
@Carson,

This is what I am proposing. Arrays do the right thing.

Yardena M

Posts: 1
Nickname: yardena
Registered: Apr, 2006

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 14, 2008 6:05 AM
Reply to this message Reply
Howard,

I really appreciate your goal - covariant generic parameter is the most used, and should require less typing, and I mean like on the keyboard, not like "static vs. dynamic"... hm, well, maybe both :-). Here's one more blog-post about it that I recently saw: http://blog.cedarsoft.eu/2008/01/12/why-you-should-only-return-collections-with-bounded-wildcards/

I have spent about an hour on my way home yesterday thinking about your proposal and here are my 2c. You'd first need to reify the generics, 'coz unlike arrays, the collection does not know its element type at run-time. Suppose you overcome this - any "reading" (using return values) from a parametrized object would be simple, and "writing" (passing method parameters) could produce warnings, rather than not compiling. To get rid of the warning one would need to capture the wildcard with [T extends Number] or something of that sort.

I have blogged about wildcards before (http://sensualjava.blogspot.com/2008/01/wildcards-observation.html) but I think the topic really deserves further investigation.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 14, 2008 6:43 PM
Reply to this message Reply
@Yardena,

Yes you are right about arrays, they know their type and generics don't. You can still get runtime exceptions if you allocate the correct object inside the generic class, EG Collections.checkedList. However it would be better if we erased erasure.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 15, 2008 5:48 PM
Reply to this message Reply
Peter Ahe sent the following to me by email:


I have already responded to Generics "bashing": http://blogs.sun.com/ahe/entry/reification

<U super T> is not allowed in Java and it would not be easy to add.
( http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5052956)

The wildcards you are talking about in Scala and Fortress are called
declaration-site variance. This was also used in Strongtalk. Java
has use-site variance, but we called it wildcards.


See: http://www.artima.com/forums/flat.jsp?forum=106&thread=136054

Gilad [Bracha] and I often talked about the complexity of generics when we both
worked for Sun. Were we to do it over again, we agreed that the
default should be covariance. I would not go as far as say that you
should remove wildcards, and I believe the chosen solution was the
best available at the time.

Juancarlo Añez

Posts: 12
Nickname: juanco
Registered: Aug, 2003

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 20, 2008 12:24 PM
Reply to this message Reply
I probably need to think about this topic more, but having taught programming language theory at the university before, I'll give it this shot:

In purely functional languages, the compiler infers the types (or signatures) involved in a function call from the local context and can favor covariance in identifier resolution. See http://en.wikipedia.org/wiki/Unification.

In OO languages with generics methods are declared within a type (a class) and thus an assumption is made at least about one of the types: the type of 'this'. Thus, something like Java's wildcards or Scala's upper-bounding are required to erase the assumption.

Given the above, the cognitive problems with Java type wildcards could be solved with free-standing (non-class-bound) functions.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 20, 2008 3:59 PM
Reply to this message Reply
@Juancarlo,

Yes you could infer the variance (the original blog mentioned this), however I am not sure that this is the best solution and hence my suggestion of covariance as a simpler alternative. Inferring the variance might lead to poor error messages and covariance is nearly always what you want anyway - so keep it simple.

David López

Posts: 4
Nickname: daviti
Registered: Apr, 2006

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 21, 2008 12:05 PM
Reply to this message Reply
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.
>

I'd like to notice that, since ImmutableList is immutable, ImmutableList<Double> is a perfect ImmutableList<Number>. I mean theoretically because Java language unfortunatelly ignores that. Since you cannot add any new element to ImmutableList<Number> you have just to afford that the already added elements are actually Numbers, and Doubles are Numbers indeed. So, you should be able to pass an ImmutableList<Double> whenever an ImmutableList<Number> is required.

But even more interesting is the simetrical proposition. Consider the UnreadableList<Number> and UnreadableList<Double> classes. Both are mutables, they accept more elements, but you cannot read the content inside. It could be useful when you request another method to add elements to your list (which is primarily Readable, but you cast to Unreadable when passed), but that method doesn't need to read anything from it, only add. In this scenario, an UnreadableList<Number> is a perfect UnreadableList<Double>. The invoked method claims to add only Doubles with an UnreadableList<Double> in its signature, and that is coherent with your UnreadableList<Number>, which accepts Doubles indeed.

I've never read anything about that concept but I find it simple and useful. What do you think?

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Simplyfing Java Generics by Eliminating Wildcards Posted: Jan 21, 2008 8:29 PM
Reply to this message Reply
@David,

The current Java wildcards are designed to support reading sub-types from a list and writing super-types to a list. The sum method:

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


is an example of a read-only method and the prepend method:

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


an example of a write-only method. (Prepend effectively writes to the newly created list.)

I am proposing that a method like prepend could fail with an array store exception. Imagine writing a prepend method with arrays:

 static <T> T[] prepend( final T[] oldArray, final T newHead ) {
    final T[] newArray = ... // create T array using reflection based on type of oldArray
    System.arraycopy( oldArray, 0, newArray, 1, oldArray.length );
    newArray[ 0 ] = newHead;
    return newArray;
  }


If you had an Integer array and you prepended a Number then the compiler would allow this. Type T would be a Number and the oldArray argument a Number array which you could assign the existing Integer array to. But when you got to the line newArray[ 0 ] = newHead you would get an array store exception, since you are trying to put a Number into an Integer array.

My own experience is that this error is rare and so it isn't a problem in practice, hence my suggestion to do away with wildcards. Also I think you can code round the problem by looking at the type of both newHead and oldArray and assigning newArray an appropriately typed array.

Flat View: This topic has 33 replies on 3 pages [ 1  2  3 | » ]
Topic: Object Adapter based on Dynamic Proxy Previous Topic   Next Topic Topic: The Simplest Thing That Could Possibly Work?


Sponsored Links



Google
  Web Artima.com   

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