替代引理类型

Question

tapl（第549页）提出以下引理，以证明系统f型系统的健全性：

替换引理类型：

$ e，x，\ delta \ vdash t：t \意味着e，[x \ mapsto s] \ delta \ vdash [x \ mapsto s] t：[x \ mapsto s] t $

t-tapp case的证明：

$ e，x，\ delta \ vdash t [a]：[y \ mapsto a] t $

和规则t-tapp我们有：

$ e，x，\ delta \ vdash t：\ lambda y。 t $

所以通过归纳假设：

$ e，[x \ mapsto s] \ delta \ vdash [x \ mapsto s] t：\ lambda y. [x \ mapsto s] t $

所以应用T-TAPP规则我们有：

$ e，[x \ mapsto s] \ delta \ vdash [x \ mapsto s] t [a]：[y \ mapsto a] [x \ mapsto s] t $

但是，我应该需要 $ [y \ mapsto a] [x \ mapsto s] t= [x \ mapsto s] [y \ mapsto a] t $

我认为我可以假设 $ a，s $ 不能包含 $ y $ 。

但是，如果 $ a $ 包含 $ x $ ？然后这些类型不合格。

假设 $ t $ 包含 $ y $ 。然后，LHS类型叶子 $ x $ 在结果中，而RHS类型不会留下任何。

其他来源

您可以在以下讲义笔记。但这种情况似乎是立竿见影的。

Answer 1

替换引理仅在替换的情况下替换是良好的： $ s $ 只能包含 $ E $ 。在t-tapp的应用中， $ y $ 是一个新的变量，不存在于 $ e，x，\ delta中$ 。特别是 $ y \ ne x $ ， $ y \ notin s $ 和 $ y \投入$ 。

有几种方法可以模拟变量名称和重命名。

• 阴影允许另一个粘合剂内的粘合剂使用相同的名称（例如 $ \ lambda x。\ lambda x。m $ ），然后是外部名称是隐藏（阴影）在内部构造中（任何 $ x $ $ m $ 指的是内部 $ x $ ）。如果要引用外部变量（例如，可能遇到测试β还原），则需要首先执行显式alpha转换以重命名其中一个变量。
• 隐式重命名始终使用表达式任何两个粘合剂的不同名称（所以你永远不会写入 $ \ color {红色} {\ lambda x。\ lambda x。m} $ 甚至 $ \ color {红色} {（\ lambda x。m）（\ lambda x。m）} $ ，但 $ \ lambda y。\ lambda x。m $ 和 $（\ lambda xm）（\ lambda y。[x \ mapstoy] m ）$ ），并且在重复术语的任何减少后存在隐式alpha转换。这被称为 Barendregt公约。
• 大多数文献声称使用Barendregt公约，但实际上使用了一个中间公约，其中嵌套绑定者从不使用相同的名称，但是彼此不重叠的粘合剂可以使用相同的名称，并且存在隐式alpha发生阴影后立即转换步骤。例如 $（\ lambda xm）（\ lambda xm）$ 以书面允许，但元符号 $ x $ 在两个子模板中应该表示两个不同的变量。据我所知，TAPL使用本公约。

环境是一个粘合剂的集合，所以没有阴影，它无法多次定义相同的变量名（否 $ \ gamma_1，x，\ gamma_2，x，\ gamma_3 $ ）。

现在，让我们看看T-TAPP的应用。前提是 $ \ gamma'\ vdash t'：\ forall y. t'$ 其中 $ \ gamma'=（ e，[x \ mapsto s] \ delta）$ ， $ t'= [x \ mapsto s] t $ 和 $ t'= [x \ mapsto s] t $ 。从这个前提，你可以得出结论 $$ \ gamma'\ vdash \ lambda t'[a']：[y \ mapsto a'] t'$$ 对于任何良好的<跨度类=“math-container”> $ a'$ 。您想证明 $ \ gamma'\ vdash [x \ mapsto s]（t [a]）：[x \ mapsto s] [y \ mapsto a] t $ 。所以拍摄 $ a'= [x \ mapsto s] $ 。结论是 $$ \ gamma'\ vdash（[x \ mapsto s] t）[[x \ mapsto s] a]：[mapsto [x \ mapsto s] a] [x \ mapsto s] t $$ 这确实如此 $$ \ gamma'\ vdash [x \ mapsto s]（t [a]）：[x \ mapsto s] [y \ mapsto a] t $$ 由于<跨越类=“math-container”> $ y \ ne x $ 和 $ y \ notin s $ 。