**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**