Seminari del Dipartimento


Logica e Informatica Teorica

The Yoneda Reduction of Polymorphic Types

Paolo Pistone

29-01-2021 - 15:00
modalitĂ  telematica


We explore a family of type isomorphisms in System F whose validity corresponds, semantically, to some form of the Yoneda isomorphism from category theory. These isomorphisms hold under theories of equivalence stronger than βη-equivalence, like those induced by parametricity and dinaturality. Based on such isomorphisms, we investigate a rewriting over types, that we call Yoneda reduction, which can be used to eliminate quantifiers from a polymorphic type, replacing them with a combination of monomorphic type constructors. We then demonstrate some applications of this rewriting to problems like counting the inhabitants of a type or characterizing program equivalence in somefragments of System F.

Per partecipare al Seminario cliccare sul seguente Link:
org: PEDICINI Marco

Copyright© 2014 Dipartimento di Matematica e Fisica