Types, Abstraction and Parametric Polymorphism

The work

AuthorsJohn C. Reynolds
Typeinproceedings
Year1983
Citekeyreynolds1983types

Where it appeared

Published inInformation Processing 83
PublisherNorth-Holland
Pages513--523

Identifiers

OpenAlexW326743114

Abstract

We explore the thesis that type structure is a syntactic discipline for maintaining levels of abstraction. Traditionally, this view has been formalized algebraically, but the algebraic approach fails to encompass higher-order functions. For this purpose, it is necessary to generalize homomorphic functions to relations; the result is an "abstraction" theorem that is applicable to the typed lambda calculus and various extensions, including user-defined types. Finally, we consider polymorphic functions, and show that the abstraction theorem captures Strachey's concept of parametric, as opposed to ad hoc, polymorphism.

A copy is held

pdf, 674.3 kB. Not published — it may be under copyright. The facts and links here are.

How it got here

How it got hereimport via bibtex
Added2026-08-09 00:00 UTC
Approved bya person 2026-08-23 14:12 UTC

Filed under

what-a-program-means

Cite it as

@inproceedings{reynolds1983types,
  title        = {Types, Abstraction and Parametric Polymorphism},
  author       = {John C. Reynolds},
  year         = {1983},
  booktitle    = {Information Processing 83},
  pages        = {513--523},
  publisher    = {North-Holland},
}

This record lives at https://refs.drheap.org/reynolds1983types/ and will keep doing so.