[TYPES] Logical relations and parametricity (Reynolds memorial paper)

[Uday S Reddy]

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