Type Inference - Nontechnical Explanation

Nontechnical Explanation

In most programming languages, all values have a type explicitly declared at compile time, limiting the values a particular expression can take on at run-time. Increasingly, just-in-time compilation renders the distinction between run time and compile time moot. However, historically, if the type of a value is known only at run-time; these languages are dynamically typed. In other languages, the type of an expression is known only at compile time; these languages are statically typed. In statically typed languages, the input and output types of functions and local variables ordinarily must be explicitly provided by type annotations. For example, in C:

int addone(int x) { int result; /*declare integer result (C language)*/ result = x + 1; return result; }

The signature of this function definition, int addone(int x), declares that addone is a function that takes one argument, an integer, and returns an integer. int result; declares that the local variable result is an integer. In a hypothetical language supporting type inference, the code might be written like this instead:

addone(x) { val result; /*inferred-type result */ val result2; /*inferred-type result #2 */ result = x + 1; result2 = x + 1.0; /* this line won't work (in the proposed language) */ return result; }

This looks very similar to how code is written in a dynamically typed language, but with some extra constraints (described below) it would be possible to infer the types of all the variables at compile time. In the example above, the compiler would infer that result and x have type integer and addone is a function int -> int. The variable result2 isn't used in a legal manner, so it wouldn't have a type.

In the imaginary language in which the last example is written, the compiler would assume that, in the absence of information to the contrary, + takes two integers and returns one integer. (This is how it works in, for example, OCaml). From this, the type inferencer can infer that the type of x + 1 is an integer, which means result is an integer and thus the return value of addone is an integer. Similarly, since + requires that both of its arguments be of the same type, x must be an integer, and therefore addone accepts one integer as an argument.

However, in the subsequent line, result2 is calculated by adding a decimal "1.0" with floating-point arithmetic, causing a conflict in the use of x for both integer and floating-point expressions. The correct type-inference algorithm for such a situation has been known since 1958 and has been known to be correct since 1982. It revisits the prior inferences and utilizes the most general type from the outset: in this case floating-point. Frequently, however, degenerate type-inference algorithms are used that are incapable of backtracking and instead generate an error message in such a situation. An algorithm of intermediate generality implicitly declares result2 as a floating-point variable, and the addition implicitly converts x to a floating point. This can be correct if the calling contexts never supply a floating point argument. Such a situation shows the difference between type inference, which does not involve type conversion, and implicit type conversion, which forces data to a different data type, often without restrictions.

The recent emergence of just-in-time compilation allows for hybrid approaches where the type of arguments supplied by the various calling context is known at compile time, and can generate a large number of compiled versions of the same function. Each compiled version can then be optimized for a different set of types. For instance, JIT compilation allows there to be at least two compiled versions of addone:

A version that accepts an integer input and uses implicit type conversion.

A version that accepts a floating-point number as input and utilizes floating point instructions throughout.