# Is the type inference here really complicated?

There's a question on SO asking why in Java the right type doesn't get picked in a concrete case. I know that Java can't do it in such "complicated" cases, but I'm asking myself WHY?

The (for simplicity slightly modified) line failing to compile is

Map<String, Number> m = ImmutableMap.builder().build();


and the methods are defined as1

class ImmutableMap {
public static <K1, V1> Builder<K1, V1> builder() {...}
...
}

class Builder<K2, V2> {
public ImmutableMap<K2, V2> build() {...}
...
}


The solution K1=K2=String and V1=V2=Number is obvious to everyone but the compiler. There are 4 variables here and I can see 4 trivial equations, so what's the problem with type inference here?

1I simplified the code piece from Guava for this example and numbered the type variables to make it (hopefully) clearer.

• If I remember correctly, Java does not do any type inference, so why do you expect it to do it in this case? Also, because of type-erasure and downward-compatibility, the code as is has a fixed semantic, namely Object is assumed as type parameter if none is given. If you want a JVM language with a proper type system, try Scala. Note also that in a type system that supports co- and contravariant type parameters, there are many possible choices for the right-hand side. – Raphael Jun 28 '12 at 11:47
• There are many case where it works, for example ImmutableMap<String, Integer> m = ImmutableMap.of("a", 1);, but you might be right that it's no type inference yet. I agree that it might get complicated, but I can't see any other choice for the RHS here, can you elaborate? – maaartinus Jun 28 '12 at 13:22
• 1) There is no type inference in this example; you provide the types explicitly by the parameters. Note how already ImmutableMap<String, Long> m = ImmutableMap.of("a", 1); fails. 2) If you have types A subtype of SA and B subtype of SB, a reference of type ImmutableMap<A, SB> can point to an object of type ImmutableMap<SA,B> (note that this requires that type K of interface ImmutableMap<K,V> is never used in a return type, and V never in a parameter type); well, not in Java, but in principle. – Raphael Jun 28 '12 at 14:31
• @Raphael: 1. You're right: There's really no inference, just checking. That's it. 2. Your example with Long would require some magic, using Number instead helped me to understand what's going on. 3. Thx! – maaartinus Dec 31 '12 at 5:00

This is a common limitation of type inferencing and it has to do with the distinction between parameters and results of a function. Generally type inferencing is done strictly with the parameters passed to a function. Consider just the expression:

ImmutableMap.builder().build();


This has to be a valid expression due to how the language works. This means the type inferencing has to work from this expression alone. There is of course nothing in this expression which reveals what type you are expecting, thus it cannot compile (the type of the expression is not known).

It really isn't a question of how complicated the inferencing is, but rather a question of the fundamental structure of the language. It is possible to design a language where the return type becomes an implicit parameter to a function. However, this starts to create a loop in the typing logic in languages where variables can be auto-type (like C++).

The reason this happens is because of how the syntax trees for such languages are built (this may be only in theory as the compiler may not match exactly). When you have an expression like the above you have a tree that might look kind something like this:

- Assignment
- LValue: Map<String, Number> m
- RValue: FunctionCall(
FunctionCall( ImmutableMap, builder ),
build
)


In such languages the "RValue" is essentially an expression -- where expressons are something that resolves to a value. These are processed on their own, and thus limited to the variables and sub-expressions which occur in them. Type inferencing doesn't usually go up tree, thus the FunctionCall has no knowledge it is part of the Assignment tree and thus no knowledge of the "LValue" (what it is being assigned to).

This is the traditional way to process languages (it even applies to formal languages like lambda calculus). Languages don't have to work this way, but there it is the most commonly understood way parsing works. You can certainly make a syntax tree which forwards type information in an assignment, but that leads to the pitfall I mentioned if the "LValue" is auto-typed. If you attempt to allow both sides to infere their type you start entering a constraint based typed system (which again, is possible and I have worked on one before).

One practical way of doing this in some languages is to pass the return variables by reference (which isn't really possible in Java). In C++ I often do this where the function requires its return type. Instead of doing:

var = someFunc(...);


I'll do:

someFunc( var, ... );


And this allows the type of "var" to be known by the function (in this case for template resolution).

• What is the conceptual barrier that prevents a type checker to use the type of the reference the expression's value is assigned to? – Raphael Jun 28 '12 at 17:01
• I expanded with a bit about syntax trees. – edA-qa mort-ora-y Jun 28 '12 at 17:13
• This is a common limitation of one particular technique for type inference. There's nothing intrinsically difficult about inferring return types. I don't see how the part about syntax trees is relevant (maybe because I come from the ML world, I'm not familiar with the techniques commonly used for Java). Why would you restrict type inference to going bottom-up? You can do type verification this way, but inference should means that you have non-local feedback somehow (constraints being one way to achieve non-local feedback). – Gilles Jul 17 '12 at 18:20
• I did indicate this is just how this language works. I understand there are other options. I myself did a full top/bottom constraint based typing system once which handled return values with ease. It comes at a cost of compilation time however. Ultimately this bottom-up approach is extremeley easy and cheap to implement. – edA-qa mort-ora-y Jul 17 '12 at 18:59