| I'm studying programming language semantics and papers like these are quite valuable in understanding type systems of real languages, see also Featherweight Java[0] and Featherweight Go[1]. At first it looks like a lot to take in, but when you start with far simpler type systems like typed arithmetic expressions and simply-typed lambda calculus, you see the same definitions and metatheorems (properties about the type system) appear over and over again (including in this paper). In particular, the pieces you see repeated are: - the terms and types of the language - the values (a subset of terms) - the evaluation relation, telling you how you go from one term to the next - the typing relation, telling you how you build well-typed terms and what their types are - Progress states that if you have a well-typed term, it either is a value or it can take one step of evaluation - Preservation states you that if you have a well-typed term of type T and it takes a step of evaluation, the resulting term still has type T And we have the slogan, safety = progress + preservation. I should also note that past a certain level of complexity of type system, you definitely would want to use a theorem prover such as Coq to formally verify and automate easy cases. The proofs themselves are actually quite boring (which is a good thing!). [0] https://www.cis.upenn.edu/~bcpierce/papers/fj-toplas.pdf [1] https://arxiv.org/pdf/2005.11710.pdf |
It was surprising to me to discover how logical and mathematical Haskell’s type system is.
It’s the kind of topic that I’d probably not ever have thought about if I didn’t do a degree, but has had an impact on how I view other areas of computer science.