Type inference
By inference (of English type, (data) type 'or' data type ' and inference, conclusion '), also known as type inference can programming much paperwork can be saved in some ( strongly typed ), by omitting the transcript of type information, the rest of the information and the typing rules are evaluated ( reconstructed ) may be; this one uses the same rules, which are also used for type checking, as these evolve, the inference is to be considered in some way. In the implementation is determined by unification the most common type (main type, principal type) of a term.
The development of type inference ( ML ) by Milner was a milestone in the development of programming languages. They related, but at the same time has also enabled more sophisticated type systems that won so much more important. Certain language features such as type adjustments and sometimes overloading were pushed back because they collide with the type inference.
Example
Consider the following code:
Int a; c = a b; Here, the type system of the programming (if it has a corresponding type system, including strict rules ) can now automatically deduce that the variable b must be of type int, because the variable a is already of type int, and the operator not with two values of different types may be used. In addition, the variable c must be an int because the int result of addition is also of type int.
Type inference is important to help the programmer to quickly detect careless mistakes. In a strongly typed language such as SML, it is not possible for example to compare integers with boolean values; exactly to avoid such errors and find types can be derived by means of type inference for all expressions, and it is checked whether all operations performed on the expressions are type- compliant ( if accepted, for example, as above additions permitted only between two numbers of the same type are ).
A more complex example of the type inference to derive the type of the function f in the following SML code:
Fun f (a, b, c) = if b then a ( b) c 1 else First, the variable b must be of type bool ( truth value ), since it is after the if the if-then -else statement. Second, one can say that the entire function must return an int, since both the then and the else part of the same type must have, and c 1 type must be an int because 1 is of type int, and thus also - must be of type int c - due to the plus operator. Now one can say that a must be a function, as applied in the then- part a to b. However, since then and else part must have the same return type, the result of the function a must be an int used to b also. Thus, for the function f of the following type:
F: ( (bool -> int) * bool * int ) -> int Note: In the above example explicitly the typing rules of the language SML used. Other languages such as C or Java have other typing rules so that the Typherleitung there may be different or possibly due to the weak typing of the language (there are many places several different types of permits ) is not possible.
Hindley - Milner
Hindley - Milner ( HM) is a classic method of inference with parametric polymorphism for the lambda calculus. It was first described by J. Roger Hindley and later rediscovered by Robin Milner. Luis Damas contributed a detailed formal analysis and a proof of the method in his doctoral thesis, which is why the method is also known as Damas - Milner. Among the outstanding features of the HM are completeness and ability the most common types of a given source without adding annotations or other instructions to be determined. HM is an efficient method, which can determine the typing with respect to the size of the source almost in linear time, thus it is applicable in practice to the type of large programs. HM is preferably used in functional languages . It was first implemented as part of the programming Sortenapparts ML. Since then, HM has been extended in various ways, in particular by limited types, as used in Haskell.