Totality for Mixed Inductive and Coinductive types

This paper introduces an ML / Haskell like programming language with nested inductive and coinductive algebraic datatypes called chariot. Functions are defined by arbitrary recursive definitions and can thus lead to non-termination and other "bad" behaviour. chariot comes with a totality checker that tags such bad definitions. Such a totality checker is mandatory in the context of proof assistants based on type theory like Agda. Proving correctness of this checker is far from trivial, and relies on - an interpretation of types as parity games due to L. Santocanale, - an interpretation of definitions as strategies for those games, - the Lee, Jones and Ben Amram's size-change principle, used to check that those strategies are "total". This paper develops the first two points, the last step being the subject of an upcoming paper. A prototype has been implemented and can be used to experiment with the resulting totality checker. It gives a practical argument in favor of this principle.