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:
https://teams.microsoft.com/dl/launcher/launcher.html?url=%2F_%23%2Fl%2Fmeetup-join%2F19%3Aab2bf8031ff84a91b69ceb7411a05aee%40thread.tacv2%2F1609941039368%3Fcontext%3D%257b%2522Tid%2522%253a%2522ffb4df68-f464-458c-a546-00fb3af66f6a%2522%252c%2522Oid%2522%253a%25226ce28123-51c5-448d-8320-d7e9bb9d7a05%2522%257d%26anon%3Dtrue&type=meetup-join&deeplinkId=e314d365-281c-48e0-a959-fc2bf4296805&directDl=true&msLaunch=true&enableMobilePage=true&suppressPrompt=true
org: PEDICINI Marco

Copyright© 2014 Dipartimento di Matematica e Fisica