×

Semantics, specification logic, and Hoare logic of exact real computation. (English) Zbl 07872364

Summary: We propose a simple imperative programming language, ERC, that features arbitrary real numbers as primitive data type, exactly. Equipped with a denotational semantics, ERC provides a formal programming language-theoretic foundation to the algorithmic processing of real numbers. In order to capture multi-valuedness, which is well-known to be essential to real number computation, we use a Plotkin powerdomain and make our programming language semantics computable and complete: all and only real functions computable in computable analysis can be realized in ERC. The base programming language supports real arithmetic as well as implicit limits; expansions support additional primitive operations (such as a user-defined exponential function). By restricting integers to Presburger arithmetic and real coercion to the “precision” embedding \(\mathbb{Z}\ni p\mapsto 2^p\in\mathbb{R}\), we arrive at a first-order theory which we prove to be decidable and model-complete. Based on said logic as specification language for preconditions and postconditions, we extend Hoare logic to a sound (w.r.t. the denotational semantics) and expressive system for deriving correct total correctness specifications. Various examples demonstrate the practicality and convenience of our language and the extended Hoare logic.

MSC:

03B70 Logic in computer science
68-XX Computer science

References:

[1] Park, Brauße, Collins, Kim, Konečný, Lee, Müller, Neumann, Preining, and Ziegler Vol. 20:2
[2] Samson Abramsky and Achim Jung. Domain theory. In Handbook of Logic in Computer Science, volume III, pages 1-168. Oxford University Press, Oxford, United Kingdom, 1995.
[3] Krzysztof R Apt and Ernst-Rüdiger Olderog. Fifty years of hoare’s logic. Formal Aspects of Computing, 31(6):751-807, 2019. doi:10.1007/s00165-019-00501-3. · Zbl 1427.68008 · doi:10.1007/s00165-019-00501-3
[4] Jeremy Avigad and Yimu Yin. Quantifier elimination for the reals with a predicate for the powers of two. Theoretical Computer Science, 370(1-3):48-59, 2007. doi:10.1016/j.tcs.2006.10.005. · Zbl 1113.03027 · doi:10.1016/j.tcs.2006.10.005
[5] Hans Boehm and Robert Cartwright. Exact Real Arithmetic: Formulating real numbers as functions. In Research Topics in Functional Programming, pages 43-64. Addison-Wesley Longman Publishing Co., Inc., USA, 1990.
[6] Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag Berlin Heidelberg, Berlin, Heidelberg, 1997. · Zbl 1087.68568
[7] Lenore Blum, Felipe Cucker, Michael Shub, and Steven Smale. Complexity and real computation. Springer, New York, NY, 1998. doi:10.1007/978-1-4612-0701-6. · doi:10.1007/978-1-4612-0701-6
[8] Alexis Bés. A survey of arithmetical definability. Soc. Math. Belgique, A tribute to Maurice Boffa:1-54, 2002. · Zbl 1013.03071
[9] Sylvie Boldo, Jean-Christophe Filliâtre, and Guillaume Melquiond. Combining Coq and Gappa for certifying floating-point programs. In Jacques Carette, Lucas Dixon, Claudio Sacerdoti Coen, and Stephen M. Watt, editors, Intelligent Computer Mathematics, pages 59-74, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. doi:10.1007/978-3-642-02614-0_10. · Zbl 1247.68232 · doi:10.1007/978-3-642-02614-0_10
[10] Vasco Brattka and Peter Hertling. Feasible real random access machines. Journal of Complexity, 14(4):490-526, 1998. doi:10.1006/jcom.1998.0488. · Zbl 0913.68099 · doi:10.1006/jcom.1998.0488
[11] Jens Blanck. cdar -Reals based on Centred Dyadic Approximations. https://github.com/ jensblanck/cdar.
[12] Sylvie Boldo and Guillaume Melquiond. Flocq: A unified library for proving floating-point algorithms in Coq. In 2011 IEEE 20th Symposium on Computer Arithmetic, pages 243-252. IEEE, 2011. doi:10.1109/ARITH.2011.40. · doi:10.1109/ARITH.2011.40
[13] Franz Brausse, Norbert Müller, and Robert Rettinger. Intensionality and multi-valued limits. In Proc. 15th International Conference on Computability and Complexity in Analysis (CCA), page 11, 2018.
[14] Andrej Bauer, Sewon Park, and Alex Simpson. Clerical. https://github.com/andrejbauer/ clerical, 2017.
[15] Andrej Bauer, Sewon Park, and Alex Simpson. Clerical: an imperative language for verified real-number computation. In Proc. 17th International Conference on Computability and Complexity in Analysis (CCA), pages 22-23, 2020. 17:48 Park, Brauße, Collins, Kim, Konečný, Lee, Müller, Neumann, Preining, and Ziegler Vol. 20:2
[16] Vasco Brattka. Computable selection in analysis. In Proc. of the Workshop on Computability and Complexity in Analysis, Informatik Berichte, FernUniversit at Hagen, volume 190, pages 125-138, 1995.
[17] Vasco Brattka. The emperor’s new recursiveness: The epigraph of the exponential function in two models of computability. In Masami Ito and Teruo Imaoka, editors, Words, Languages & Combinatorics III, pages 63-72, Singapore, 2003. World Scientific Publishing. ICWLC 2000, Kyoto, Japan, March 14-18, 2000. doi:10.1142/9789812704979_0005. · doi:10.1142/9789812704979_0005
[18] Stephen Brookes and Kathryn Van Stone. Monads and comonads in intensional semantics. Technical report, Carnegie-Mellon University Pittsburgh PA Department of Computer Science, 1993. [CGC + 20] Pieter Collins, Luca Geretti, Alberto Casagrande, Ivan Zapreev, and Sanja Zivanovic. Ariadne. http://www.ariadne-cps.org/, 2005-20.
[19] Stephen A Cook. Soundness and completeness of an axiom system for program verification. SIAM Journal on Computing, 7(1):70-90, 1978. doi:10.1137/0207005. · Zbl 0374.68009 · doi:10.1137/0207005
[20] Pietro Di Gianantonio and Abbas Edalat. A language for differentiable functions. In Frank Pfenning, editor, Foundations of Software Science and Computation Structures, pages 337-352, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. doi:10.1007/978-3-642-37075-5_22. · Zbl 1260.68073 · doi:10.1007/978-3-642-37075-5_22
[21] Lou van den Dries. The field of reals with a predicate for the powers of two. Manuscripta mathematica, 54:187-195, 1985. doi:10.1007/BF01171706. · Zbl 0631.03020 · doi:10.1007/BF01171706
[22] Abbas Edalat and Martın Hötzel Escardó. Integration in real PCF. Information and Computation, 160(1-2):128-166, 2000. · Zbl 1005.03035
[23] Martín Hötzel Escardó and Alex Simpson. Abstract datatypes for real numbers in type theory. In Gilles Dowek, editor, Rewriting and Typed Lambda Calculi, pages 208-223, Cham, 2014. Springer International Publishing. doi:10.1007/978-3-319-08918-8_15. · Zbl 1416.68036 · doi:10.1007/978-3-319-08918-8_15
[24] Martín Hötzel Escardó. PCF extended with real numbers. Theoretical Computer Science, 162:79-115, 1996. doi:10.1016/0304-3975(95)00250-2. · Zbl 0871.68034 · doi:10.1016/0304-3975(95)00250-2
[25] Jean-Christophe Filliâtre and Andrei Paskevich. Why3 -Where programs meet provers. In Matthias Felleisen and Philippa Gardner, editors, Programming Languages and Systems, pages 125-128, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. doi:10.1007/978-3-642-37036-6_8. · Zbl 1435.68366 · doi:10.1007/978-3-642-37036-6_8
[26] Peter Hertling. Topological complexity with continuous operations. Journal of Complexity, 12:315-338, 1996. doi:10.1006/jcom.1996.0021. · Zbl 0862.68060 · doi:10.1006/jcom.1996.0021
[27] Peter Hertling. A real number structure that is effectively categorical. Mathematical Logic Quarterly, 45(2):147-182, 1999. doi:10.1002/malq.19990450202. · Zbl 0946.03050 · doi:10.1002/malq.19990450202
[28] C. A. R. Hoare. An axiomatic basis for computer programming. Commun. ACM, 12(10):576-580, oct 1969. doi:10.1145/363235.363259. · Zbl 0179.23105 · doi:10.1145/363235.363259
[29] Bruce M. Kapron and Steven A. Cook. A new characterization of type-2 feasibility. SIAM Journal on Computing, 25(1):117-132, 1996. doi:10.1137/S0097539794263452. · Zbl 0843.68028 · doi:10.1137/S0097539794263452
[30] Akitoshi Kawamura and Stephen Cook. Complexity theory for operators in analysis. ACM Trans. Comput. Theory, 4(2):5:1-5:24, May 2012. doi:10.1145/2189778.2189780. · Zbl 1322.68083 · doi:10.1145/2189778.2189780
[31] KMP + 08] Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee-Keng Yap. Classroom examples of robustness problems in geometric computations. Computational Geometry, 40(1):61-78, 2008. doi:10.1016/j.comgeo.2007.06.003. · Zbl 1135.65311 · doi:10.1016/j.comgeo.2007.06.003
[32] Ker-I Ko. Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkhäuser, Boston, 1991. · Zbl 0791.03019
[33] Michal Konečný. Verified exact real limit computation. In Proc. 15th International Conference on Computability and Complexity in Analysis (CCA), pages 9-10, 2018.
[34] Michal Konečný, Florian Steinberg, and Holger Thies. Computable analysis for verified exact real computation. In Nitin Saxena and Sunil Simon, editors, 40th IARCS Annual Conference on 17:49 Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, December 14-18, 2020, BITS Pilani, K K Birla Goa Campus, Goa, India (Virtual Conference), volume 182 of LIPIcs, pages 50:1-50:18. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.FSTTCS.2020.50. · doi:10.4230/LIPIcs.FSTTCS.2020.50
[35] Akitoshi Kawamura, Florian Steinberg, and Martin Ziegler. Complexity theory of (functions on) compact metric spaces. In Proc. 31st Ann. Symposium on Logic in Computer Science, pages 837-846, New York, NY, United States, 2016. ACM/IEEE, Association for Computing Machinery. doi:10.1145/2933575.2935311. · Zbl 1401.03086 · doi:10.1145/2933575.2935311
[36] KTD + 13] Michal Konečný, Walid Taha, Jan Duracz, Adam Duracz, and Aaron Ames. Enclosing the behavior of a hybrid system up to and beyond a zeno point. In 2013 IEEE 1st International Conference on Cyber-Physical Systems, Networks, and Applications (CPSNA), pages 120-125, 2013. doi:10.1109/CPSNA.2013.6614258. · doi:10.1109/CPSNA.2013.6614258
[37] Branimir Lambov. RealLib: An efficient implementation of exact real arithmetic. Mathematical Structures in Computer Science, 17:81-98, 2007. doi:10.1017/S0960129506005822. · Zbl 1112.65137 · doi:10.1017/S0960129506005822
[38] Horst Luckhardt. A fundamental effect in computations on real numbers. Theoretical Computer Science, 5(3):321-324, 1977. doi:10.1016/0304-3975(77)90048-2. · Zbl 0374.02018 · doi:10.1016/0304-3975(77)90048-2
[39] David Marker. Model Theory of Fields. Lecture Notes in Logic. Cambridge University Press, Cambridge, United Kingdom, 2017. doi:10.1017/9781316716991. · doi:10.1017/9781316716991
[40] Guillaume Melquiond. Proving bounds on real-valued functions with computations. In Alessandro Armando, Peter Baumgartner, and Gilles Dowek, editors, Automated Reasoning, pages 2-17, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. doi:10.1007/978-3-540-71070-7_2. · Zbl 1165.68464 · doi:10.1007/978-3-540-71070-7_2
[41] Dragoslav S. Mitrinović. Analytic Inequalities, volume 165 of Die Grundlehren der mathematischen Wissenschaften. Springer, 1970. doi:10.1007/978-3-642-99970-3. · Zbl 0199.38101 · doi:10.1007/978-3-642-99970-3
[42] J. Raymundo Marcial-Romero and Martín H. Escardó. Semantics of a sequential language for exact real-number computation. Theoretical Computer Science, 379(1):120-141, 2007. doi: 10.1016/j.tcs.2007.01.021. · Zbl 1118.68083 · doi:10.1016/j.tcs.2007.01.021
[43] Norbert Th. Müller. The iRRAM: Exact arithmetic in C++. In Jens Blanck, Vasco Brattka, and Peter Hertling, editors, Computability and Complexity in Analysis, volume 2064 of Lecture Notes in Computer Science, pages 222-252, Berlin, 2001. Springer. 4th International Workshop, CCA 2000, Swansea, UK, September 2000. doi:10.1007/3-540-45335-0_14. · Zbl 0985.65523 · doi:10.1007/3-540-45335-0_14
[44] Aleksandar Nanevski, Greg Morrisett, and Lars Birkedal. Polymorphism and separation in hoare type theory. In Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, pages 62-73, 2006. doi:10.1145/1160074.1159812. · Zbl 1321.68351 · doi:10.1145/1160074.1159812
[45] Sewon Park. Continuous Abstract Data Types for Verified Computation. PhD thesis, KAIST, School of Computing, Daejeon, South Korea, 2021.
[46] Marian B. Pour-El and J. Ian Richards. Computability in Analysis and Physics. Perspectives in Mathematical Logic. Springer, Berlin, 1989. doi:10.1017/9781316717325. · doi:10.1017/9781316717325
[47] Gordon D. Plotkin. A powerdomain construction. SIAM Journal on Computing, 5(3):452-487, 1976. doi:10.1137/0205035. · Zbl 0355.68015 · doi:10.1137/0205035
[48] Gordon D. Plotkin. LCF considered as a programming language. Theoretical computer science, 5(3):223-255, 1977. doi:10.1016/0304-3975(77)90044-5. · Zbl 0369.68006 · doi:10.1016/0304-3975(77)90044-5
[49] Franco P. Preparata and Michael Ian Shamos. Computational Geometry. Monographs in Computer Science. Springer, 1985. doi:10.1007/978-1-4612-1098-6. · Zbl 0759.68037 · doi:10.1007/978-1-4612-1098-6
[50] William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical recipes: The art of scientific computing. Cambridge university press, Cambridge, United Kingdom, 3 edition, 2007. 17:50 Park, Brauße, Collins, Kim, Konečný, Lee, Müller, Neumann, Preining, and Ziegler Vol. 20:2
[51] John C Reynolds. Separation logic: A logic for shared mutable data structures. In Proceedings 17th Annual IEEE Symposium on Logic in Computer Science, pages 55-74. IEEE, 2002. doi: 10.1109/LICS.2002.1029817. · doi:10.1109/LICS.2002.1029817
[52] John C Reynolds. Theories of programming languages. Cambridge University Press, Cambridge, United Kingdom, 2009. doi:10.1017/CBO9780511626364. · Zbl 1184.68157 · doi:10.1017/CBO9780511626364
[53] Daniel Richardson. Some undecidable problems involving elementary functions of a real variable. Journal of Symbolic Logic, 33(4):514-520, 1968. doi:10.2307/2271358. · Zbl 0175.27404 · doi:10.2307/2271358
[54] Julia Robinson. The undecidability of algebraic rings and fields. Proceedings of the American Mathematical Society, 10:950-957, 1959. doi:10.2307/2033628. · Zbl 0100.01501 · doi:10.2307/2033628
[55] SAL + 18] Joonhyung Shin, Namjo Ahn, Seungwoo Lee, Chansu Park, and Martin Ziegler. Towards ten-sor calculus in exact real computation. 21st Japan-Korea Joint Workshop on Algorithms and Computation, August 2018.
[56] Matthias Schröder. Effectivity in spaces with admissible multirepresentations. Mathematical Logic Quarterly, 48(S1):78-90, 2002. · Zbl 1032.03039
[57] Matthias Schröder. Spaces allowing type-2 complexity theory revisited. Mathematical Logic Quarterly, 50(4,5):443-459, 2004. doi:10.1002/malq.200310111. · Zbl 1058.03069 · doi:10.1002/malq.200310111
[58] Ernst Specker. Der Satz vom Maximum in der rekursiven Analysis. In A. Heyting, editor, Constructivity in mathematics, Studies in Logic and the Foundations of Mathematics, pages 254-265, Amsterdam, 1959. North-Holland. Proc. Colloq., Amsterdam, Aug. 26-31, 1957. · Zbl 0088.01702
[59] Florian Steinberg, Laurent Thery, and Holger Thies. Computable analysis and notions of continuity in Coq. Logical Methods in Computer Science, Volume 17, Issue 2, May 2021. doi:10.23638/ LMCS-17(2:16)2021. · Zbl 1535.03232 · doi:10.23638/LMCS-17(2:16)2021
[60] Dongseong Seon and Martin Ziegler. Computing Haar averages. In Proc. 15th International Conference on Computability and Complexity in Analysis (CCA), pages 43-44, 2018.
[61] Alan M. Turing. On computable numbers, with an application to the “Entscheidungsproblem”. Proceedings of the London Mathematical Society, 42(2):230-265, 1937. · JFM 62.1059.03
[62] Alan M. Turing. Rounding off errors in matrix processes. Quarterly Journal of Mechanical and Applied Math, 1(1):287-308, 1948. · Zbl 0033.28501
[63] J.V. Tucker and J.I. Zucker. Computation by ’While’ programs on topological partial algebras. Theoretical Computer Science, 219:379-420, 1999. doi:10.1016/S0304-3975(98)00297-7. · Zbl 0916.68046 · doi:10.1016/S0304-3975(98)00297-7
[64] J.V. Tucker and J.I. Zucker. Abstract versus concrete computation on metric partial algebras. ACM Transactions on Computational Logic, 5(4):611-668, 2004. doi:10.1145/1024922.1024924. · Zbl 1367.68102 · doi:10.1145/1024922.1024924
[65] Klaus Weihrauch. Computable Analysis. Springer, Berlin, 2000. doi:10.1007/ 978-3-642-56999-9. · Zbl 0956.68056 · doi:10.1007/978-3-642-56999-9
[66] Klaus Weihrauch. Computational complexity on computable metric spaces. Mathematical Logic Quarterly, 49(1):3-21, 2003. doi:10.1002/malq.200310001. · Zbl 1018.03049 · doi:10.1002/malq.200310001
[67] YYD + 10] Jihun Yu, Chee Yap, Zilin Du, Sylvain Pion, and Hervé Brönnimann. The design of Core 2: A library for exact numeric computation in geometry and algebra. In Komei Fukuda, Joris van der Hoeven, Michael Joswig, and Nobuki Takayama, editors, Mathematical Soft-ware -ICMS 2010, pages 121-141, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. doi:10.1007/978-3-642-15582-6_24. · Zbl 1295.65147 · doi:10.1007/978-3-642-15582-6_24
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.