Abstract Datatypes for Real Numbers in Type Theory

Martín Hötzel Escardó, Alexander Simpson

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We propose an abstract datatype for a closed interval of real numbers to type theory, providing a representation-independent approach to programming with real numbers. The abstract datatype requires only function types and a natural numbers type for its formulation, and so can be added to any type theory that extends Gödel’s System T. Our main result establishes that programming with the abstract datatype is equivalent in power to programming intensionally with representations of real numbers. We also consider representing arbitrary real numbers using a mantissa-exponent representation in which the mantissa is taken from the abstract interval.
Original languageEnglish
Title of host publicationRewriting and Typed Lambda Calculi
Subtitle of host publicationJoint International Conference, RTA-TLCA 2014, Held as Part of the Vienna Summer of Logic, VSL 2014, Vienna, Austria, July 14-17, 2014. Proceedings
PublisherSpringer International Publishing
Number of pages16
ISBN (Electronic)978-3-319-08918-8
ISBN (Print)978-3-319-08917-1
Publication statusPublished - 2014

Cite this