Proof theory provides a foundation for studying and reasoning about programming languages, most directly based on the well-known Curry-Howard isomorphism between intuitionistic logic and the typed lambda-calculus. More recently, a correspondence between intuitionistic linear logic and the session-typed pi-calculus has been discovered. In this paper, we establish an extension of the latter correspondence for a fragment of substructural logic with least and greatest fixed points. We describe the computational interpretation of the resulting infinitary proof system as session-typed processes, and provide an effectively decidable local criterion to recognize mutually recursive processes corresponding to valid circular proofs as introduced by Fortier and Santocanale. We show that our algorithm imposes a stricter requirement than Fortier and Santocanale's guard condition, but is local and compositional and therefore more suitable as the basis for a programming language.
翻译:证据理论为学习和推理编程语言提供了基础,最直接基于著名的Curry-Howard直觉逻辑和键入的羊羔计算法之间的形态论。最近发现了直觉线性逻辑和会话型的二次计算法之间的对应关系。在本文中,我们为分解的固定点最小和最大的亚结构逻辑确定了后一种对应关系的延伸。我们将由此产生的非结构性证明系统的计算解释描述为会话型程序,并提供可有效确定的地方标准,以承认与Fortier和Santocanale引入的有效循环证据相对应的相互重复过程。我们表明我们的算法比Fortier和Santocanale的守卫条件规定了更严格的要求,但是一种局部和构成性的,因此更适合作为编程语言的基础。