一句话：提出精确实数计算语言 ERC，给出可计算完备的指称语义、可判定规约逻辑及可靠且表达力强的霍尔逻辑。
论文为精确处理任意实数的算法计算建立语言理论基础。作者提出命令式语言 ERC，将任意实数作为原始数据类型，并给出指称语义；为刻画实数计算固有的多值性，语义采用 Plotkin 幂域，证明其可计算且完备：可计算分析中可计算的实函数恰可由 ERC 实现。语言支持实数算术与隐式极限，并可通过扩展加入用户定义指数函数等原语。将整数限制为 Presburger 算术、实数嵌入限制为精度嵌入 p ↦ 2^p 后，所得一阶规约逻辑可判定且模型完全。基于该逻辑，作者将霍尔逻辑扩展为相对于指称语义可靠且表达力充分的总正确性验证系统，并用多个例子展示实用性。
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.
@article{paperbot2751,
title = {Semantics, Specification Logic, and Hoare Logic of Exact Real Computation},
author = {Sewon Park and Franz Brauße and Pieter Collins and SunYoung Kim and Michal Konečný and Gyesik Lee and Norbert Müller and Eike Neumann and Norbert Preining and Martin Ziegler},
journal = {Logical Methods in Computer Science},
volume = {Volume 20, Issue 2},
year = {2024},
doi = {10.46298/lmcs-20(2:17)2024}
}