Iowa Type Theory Commute
Iowa Type Theory Commute
Aaron Stump
Compositional termination checking with sized types
18 minutes Posted Mar 30, 2020 at 7:00 pm.
0:00
18:37
Download MP3
Show notes

Discussion of a compositional method of termination checking using so-called sized types.  Datatypes are indexed by sizes, and recursive calls can only be made on data of strictly smaller size than the data as input to the recursion.  Since the method is type-based, it is compositional: we can break out helper functions from a recursive function and not upset the termination checker.  A readable and interesting tutorial on the subject is here.