We introduce an extension of first-order logic that comes equipped with additional predicates for reasoning about an abstract state. Sequents in the logic comprise a main formula together with pre- and postconditions in the style of Hoare logic, and the axioms and rules of the logic ensure that the assertions about the state compose in the correct way. The main result of the paper is a realizability interpretation of our logic that extracts programs into a mixed functional/imperative language. All programs expressible in this language act on the state in a sequential manner, and we make this intuition precise by interpreting them in a semantic metatheory using the state monad. Our basic framework is very general, and our intention is that it can be instantiated and extended in a variety of different ways. We outline in detail one such extension: A monadic version of Heyting arithmetic with a wellfounded while rule, and conclude by outlining several other directions for future work.
翻译:我们引入了一阶逻辑的延伸,该逻辑的扩展配有用于抽象状态推理的更多前提。 逻辑中的序列包含一个主要公式,加上Hoare逻辑风格的预设和后设条件,逻辑的逻辑法和规则确保关于国家的主张以正确的方式表达。 论文的主要结果是对我们的逻辑的可真实性解释,它将程序引出一种混合功能/障碍语言。 以这种语言表达的所有程序都能够以顺序方式对状态进行表达,我们通过用州元律来解释这些直觉,我们用语义的元词来精确地解释这些直觉。 我们的基本框架非常笼统,我们的意图是它可以以不同的方式即时和扩展。 我们详细概述了一个这样的延伸:一个有理、有理、有理、有理有据的元的算术版本,最后通过概述未来工作的其他方向来结束。