Axiomatic Reals and Certified Efficient Exact Real Computation

Michal Konečný, Sewon Park, Holger Thies

Research output: Chapter in Book/Published conference outputConference publication


We introduce a new axiomatization of the constructive real numbers in a dependent type theory.
Our main motivation is to provide a sound and simple to use backend for verifying algorithms for exact real number computation and the extraction of efficient certified programs from our proofs.
We prove the soundness of our formalization with regards to the standard realizability interpretation from computable analysis.
We further show how to relate our theory to a classical formalization of the reals to allow certain non-computational parts of correctness proofs to be non-constructive.
We demonstrate the feasibility of our theory by implementing it in the Coq proof assistant and present several natural examples.
From the examples we can automatically extract Haskell programs that use the exact real computation framework AERN for efficiently performing exact operations on real numbers.
In experiments, the extracted programs behave similarly to native implementations in AERN in terms of running time.
Original languageEnglish
Title of host publicationLogic, Language, Information, and Computation - 27th International Workshop, WoLLIC 2021, Proceedings
Subtitle of host publication 27th International Workshop, WoLLIC 2021
EditorsAlexandra Silva, Renata Wassermann, Ruy de Queiroz
Place of PublicationBerlin / Heidelberg
Number of pages17
ISBN (Print)978-3-030-88852-7
Publication statusPublished - 17 Nov 2021
Event27th International Workshop, WoLLIC 2021 -
Duration: 5 Oct 20218 Oct 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13038 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference27th International Workshop, WoLLIC 2021

Bibliographical note

© Springer Nature B.V. 2021. The final publication is available at Springer via

Funding Information:
Holger Thies is supported by JSPS KAKENHI Grant Number JP20K19744. Sewon Park is supported by the National Research Foundation of Korea (NRF) grants funded by the Korea government (No. NRF-2016K1A3A7A03950702, NRF-2017R1E1A1A03071032 (MSIT) & No. NRF-2017R1D1A1B05031658 (MOE)).


  • Constructive real numbers
  • Exact real number computation
  • Formal proofs
  • Program extraction


Dive into the research topics of 'Axiomatic Reals and Certified Efficient Exact Real Computation'. Together they form a unique fingerprint.

Cite this