类型正确和错误类型的 lambda 术语
Well typed and ill typed lambda terms
我一直在努力理解应用 lambda 演算。到目前为止，我已经了解了类型推断的工作原理。但是我无法理解说一个术语类型正确或类型错误的含义是什么，然后我如何确定给定术语是类型正确还是错误类型。
例如，考虑定义为 λx[(x x)] 的 lambda 项 tw。如何判断它是一个类型正确还是错误类型的术语？
如果我们谈论 Simply Typed Lambda Calculus 与一些额外的常量和基本类型（即应用 lambda 演算），那么术语 λx:σ. (x x) 是合式的，但类型错误。
'Well-formed' 表示句法正确，即会被 STLC 的解析器接受。 'Ill-typed' 表示类型检查器不会进一步传递它。
类型检查器根据 typing rules 进行工作，通常表示为多个类型判断（每个句法形式一个类型方案）。
让我证明一下，您提供的字词确实有误。
根据规则 (3) [参见类型规则 link]，λx:σ. (x x) 必须具有一般形式 σ -> τ 的类型（因为它 是 一个功能，或更正确的抽象）。但这意味着主体 (x x) 必须具有某种类型 τ（假设 x : σ）。这与用自然语言表达的规则 (3) 基本相同。所以，现在我们需要弄清楚函数体的类型，它是一个应用程序。
现在，应用程序 (4) 的规则说如果我们有这样的表达式 (e1 e2)，那么 e1 必须是某个函数 e1 : α -> β 和 e2 : α必须是正确类型的参数。让我们将此规则应用于正文 (x x) 的表达式。 (1) x : α -> β 和 (2) x : α。由于 STLC 中的一项只能有一种类型，因此我们有一个等式：α -> β = α。
但是我们无法将这两种类型统一在一起，因为 α 是 α -> β 的子部分。这就是为什么这不会进行类型检查。
顺便说一句，STLC 的主要要点之一是禁止自我应用（如 (x x)），因为它阻止使用（无类型的）lambda 演算作为逻辑，因为可以执行非- 使用自应用程序终止计算（参见示例 Y-combinator）。
我一直在努力理解应用 lambda 演算。到目前为止，我已经了解了类型推断的工作原理。但是我无法理解说一个术语类型正确或类型错误的含义是什么，然后我如何确定给定术语是类型正确还是错误类型。
例如，考虑定义为 λx[(x x)] 的 lambda 项 tw。如何判断它是一个类型正确还是错误类型的术语？
如果我们谈论 Simply Typed Lambda Calculus 与一些额外的常量和基本类型（即应用 lambda 演算），那么术语 λx:σ. (x x) 是合式的，但类型错误。
'Well-formed' 表示句法正确，即会被 STLC 的解析器接受。 'Ill-typed' 表示类型检查器不会进一步传递它。 类型检查器根据 typing rules 进行工作，通常表示为多个类型判断（每个句法形式一个类型方案）。
让我证明一下，您提供的字词确实有误。
根据规则 (3) [参见类型规则 link]，λx:σ. (x x) 必须具有一般形式 σ -> τ 的类型（因为它 是 一个功能，或更正确的抽象）。但这意味着主体 (x x) 必须具有某种类型 τ（假设 x : σ）。这与用自然语言表达的规则 (3) 基本相同。所以，现在我们需要弄清楚函数体的类型，它是一个应用程序。
现在，应用程序 (4) 的规则说如果我们有这样的表达式 (e1 e2)，那么 e1 必须是某个函数 e1 : α -> β 和 e2 : α必须是正确类型的参数。让我们将此规则应用于正文 (x x) 的表达式。 (1) x : α -> β 和 (2) x : α。由于 STLC 中的一项只能有一种类型，因此我们有一个等式：α -> β = α。
但是我们无法将这两种类型统一在一起，因为 α 是 α -> β 的子部分。这就是为什么这不会进行类型检查。
顺便说一句，STLC 的主要要点之一是禁止自我应用（如 (x x)），因为它阻止使用（无类型的）lambda 演算作为逻辑，因为可以执行非- 使用自应用程序终止计算（参见示例 Y-combinator）。