TY - JOUR
T1 - Type classes for efficient exact real arithmetic in CoQ
AU - Krebbers, Robbert
AU - Spitters, Bas
PY - 2013/2/25
Y1 - 2013/2/25
N2 - Floating point operations are fast, but require continuous effort by the user to ensure correctness. This burden can be shifted to the machine by providing a library of exact analysis in which the computer handles the error estimates. Previously, we provided a fast implementation of the exact real numbers in the Coq proof assistant. This implementation incorporates various optimizations to speed up the basic operations of O'Connor's implementation by a 100 times. We implemented these optimizations in a modular way using type classes to define an abstract specification of the underlying dense set from which the real numbers are built. This abstraction does not hurt the efficiency. This article is a substantially expanded version of (Krebbers/Spitters, Calculemus 2011) in which the implementation is extended in the various ways. First, we implement and verify the sine and cosine function. Secondly, we create an additional implementation of the dense set based on Coq's fast rational numbers. Thirdly, we extend the hierarchy to capture order on undecidable structures, while it was limited to decidable structures before. This hierarchy, based on type classes, allows us to share theory on the naturals, integers, rationals, dyadics, and reals in a convenient way. Finally, we obtain another dramatic speed-up by avoiding evaluation of termination proofs at runtime.
AB - Floating point operations are fast, but require continuous effort by the user to ensure correctness. This burden can be shifted to the machine by providing a library of exact analysis in which the computer handles the error estimates. Previously, we provided a fast implementation of the exact real numbers in the Coq proof assistant. This implementation incorporates various optimizations to speed up the basic operations of O'Connor's implementation by a 100 times. We implemented these optimizations in a modular way using type classes to define an abstract specification of the underlying dense set from which the real numbers are built. This abstraction does not hurt the efficiency. This article is a substantially expanded version of (Krebbers/Spitters, Calculemus 2011) in which the implementation is extended in the various ways. First, we implement and verify the sine and cosine function. Secondly, we create an additional implementation of the dense set based on Coq's fast rational numbers. Thirdly, we extend the hierarchy to capture order on undecidable structures, while it was limited to decidable structures before. This hierarchy, based on type classes, allows us to share theory on the naturals, integers, rationals, dyadics, and reals in a convenient way. Finally, we obtain another dramatic speed-up by avoiding evaluation of termination proofs at runtime.
KW - Coq
KW - Exact real arithmetic
KW - Type classes
KW - Type theory
KW - Verified computation
UR - http://www.scopus.com/inward/record.url?scp=84874024971&partnerID=8YFLogxK
U2 - 10.2168/LMCS-9(1:01)2013
DO - 10.2168/LMCS-9(1:01)2013
M3 - Journal article
AN - SCOPUS:84874024971
SN - 1860-5974
VL - 9
JO - Logical Methods in Computer Science
JF - Logical Methods in Computer Science
IS - 1
ER -