Hostname: page-component-8448b6f56d-qsmjn Total loading time: 0 Render date: 2024-04-18T20:05:14.190Z Has data issue: false hasContentIssue false

Parametric polymorphism and operational equivalence

Published online by Cambridge University Press:  01 June 2000

ANDREW M. PITTS
Affiliation:
Cambridge University Computer Laboratory, Pembroke Street, Cambridge, CB2 3QG, UK

Abstract

Studies of the mathematical properties of impredicative polymorphic types have for the most part focused on the polymorphic lambda calculus of Girard–Reynolds, which is a calculus of total polymorphic functions. This paper considers polymorphic types from a functional programming perspective, where the partialness arising from the presence of fixpoint recursion complicates the nature of potentially infinite (‘lazy’) data types. An approach to Reynolds' notion of relational parametricity is developed that works directly on the syntax of a programming language, using a novel closure operator to relate operational behaviour to parametricity properties of types. Working with an extension of Plotkin's PCF with ∀-types, lazy lists and existential types, we show by example how the resulting logical relation can be used to prove properties of polymorphic types up to operational equivalence.

Type
Research Article
Copyright
2000 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)