Lecture 5: Higher Polymorphism

Title slide

Slides : Recording

This lecture continued the exploration of polymorphism from Lecture 3 with more varieties of polymorphism and more expressive applications of the technique. This included: subtypes and the Liskov substitutivity principle; how this interacts with parametric types; covariant, contravariant and invariant types; how subtyping is not inheritance; polymorphic type schemes; Hindley-Milner type inference; rank-2 types and higher; and the history of the Great Computer Language Shootout.

Links: Slides from Lecture 5; Recording of Lecture 5

Homework
1. Do This

Before the next lecture find an online tutorial or introductory guide for each of the assignment topics. Send me by email your five links and I will summarize them for the class.

Use these to help choose your topic for the written assignment.

Links: Topic list; Ian.Stark@ed.ac.uk

2. Watch This

Dependent Typing, Extending Haskell, Type System Research
Interview by InfoQ

Stephanie Weirich
Professor of Computer and Information Science
University of Pennsylvania

Link: Video (29’33”)Prof. Weirich at Penn

Photograph of Prof. Weirich
References

On the Liskov principle to express subtyping in terms of the behaviour of objects rather than their implementation.

Barbara Liskov
ACM Turing Award 2008

For contributions to practical and theoretical foundations of programming language and system design, especially related to data abstraction, fault tolerance, and distributed computing.

Link: Turing Award citation

Photograph of Prof. Liskov

Jeanette Wing
Professor of Computer Science, Columbia University

Previously Corporate Vice-President of Microsoft Research, Prof. Wing is a strong advocate for the effectiveness of computational thinking across multiple disciplines.

Links: Prof. Wing at Columbia; Computational Thinking; Dragon Lady interview

Photograph of Prof. Wing

A Behavioral Notion of Subtyping
Barbara Liskov and Jeanette Wing

ACM Transactions on Programming Languages and Systems 16(6):1811–1841. DOI 10.1145/197320.197383

Links: Publisher page; Prepaid access through Edinburgh University Library with EASE login

First page of “A Behavioral Notion of Subtyping”

On the distinction between subtyping and inheritance.

Interfaces and specifications for the Smalltalk-80 collection classes
William R. Cook

In OOPSLA ’92: Proceedings of the Seventh Annual Conference on Object-Oriented Programming Systems, Languages, and Applications. ACM Press, 1992. DOI: 10.1145/141936.141938

Explores the structure of a mature class library and various hierarchies of inheritance, subtyping, specification and implementation.

Links: Publisher page; Prepaid access through Edinburgh University Library with EASE login

Diagram showing interfaces vs inheritance in the Smalltalk-80 collection classes

Inheritance Is Not Subtyping
Cook, Hill and Canning

In POPL ’90: Proceedings of the 17th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, 1990. DOI: 10.1145/96709.96721

Early paper exploring how basing subtyping on inheritance doesn’t properly do justice to either concept.

Links: Publisher page; Prepaid access through Edinburgh University Library with EASE login

First page of “Inheritance Is Not Subtyping”

On the evolution of the Java max method over time.

java.util.Collections.max(…)
Java 2 JDK 1.2, 1998

The original release of the Collections classes.

Link: Documentation from Sun recorded by the Wayback Machine

Screenshot of Java 2 documentation page

java.util.Collections.max(…)
Java 11, 2018

The most recent Collections classes, making use of generics, bounds and wildcards.

Link: Documentation from Oracle

Screenshot of Java 11 documentation page

Leave a Reply

%d bloggers like this: