polymorphic function in compiler

POLYMORPHIC FUNCTION

POLYMORPHIC   FUNCTION:

1-The term “POLYMORPHIC” refers to any code fragments that can be executed with arguments of different type’s .suppose parametric polymorphism, where the polymorphism is characterized by parameters or type variable.

2-The running example is the ML program, which defines the function Length. The type of Length can be described as “for any type α. length maps a list of elements of type α to an   integer.”

3-Type inference is useful for a language like ML, which is strongly typed but does not require names to be declared before they are used Type inference ensures that names are used consistently.
Fun length(x) = if null(x) then 0 else length (Tl(x)) +1;

ALGORITHM:
Type inference for polymorphic function.

Input:
A program consisting of a sequence of function definitions followed by an expression to be evaluated. An expression is made up of function application and names, where names can have predefined polymorphic types

Output:
Inferred types for the names in the program.

Method:
The type of a function F(x1, x2) with two parameters can be represented by a type expression
s1+s2 = t, where s1 and s2 are the types of x1 and x2 respectively and t is the type of result f(x1,x2).

An expression f (a, b) can be checked by matching the type of a with s1 and the type of b with s2.

Check the function definition and the expression in the input sequence. Use the inferred type of a function if it is subsequently used in an expression.


  • For a function definition fun id1 (id2) = E, create fresh type variable α and β. Associate the type α-> β with the function id1.and the type a with the parameter id2. Then infer a type for an expression E.
  • Suppose α denote type s and β denote type t after type inference for E. the inferred type function id1 is s->t. Bind any type variable that remain unconstrained in s->t by V quantifiers.
  • For a function application   E1 (E2), infer types for E1 and E2. Since E1 is used as a function, its type must have the form s->s’ .Let T be the inferred type of E2. Unify s and t. if unification fails, the expression has a type error otherwise the inferred type of E1 (E2) is s’.
  • For each occurrence of a polymorphic function, replace the bound variables in its type by distinct fresh variable and remove the V quantifier. The resulting type expression is the inferred type of this occurrence.
  • For a name that is encountered for the first time, introduces a fresh variable for its type.


BY:
SHAMI DALAL

TSEC BURHANPUR

Related topics

Please use contact page in this website if you find anything incorrect or you want to share more information about the topic discussed above.