From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/8071 Path: news.gmane.org!not-for-mail From: Uday S Reddy Newsgroups: gmane.science.mathematics.categories Subject: Logical relations and parametricity (Reynolds memorial paper) Date: Tue, 8 Apr 2014 17:19:47 +0100 Message-ID: Reply-To: Uday S Reddy NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1397086048 11876 80.91.229.3 (9 Apr 2014 23:27:28 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 9 Apr 2014 23:27:28 +0000 (UTC) Cc: claudio.hermida@gmail.com, Edmund Robinson To: types-list , categories@mlist.mta.ca Original-X-From: majordomo@mlist.mta.ca Thu Apr 10 01:27:23 2014 Return-path: Envelope-to: gsmc-categories@m.gmane.org Original-Received: from smtp3.mta.ca ([138.73.1.186]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WY1tr-0000qG-DL for gsmc-categories@m.gmane.org; Thu, 10 Apr 2014 01:27:23 +0200 Original-Received: from mlist.mta.ca ([138.73.1.63]:51240) by smtp3.mta.ca with esmtp (Exim 4.80) (envelope-from ) id 1WY1su-0007IE-2V; Wed, 09 Apr 2014 20:26:24 -0300 Original-Received: from majordomo by mlist.mta.ca with local (Exim 4.71) (envelope-from ) id 1WY1ss-000263-Aq for categories-list@mlist.mta.ca; Wed, 09 Apr 2014 20:26:22 -0300 Precedence: bulk Xref: news.gmane.org gmane.science.mathematics.categories:8071 Archived-At: 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 =E2=80=93=20 A Reynolds Programme for Category Theory and Programming Languages (Dedicated to the memory of John C. Reynolds, 1935=E2=80=932013) Abstract In his seminal paper on =E2=80=9CTypes, Abstraction and Parametric Poly= morphism,=E2=80=9D John Reynolds called for homomorphisms to be generalized from functions= to relations. He reasoned that such a generalization would allow type-base= d =E2=80=9Cabstraction=E2=80=9D (representation independence, information= hiding, naturality or parametricity) to be captured in a mathematical theory, while accoun= ting 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 f= or a renewed attempt at addressing the problem. Electronic Notes in Theoretical Computer Science Volume 303, 28 March 2014, Pages 149=E2=80=93180 Proceedings of the Workshop on Algebra, Coalgebra and Topology (WACT 20= 13) The ENTCS version may be found here:=20 http://www.sciencedirect.com/science/article/pii/S1571066114000346 and a preprint here http://www.cs.bham.ac.uk/~udr/papers/logical-relations-and-parametr= icity.pdf --- Part of our intent in writing this article has been to regenerate inter= est in the problem of parametricity, which some people perceive as having d= ied down after sustained efforts in the 90's, and to provide clean definiti= ons for new entrants to the area. So, if you have wondered what parametric= ity is all about, we hope you will find the answers here. We continue to work on parametricity ourselves and we would be very gla= d to hear from other people who would like to get involved. If you have wor= k 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/ ]