Podcasts Technology Iowa Type Theory Commute Normalization in type theory: where it is needed, and where not

Normalization in type theory: where it is needed, and where not

Published: March 6, 2020, 9 p.m.

b'

Normalization (every term reaches a normal form via some reduction sequence) is needed essentially in type theory due to the Curry-Howard isomorphism: diverging programs become unsound proofs.\\xa0 Traditionally, type theorists have also desired normalization or even termination (every term reaches a normal form no matter what reduction sequence is explored in a nondeterministic operational semantics) for conversion checking.\\xa0 This is the process of confirming that types are equivalent during type checking, which, due to dependent types, can require checking program equivalence.\\xa0 The latter is usually restricted to just beta-equivalence (where beta-reduction is substitution of argument for input variable when applying a function), because richer notions of program equivalence are usually undecidable.\\xa0 I have a mini-rant in this episode explaining why this usual requirement of normalization for conversion checking is not sensible.

Also I note that you can find the episodes of the podcast organized by chapter on my web page.

'