Lecture 3: Parameterized Types and Polymorphism

Title slide

Slides : Recording

Monday’s lecture gave examples of parameterized types in different programming languages: families of data types with a common structure, built by applying type constructors to one or more type parameters. Examples include in Java or C# generics as well as the algebraic datatypes of Haskell and OCaml. To work with parameterized types we use polymorphic functions — code that can work with more than one type, either in a uniform way (parametric polymorphism) or with type-specific variations (ad-hoc polymorphism).

Links: Slides from Lecture 3; Recording of Lecture 3

1. Read This

Type Systems
Section 1: Introduction

Luca Cardelli
Chapter 97 of The Computer Science and Engineering Handbook, 2nd Edition, 2004

This is a 40-page paper that covers a lot of material on type systems. The part to read today is the first 9 pages that set out what a type system is and what it can bring to programming.

Links: Paper in PDF; Author web page

Photograph of Luca Cardelli

There’s a new version of this by Stephanie Weirich in a more recent edition of the Handbook: I’m working to get copies of that through the library.

2. Watch This

Propositions as Types
Strange Loop, September 2015

Phil Wadler
Professor of Theoretical Computer Science
The University of Edinburgh

Links: Video (42’42”); Prof. Wadler at Edinburgh

Photograph of Wadler

There’s also a paper to accompany this talk which you might find helpful to read.

Philip Wadler. Propositions as Types. Communications of the ACM, 58(12):75–84, December 2015.
HTML · PDF (EASE login) · Author PDF https://doi.org/10.1145/2699407
3. Code This

Java has subtyping: a value of one type may be used at any more general type. For example, StringObject, and every Java String is an Object. This isn’t always straightforward — consider the following code.

String[] a = { "Hello", "world" };    // Array of strings
Object[] b = a;                       // Array of objects (every string is an object)
b[0] = Boolean.FALSE;                 // Assign object to array of objects
String s = a[0];                      // Fetch string from array of strings
System.out.println(s.toUpperCase());  // Convert string to upper-case
  1. Build a Java program around this.

  2. Compile it. Run it.

  3. What happens? Can you explain why?

  4. How might you change the Java language to prevent this?

  5. Pick another object-oriented language: what happens when you try this there?


AWS Lambda
Run code without thinking about servers

First-class functions in the cloud: Amazon’s Lambda platform for “serverless computing”. In fact huge numbers of servers are involved; but abstraction means they aren’t the programmer’s concern.

Civilization advances by extending the number of important operations which we can perform without thinking about them. (Whitehead, 1911)

Link: AWS Lambda


GJ: A Generic Java Language Extension

Wadler’s page recording the development of Java generics, and their eventual inclusion into the language.

Links: GJ web page; A recent Java Generics tutorial

Screenshot of web page

Generics for .NET

Andrew Kennedy’s page recording the development of .NET generics, and some of the work involved going from a theoretically clean and useful concept all the way to practical deployment in the .NET tools and runtime.

Links: Kennedy on .NET generics; Don Syme’s whiteboard; Microsoft current generics documentation

 Andrew Kennedy's generic mug

Leave a Reply

%d bloggers like this: