课程主页：

https://www.edx.org/course/compilers

课程视频：

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

备注：

图片均来自于课件。

这部分回顾Cool的类型检查。

静态类型 vs 动态类型

  • 静态类型系统（在编译时刻）检测常见错误。

  • 但是某些正确的程序不被静态类型系统允许

    • 所以有些人主张动态类型检查。
    • 其他人想要更具表达力的静态类型检查。

  • 更具表达力的类型系统往往更复杂。

  • 对象的动态类型是创建它的“new C”表达式中使用的类C。

    • 动态类型是运行时概念。
    • 即使非静态类型的语言也具有动态类型的概念。

  • 表达式的静态类型捕获该表达式可能具有的所有动态类型。

    • 静态类型是编译时概念。

  • 稳定性定理：

    对于所有表达式$\mathrm{E}$

    在所有执行中，$\mathrm{E}$求值为编译器推断的类型的值。

  • Cool类型系统的稳定性定理：

  • 可以在类型$\mathrm{C}$的对象上使用的所有操作也可以在类型为$\mathrm{C}’$的对象上使用，其中$\mathrm{C’}\le \mathrm C$

    • 例如获取属性的值。
    • 或在对象上调用方法。

  • 子类仅添加属性或方法。

  • 可以重新定义方法，但类型相同。

例子

class A { ... }
class B inherits A {...}
class Main {
    x:A <- new A;
    ...
    x <- new B;
    ...
}

分析：

x:A : x的静态类型是A
new A : x的动态类型是A
new B : x的动态类型是B

习题

第一，第二项正确。

Self_Type

例子

class Count {
    i : int <- 0;
    inc () : Count {
        {
            i <- i + 1;
            self;
        }
    };
};
  • 类Count包含一个计数器。
  • inc方法适用于任何子类。
  • 考虑Count的子类Stock
class Stock inherits Count { 
	name : String; -- name of item
};
  • 以及对Stock的如下用法
class Main {
    Stock a <- (new Stock).inc();
    ... a.name ...
};

上述用法会报错，因为inc返回的类型是Count，但是Count不包含属性name：

  • $\text{(new Stock).inc()}$具有动态类型$\text{Stock}$；

  • 因此如下语句是合法的

  • 但这不是很好的类型，因为$\mathrm{(new Stock).inc()}$的静态类型为$\mathrm{Count}$；

  • 类型检查器“丢失”类型信息

    • 这使得继承$\mathrm{inc}$毫无用处 ；
    • 因此，我们必须为每个子类重新定义$\mathrm{inc}$，并使用专门的返回类型 。

解决上述问题需要引入$\text{SELF_TYPE}$。

Self_Type

  • 我们将扩展类型系统

  • 注意到：

    • inc返回self；
    • 因此，返回值与“self”具有相同的类型；
    • 可以是Count或Count的任何子类型！

  • 引入关键字$\text{SELF_TYPE}$以用于此类函数的返回值

    • 我们还需要修改输入规则以处理$\text{SELF_TYPE}$

  • $\text{SELF_TYPE}$允许在继承inc时更改inc的返回类型

  • 修改inc的声明

  • 类型检查器现在可以证明：

  • 之前的程序现在类型正确。

  • 注意$\text{SELF_TYPE}$不是动态类型

    • 它也不是类名；
    • 它是静态类型；
    • 帮助类型检查器更好地跟踪类型；
    • 使类型检查器接受更正确的程序；

  • 简而言之，拥有$\text{SELF_TYPE}$可以提高类型系统的表达能力。

Self_Type操作

回忆之前的例子

class Count {
    i : int <- 0;
    inc () : Count {
        {
            i <- i + 1;
            self;
        }
    };
};

  • inc返回的对象的动态类型是什么？

    • 答案：“$\text{SELF_TYPE}$”的任意可能类型（Count或Count的任意子类），inc可以通过任何这些类来调用。

      class A inherits Count { } ; 
class B inherits Count { } ; 
class C inherits Count { } ;

  • 通常，如果在类C内部声明E的类型为$\text{SELF_TYPE}$，

    class C {
    E : SELF_TYPE
}

    则

  • 注意：$\text{SELF_TYPE}$的含义取决于它出现的位置

    • 用$\text{SELF_TYPE}_{\text{C}}$表示在类C中出现的$\text{SELF_TYPE}$

  • 所以建议如下规则

  • 上述规则产生如下重要结果：

    • 在类型检查中，始终可以用C安全替换$\mathrm{SELF\text{_}TYPE_C}$。

  • 这就建议了一种处理$\text{SELF_TYPE}$的方法：

    • 用C替换所有出现的$\mathrm{SELF\text{_}TYPE_C}$

  • 回顾类型上的操作

    • $\mathrm{T_1\le T_2}$表示$\mathrm{T_1}$是$\mathrm{T_2}$的子类型。
    • $\mathrm{lub(T_1,T_2)}$表示$\mathrm{T_1}$和$\mathrm{T_2}$的最小上界。

  • 扩展这些操作以处理$\text{SELF_TYPE}$

    • 令$\mathrm{T}$和$\mathrm{T’}$是除了$\text{SELF_TYPE}$以外的类型
      • 那么$\text {SELF_} \text {TYPE}_{\text{C}} \leq \text {SELF_} \text {TYPE}_{\text{C}}$
        • 在Cool中，我们永远不会比较来自不同类的$\text{SELF_TYPE}$。
      • $\text{SELF_TYPE}_{\text{C}}\le \text{T}$，如果$\mathrm{C\le T}$
        • $\text {SELF_} \text {TYPE}_{\text{C}}$可以是$\mathrm{C}$的任意子类型；
        • 这包含$\mathrm{C}$本身；
        • 因此，这是我们可以允许的最灵活的规则。
      • $\text{T}\le \text{SELF_TYPE}_{\text{C}}$永远错误
        • 注意$\text{SELF_TYPE}_{\text{C}}$表示$\text{C}$的任意子类型。
      • $\mathrm{T\le T’}$（根据之前的规则）
    • 令$\mathrm{T}$和$\mathrm{T’}$是除了$\text{SELF_TYPE}$以外的类型
      • $\mathrm{lub(SELF\text{_}TYPE_C, SELF\text{_}TYPE_C) = SELF\text{_}TYPE_C}$
      • $\mathrm{lub(SELF\text{_}TYPE_C, T) =\mathrm{lub(C,T)}}$
        • 这是最好的结果，因为$\text{SELF_TYPE}_{\text{C}}\le \text{C}$
      • $\mathrm{lub( T,SELF\text{_}TYPE_C) =\mathrm{lub(C,T)}}$
      • $\text{lub(T,T’)}$和之前定义相同

习题

第三，第四项正确。

Self _Type的用处

SELF_TYPE并不能出现在所有类型都能出现的位置：

  • $\text{class T inherits T’ {…}}$

    • 那么$\mathrm{T,T’}$不能是$\text{SELF_TYPE}$

  • $\mathrm{x:T}$

    • 属性$\mathrm x$
    • $\mathrm T$可以是$\text{SELF_TYPE}$

  • $\text{let x : T in E}$

    • $\mathrm T$可以是$\text{SELF_TYPE}$

  • $\text{new T}$

    • $\text{T}$可以是$\text{SELF_TYPE}$
    • 创建与$\text{self}$动态类型的相同对象

  • $\mathrm{m@T(E_1,\ldots, E_n)}$

    • $\mathrm T$不能是$\text{SELF_TYPE}$

  • $\mathrm{m(x:T):T’}\{\ldots\}$

    • 只有$\text{T’}$可以是$\text{SELF_TYPE}$

    • 如果$\text{T}$是$\text{SELF_TYPE}$会有什么问题？

    • 考虑其对应的分派$\mathrm{e.m(e’), e’:T_0}$，那么

      注意这一步是错误的。

    • 在下例中，$\text{T}$是$\text{SELF_TYPE}$，但是$\text{A}$不包含属性$\text{b}$

      class A { comp(x : SELF_TYPE) : Bool {...}; }; 
class B inherits A {
    b : int;
    comp(x : SELF_TYPE) : Bool { ... x.b ... }; }; 
    ...
    let x : A <- new B in ... x.comp(new A); #A没有属性b
    ...
}

习题

第三项错误。

Self_Type检查

  • $\text{SELF_TYPE}$的含义取决于所在的类：

    上述符号表示，在给定变量类型环境O和方法签名M的情况下，在C中出现的表达式e具有静态类型T。

  • 下一步是使用$\text{SELF_TYPE}$设计类型规则。

  • 大多数规则保持不变

    • 但要使用$\le $和$\text{lub}$

  • 回忆分派的规则

  • 如果方法的返回类型为$\text{SELF_TYPE}$，则分派的类型为分派表达式的类型：

  • 形式参数不能为$\text{SELF_TYPE}$

  • 实际参数可以是$\text{SELF_TYPE}$

    • 扩展的$\le $关系处理这种情况。

  • 分派表达式的类型$\mathrm{T}_0$可以为$\text{SELF_TYPE}$

    • 哪个类用于查找$\mathrm{f}$的声明？
    • 答案：使用分派所出现的类是安全的。

  • 回顾静态分派的原始规则

  • 如果该方法的返回类型为$\text{SELF_TYPE}$，则我们有：

  • 使用$\text{SELF_TYPE}$有两个新规则

  • 扩展的$\le $和$\text{lub}$操作可以完成很多工作。

  • $\text{SELF_TYPE}$只能在少数地方使用。

  • $\text{SELF_TYPE}$的使用总是指当前类的任何子类型

    • 例外是分派的类型检查，$\text{SELF_TYPE}$的方法返回类型可能与当前类无关。

  • $\text{SELF_TYPE}$是一个研究思路

    • 它增加了类型系统的表现力。

  • $\text{SELF_TYPE}$本身并不那么重要

    • 除了项目中。

  • 相反，$\text{SELF_TYPE}$旨在说明类型检查可能非常微妙。

  • 在实际中，类型系统的复杂性与其表现力之间应该保持平衡。

习题

第二项，第四项正确。

错误恢复

  • 与解析一样，从类型错误中恢复也很重要。

  • 这里检测错误发生的位置比解析容易

    • 没有理由跳过部分代码。

  • 问题：

    • 将什么类型分配给没有合法类型的表达式？
    • 此类型将影响封闭表达式的类型。

  • 一个方法是将类型Object分配给错误类型的表达式

    • 错误：

      • $\mathrm x$未定义；
      • $+$应用于Object；
      • 不正确的赋值。

    • 这是一个可行的解决方案，但有级联错误。

  • 引入一种新的$\text{No_type}$类型，用来不良类型的表达式一起使用。

  • 对所有类型$\text{C}$定义$\text { No_type} \leq \mathrm{C}$

  • 每个操作都对$\text{No_type}$有定义

    • 结果为$\text{No_type}$

  • 对于之前的例子，此时错误为

    • $\mathrm x$未定义

  • 一个“真正的”编译器将使用No_type之类的东西

  • 但是，存在一些实现问题

    • 类层次结构不再是一棵树

  • Object解决方案在课程项目效果中很好。

习题

选择第二项。