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.
Compiler Design

EasyExamNotes.com covered following topics in Compiler Design.

Python Programming ↓ 👆
Java Programming ↓ 👆
JAVA EasyExamNotes.com covered following topics in these notes.
JAVA Programs
Principles of Programming Languages ↓ 👆
Principles of Programming Languages
EasyExamNotes.com covered following topics in these notes.

Practicals:
Previous years solved papers:
A list of Video lectures References:
  1. Sebesta,”Concept of programming Language”, Pearson Edu 
  2. Louden, “Programming Languages: Principles & Practices” , Cengage Learning 
  3. Tucker, “Programming Languages: Principles and paradigms “, Tata McGraw –Hill. 
  4. E Horowitz, "Programming Languages", 2nd Edition, Addison Wesley

    Computer Organization and Architecture ↓ 👆

    Computer Organization and Architecture 

    EasyExamNotes.com covered following topics in these notes.

    1. Structure of desktop computers
    2. Logic gates
    3. Register organization
    4. Bus structure
    5. Addressing modes
    6. Register transfer language
    7. Direct mapping numericals
    8. Register in Assembly Language Programming
    9. Arrays in Assembly Language Programming

    References:

    1. William stalling ,“Computer Architecture and Organization” PHI
    2. Morris Mano , “Computer System Organization ”PHI

    Computer Network ↓ 👆
    Computer Network

    EasyExamNotes.com covered following topics in these notes.
    1. Data Link Layer
    2. Framing
    3. Byte count framing method
    4. Flag bytes with byte stuffing framing method
    5. Flag bits with bit stuffing framing method
    6. Physical layer coding violations framing method
    7. Error control in data link layer
    8. Stop and Wait scheme
    9. Sliding Window Protocol
    10. One bit sliding window protocol
    11. A protocol Using Go-Back-N
    12. Selective repeat protocol
    13. Application layer
    References:
    1. Andrew S. Tanenbaum, David J. Wetherall, “Computer Networks” Pearson Education.
    2. Douglas E Comer, “Internetworking with TCP/IP Principles, Protocols, And Architecture",Pearson Education
    3. KavehPahlavan, Prashant Krishnamurthy, “Networking Fundamentals”, Wiley Publication.
    4. Ying-Dar Lin, Ren-Hung Hwang, Fred Baker, “Computer Networks: An Open Source Approach”, McGraw Hill.