Advanced Programming Languages
CIS 670 Fall 2002

Course Description

SPECIAL TOPIC: POLYMORPHISM

An important principle of software construction is to factor out common functionality. Many programming languages use type abstraction, also called polymorphism, to support this process. With polymorphism, functions and procedures can operate over many different types of data so that the same code can be used in many situations. Examples include: 

• data structures, such as lists and trees, that store and provide
  access to many different types of elements
• run-time services, such as serialization, structural equality,
  and garbage collection, that iterate over any type of data
• operations that apply to all types of data supporting a common interface.

However, few programming languages support the rich forms of polymorphism needed for all of the above situations. Traditionally, polymorphism has been divided into three distinct flavors (parametric, ad hoc and subtype) and languages typically support only one or two of these varieties. It is becoming clear that all three of these forms of polymorphism are essential. Therefore, much current research seeks to integrate these forms of polymorphism together into next-generation programming languages.

In this graduate course, we will investigate these three different forms of polymorphism. We will ask questions such as: What operations can they express? How can languages supporting them be mathematically modeled? What issues are important in their implementation? What happens when they are combined together and with other language features? How does polymorphism relate to other mechanisms for software abstraction?

Tentative list of topics

1.  Parametric polymorphism
   • Girard-Reynolds polymorphic lambda calculus
   • Existential Types
   • Encoding of inductive types
   • Parametricity
   • Higher-order types
   • Pitfalls with references
2. Ad hoc polymorphism
   • Overloading
   • Dynamic types
   • Intensional polymorphism
   • Type classes in Haskell
   • Polytypic programming
   • Generic Haskell
3. Subtype polymorphism
   • Named vs. structural subtyping
   • Bounded quantification
   • Generic types in Java
   • Aspect-Oriented Programming