paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Logic for exact real arithmetic

精确实数算术的逻辑
LMCS vol.Volume 17, Issue 22021匹配度 2/10 · 论文属于定理证明与证明提取,形式化验证/程序合成与用户兴趣有边缘交集,但不涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析,且研究对象是精确实数算术而非浮点分析。引用 1 inbox
Helmut Schwichtenberg, Franziskus Wiesnet
crossref: 2026-09-10

AI 速览

一句话:在 Minlog 中形式化共归纳实数流,并从证明中提取精确实数除法算法,再转译到 Haskell 运行。

本文延续 Berger、Miyamoto、Tsuiki 等人的工作,研究如何从形式证明中提取精确实数算术算法。实数被表示为带符号数字流,其性质用余归纳定义的谓词描述,相关证明也使用余归纳。作者在证明助手 Minlog 中构造并机器检查这些证明,依托一种可处理有穷与无穷数据的类型论,将证明的计算内容抽取为项。抽取结果给出实数除法算法;随后将项翻译到 Haskell 并进行运行实验,验证了提取算法的可行性。

问题
如何为以带符号数字流表示的实数建立形式化证明,并从中机械提取出精确实数除法等算术算法。
方法
使用余归纳定义实数流谓词,在 Minlog 中机器化证明,并从构造性类型论证明中提取计算内容为项。
评估
将提取项翻译为 Haskell 并运行实验,以检验所提取除法算法的行为与可行性。
原文摘要(Abstract)

Continuing earlier work of the first author with U. Berger, K. Miyamoto and H. Tsuiki, it is shown how a division algorithm for real numbers given as a stream of signed digits can be extracted from an appropriate formal proof. The property of being a real number represented as a stream is formulated by means of coinductively defined predicates, and formal proofs involve coinduction. The proof assistant Minlog is used to generate the formal proofs and extract their computational content as terms of the underlying theory, a form of type theory for finite or infinite data. Some experiments with running the extracted term are described, after its translation to Haskell.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot1321,
  title = {Logic for exact real arithmetic},
  author = {Helmut Schwichtenberg and Franziskus Wiesnet},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 2},
  year = {2021},
  doi = {10.23638/lmcs-17(2:7)2021}
}