在研究简单类型的 Lambda 微积分时发现了哪些奇怪的方程式

Question

我正在学习简单类型的 Lambda 微积分，但我对这些方程式感到困惑。

我想知道它们叫什么以及它们是如何工作的。

感谢您的帮助！

（图片取自https://softwarefoundations.cis.upenn.edu/current/plf-current/Stlc.html）

Answer 1

它们通常被称为演绎规则，typing rule，或者通常称为推理规则。由于 Gentzen 在自然演绎中的使用，推理栏的符号是 AFAIK。

确切的解释取决于您所描述的系统，但总体思路是“顶部的东西 imply/allow 底部的东西”。在这个特定的例子中，它看起来并不那么正式，但如果你以前见过这种东西就足够了。有关人们通常编写的类型理论的更正式的“语义”，请参阅 here。

在你的具体情况下，我会将规则翻译为：

• 当 v2 是一个值时，lambda 应用程序 (\x : T2 . t1) v2 缩减为 t1，t1 中的 x 被 v2 替代. （这是 Beta 减少）
• 当t1减少到t1'时，那么应用程序t1 t2减少到t1' t2。
• 当v1为一个值时，t2缩减为t2'，则应用v1 t2缩减为v1 t2'。

所以在这种情况下，它们实际上不是类型规则，而是评估（归约）工作方式的规则。