POPL 2024
Sun 14 - Sat 20 January 2024 London, United Kingdom
Sat 20 Jan 2024 14:30 - 15:00 at Haslett Room - Session 3

GHC is, I believe, one of the only type inference engines in production use that wholeheartedly adopts Pottier and Rémy’s idea of “walk over the syntax tree to generate constraints; and separately solve those constraints”. The general idea is easy to understand, but the implementation experience has been a long, long road. In my talk I will cover:

Bidirectional type inference. Sometimes we know the expected type of an expression and want to check that the expression has that type; sometimes we don’t, and we want to infer the type. This works out very nicely.

Implication constraints: the key innovation that supports type abstraction, GADTs, and more.

Level numbers, and promotion. Again this is an old idea (due to Rémy and probably earlier), but it meshes very well with the generate-and-solve plan.

Evidence generation. In GHC we generate evidence for every constraint; sometimes this evidence is purely type-level, but sometimes (especially in the case of type classes) very much term level. Generate-and-solve works out nicely again: but with a bit of imperative update!

Quantified constraints in the source language. Remarkably, the same implication constraints make it easy to implement the apparently-rather-sophisticated language feature of “quantified constraints”.

Simon Peyton Jones, MA, MBCS, CEng, graduated from Trinity College Cambridge in 1980. After two years in industry, he spent seven years as a lecturer at University College London, and nine years as a professor at Glasgow University, before moving to Microsoft Research (Cambridge) in 1998. He became an Engineering Fellow at Epic Games in 2021.

His main research interest is in functional programming languages, their implementation, and their application. He has led a succession of research projects focused around the design and implementation of production-quality functional-language systems for both uniprocessors and parallel machines. He was a key contributor to the design of the now-standard functional language Haskell, and is the lead designer of the widely-used Glasgow Haskell Compiler (GHC). He has written two textbooks about the implementation of functional languages.

More generally, he is interested in language design, rich type systems, software component architectures, compiler technology, code generation, runtime systems, virtual machines, and garbage collection. He is particularly motivated by direct use of principled theory to practical language design and implementation – that’s one reason he loves functional programming so much.

Sat 20 Jan

Displayed time zone: London change

14:00 - 15:30
Session 3WITS at Haslett Room
On Modelling Heap Invariants for Type Systems in Dafny
James Noble Creative Research & Programming, Tobias Wrigstad Uppsala University
Solving constraints during type inference
Simon Peyton Jones Epic Games
Yaffle: A New Core for Idris 2
Edwin Brady University of St Andrews, UK