Beyond 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
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 |
|
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(…) 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(…) Java 8, 2014 The most recent Collections classes, with heavy use of generics. Link: Documentation from Oracle |
|
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 |
|
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 |