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

Professor Jayesh video tutorial

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