Lecture 17: Higher Polymorphism

Title slideBeyond the simply-typed lambda-calculus, and even Hindley-Milner polymorphism, there’s a whole world of type systems for more expressivity, more precision, and more polymorphism. Tuesday’s lecture looked at some of this: issues around subtype polymorphism in object-oriented code, motivations for higher-rank polymorphism, and the wonders of System F. For System F in particular there’s a range of further possibilities: this lecture covered encoding datatypes, but there are also subtyping, bounded and F-bounded quantification, F2, Fω, existential types, and more…

Link: Slides for Lecture 17

Homework

Friday has the last technical lecture of the course, and Tuesday will be an exam review lecture where I shall go through past exam questions or topics from those nominated by you.

  • Go to the exams page, read it, then download and look through the past papers.
  • Pick out specific questions, part-questions, or topics to nominate for the review lecture.
  • Post them to the mailing list, the Facebook page, or as a comment on this blog entry.

Please note that some past questions address topics not covered this year: naturally, those areas won’t appear on the exam.

References

Cook: Interfaces and Specifications for the Smalltalk-80 Collection Classes 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
Links: ACM Digital Library, Paid-for access through Edinburgh University Library
Cook, Hill and Canning: Inheritance is not Subtyping 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
Links: ACM Digital Library, Paid-for access through Edinburgh University Library
java.util.Collections.max from JDK 1.2.2 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
java.util.Collections.max() from Java 8 java.util.Collections.max(…)
Java 8, 2014
The most recent Collections classes, with heavy use of generics.
Link: Documentation from Oracle
The Computer Language Benchmarks Game The Computer Language Benchmarks Game
Previously the Computer Language Shootout, with its custom “Completely Random and Arbitrary Point System” select-your-own scorecard.
Links: The Benchmarks Game; Archives of The Shootout and The Scorecard
Okasaki: Even Higher-Order Functions for Parsing or Why Would Anyone Ever Want to Use a Sixth-Order Function? Even Higher-Order Functions for Parsing
or: Why would anyone ever want to use a sixth-order function?
Chris Okasaki
Journal of Functional Programming 8(2):195–199, March 1998
DOI: 10.1017/S0956796898003001
Links: Publisher page, Paid-for access through Edinburgh University Library