Type inference

Type inference, sometimes called type reconstruction,^[1]^: 320 refers to the automatic detection of the type of an expression in a formal language. These include programming languages and mathematical type systems, but also natural languages in some branches of computer science and linguistics.

Nontechnical explanation

Types in a most general view can be associated to a designated use suggesting and restricting the activities possible for an object of that type. Many nouns in language specify such uses. For instance, the word leash indicates a different use than the word line. Calling something a table indicates another designation than calling it firewood, though it might be materially the same thing. While their material properties make things usable for some purposes, they are also subject of particular designations. This is especially the case in abstract fields, namely mathematics and computer science, where the material is finally only bits or formulas.

To exclude unwanted, but materially possible uses, the concept of types is defined and applied in many variations. In mathematics, Russell's paradox sparked early versions of type theory. In programming languages, typical examples are "type errors", e.g. ordering a computer to sum values that are not numbers. While materially possible, the result would no longer be meaningful and perhaps disastrous for the overall process.

In a typing, an expression is opposed to a type. For example, $4$ , $2+2$ , and $2\cdot 2$ are all separate terms with the type $\mathrm {nat}$ for natural numbers. Traditionally, the expression is followed by a colon and its type, such as $2:\mathrm {nat}$ . This means that the value $2$ is of type $\mathrm {nat}$ . This form is also used to declare new names, e.g. $n:\mathrm {nat}$ , much like introducing a new character to a scene by the words "detective Decker".

Contrary to a story, where the designations slowly unfold, the objects in formal languages often have to be defined with their type from very beginning. Additionally, if the expressions are ambiguous, types may be needed to make the intended use explicit. For instance, the expression $2$ might have a type $\mathrm {nat}$ but could also be read as a rational or real number or even as a plain text.

As a consequence, programs or proofs can become so encumbered with types, that it is desirable to deduce them from the context. This can be possible by collecting the uses of untyped expression (including undefined names). If, for instance, a yet undefined name n is used in an expression $n+2$ , one could conclude, that n is at least a number. The process of deducing the type from an expression and its context is type inference.

In general not only objects, but also activities have types and may be introduced simply by their use. For a Star Trek story, such an unknown activity could be "beaming", which for sake of the story's flow is just executed and never formally introduced. Nevertheless, one can deduce its type (transport) following what happens. Additionally, both objects and activities can be constructed from their parts. In such a setting, type inference cannot only become more complex, but also more helpful, as it allows to collect a complete description of everything in a composed scene, while still being able to detect conflicting or unintended uses.

Type-checking vs. type-inference

In a typing, an expression E is opposed to a type T, formally written as E : T. Usually a typing only makes sense within some context, which is omitted here.

In this setting, the following questions are of particular interest:

E : T? In this case, both an expression E and a type T are given. Now, is E really a T? This scenario is known as type-checking.
E : _? Here, only the expression is known. If there is a way to derive a type for E, then we have accomplished type inference.
_ : T? The other way round. Given only a type, is there any expression for it or does the type have no values? Is there any example of a T? This is known as type inhabitation.

For the simply typed lambda calculus, all three questions are decidable. The situation is not as comfortable when more expressive types are allowed.

Types in programming languages

Types are a feature present in some strongly statically typed languages. It is often characteristic of functional programming languages in general. Some languages that include type inference include C23,^[2] C++11,^[3] C# (starting with version 3.0), Chapel, Clean, Crystal, D, F#,^[4] FreeBASIC, Go, Haskell, Java (starting with version 10), Julia,^[5] Kotlin,^[6] ML, Nim, OCaml, Opa, Q#, RPython, Rust,^[7] Scala,^[8] Swift,^[9] TypeScript,^[10] Vala,^[11] Dart,^[12] and Visual Basic^[13] (starting with version 9.0). The majority of them use a simple form of type inference; the Hindley–Milner type system can provide more complete type inference. The ability to infer types automatically makes many programming tasks easier, leaving the programmer free to omit type annotations while still permitting type checking.

In some programming languages, all values have a data type explicitly declared at compile time, limiting the values a particular expression can take on at run-time. Increasingly, just-in-time compilation blurs the distinction between run time and compile time. 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 most statically typed languages, the input and output types of functions and local variables ordinarily must be explicitly provided by type annotations. For example, in ANSI C:

int add_one(int x) {
    int result; /* declare integer result */

    result = x + 1;
    return result;
}

The signature of this function definition, int add_one(int x), declares that add_one 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:

add_one(x) {
    var result;  /* inferred-type variable result */
    var result2; /* inferred-type variable result #2 */

    result = x + 1;
    result2 = x + 1.0;  /* this line won't work (in the proposed language) */
    return result;
}

This is identical to how code is written in the language Dart, except that it is subject to some added constraints as 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 since the constant 1 is type integer, and hence that add_one 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 add_one is an integer. Similarly, since + requires both of its arguments be of the same type, x must be an integer, and thus, add_one 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 uses the most general type from the outset: in this case floating-point. This can however have detrimental implications, for instance using a floating-point from the outset can introduce precision issues that would have not been there with an integer type.

Frequently, however, degenerate type-inference algorithms are used that cannot backtrack and instead generate an error message in such a situation. This behavior may be preferable as type inference may not always be neutral algorithmically, as illustrated by the prior floating-point precision issue.

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.

Finally, a significant downside of complex type-inference algorithm is that the resulting type inference resolution is not going to be obvious to humans (notably because of the backtracking), which can be detrimental as code is primarily intended to be comprehensible to humans.

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 add_one:

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

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

Technical description

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 as an aggregate and subsequent reduction of the type annotations given for its subexpressions, or through an implicit understanding of the type of various atomic values (e.g. true : Bool; 42 : Integer; 3.14159 : Real; etc.). It is through recognition of the eventual 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 complex forms of higher-order programming and polymorphism, it is not always possible for the compiler to infer as much, and type annotations are occasionally necessary for disambiguation. For instance, type inference with polymorphic recursion is known to be undecidable. Furthermore, explicit type annotations can be used to optimize code by forcing the compiler to use a more specific (faster/smaller) type than it had inferred.^[14]

Some methods for type inference are based on constraint satisfaction^[15] or satisfiability modulo theories.^[16]

High-Level Example

As an example, the Haskell function map applies a function to each element of a list, and may be defined as:

map f [] = []
map f (first:rest) = f first : map f rest

Type inference on the map function proceeds as follows. map is a function of two arguments, so its type is constrained to be of the form a -> b -> c. In Haskell, the patterns [] and (first:rest) always match lists, so the second argument must be a list type: b = [d] for some type d. Its first argument f is applied to the argument first, which must have type d, corresponding with the type in the list argument, so f :: d -> e (:: means "is of type") for some type e. The return value of map f, finally, is a list of whatever f produces, so [e].

Putting the parts together leads to map :: (d -> e) -> [d] -> [e]. Nothing is special about the type variables, so it can be relabeled as

map :: (a -> b) -> [a] -> [b]

It turns out that this is also the most general type, since no further constraints apply. As the inferred type of map is parametrically polymorphic, the type of the arguments and results of f are not inferred, but left as type variables, and so map can be applied to functions and lists of various types, as long as the actual types match in each invocation.

Detailed Example

The algorithms used by programs like compilers are equivalent to the informally structured reasoning above, but a bit more verbose and methodical. We again begin with the definition of map:

map f [] = []
map f (first:rest) = f first : map f rest

First, we make fresh type variables for each individual term:

α shall denote the type of map that we want to infer.
β shall denote the type of f in the first equation.
[γ] shall denote the type of [] on the left side of the first equation.
[δ] shall denote the type of [] on the right side of the first equation.
ε shall denote the type of f in the second equation.
ζ -> [ζ] -> [ζ] shall denote the type of : on the left side of the first equation. (This pattern is known from its definition.)
η shall denote the type of first.
θ shall denote the type of rest.
ι -> [ι] -> [ι] shall denote the type of : on the right side of the first equation.

Then we make fresh type variables for subexpressions built from these terms, constraining the type of the function being invoked accordingly:

κ shall denote the type of map f []. We conclude that α ~ β -> [γ] -> κ where the "similar" symbol ~ means "unifies with"; we are saying that α, the type of map, must be compatible with the type of a function taking a β and a list of γs and returning a κ.
λ shall denote the type of (first:rest). We conclude that ζ -> [ζ] -> [ζ] ~ η -> θ -> λ.
μ shall denote the type of map f (first:rest). We conclude that α ~ ε -> λ -> μ.
ν shall denote the type of f first. We conclude that ε ~ η -> ν.
ξ shall denote the type of map f rest. We conclude that α ~ ε -> θ -> ξ.
ο shall denote the type of f first : map f rest. We conclude that ι -> [ι] -> [ι] ~ ν -> ξ -> ο.

We also constrain the left and right sides of each equation to unify with each other: κ ~ [δ] and μ ~ ο. Altogether the system of unifications to solve is:

α ~ β -> [γ] -> κ
ζ -> [ζ] -> [ζ] ~ η -> θ -> λ
α ~ ε -> λ -> μ
ε ~ η -> ν
α ~ ε -> θ -> ξ
ι -> [ι] -> [ι] ~ ν -> ξ -> ο
κ ~ [δ]
μ ~ ο

Then we substitute until no further variables can be eliminated. The exact order is immaterial; if the code type-checks, any order will lead to the same final form. Let us begin by substituting ο for μ and [δ] for κ:

α ~ β -> [γ] -> [δ]
ζ -> [ζ] -> [ζ] ~ η -> θ -> λ
α ~ ε -> λ -> ο
ε ~ η -> ν
α ~ ε -> θ -> ξ
ι -> [ι] -> [ι] ~ ν -> ξ -> ο

Substituting ζ for η, [ζ] for θ and λ, ι for ν, and [ι] for ξ and ο, all possible because a type constructor like · -> · is invertible in its arguments:

α ~ β -> [γ] -> [δ]
α ~ ε -> [ζ] -> [ι]
ε ~ ζ -> ι

Substituting ζ -> ι for ε and β -> [γ] -> [δ] for α, keeping the second constraint around so that we can recover α at the end:

α ~ (ζ -> ι) -> [ζ] -> [ι]
β -> [γ] -> [δ] ~ (ζ -> ι) -> [ζ] -> [ι]

And, finally, substituting (ζ -> ι) for β as well as ζ for γ and ι for δ because a type constructor like [·] is invertible eliminates all the variables specific to the second constraint:

α ~ (ζ -> ι) -> [ζ] -> [ι]

No more substitutions are possible, and relabeling gives us map :: (a -> b) -> [a] -> [b], the same as we found without going into these details.

Hindley–Milner type inference algorithm

The algorithm first used to perform type inference is now informally termed the Hindley–Milner algorithm, although the algorithm should properly be attributed to Damas and Milner.^[17] It is also traditionally called type reconstruction.^[1]^: 320 If a term is well-typed in accordance with Hindley–Milner typing rules, then the rules generate a principal typing for the term. The process of discovering this principal typing is the process of "reconstruction".

The origin of this algorithm is the type inference algorithm for the simply typed lambda calculus that was devised by Haskell Curry and Robert Feys in 1958.^{[citation needed]} In 1969 J. Roger Hindley extended this work and proved that their algorithm always inferred the most general type. In 1978 Robin Milner,^[18] independently of Hindley's work, provided an equivalent algorithm, Algorithm W. In 1982 Luis Damas^[17] finally proved that Milner's algorithm is complete and extended it to support systems with polymorphic references.

Side-effects of using the most general type

By design, type inference, especially correct (backtracking) type inference will introduce use of the most general type appropriate, however this can have implications as more general types may not always be algorithmically neutral, the typical cases being:

floating-point being considered as a general type of integer, while floating-point will introduce precision issues
variant/dynamic types being considered as a general type of other types, which will introduce casting rules and comparison that could be different, for instance such types use the '+' operator for both numeric additions and string concatenations, but what operation is performed is determined dynamically rather than statically

Type inference for natural languages

Type inference algorithms have been used to analyze natural languages as well as programming languages.^[19]^[20]^[21] Type inference algorithms are also used in some grammar induction^[22]^[23] and constraint-based grammar systems for natural languages.^[24]

References

^ ^a ^b Benjamin C. Pierce (2002). Types and Programming Languages. MIT Press. ISBN 978-0-262-16209-8.
^ "WG14-N3007 : Type inference for object definitions". open-std.org. 2022-06-10. Archived from the original on December 24, 2022.
^ "Placeholder type specifiers (since C++11) - cppreference.com". en.cppreference.com. Retrieved 2021-08-15.
^ cartermp. "Type Inference - F#". docs.microsoft.com. Retrieved 2020-11-21.
^ "Inference · The Julia Language". docs.julialang.org. Retrieved 2020-11-21.
^ "Kotlin language specification". kotlinlang.org. Retrieved 2021-06-28.
^ "Statements - The Rust Reference". doc.rust-lang.org. Retrieved 2021-06-28.
^ "Type Inference". Scala Documentation. Retrieved 2020-11-21.
^ "The Basics — The Swift Programming Language (Swift 5.5)". docs.swift.org. Retrieved 2021-06-28.
^ "Documentation - Type Inference". www.typescriptlang.org. Retrieved 2020-11-21.
^ "Projects/Vala/Tutorial - GNOME Wiki!". wiki.gnome.org. Retrieved 2021-06-28.
^ "The Dart type system". dart.dev. Retrieved 2020-11-21.
^ KathleenDollard. "Local Type Inference - Visual Basic". docs.microsoft.com. Retrieved 2021-06-28.
^ Bryan O'Sullivan; Don Stewart; John Goerzen (2008). "Chapter 25. Profiling and optimization". Real World Haskell. O'Reilly.
^ Talpin, Jean-Pierre, and Pierre Jouvelot. "Polymorphic type, region and effect inference." Journal of functional programming 2.3 (1992): 245-271.
^ Hassan, Mostafa; Urban, Caterina; Eilers, Marco; Müller, Peter (2018). "MaxSMT-Based Type Inference for Python 3". Computer Aided Verification. Lecture Notes in Computer Science. Vol. 10982. pp. 12–19. doi:10.1007/978-3-319-96142-2_2. ISBN 978-3-319-96141-5.
^ ^a ^b Damas, Luis; Milner, Robin (1982), "Principal type-schemes for functional programs", POPL '82: Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on principles of programming languages (PDF), ACM, pp. 207–212
^ Milner, Robin (1978), "A Theory of Type Polymorphism in Programming", Journal of Computer and System Sciences, 17 (3): 348–375, doi:10.1016/0022-0000(78)90014-4, hdl:20.500.11820/d16745d7-f113-44f0-a7a3-687c2b709f66
^ Center, Artificiał Intelligence. Parsing and type inference for natural and computer languages Archived 2012-07-04 at the Wayback Machine. Diss. Stanford University, 1989.
^ Emele, Martin C., and Rémi Zajac. "Typed unification grammars Archived 2018-02-05 at the Wayback Machine." Proceedings of the 13th conference on Computational linguistics-Volume 3. Association for Computational Linguistics, 1990.
^ Pareschi, Remo. "Type-driven natural language analysis." (1988).
^ Fisher, Kathleen, et al. "Fisher, Kathleen, et al. "From dirt to shovels: fully automatic tool generation from ad hoc data." ACM SIGPLAN Notices. Vol. 43. No. 1. ACM, 2008." ACM SIGPLAN Notices. Vol. 43. No. 1. ACM, 2008.
^ Lappin, Shalom; Shieber, Stuart M. (2007). "Machine learning theory and practice as a source of insight into universal grammar" (PDF). Journal of Linguistics. 43 (2): 393–427. doi:10.1017/s0022226707004628. S2CID 215762538.
^ Stuart M. Shieber (1992). Constraint-based Grammar Formalisms: Parsing and Type Inference for Natural and Computer Languages. MIT Press. ISBN 978-0-262-19324-5.

External links

Archived e-mail message by Roger Hindley, explains history of type inference
Polymorphic Type Inference by Michael Schwartzbach, gives an overview of Polymorphic type inference.
Basic Typechecking paper by Luca Cardelli, describes algorithm, includes implementation in Modula-2
Implementation of Hindley–Milner type inference in Scala, by Andrew Forrest (retrieved July 30, 2009)
Implementation of Hindley-Milner in Perl 5, by Nikita Borisov at the Wayback Machine (archived February 18, 2007)
What is Hindley-Milner? (and why is it cool?) Explains Hindley–Milner, examples in Scala

[TAPL-1] Benjamin C. Pierce (2002). Types and Programming Languages. MIT Press. ISBN 978-0-262-16209-8.

[2] "WG14-N3007 : Type inference for object definitions". open-std.org. 2022-06-10. Archived from the original on December 24, 2022.

[3] "Placeholder type specifiers (since C++11) - cppreference.com". en.cppreference.com. Retrieved 2021-08-15.

[4] rtermp. "Type Inference - F#". docs.microsoft.com. Retrieved 2020-11-21.

[5] "Inference · The Julia Language". docs.julialang.org. Retrieved 2020-11-21.

[6] "Kotlin language specification". kotlinlang.org. Retrieved 2021-06-28.

[7] "Statements - The Rust Reference". doc.rust-lang.org. Retrieved 2021-06-28.

[8] "Type Inference". Scala Documentation. Retrieved 2020-11-21.

[9] "The Basics — The Swift Programming Language (Swift 5.5)". docs.swift.org. Retrieved 2021-06-28.

[10] "Documentation - Type Inference". www.typescriptlang.org. Retrieved 2020-11-21.

[11] "Projects/Vala/Tutorial - GNOME Wiki!". wiki.gnome.org. Retrieved 2021-06-28.

[12] "The Dart type system". dart.dev. Retrieved 2020-11-21.

[13] KathleenDollard. "Local Type Inference - Visual Basic". docs.microsoft.com. Retrieved 2021-06-28.

[14] Bryan O'Sullivan; Don Stewart; John Goerzen (2008). "Chapter 25. Profiling and optimization". Real World Haskell. O'Reilly.

[15] Talpin, Jean-Pierre, and Pierre Jouvelot. "Polymorphic type, region and effect inference." Journal of functional programming 2.3 (1992): 245-271.

[16] Hassan, Mostafa; Urban, Caterina; Eilers, Marco; Müller, Peter (2018). "MaxSMT-Based Type Inference for Python 3". Computer Aided Verification. Lecture Notes in Computer Science. Vol. 10982. pp. 12–19. doi:10.1007/978-3-319-96142-2_2. ISBN 978-3-319-96141-5.

[Damas-and-Milner-1982-17] Damas, Luis; Milner, Robin (1982), "Principal type-schemes for functional programs", POPL '82: Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on principles of programming languages (PDF), ACM, pp. 207–212

[18] Milner, Robin (1978), "A Theory of Type Polymorphism in Programming", Journal of Computer and System Sciences, 17 (3): 348–375, doi:10.1016/0022-0000(78)90014-4, hdl:20.500.11820/d16745d7-f113-44f0-a7a3-687c2b709f66

[19] Center, Artificiał Intelligence. Parsing and type inference for natural and computer languages Archived 2012-07-04 at the Wayback Machine. Diss. Stanford University, 1989.

[20] Emele, Martin C., and Rémi Zajac. "Typed unification grammars Archived 2018-02-05 at the Wayback Machine." Proceedings of the 13th conference on Computational linguistics-Volume 3. Association for Computational Linguistics, 1990.

[21] Pareschi, Remo. "Type-driven natural language analysis." (1988).

[22] Fisher, Kathleen, et al. "Fisher, Kathleen, et al. "From dirt to shovels: fully automatic tool generation from ad hoc data." ACM SIGPLAN Notices. Vol. 43. No. 1. ACM, 2008." ACM SIGPLAN Notices. Vol. 43. No. 1. ACM, 2008.

[23] Lappin, Shalom; Shieber, Stuart M. (2007). "Machine learning theory and practice as a source of insight into universal grammar" (PDF). Journal of Linguistics. 43 (2): 393–427. doi:10.1017/s0022226707004628. S2CID 215762538.

[Shieber1992-24] Stuart M. Shieber (1992). Constraint-based Grammar Formalisms: Parsing and Type Inference for Natural and Computer Languages. MIT Press. ISBN 978-0-262-19324-5.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]