Parametric Polymorphism


Parametric Polymorphism

Parametric polymorphism is the ability to have type variables in your program. A type variable is a symbol that could be replaced by a type expression.

For example, you might want to implement a list which works regardless of the type of it's elements. A language with parametric polymorphism allows you to define the type $\text{List}[E]$, where $E$ is a type variable that could be replaced by any type expression. In a way, parametric polymorphism allows you to define many types at once.

Here is the definition of a small type syntax (see Type System) which allows type variables:

[ \texttt{ty} &::= \texttt{INT}\ &| \texttt{BOOL}\ &| \texttt{LIST}~[ \langle\texttt{ty}\rangle ]\ &| \texttt{tyvar}\

\texttt{tyvar} &::= \alpha~|~\beta~|~\gamma~| \dots ]