# 类型、符号和作用域

我们首先了解三个关键性的概念：类型、符号和作用域。这三者会作为 `TypedTree` 的标注 (`annot`) 出现。

## 类型

这里的“类型”是指语义层面的，与语法树上的 `TypeLit` 有区别。 在框架中，对应于 `Type.scala` 中的类。 具体分为以下几种：

* 内置基本类型 `BaseType`：包括 `IntType`, `BoolType`, `StringType`, `NullType` 和 `VoidType`。其中 `VoidType` 仅用于描述无返回值函数的返回值类型。此外，我们用 `NoType` 表示在类型推导过程中的错误。
* 类类型 `ClassType`：用户定义的类所对应的类型，形如 `class A`。
* 数组类型 `ArrayType`：其元素可以是任何类型，形如 `t[]`。
* 函数类型 `FunType`：函数/方法所具有的类型，形如 `(t1, t2, ..., tn) => t`，其中 `t1, t2, ..., tn` 为各参数的类型，`t` 为返回值类型。在原版的 Decaf 语言中，函数类型只是一种内部表示，用户无法在语法上写出来。

在类型之上，我们定义两种关系：**等价**关系 `===`（自然诱导出不等价关系 `!==`）和**子类型** (subtype) 关系 `<:`，分别对应于代码中的 `===` 和 `<=` 方法。 类型等价的定义是自然的：

* 针对内置基本类型 `t`： `t === t`
* 若 `A == B`，则 `class A === class B`
* 若 `t1 === t2`，则 `t1[] === t2[]`
* 若 `s1 === t1, s2 === t2, ..., sn === tn, s === t`，则 `(s1, s2, ..., sn) => s === (t1, t2, ..., tn) => t`

子类型关系的定义如下：

* 自反性：`t <: t`
* 传递性：若 `t1 <: t2` 且 `t2 <: t3`，则 `t1 <: t3`
* 类继承：若 `class A` 继承自 `class B`，则 `class A <: class B`
* 函数：若 `t1 <: s1, ..., tn <: sn` 且 `s <: t`，则 `(s1, s2, ..., sn) => s <: (t1, t2, ..., tn) => t`

以及特别规则：

* `NullType` 是任何类类型的子类型：`NullType <: class A`，其中 `A` 任取
* `NoType` 与任何类型互为子类型：`NoType <: t, t <: NoType`，其中 `t` 任取

类继承规则揭示了子类型这一关系在 OOP 中的直观含义：即子类和父类间存在着子类型关系。 而函数的子类型规则告诉我们，在调用某个函数时，参数允许向下转型（变得更“具体”，“多余”的成员在调用时被扔掉），而返回值可以向上转型（变得更“抽象”，把返回的“多余”的成员扔掉），例如：

```
class A extends B { }
A f(class B x) { ... }
```

我们可以这样调用 `f`：

```
class A a = new A();
class B b = f(a);
```

注意到 `(class B) => class A <: (class A) => class B`。

## 符号

对于每一个程序中出现的标识符，我们都用一个符号把它包装起来，并记录下这个符号的基本信息，如它的类型是什么，定义在哪个作用域等。 在框架中，对应于 `Symbol.scala` 中定义的类。 具体分为以下四种：

* 变量符号 `VarSymbol`：局部变量和函数的参数变量。
* 成员变量符号 `MemberVarSymbol`：类的成员变量。
* 方法符号 `MethodSymbol`：类中的成员和静态方法。
* 类符号 `ClassSymbol`：一个类。

其中，`MemberVarSymbol` 和 `MethodSymbol` 均继承自 `FieldSymbol`，表明它们都是类成员对应的符号。

## 作用域

Decaf 支持多种层次的作用域，对应于 `Scope.scala` 中定义的类：

* 全局作用域 `GlobalScope`：存放各类定义对应的类符号。
* 类作用域 `ClassScope`：存放该类所有成员的符号（变量符号和方法符号），有成员变量、成员方法和静态方法。
* 参数作用域 `FormalScope`：存放各参数对应的变量符号。
* 局部作用域 `LocalScope`：存放各局部变量对应的变量符号。局部作用域允许嵌套，if/while/for 语句都会打开一层新的局部作用域。

我们使用一个 `ScopeStack` 来维护作用域的层次结构，实际采用 `List` 作为其内部数据结构，其头部元素 (`head`) 是当前作用域。 它提供了在语义分析阶段常用的操作接口：

* `open`：打开一个作用域，如果是类作用域且该类存在父类，则递归地先打开父类的作用域。
* `lookup`：在当前作用域（及更外层的作用域，如有必要）查询某个符号。
* `declare`：在当前作用域中新定义一个符号。

作用域符号的访问规则主要有以下两条： 第一，内层作用域可以访问到外层作用域的所有符号。 第二，在局部作用域中声明的符号不能与任何该声明之前的外层作用域的符号重名。在类作用域中重新声明的符号需要满足重写规则。

这些规则需要利用上述提供的接口，在 `Namer` 中实现相应的检查处理。