7.1 Overview - 编程语言语用论（第4版）

计算机硬件可以将内存中的比特以多种方式解释：指令，地址，字符，整数，变长浮点数。比特本身，没有类型：大多数计算机上的硬件无法跟踪解释内存内容的含义。汇编反映了类型的缺失：任何类型的操作都可以应用于任何位置的值。但是，高层语言总是将值与类型绑定，提供上下文信息和错误检查。

不正式的，类型系统包括：（1）定义类型的机制并将类型绑定到结构（2）type equivalence, type compatibility, type inference 的一系列规则。这些结构包括命名不变量，变量，record fields, 参数，或者 subroutines ，literal 不变量以及更加复杂的表达式。在多态性语言中的变量或者参数，引用或者指针关联的变量类型的区分更重要：给定名字可能在不同时间关联了不同类型的对象。

subroutines 有些语言中也被认为有类型，但不是所有的语言都这样定义。subroutine 在第一或者第二类时（可以作为参数传递，被函数返回，存储在变量中）需要有类型。在每种情况下的 subroutine 有一个类型，类型信息允许语言限制 subroutine 接口可以接受的值（特定数量和类型的参数）。在静态 scope 语言中不能动态创建 subroutine 引用，编译器总是确定 subroutine 唯一名称，可以确保正确调用 routine 而不必要使用 subroutine 类型的正式概念。

类型检查是对于程序遵守语言的类型兼容规则的处理过程。违反规则被称为 type clash。语言被称为强类型，如果语言实现可以禁止应用对象进行不允许的操作。语言被称为静态类型如果它是强类型和在编译期执行类型检查。在最严格的约束下，几乎没有语言是静态类型。实际上，静态类型经常形容大多数类型检查在编译器，少数类型检查在运行期的语言。

从 1970 中期开始，大多数新语言倾向于强类型（尽管不一定是静态类型）。有趣的是，尽管还存在漏洞，C 在不断加强自己成为强类型语言，漏洞包括 uion, 不标准的类型转换，可变参 subroutine，指针和数组的互操作性。C 的实现几乎不在运行期检查。

动态（运行期）类型检查可以看作延迟绑定的一种形式，倾向于在运行期间发现问题。静态类型语言更倾向于性能，动态类型语言更倾向于易用。Lisp 和 Smalltalk 是动态类型。大多数脚本语言是动态类型，有些（Python 和 Ruby）是强类型。有动态 scope 的语言也被称为动态类型（或者没有类型）：如果编译器无法确定名称引用的对象，通常也不能确定类型。

7.1.1 The Meaning of "Type"

每个程序员都有自己对于“类型”的理解，这个概念可以通过集中不同的方式规范化。三个最重要的是 denotational, structural, abstraction-based 的观点。从 denotational 观点，类型就是一族值。给定类型的值属于特定集合；一个对象有类型如果这个值在特定集合中。从 structural 的观点来看，类型要不是内建类型的集合（整数，字符，布尔，实数等，也称为 primitive or predefined 类型），或者复合类型（record， array，set 等）以及其组合类型。从 abstraction-based 观点来看，类型就是一个接口，包含了一些定义好的操作保持语义的一致性。对程序员和语言设计者来说，类型是上述观点的综合。

在 denotational 语义中，一族值称为域。类型就是域，表达式的含义就是代表表达式类型的域中的值。比如，有些域：整数简单熟悉，有些更复杂些。array 可以看作域中元素是映射【译者注：函数的原始定义】，每个元素从下标类型映射到某种类型的值。事实证明， denotational 语义可以将程序中的所有都绑定类型--即使有 side effect 的语句。赋值语句的意义就是更高层次的映射域，每个元素对应从一个存储到另一个。

从 denotational 观点看类型一件好处就是允许我们在集合上的数学操作中描述用户定义复合类型（record，arrays 等）。因为是基于数学对象的，denotational 类型的观点通常会忽略实现中的精确和字长有限的问题。这个限制没刚出现时那么严重了：检查类似算术溢出通常在语言的类型系统之外实现。这是运行时错误，但是这种错误不能称为 type clash。

当程序员定义枚举类型，可以将类型看作一族值。但是对于其他用户定义类型，denotational 类型的观点就没那么自然。而且，程序员可能会想从其他简单类型构建类型。这就反映了 structuiral 和 abstraction-based 类型的观点。structural 的观点被 Algol W 和 Algol 68 开创的，1970 和 1980 年代很多语言都有这种特征。abstraction-based 观点时 Simula-67 和 Smalltalk 开创的，很多现代面向对象语言都采用了，也可以在各种语言的模块中看到，并且可以被任何语言的编程问题采用。我们在第 8 章详细讨论 structural point ，在第 10 章讨论 abstraction-based。

7.1.2 Polymorphism

多态，我们在 3.5.2 中简单介绍了，从希腊语中得名，意味着“有多个形状”。应用到代码中，数据结构或者 subroutine，被设计为可以与多种类型一起工作。为了正确性，类型必须有一些公共特征，代码不依赖其他特征。通常有两种方式捕捉共性。parametric polymorphism 是代码将类型作为参数【译者注：模板？】。subtype polymorphism 代码设计为可以与一些特定类型 T 一起工作，但是程序员可以定义额外类型作为 T 的补充或者重定义，代码也可以正确工作。

显式的 parametric polymorphism ，也被称为 generics （或者 C++ 中的 templates），通常出现在静态类型语言中，在编译期实现。隐式版本也可以在编译器实现，特别是 ML 家族语言，但是更常见的是匹配动态类型，在运行时检查。

subtype polymorphism 主要在面向对象语言中出现。使用静态类型，可以在编译期处理多类型的工作：主要的运行时成本是方法的调用。设想这种实现的大多数语言，包括 C++ Eiffel, OCaml, Java, C# 提供了编译期 generics 检查的单独实现。subtype 和 parametric 多态的结合尤其在容器类中有用，比如 List<T> or Stack<T>，T 是未指定的，可以后续实例化为任何类型。

相反动态类型的面向对象语言，包括 Smalltalk， Python，Ruby 对于 parametric 和 subtype 使用同一种机制实现，都在运行时检查。统一的机制也出现在 Objective-C 中，在一些静态类型之上提供了动态类型对象。

我们在 7.3 中详细讨论 parametirc 多态，在 10 章讨论 subtype 多态。

7.1.3 Orthogonality（最少的类型可以支持更多的类型）

6.1.2 中我们讨论了设计 expression, statement, control-flow 结构的正交性。在高度正交的语言中，我们可以任意组合三种结构，而且不会出现错误。正交性在类型系统中同样重要。我们已经注意到 Algol 68 和 C 通过消除（至少是模糊）语句和表达式的区别来增强正交性。为了表示有 side effect 的语句，并且没有有用的值，某些语言提供了单独的琐碎类型。在 C 和 Algol 68 中，subroutine 表示返回类型为 void 的 procedure。在 ML 中，有个琐碎类型 unit。如果程序员想要调用有返回值的 subroutine，但是返回值不被需要，C 中的返回值可以被“转换”为 void：

foo_index = insert_in_symbol_table(foo);
...
(void) insert_in_symbol_table(bar); // don't care where it went

在没有琐碎类型的语言（Pascal）中，需要这样使用“哑巴”变量：

var dummy: symbol_table_index;
...
dummy := insert_in_symbol_table(bar);

另一个正交性的例子，考虑“擦除”值--表示不再持有值。对于指针类型，我们可以使用 null。对于枚举类型，我们可以在定义中加入 None。但是这两种方式是不同的，它们没有泛化到所有使用可用位模式实现的类型。

为了更正交地表示”不是以上所有“需求，很多函数式语言--和一些命令式语言--提供了特殊的类型构造器，通常称为 Option or Maybe。在 OCaml，我们可以这样写:

let divide n d: float option = (* n and d are parameter *)
match d with						(* "float option" is the return type *)
| 0. -> None
| _ -> Some(n /. d);;  (* underscore means "anything else" *)

let show v: string = match v with
| None -> "??"
| Some x -> string_of_float x;;

这里的 divide函数返回 None 如果除0；否则返回 Some x，x表示结果。函数 show 返回 “？？”或者 x 的字符串表示，取决于 v 是 None 还是 Some x。

Option 类型也在其他语言中出现，Haskell（称为 Maybe），Scala，C#，Swift，Java 和 C++ 以及 Rust。为了简介，C# 和 Swift 使用尾部问好代替 option 构造器。使用 Swift 重写上面的例子：

func divide(n: Double, d: Double) -> Double? {
  if d == 0 {return nil}
  return n / d
}

func show(v: Double?) -> String {
  if v == nil {return "??"}
  return "\(v!)"
}

另一个正交性的例子当给复合类型对象指定字面值时。这些字面量有时被称为 aggregates。在初始化使用静态数据存储，否则，程序需要在运行时浪费时间进行初始化。

Ada 给所有结构类型提供了 aggregates。下面的代码：

type persion is record
	name: string(1..10);
  age: integer;
end record;

p, q : persion
A, B : array(1..10) of integer;

我们可以这样赋值：

p := ("Jane Doe", 37);
q := (age => 36, name => "John Doe");
A := (1, 0, 3, 0, 3, 0, 3, 0, 0, 0);
B := (1 => 1, 3 | 5 | 7 => 3, others => 0);

p 和 A 的 aggregate 赋值是按照位置；q 和 B 的按照名字。C/C++，Fortran 90 ，Lisp 也支持类型能力。

ML 提供了对于复合表达式非常泛化的能力，基于构造器的使用（11.4.3 讨论）。Lambda 表达式，在 11 章讨论。

7.1.4 Classification of Types

类型的术语在语言之间大有不同。本节为最常见的术语提供定义。大多数语言提供了大多数处理都支持的内建类型：整数，字符，布尔值，实数。

布尔值通常为实现为单字节。少数语言中，打包成 array 只使用一个比特。C 在历史上省略了布尔类型：大多数语言会使用布尔值，C 是整数的0和非零。C99 才引入了 _Bool 类型，但是实际上是一个整数，编译器保证使用一个比特存储。

字符传统上使用一个字节表示，典型的是 ASCII 编码。更多的近代语言（Java 和 C#）使用两个字节表征 Unicode 字符集。Unicode 被设计为可以表示更多语言的字符集。前 128 个 Unicode 的字符(\u0000 到 \u007f) 对应 ASCII。C 和 C++ 提供了标准字符和“宽”字符。Fortran 2003 支持四个字节的 Unicode 字符。

数字类型

整数，实数，有符号/无符号，复数，有理数，decimal

整数，布尔值，字符都是离散类型，以及用户定义的枚举和 subrange 也是离散类型。离散，有理数，实数和复数一起被称为标量类型（scalar type），标量类型有时也称为简单类型。

枚举类型

从整数兼容发胀为整数不兼容

Subrange 类型

如同枚举，subrange 也是由 Pascal 引入，然后后续很多语言支持。subrange 就是包含了很多离散类型值的集合的类型。

type test_score = 0..100;
workday = mon..fri;

Ada 可以这样写：

type test_score is new integer range 0..100;
subtype workday is weekday range mon..fri;

range.. 部分的定义在 Ada 中称为类型约束。这个例子中 test_score 被称为 derived 类型，与整数不兼容。workday 类型是 constrained subtype，workday 和 weekday 或多或少有交集。derived 类型和 subtype 的区别是 Ada 的有价值的特征，我们在 7.2.1 讨论。

当然可以使用整数表示 test_score，或者使用 weekday 表示 workday。但是显式使用 subrange 有几个好处。第一，代码更可读。注释是文档，但是注释可能与代码不符。因为编译器会分析 subrange 声明，知道 subrange 的值范围，可以检查是否有效。这种检查对于 debug 工具也有用。另外，因为编译器知道 subrange 值的数量，有时可以使用更少的空间表示。比如 test_score 可以使用一个字节。

大多数实现使用与整数相同的位模式。因此即使 subrange 个数很少，也可能占据较大的空间。比如：

type water_temperature = 273..373;

至少两个字节，但是仅有 101 个不同值，373 使用一个字节又不够。【译者注：所以这里使用 base 和 offset 的优化空间】

复合类型

非标量类型通常称为复合类型。通常使用一个或者多个简单类型组合而成。在 7.6 中的例子 Options 是最简单的复合类型。常见的复合类型包括 records(structure)，variant record（union），array ,set, pointer, list, file。除了指针和 list 类型都可以用数学集来表示。

Records(struct) 由 Cobol 引入，大多数语言都支持。record 包含了一系列 field ，每个 field 都是简单类型。record 类似数学的 tuple；record 类型就是 field 类型的笛卡尔积。
Variant record（union）不同于正常的 record，只是一系列 record 的变体，给定时刻只有一个 field 有效。类型是 field 类型的不相交联合。
Array 是最常见的复合类型。字符的 Array 就是字符串，也被特殊支持。
Sets 就像枚举和 subrange，由 Pascal 首次引入。set 类型是其基本类型的数学集，通常是离散的。包含了离散类型值的集合。
Lists 像 Array，包含了一系列元素，但是没有下标到元素的映射。而是，递归定义，每个元素指向相同的元素。array 的长度在 elaboration time 【译者注：语义推敲，上下文分析】是确定的，list 是变长的。为了找到一个元素，程序必须遍历整个 list。因为其递归的定义，list 在大多数函数式语言中是基石。
Files 用来表示在大存储设备上的数据，内存之外。就像 array，大多数文件也是下标到数据的映射。不想 array 的点是文件由当前位置的概念。文件也用来表示物理上的 I/O 设备。特别的事某些文件的元素必须顺序访问。

我们在第 8 章详细讨论复合类型。