Relational Parametricity for Computational Effects

Alexander Simpson, Rasmus Mogelberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution


According to Strachey, a polymorphic program is parametric if it applies a uniform algorithm independently of the type instantiations at which it is applied. The notion of relational parametricity, introduced by Reynolds, is one possible mathematical formulation of this idea. Relational parametricity provides a powerful tool for establishing data abstraction properties, proving equivalences of datatypes, and establishing equalities of programs. Such properties have been well studied in a pure functional setting. Many programs, however, exhibit computational effects. In this paper, we develop a framework for extending the notion of relational parametricity to languages with effects.
Original languageEnglish
Title of host publicationProceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages10
ISBN (Print)0-7695-2908-9
Publication statusPublished - Jul 2007

Cite this