Logical relations and parametricity (Reynolds memorial paper)
We would like to announce a Reynolds memorial paper that has just been published in a volume edited by John Power and Cai Wingfield: Logical Relations and Parametricity – A Reynolds Programme for Category Theory and Programming Languages (Dedicated to the memory of John C. Reynolds, 1935–2013) Abstract In his seminal paper on “Types, Abstraction and Parametric Polymorphism,” John Reynolds called for homomorphisms to be generalized from functions to relations. He reasoned that such a generalization would allow type-based “abstraction” (representation independence, information hiding, naturality or parametricity) to be captured in a mathematical theory, while accounting for higher-order types. However, after 30 years of research, we do not yet know fully how to do such a generalization. In this article, we explain the problems in doing so, summarize the work carried out so far, and call for a renewed attempt at addressing the problem. Electronic Notes in Theoretical Computer Science Volume 303, 28 March 2014, Pages 149–180 Proceedings of the Workshop on Algebra, Coalgebra and Topology (WACT 2013) The ENTCS version may be found here: http://www.sciencedirect.com/science/article/pii/S1571066114000346 and a preprint here http://www.cs.bham.ac.uk/~udr/papers/logical-relations-and-parametricity.pdf --- Part of our intent in writing this article has been to regenerate interest in the problem of parametricity, which some people perceive as having died down after sustained efforts in the 90's, and to provide clean definitions for new entrants to the area. So, if you have wondered what parametricity is all about, we hope you will find the answers here. We continue to work on parametricity ourselves and we would be very glad to hear from other people who would like to get involved. If you have work that we have missed, please let us know about it as well. (We couldn't cite all the work we would have liked to cite due to page limitations.) Claudio Hermida Uday Reddy Edmund Robinson [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
participants (1)
-
Uday S Reddy