论文标题
关系λ-calculus的语义（扩展版）
Semantics of a Relational λ-Calculus (Extended Version)
论文作者
论文摘要
我们使用适合关系和功能性编程的构造扩展了λ-calculus：非确定性选择，新鲜的可变引入和表达式统一。为了能够统一表达并仍然获得汇合理论，我们脱离了相关方法，例如λprolog，因为我们没有尝试解决高阶统一。取而代之的是，抽象装饰有一个位置，该位置可以直观地理解为其内存地址，我们强加了一个简单的连贯性不变性：在同一位置中的抽象必须相等。这使我们能够制定一个仅执行一阶统一并且不需要进行强有力评估的汇合小步操作语义（在lambdas下方）。我们研究系统的简单键入版本。此外，提出了计算的典型语义，并显示还原相对于示意性语义而言是合理的。
We extend the λ-calculus with constructs suitable for relational and functional-logic programming: non-deterministic choice, fresh variable introduction, and unification of expressions. In order to be able to unify λ-expressions and still obtain a confluent theory, we depart from related approaches, such as λProlog, in that we do not attempt to solve higher-order unification. Instead, abstractions are decorated with a location, which intuitively may be understood as its memory address, and we impose a simple coherence invariant: abstractions in the same location must be equal. This allows us to formulate a confluent small-step operational semantics which only performs first-order unification and does not require strong evaluation (below lambdas). We study a simply typed version of the system. Moreover, a denotational semantics for the calculus is proposed and reduction is shown to be sound with respect to the denotational semantics.
