Hindleyâ€“Milner type system

Hindley - Milner ( HM) is a 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 completeness and ability, the most common type are able to determine a given source without adding annotations or other instructions. HM is an efficient method, which can determine the typing with respect to the size of the source almost in linear time, whereby it is practically applied for typing of large programs. HM is preferably used in functional languages . It was first implemented as part of the type system of the programming language ML. Since then, HM has been extended in various ways, in particular by limited types, as used in Haskell.

5.1 Main Type
5.2 Let- polymorphism

6.1 degrees of freedom in the rule selection
6.2 Syntax -directed control system
6.3 degree of freedom in Regelinstanzierung

7.1 The algorithm W in the original

8.1 Recursive Definitions

Introduction

Damas and Milner disconnect in the outline of its original publication of two very different tasks, the first is to describe which types can have an expression. The other is to provide an algorithm that actually computes a type.

To consider both aspects separately, allowed to specifically refer to the logic ( ie meaning) to be able to focus behind the algorithm and at the same time set a touchstone for the characteristics of the process. As expressions and types match zueinder, is described by means of an inference system. Like any proof system allows to reach in different ways to a conclusion. Since one and the same expression justifiable different types may have the inference can also come to very different conclusions about an expression. In contrast, each execution step is uniquely determined when the inference method itself (Algorithm W). Of course, decisions in the design of the algorithm have been made which do not occur in logic, and a closer examination and justification demand that would not be visible without the above differentiation.

The syntax

Logic and algorithm share the terms " expression " and "type", whose shape is specified by the syntax.

The expressions to be typed are those of the lambda calculus, extended with a let expression.

The shape represents the often written as function application, while the abstraction of the anonymous function or the function literal thinks, which is now available in many contemporary programming languages, there may be only more verbose about as advertised.

The total of types ( varieties) is divided into two groups, which are called mono- and polytypes. [Note 1]

Monotypes, syntactically Terme, always designate certain types in the sense that they are equal only to itself and different from all others. Characteristic representatives of monotypes are type constants such as or. Types can be parametric, eg. All these types are examples of applications of type functions, such as in the previous examples, the superscript number indicates the number of type parameters. While the choice of is arbitrary in principle, it must contain at least the conveniently written infix function type in the context of the HM. For example, a function that maps integers to strings, the type. [note 2]

Maybe a little irritating as are type variables also monotypes. A single type variable refers to a type that is as concrete as, say, or, and is different from both. An occurring as a monotype type variable behaves just as if it were a type constant over you but just does not have any additional information. According forms a functions with the type only values of type to itself and can only be applied to values of that type and no other else

In contrast, map each value to a value of the same type, a function with the polytype. The identical function is a value of this type. As another example, the type of a function mapping arbitrary finite amount to whole numbers. The number of elements of the set is a value for that type. Note that quantifiers may occur only at the top level, ie the type, for example, is excluded by the syntax. Furthermore, monotypes a subset of the polytypes, so that a total of types have the general form.

Free type variables

In one type is the symbol of the type variables in the type mono binding quantifier. The variables are called quantified. Each bound occurrence of a quantified variable in means and any unbound type variables are called free. As in the lambda calculus is the notion of free and bound variables fundamental to understanding the importance of the types.

This is certainly the hardest part of HM, perhaps because polytypes, which contain free type variables that can not be expressed in programming languages such as Haskell. Just as there are no free variables in Prolog clauses. In particular, with both languages experienced developers who thus actually know all the requirements for the HM can easily overlook this point. In Haskell, for example, all type variables are implicitly quantified, such as the Haskell type means here. Because guys like, although they can occur in Haskell well, there can not be expressed, they can be easily confused with the quantified version.

Which functions can now have a type, such as, that is a mixture of bound and unbound type variables contain and what does a free type variable in it?

Consider in Example 1, with type annotations in square brackets. Obviously, the parameters in the body is not used, but rather in the context of the outer bound variable. As a consequence, accepts any value as an argument, while providing a value that is outside bound and hence also its type.

In contrast, the type in which all type variables occur bound. You Evaluates for example, the result obtained is a function of type, reflecting perfectly that the monotype was refined by in by the call.

In this example, the free mono -type variable is loaded in type with the quantification of the outer scope with meaning, namely the type. This means in the context of this example, that the same type variable occurs both bound and free in different types. In this respect, a free type variable can not be interpreted more than can be said that it is a mono type without knowing the context. In other words, is a Typung generally involves. without knowledge of the context is not meaningful.

Context and Typung

To bring together the previously separate parts of the syntax, expressions and types useful, so is a third thing, the context requires. Syntactically, this is a list of pairs, assignment (see assignment, allocation, assignment ), called in the context assigns a value type of each variable. All three parts together form a Typung the form, which states that, assuming the expression is of type.

Because now is the full syntax available, finally a meaningful statement about the type of can be made in Example 1, namely. In contrast to previous formulations, the mono -type variable is no longer free, that is meaningless, but bound in the context as the type of value variables. Apparently playing the fact whether a type variable occurs in the context of free or bound, an important role for a type in the context of a Typung, therefore, is clarified in the box on the sides.

Comments on the expressiveness

Since the syntax of the expression like an unfamiliar with the lambda calculus readers appear to expressive weak by far and since the examples will support this prejudice rather, perhaps the hint is helpful that HM does not apply to toy languages. A key finding of the research in the area of predictability is that the above expression syntax (without the let clause ) is strong enough to describe any computable function. In addition, all other constructions can be transferred into programming languages syntactically relatively directly in terms of the lambda calculus. Therefore, these simple expressions are used as a model for programming languages. One method that is well applicable to the lambda calculus, can be easily applied to all or at least many other syntactic constructions of a particular programming language by means of the above-mentioned transformations.

For example, the additional expression variation can be transformed by. It has been added to the expression syntax in HM only in support of generalization during type inference and not because it lacks the syntax of computation power. So HM treated the inference of types in programs in general and the different functional languages that use this method, prove how good a result that is formulated only for the syntax of the lambda calculus, can be extended to syntactically complex languages .

In contrast to the impression that the expressions expressive weak for practical applications, whether they are actually expressive, to be ( in general) typed at all. This is a consequence of undecidability for substantive statements about expressions in the lambda calculus. Accordingly, the calculation of the Typung programs I. General. a hopeless task. Depending on the nature of the type system, this may either not terminate, or otherwise refuse to serve.

HM belongs to the latter group of type systems. A collapse of the variety apparatus appears here as more subtle situation in which only one and the same type is determined for expressions of interest. This is not a fault in the HM, but a problem of the typing itself inside dwelling property that can be easily produced in any strongly typed language. For this purpose, one encoding an evaluator (i.e., a universal function ) for the "too easy " expressions. We thus obtain a single concrete type that represents the universal data type, such as occurs in typeless languages. The variety of the host machine language is then collapsed and can no longer distinguish the different types of values that are passed to the evaluation or obtained from this. In this context, determined or the variety set checks are still types, but always the same, just as if the type system no longer exist.

Order polymorphic types

While the equality of monotypes is purely syntactic, polytypes have a richer relationship to other varieties, which is expressed by a specialization relation, which means that is more special than.

If a polymorphic function applied to a value, then they must adapt their shape to the specific type of this value. During this adjustment, it changes therefore also its type to match that of the parameter. For example, the identical function applied to the type on a number with the type, then they can not cooperate at first, because all types are different and do not fit. What is needed in this situation, is a function of type. To this end, the polymorphic identity in the context of the application in a monomorphic version of their transforms itself. Expressed in terms of specialization, you can write this as.

Now the form of conversion of polymorphic values is not completely arbitrary, but rather restricted by the original polytype. Following the procedure in this example, one can rewrite the specialization rule so that a polymorphic type is specialized by replacing each occurrence of consistent in what the Quantifierung omitted. While this usually works well for all monotypes as establishment, it fails if a polytype occurs as a replacement. If you try this for example with, then you get a unsyntaktischen type. But not only that, even if a nested quantification in syntax would be admissible, the result of this substitution would be the property of the original type in the parameters and results of the function are the same type, no longer obtained since now both subtypes have become independent and everyone would allow a specialization of different types, such as what would hardly be the right job for an identical function.

The syntactic restriction of the quantification at the top level prevents this undesirable generalization during specialization. Be used instead of must in this case, the more specific type.

You can pick up again the specialization had just been through another with the type. In terms of the relation obtained in summary, meaning that different syntactic polytypes are identical with respect to the renaming of their quantified variables.

Now, if we focus only on the question of whether a type is more special than another, and more, for which a more specific type is used, one can summarize the specialization as in the adjacent box. Clockwise circumscribed, a type is specialized by consistently replacing each of the quantified variables by any single type, so that one obtains a total mono type. Finally can type variables that are not free within the original type, are quantified optional.

The specialization rule, so take care that no free variable, that is, mono type in the original type, is bound by a quantifier unintentionally. Originally quantified variables can also be replaced ( consistent) arbitrarily, by types that introduce new or unquantifizierte quantified variables.

Starting with the polytype can be a specialization replace the body either by another quantized variable, ultimately renaming, or by a type constant (including the function type ), which can have parameters or not, each filled with a single type or a quantified type variables. Once a quantified variable has been replaced by a type application, it can not be canceled more by further specialization again, as in the substitution of a quantified variable was possible. Type uses are thus there to stay. Only if these contain another quantified type variable, can can specialization be continued by the subsequent replacement.

Thus, the specialization take no further equalities on a polytypes except the renaming already known. Polytypes are syntactically identical up to the renaming of their bound variables. The equality of types is a reflexive, antisymmetric and transitive relation and the remaining specialization of polytypes is transitive. Thus the relation is an order.

The Deduktionsmaschinerie

The syntax of HM is continued by the syntax of inference rules that form the body of the formal system, by using the Typungen as judgments. The rules define in which conditions one can draw what conclusions. In addition to the judgments can be used as premises some introduced above boundary conditions.

A proof by means of the rules is a sequence of judgments, so that all the premises are listed before the finals. See Examples 2,3 of a possible format of the evidence. From left to right, each row shows the circuit, the applied rule and the premises. Either by reference to a preceding line ( - nnummer ) if the premise is a judgment, or by explicitly specifying the predicate

The Typungsregeln

The lateral box shows the inference rule of the HM type system. They can be roughly divided into two groups:

The first four rules, and are centered about the syntax and type depending on a rule for each of the expressions. Their meaning is at first sight quite obvious, since they divide each term, consult the evidence that the subexpressions and combining the individual types in the premises to type in contract.

The second group is formed by the remaining rules and dealing with the specialization and generalization of types. While the rule has already been described in the contents section on the specialization, completes the control it through the reverse direction. It allows a generalization, that is, a quantification of a non-bound in the context of mono -type variables. The need for the restriction was introduced in the section on the free type variables.

The following two examples exercising the control system in action.

Example 2: A proof of with can be written as follows:

Example 3: To demonstrate the generalization is shown:

Main Type

As mentioned in the introduction, the rules allow for different types and tap into the same expression. See the example 2, steps 1.2 and Example 3, steps 2,3 of the same for three different Typungen expression. Apparently, the different results are not completely independent, but connected by the type of procedure. It is an essential feature of the control system and the type of order that, if more than one type can be inferred for an expression, an explicitly identified, the most common type is among these types (modulo equality) in the sense that all other specializations of him are. During a control system must allow it to derive specialized types, a Typinfernzalgorithmus should provide the most general or principal type as a result.

Let- polymorphism

Not immediately apparent encodes the set of rules a provision under which circumstances a type must not be generalized and when. This is done by a slight variation in the use of mono-and polytypes in the rules.

In general, the value variable of the parameter of the function is added to the context as a monomorphic type by the premise, while the variable enters in the rule of the surrounding region in polymorphic form. Although in both cases, in the context of preventing the presence of x the use of Generalisierungsregel for every single type variable in the assignment, enforces this rule that a parameter remains monomoph x in an expression, while in a let expression, the type variables can already be introduced polymorphic, which allows specializations.

As a consequence of these regulations can not be tapped for type, since the parameter is monomorphic in position while the guy gives reason that is introduced in a let expression and therefore treated polymorphically. Note that this behavior is in stark contrast to the usual definition, which is the reason at all to take the let- variation in the syntax of the expression. This distinction is called let- polymorphism and the HM is peculiar.

Transition to the algorithm

Now is the inference of the HMs at hand, one could imagine an algorithm that check against the rule. Alternatively, it may be due to a closer look at how its rules and the evidence is formed, also derived. This route is now trodden by focusing on the possible decisions during the proving a Typung the remainder of this article.

Degrees of freedom in the rule selection

Is isolated in a evidence, the points at which no selection is possible, then one obtains the centered around the expression syntax first group of rules as it determines the structure of the proof, since each of the rules of inference exactly corresponds to a rule of syntax, while between the premises and conclusions of this fixed rule applications can occur connecting chains and. All the evidence must have the form as outlined.

Since the only way are in a proof with regard to the rule selection and these chains, the shape shall provide the evidence leads to the question whether one can specify where these chains are required. This is indeed possible and leads to a variant of the control system without these two rules.

Syntax -directed control system

A contemporary treatment of the HM used a purely syntax -driven control system according to Clement as an intermediate step. In this system, the specialization is placed directly behind the original rule and now mixed into this, while generalization was recorded with in the rule. Here, the generalization also by the introduction of the function is determined so that it always generates the most general type, by all not quantified in bonded mono -type variables.

To verify that this new control system to the original equivalent, one has to show that what is divided into two sub- proofs:

( Correctness)
(Completeness )

While one can see the correctness of decomposition of the rules and to evidence of in, is just as evident that is incomplete because it can not show, for example, that is true, but at best only. However, a slightly weaker version of completeness is detectable, namely:

Which states that one can not derive the main type for an expression in if you allowed to generalize the proof at the end.

Note that contains compared to only monotypes in the judgments of its rules.

Degree of freedom in Regelinstanzierung

For a given expression for all the instances ( usually ) one is free within the rules themselves to choose variables that are not already defined by the expressions. These are the instances for the type variables in the rules. If you work out, to show the main type, then leaves the choice to the Choosing of suitable types for in and restrict. The decision for an appropriate selection can not be done locally, but their quality is, must come together in the premises of a recognizable, the only rule in which two different types, namely, that of the formal and the actual parameter.

Why would a general strategy to find a proof, be to make the common assumption () and for these, as well as to refine the choice to be in until all the conditions required by the rules are finally fulfilled. Fortunately, neither trial and error nor any iterations are required for this purpose, as an effective method to calculate all necessary decisions is known that the unification by Robinson in connection with the so-called union-find algorithm.

To summarize briefly the union-find method allows for a given set of all types in a proof, to share by means of the procedure into equivalence classes and to determine a representative means of the procedure. The word procedure in terms of accentuating side effect, will leave the realm of logic here to prepare an effective algorithm. The representative of here is determined so that, if both and also type variables, the representative is any one of them, whereas an association of a variable and an application latter is elected representatives. If you have such an implementation of the union-find at hand, one can formulate the unification of two monotypes as follows:

Unify (ta, tb ): ta = find (ta) tb = find (tb ) if ta, tb both applications the form D p1 .. pn with identical D, n are then unify (ta [i ], tb [i ] ) for each corresponding i-th parameter otherwise if at least one of ta tb, a type variable is then union ( ta, tb ) otherwise Error ' The types ta, tb do not match. ' algorithm W

The presentation of the algorithm W as it is shown in the box on the side, does not differ significantly only from the original, but also represents a significant misuse of the notation of logical rules, as he side-effects including. This is legitimized here to allow direct comparison with and at the same time provide an effective implementation. The rules specify now a procedure with parameters and result in the final, the execution of the premises from left to right runs. As an alternative to a procedure, the rules can be used as an attribute assignment ( with the same comments regarding the side effects ) are considered.

The procedure '' specializing the polytype by copying the term, replacing the bound variables contained therein consistent with (global) new mono type variables. '' Creates a new mono -type variable. Similarly, a copy of the type has to produce, are introduced into the (global) new type variables for the quantification, to avoid unwanted bonds.

Overall, the algorithm proceeds now by getting hit every possible de most common selection and specialization of unification leaves, which in turn generates the de most common possible outcome. As noted above, the result is once again at the end to generalize in order to receive the main type for a given expression.

Since the procedures used in the algorithm have cost close to O (1 ), the Gesamtkonsten the procedure almost linear to the size of the expression for which a type is to infer. It stands in stark contrast to many other attempts to produce a Typinferenzverfahren that have often been shown to be NP- hard, if not unentscheibar regarding termination. Thus, HM has the same throughput, the best fully informed type examination procedure may have. Type test here means that an algorithm has to find no evidence but this only needs to check.

The efficiency is slightly lower for two reasons. First, the bonds of the type variables are to be managed in the context to allow the calculation of. Further, a check OCCURS is required to prevent the formation of a recursive type for unification. An example of such a case is, for which no type can be derived with the HM. Since in practice the types are only small Terme and also not to build expanding structures, they may be considered in the complexity analysis as less than a certain constant, so that the O are preserved ( 1) costs.

The algorithm W in the original

In the original publication of the algorithm is formally described in a substitution style instead by side effects such as in the above method. In the last form, the side effects care invisible to all points in which type variables are used. Explicit use of the substitution not only makes the algorithm more difficult to read because the side effects occur practically everywhere, but also gives the false impression that the method is expensive. If they, however, implemented with purely functional agents or for the purpose of the proof of equivalence for inference, explicitness is full of course necessary and the original formulation of a necessary refinement.

Comments

ML (programming language) Haskell (programming language) Polymorphism (computer science) Soundness John Alan Robinson Occurs check Substitution (logic)

48048