Aaron Steven White

Plotkin (Theoretical Computer Science 1, 1975; pp 125-159). 'Call-by-Name, Call-by-Value and the λ-Calculus' introduces the λ_v (call-by-value λ-calculus) and develops standardisation theorems giving correspondence with ISWIM and the SECD machine. Continuation technique to translate between CBV and CBN via mutual simulations. Operational equality (contextual equivalence) studied throughout. Foundation of operational semantics for functional languages.

Aaron Steven White

Reynolds (IFIP Information Processing 83, North-Holland, pp 513-523). 'Types, Abstraction and Parametric Polymorphism' formalises types as relations to capture parametric polymorphism. Key results: Identity Extension Lemma (an identity relation extends to identity on built types) and the Abstraction Theorem (semantics maps related environments into related values, by structural induction). Foundational for parametricity / free theorems (Wadler 1989, Voigtländer 2009) and the relational reading …

Aaron Steven White

Milner (J. Computer & System Sciences 17, 1978; pp 348-375). 'A Theory of Type Polymorphism in Programming' formalises ML's polymorphic type discipline: type variables, generalisation at let-bindings, and instantiation at use-sites. Presents a type-checking algorithm and proves semantic soundness ('well-typed programs do not go wrong'). Left open the question of automatic type inference, which Damas-Milner (POPL 1982) Algorithm W later supplied. The original ML type-system paper.

Aaron Steven White

Martin-Löf (Bibliopolis, Naples 1984; ISBN 978-88-7088-105-7). 'Intuitionistic Type Theory' notes by Giovanni Sambin of Padova lectures (June 1980). Introduces dependent type theory with Π (cartesian product of a family of sets), Σ (disjoint union of a family), W (well-orderings), I (identity types), universes, and the propositions-as-types correspondence. Foundation of dependent type theory and the conceptual basis of HoTT, Coq, Agda, Idris.

Aaron Steven White

Hindley (Trans. Amer. Math. Soc. 146, December 1969, pp 29-60). 'The Principal Type-Scheme of an Object in Combinatory Logic' establishes that every typable object in combinatory logic has a unique most-general (principal) type-scheme. Builds on Curry-Feys functional-character ('type-scheme') notion. Defines simultaneous unification of type-schemes, proves the principal-type theorem via a constructive procedure. Direct ancestor of Hindley-Milner type inference for ML.

Aaron Steven White

Girard (Thèse d'État, Université Paris VII, 1972). 'Interprétation fonctionnelle et élimination des coupures de l'arithmétique d'ordre supérieur' introduces System F (the polymorphic λ-calculus, here 'F' or 'système d'ordre 2'). §I extensional vs algorithmic viewpoints on functions. §II functional systems (syntactic study): types as classifying objects (a:σ, λx.a : σ→τ), polymorphism via type-quantified functions. Proves cut-elimination (strong normalisation) for higher-order arithmetic via the…

Aaron Steven White

Dybjer (TYPES 1996, LNCS 1158, pp 120-134). 'Internal Type Theory' introduces categories with families (CwF) as a categorical model of dependent type theory that internalises Martin-Löf's framework. Variants of Cartmell's contextual categories. §1 CwF definition; §2 how to formalise basic categorical notions internally; §3 coherence problem; §4 normal-forms model solving coherence. Foundational for the categorical semantics of dependent types subsequent work (HoTT models) builds on.