论文标题
galois连接呼叫和呼叫的名字
Galois connecting call-by-value and call-by-name
论文作者
论文摘要
我们建立了一个通用框架，用于推理逐个呼叫和逐个名称之间的关系。 在具有计算效果的语言中，程序的呼叫和呼叫执行通常具有不同但相关的可观察行为。例如，如果程序可能会发出差异，但没有效果，那么每当终止逐次呼叫时，它会以相同的结果终止逐个呼叫。我们提出了一种陈述和证明此类属性的技术。关键要素是Levy的逐个通话值演算，我们将其用作推理评估订单的框架。我们表明，在某些条件下，逐个呼叫和逐个名称的呼叫和逐名翻译在某些条件下对计算效应具有可观察的行为，我们可以确定。然后，我们使用这个事实来构建类型的呼叫和呼叫呼叫解释之间的地图，并确定效果的进一步属性，这些效果暗示这些地图形成了Galois连接。这些属性具有某些计算效应（例如差异），但没有其他效果（例如可变状态）。这引起了一个一般的推理原则，该原则将逐个呼叫和按名称呼叫。我们将推理原理应用于示例计算效应，包括差异和非确定性。
We establish a general framework for reasoning about the relationship between call-by-value and call-by-name. In languages with computational effects, call-by-value and call-by-name executions of programs often have different, but related, observable behaviours. For example, if a program might diverge but otherwise has no effects, then whenever it terminates under call-by-value, it terminates with the same result under call-by-name. We propose a technique for stating and proving properties like these. The key ingredient is Levy's call-by-push-value calculus, which we use as a framework for reasoning about evaluation orders. We show that the call-by-value and call-by-name translations of expressions into call-by-push-value have related observable behaviour under certain conditions on computational effects, which we identify. We then use this fact to construct maps between the call-by-value and call-by-name interpretations of types, and identify further properties of effects that imply these maps form a Galois connection. These properties hold for some computational effects (such as divergence), but not others (such as mutable state). This gives rise to a general reasoning principle that relates call-by-value and call-by-name. We apply the reasoning principle to example computational effects including divergence and nondeterminism.
