CODEWITHSUNDEEP
algorithmcompiler-constructiontype-inference
Jon Flow
Jon Flow

Reputation: 535

How is type inference implemented in a language like C++11 or Go?

I saw this question here, but it doesn't answer what I had in mind in particular detail. If languages like Go or C++11 don't use an inference algorithm like Damas-Milner, what exactly do they do? I don't think it's as simple as taking the type on the right hand side because what if you had something like:

5 + 3.4

How would the compiler decipher what type that is? Is there any algorithm that isn't as simple as

if left is integer and right is float:
    return float;
if left is float and right is integer:
    return float;
etc... for every possible pattern

And if you could explain things in simple terms that would be great. I'm not studying compiler construction or any of the theoretical topics in great detail, and I don't really speak functional languages or complex mathematical notation.

Upvotes: 0

Views: 392

Answers (1)

sepp2k
sepp2k

Reputation: 370082

I don't think it's as simple as taking the type on the right hand side

For basic type inference of the form auto var = some_expression;, it is exactly that simple. Every well-typed expression has exactly one type and that type will be the type of var. There will be no implicit conversion from the type of the expression to another type (as there might be if you gave an explicit type for var).

what if you had something like:

5 + 3.4

The question "What is the type of 5 + 3.4?" isn't specific to type inference, C++ compilers always had to answer this question - even before type inference was introduced.

So let's take a step back and look at how a C++ compiler typechecks the statement some_type var = some_expression;:

First it determines the type of some_expression. So in code you can imagine something like Type exp_type = type_of(exp);. Now it checks whether exp_type is equal to some_type or there exists an implicit conversion from exp_type to some_type. If so, the statement is well-typed and var is introduced into the environment as having the type some_type. Otherwise it is not.

Now when we introduce type inference and write auto var = some_expression;, the equation changes as such: We still do Type exp_type = type_of(exp);, but instead of then comparing it to another type or applying any implicit conversions, we instead simply set exp_type as the type of var.

So now let's get back to 5 + 3.4. What is its type and how does the compiler determine it? In C++ its type is double. The exact rules to determine the type of an arithmetic expression are listed in the C++ standard (look for "usual arithmetic conversions"), but basically boil down to this: Of the two operand types, pick the one that can represent the greater range of values. If the type is smaller than int, convert both operands to int. Otherwise convert both operands to the type you picked.

In code you'd implement this by assigning each numeric type a conversion rank and then doing something like this:

Type type_of_binary_arithmetic_expression(Type lhs_type, Type rhs_type) {
    int lhs_rank = conversion_rank(lhs_type);
    int rhs_rank = conversion_rank(rhs_type);
    if(lhs_rank < INT_RANK && rhs_rank < INT_RANK) return INT_TYPE;
    else if(lhs_rank < rhs_rank) return rhs_type;
    else return lhs_type;
}

Presumably the rules for Go are somewhat different, but the same principles apply.

Upvotes: 5

Related Questions