© University of Kent - Contact | Feedback | Legal | FOI | Cookies
A logic for abstract data types as existential types
Erik Poll and Jan Zwanenburg
In Typed Lambda Calculi and Applications (TLCA'99), LNCS, pages 182-196. Spinger-Verlag, April 1999.Abstract
The second-order lambda calculus allows an elegant formalisation of abstract data types (ADT's) using existential types. Plotkin and Abadi's logic for parametricity then provides the useful proof principle of simulation for ADT's, which can be used to show equivalence of data representations.
However, we show that this logic is not sufficient for reasoning about specifications of ADT's, and we present an extension of the logic that does provide the proof principles for ADT's that we want.
Download publication 72 kbytes
Bibtex Record
@inproceedings{644,
author = {Erik Poll and Jan Zwanenburg},
title = {A Logic for Abstract Data Types as Existential Types},
month = {April},
year = {1999},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1999/644},
booktitle = {Typed Lambda Calculi and Applications (TLCA'99)},
publisher = {Spinger-Verlag},
refereed = {yes},
series = {LNCS},
}