6.5 Type Inference

Type inference refers to the ability to deduce automatically the type of a value in a programming language. It is a feature present in some strongly statically typed languages. It is often characteristic of, but not limited to, functional programming languages in general. Some languages that include type inference are Visual Basic (starting with version 9.0), C# (starting with version 3.0), Clean, Haskell, ML, OCaml, Scala. This feature is also planned for C++0x and Perl 6. The ability to infer types automatically makes many programming tasks easier, leaving the programmer free to omit type annotations while still permitting type checking.

Let us take an example.

int addone(int x) {
    int result;
    result = x + 1;
    return result;
}

This function returns an int, so we can infer that result should be type int. As the result is obtained by adding 1 (an integer) to x, then we can surmise that x is type int. It will be nice if we could write the above program as:

int addone(x) {
    result = x + 1;
    return result;
}

Thus we can “reverse engineer” the types of various program components.

However, languages that support type inference to the degree the above example illustrates rarely support such implicit type conversions. 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.

Type inference is the ability to automatically deduce, either partially or fully, the type of an expression at compile time. The compiler is often able to infer the type of a variable or the type signature of a function, without explicit type annotations having been given. In many cases, it is possible to omit type annotations from a program completely if the type inference system is robust enough, or the program or language is simple enough.

To obtain the information required to infer the type of an expression, the compiler either gathers this information throughout the program as a whole and subsequent reduction of the type annotations given for its subexpressions, or through an implicit understanding of the type of various atomic values, for example, True is type bool, 42 is type integer, 3.14159 is type float or double, etc. It is through reduction of expressions to implicitly typed atomic values that the compiler for a type inferring language is able to compile a program completely without type annotations. In the case of languages having complex structure, operator overloading and polymorphism, it is not always possible for the compiler to do such inferences and hence type annotations are occasionally necessary for disambiguation of types.

6.5.1 Formal Semantics

The semantic information associated with an identifier is sometimes called its environment. For an identifier a, it is written as E(a). As suggested in Exercise 1, it can be stored in the Symbol Table. As we shall see in Chapter 7, block structured languages use Symbol Table which changes its contents at run-time. Thus, the environment associated with an identifier may go on changing as the computation proceeds.

Formal Semantics is a mathematical method of defining the semantics of language constructs. Inference rules are widely used in formal specifications of programming language semantics. An inference rule defines for certain set of hypotheses what should be the conclusion and looks like this:

You should read this as a rule: “if all of the hypotheses 1 to n are true, then the conclusion will hold”.

For example, the rule for type checking multiplication is:

E e : t means that, in environment E, the expression e has type t.

To type check the occurrence of a variable, we have to check that the variable is defined in the current environment, and find the corresponding type:

Here are some example rules:

This rule is an axiom, because it does not have a precedence hypothesis.

This is another axiom.

We can combine several rules to build a complete “rule tree”.

This rule tree says that in any environment where x and y are both defined with type int, the expression x2 * y has type boolean.

We can check statements using similar idea:

Note that sentences do have a type, so we just write E ├ s to indicate that s is well formed in environment E.

A function body having a statement s, introducing a variable v of type t, would be type-checked as:

The symbol ⊕ indicates environment E merged with variable-type pair (v, t).

Checking Variable Declarations: Formal arguments count as local variables as far as type-checking is concerned.