Lecture 6: Higher Types

Title slide

Slides : Recording

Digging deeper into types for parametric polymorphism, this lecture reviewed Hindley-Milner systems with let-polymorphism and type inference before moving on to System F with more explicit interaction between types and terms. Exercises explore how familiar datatypes can be encoded in System F purely as polymorphic functions.

Links: Slides from Lecture 6; Recording of Lecture 6

1. Do This

There is a slide towards the end of the material on System 4 titled “Exercises for the Reader”. Do those exercises yourself, writing out your answers to check types and reductions. If you have questions then send me mail or ask on Piazza.

Links: APL on Piazza; Ian.Stark@ed.ac.uk

2. Write This

The outline draft for your written coursework assignment. Aim to have by Monday’s lecture either your “Hello, World!” screenshot in the Example section or a paragraph for each of three references in the Resources section.

Link: Coursework

  • Pick a strongly-typed programming language then try writing (and typechecking) two sorters, two testers, and code to testManySorters.

  • Find out how { Java, Scala, C#, Haskell, … } handles type { variance, bounds, quantification, kinds }.


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

This is a “Functional Pearl”: just five pages long, it walks you through an answer to the question in the title.

Links: Publisher page; Prepaid library access with EASE login

Cover image from Journal of Functional Programming

Leave a Reply

%d bloggers like this: