Hostname: page-component-74656f9884-7drmj Total loading time: 0 Render date: 2026-11-05T12:22:22.014Z 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
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
2000 Cambridge University Press