Skip to main content

A logic for abstract data types as existential types

Poll, Erik and Zwanenburg, Jan (1999) A logic for abstract data types as existential types. In: Girard, J.Y., ed. Typed Lambda Calculi and Applications 4th International Conference. Lecture Notes in Computer Science . Springer, Berlin, Germany, pp. 310-324. ISBN 978-3-540-65763-7. E-ISBN 978-3-540-48959-7. (doi:10.1007/3-540-48959-2_22) (KAR id:16484)

PDF
Language: English
Download (362kB) Preview
[thumbnail of a_logic_for_abstract_data_poll.pdf]
Preview
This file may not be suitable for users of assistive technology.
Request an accessible format
Postscript
Language: English
Download (197kB) Preview
[thumbnail of a_logic_for_abstract_data_poll.ps]
Preview
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL
http://dx.doi.org/10.1007/3-540-48959-2_22

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 [PA93] 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.

Item Type: Book section
DOI/Identification number: 10.1007/3-540-48959-2_22
Additional information: Proceedings Paper
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science
Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: F.D. Zabet
Date Deposited: 23 Apr 2009 11:46 UTC
Last Modified: 16 Feb 2021 12:27 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/16484 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year