propositional equality

In this episode, I introduce an important paper by Pujet and Tabareau, titled "Observational Equality: Now for Good", that develops earlier work of McBride, Swierstra, and Altenkirch (which I will cover in a later episode) on a new approach to making a type theory extensional.  The idea is to have equality types reduce, within the theory, to statements of extensional equality for the type of the values being equated.

In this episode, I discuss the basic distinguishing rule of Extensional Martin-Loef Type Theory, namely equality reflection.  This rule says that propositional equality implies definitional equality.  Algorithmically, it would imply that the type checker should do arbitrary proof search during type checking, to see if two expressions are definitionally equal.  This immediately gives us undecidability of type checking for the theory, at least as usually realized.

This episode begins a new chapter on extensionality in type theory, where we seek to equate terms in different ways based on their types.  The basic example is function extensionality, where we would like to equate functions from A to B if given equal inputs at type A, they produce equal outputs at type B.  With this definition, quicksort and mergesort are equal, even though their codes are not syntactically equivalent.  The episode begins by reviewing the distinction between definitional and propositional equality.

Also, I am still seeking your small donations ($5 or $10 would be awesome) to pay my podcast-hosting fees at Buzzsprout.  To donate, click here, and then under "Gift details" select "Search for additional options" and then search for Computer Science.  Select the Computer Science Development Fund, College of Liberal Arts and Sciences.  Then add gift instructions saying that this is to support the Iowa Type Theory Commute podcast of Aaron Stump.  Sorry it's that complicated.