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 [5057857].
The coding pattern can be made typesafe but it requires a small language
change.  We propose to make a corresponding API change [5060257] 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 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. 

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.  This language change is the subject of this report.
With these two changes, the coding pattern can now be
expressed in a typesafe way:

    class MyList<T> implements Iterable<T> {
        private final 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.