We noticed a recurring problem that in some program designs that
require a coding pattern that is entirely typesafe yet can't be
expressed in the current type system. It occurs in the implementation
of Collections and it arose recently in a compiler refactoring. The coding
pattern can be made typesafe but it requires a small API change. We propose
to make that API change in Tiger. It cannot be done after Tiger because
the change would be incompatible with the APIs in Tiger.

Here is the issue.

Consider the following optimization. Suppose you have a List class

    class MyList<T> implements Iterable<T> {
        public Iterator<T> iterator() {
            return new Iterator<T> {
                public boolean hasNext() {
                    return whatever;
                }
                public void remove() {
                }
                public T next() {
                    return whatever;
                }
            }
        }
    }

now suppose your application happens to be structured such that most
lists are empty. You can avoid creating a new iterator object every
time an empty loop appears in a for-each statement by the following
optimization:

    class MyList<T> implements Iterable<T> {
        private final static Iterator EMPTY_ITERATOR = new Iterator() {
            public boolean hasNext() { return false }
            public void remove() {
                throw new UnsupportedOperationException();
            }
            public Object next() { throw new NoSuchElementException(); }
        };
        public Iterator<T> iterator() {
            if (size == 0) return EMPTY_ITERATOR; // ***
            return new Iterator<T>() {
                public boolean hasNext() {
                    return whatever;
                }
                public void remove() {
                }
                public T next() {
                    return whatever;
                }
            }
        }
    }

Now there is no object creation when you ask for an iterator on an
empty List. However, there is an unchecked conversion at the line
marked *** even though this coding pattern is perfectly safe, and
there is no way to express in the Java type system that this is safe.

There is a trivial extension to the Java type system that can be used
along with a simple API change to make this safe. The required API
change is to change Iterable from this

    public interface Iterable<T> {
        java.util.Iterator<T> iterator();
    }

to this

    public interface Iterable<T> {
        java.util.Iterator<? extends T> iterator();
    }

Although not required, we would also benefit from making this change
in any interface that extends Iterable. This change to the return
type of Iterable.iterator() and its overriders is what is proposed for
tiger. It enables the rest of the solution to be completed in a
subsequent version of the languae. If we don't make the API change
now, we will never be able to make the coding pattern typesafe without
making incompatible API changes.

The language part of the change is to introduce a name for the null
type. For simplicity, I recommend it be called "null". Since types
and variables occupy separate namespaces, there is no
confusion. With these two changes, the coding pattern can now be
expressed in a typesafe way:

    class MyList<T> implements Iterable<T> {
        private final static Iterator<null> EMPTY_ITERATOR = new Iterator<null>() {
            public boolean hasNext() { return false }
            public void remove() {
                throw new UnsupportedOperationException();
            }
            public null next() { throw new NoSuchElementException(); }
        };
        public Iterator<? extends T> iterator() {
            if (size == 0) return EMPTY_ITERATOR; // ***
            return new Iterator<T>() {
                public boolean hasNext() {
                    return whatever;
                }
                public void remove() {
                }
                public T next() {
                    return whatever;
                }
            }
        }
    }

The marked line is now totally typesafe.

Because the Iterable and Iterator interfaces are inherently covariant it is
safe, for example, for a Collection<Object>'s iterator() method to return an
Iterator<String> instead of an Iterator<Object>. This proposed change
makes that possible when it is useful in an application.

Clients using the for-each language construct need not adjust