Projects per year
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 language | English |
---|---|
Title of host publication | Automata, Languages and Programming |
Subtitle of host publication | 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8–13, 2002 Proceedings |
Publisher | Springer-Verlag GmbH |
Pages | 488-500 |
Number of pages | 13 |
ISBN (Print) | 978-3-540-43864-9 |
DOIs | |
Publication status | Published - 2002 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer Berlin / Heidelberg |
Volume | 2380 |
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.Projects
- 1 Finished