Comparing Functional Paradigms for Exact Real-number Computation

Andrej Bauer, Martín Escardó, Alexander Simpson

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)

Abstract

We compare the definability of total functionals over the reals in two functional-programming approaches to exact real-number computation: the extensional approach, in which one has an abstract datatype of real numbers; and the intensional approach, in which one encodes real numbers using ordinary datatypes. We show that the type hierarchies coincide up to second-order types, and we relate this fact to an analogous comparison of type hierarchies over the external and internal real numbers in Dana Scott’s category of equilogical spaces. We do not know whether similar coincidences hold at third-order types. However, we relate this question to a purely topological conjecture about the Kleene-Kreisel continuous functionals over the natural numbers. Finally, although it is known that, in the extensional approach, parallel primitives are necessary for programming total first-order functions, we demonstrate that, in the intensional approach, such primitives are not needed for second-order types and below.
Original languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication29th International Colloquium, ICALP 2002 Málaga, Spain, July 8–13, 2002 Proceedings
PublisherSpringer-Verlag GmbH
Pages488-500
Number of pages13
ISBN (Print)978-3-540-43864-9
DOIs
Publication statusPublished - 2002

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
Volume2380
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'Comparing Functional Paradigms for Exact Real-number Computation'. Together they form a unique fingerprint.

Cite this