chapter c

I was reading Benjamin Pierce's dissertation, and learning some intriguing things about intersection types in the context of Church-style typing.  I summarize the parts of this I comprehended so far.

I discuss the perhaps surprising fact that union and intersection types are quite actively used and promoted for languages like TypeScript, also OO languages like Scala.  I also try to explain briefly a counterexample to type preservation with union types, which you can find at the start of Section 2 of Barbanera and Dezani-Ciancaglini's paper "Intersection and Union Types: Syntax and Semantics", where it is attributed to Benjamin Pierce.

I sketch the argument that pure lambda terms in normal form are typable using intersection types.  This completes the argument started in the previous episode, that intersection types are complete for normalizing terms: normal forms are typable, and typing is preserved by beta-expansion.  Hence any normalizing term is typable (since it reduces to a normal form by definition, and from this normal form we can walk typing back to the term).

Type systems usually have the type preservation property: if a typable term beta-reduces, then the resulting term is still typable.  So typing is closed under beta-reduction.  With intersection typing, typing is also closed under beta-expansion, which is a critical step in showing that intersection typing is complete for normalizing terms: any normalizing term can be typed with intersection types (and simple function types).  

In a type system with intersection types, a term t that has type A and also has type B can be assigned the type 'A intersect B'.   This episode begins Chapter 12 of the podcast on intersection types.