Reduction-free normalisation for a polymorphic system
Thorsten Altenkirch, Martin O. Hofmann, Thomas Streicher · 2002
We give a semantical proof that every term of a combinator version of system F has a normal form. As the argument is entirely formalisable in an impredicative constructive type theory a reduction-free normalisation algorithm can be extracted from this. The proof is presented as the construction of a model of the calculus inside a category of presheaves. Its definition is given entirely in terms of the internal language.