Why is this invalid Java? Type of ternary operator output

Question

Check out this code.

// Print object and recurse if iterable
private static void deep_print(Object o) {
  System.out.println(o.getClass().toString() + ", " + o.toString());

  boolean iter = false;
  Iterable<?> i1 = null;
  Object[] i2 = null;

  if (o instanceof Iterable<?>) {
    iter = true;
    i1 = (Iterable<?>) o;
  } else if (o instanceof Object[]) {
    iter = true;
    i2 = (Object[]) o;
  }

  if (iter) {
    for (Object o_ : i2 == null ? i1 : i2) deep_print(o_); // ERROR: Can only iterate over an array or an instance of java.lang.Iterable
  }

I know how to solve it. I just want to know why it happens. Shouldn't the compiler simply check all the possible outputs?

Answer 1

The static result type of the expression (i2 == null) ? i1 : i2 is the common ancestor of i1 and i2 which is Object. A for statement requires the static type of the expression to be either an Iterable or an array type. That is not the case, so you get a compilation error.

Now if you are asking why doesn't the compiler deduce that (i2 == null) ? i1 : i2 will always be an array or an Iterable:

1. The Java language specification (JLS) does not allow this.
2. If the JLS did allow it (but not require it) then different compilers would behave differently, depending on how good they were at theorem proving. BAD.
3. If the JLS required it, then the compiler has to incorporate a sophisticated theorem prover^`1 (BAD SLOW), and you run into the "minor inconvenience" of solving the Halting Problem² (BAD BAD BAD).
4. In actual fact the compiler needs to know which of the two kinds of type the expression has because it needs to generate different code in each case.

---

Hypothetically, if the Java type system was a bit different, this particular case could be handled better. Specifically, if Java supported algebraic data types then it would be possible to declare o as being "either an object array or an iterable" ... and the for loop would be type-checkable.

---

^{1 - Suppose that o had been initialized as o = (x * x < 0) ? new Object() : new Object[0]. Determining that that will always result in an Object[] instance entails a small proof involving the fact that the square of a (real) number is not negative. That's a simple example, it is possible to construct arbitrarily complicated examples requiring arbitrary difficult proofs.}

^{2 - The Halting Problem is mathematically proven to be an incomputable function. In other words, there exist functions where it is mathematically impossible to prove whether or not they terminate.}

Answer 2

To illustrate Stephen C's answer, consider the following code:

void test() {
      Iterable<Integer> i1 = new ArrayList<Integer>();
      Object[] i2 = { 1, 2, 3 };      
      method1(false ? i1 : i2);
      method1(true ? i1 : i2);  
}

void method1(Object o) {
    System.out.println("method1(Object) called");
}

void method1(Object[] o) {
    System.out.println("method1(Object[]) called");
}

void method1(Iterable<?> o) {
    System.out.println("method1(Iterable<?>) called");
}

This is the output of test():

method1(Object) called
method1(Object) called

Since method overloading is done at compile-time, you can see that the static type of the ternary operator expression is Object, since the types of the operands differ. Therefore, when you do :

for (Object o_ : i2 == null ? i1 : i2)

you are really asking the compiler to generate a foreach loop over an Object, which is illegal.

Answer 3

in this case, the conditional expression has the type of the least upper bound of the two types, which is Object, and the foreach loop does not work on type Object

Answer 4

You really should add two overloaded deepPrint( Object[] ) and deepPrint(Iterator i) methods and do the dispatch in your deepPrint(Object object). Yes because of the nature of how the for/each loop works you will need to copy and paste the same code with minor changes.

Trying to put all that into one big method is a smell.

Answer 5

You can avoid the code duplication by wrapping the Object[] in an Arrays.asList(Object[]) and then have an Iterable in all cases. Yes its slightly slower than working on an array, but it has the advantage of being DRY, which should always be the first approximation, IMHO.

So you would end up with something like this:

Iterable<?> it = null;
if (o instanceof Iterable<?>) {
    it = (Iterable<?>) o;
} else if (o instanceof Object[]) {
    it = Arrays.asList((Object[]) o);
}

if (it != null) {
   for (Object o_ : it) deep_print(o_);
}

For simplicity's sake (see Stephen C's answer for how it is simpler for compiler writers, but it is arguably a simpler language design as well) the ternary operator assumes the type to be the lowest common demoninator between the two return types, rather than accomidating one of the two return types. Consider the case of a method overloading. The right method is determined and compile time. This means that the compiler has to be able to make a decision about the declared return type at compile time, and can't delay that decision to run time.