3.1 数据类型与类型检验

编程语言的数据类型

数据类型：指的是一些值和在其上可以进行的操作的集合
变量：用特定数据类型定义，可存储满足类型约束的值

Java中的基本数据类型：int,short,long,byte,boolean,float,double,char
只有值，没有ID (与其他值无法区分)，是不可变类型，在栈中分配内存，没有统一的表达式，代价低

Java中的对象数据类型：String,BigInteger等
值和ID都有，可变类型，在堆中分配内存，以泛型来统一表达式，但代价昂贵

按照Java惯例，基本类型一般小写，对象类型一般首字母大写

所有对象类型的根是Object类型。除了Object之外，所有类都有一个父类，由extends子句指定，缺省为Object，一个类是它的所有父类的实例，继承其父类的属性和方法，可以通过重写父类的方法来改变其行为。

动/静态类型检查

Java是一种静态类型语言。所有变量的类型在编译时(程序运行之前)都是已知的，因此编译器也可以推断出所有表达式的类型。如果a和b被声明为int，那么编译器会得出a+b也是int的结论， Eclipse会在你编写代码时就进行这一步，因此你会在敲代码的时候就发现很多错误，即在编译阶段进行类型检查。而像Python这种动态类型语言中，这种类型检查会被延迟到程序运行时。

一种编程语言可能自动进行以上两种任一种类型检查，亦或是根本不进行检查。显然程序执行前就发现错误比较好，所以静态>动态>无检查。

Java还会验证变量类型是否始终匹配。

静态类型检查：可在编译阶段发现错误，避免了将错误带入到运行阶段，可提高程序正确性/健壮性，其中检测的错误类型包括语法错误、类名/函数名错误、参数数目/类型错误、返回值类型错误、非法的参数值和返回值、越界、空指针……静态类型检查会检查变量的类型，往往和变量具体值无关，因此比如除0错误和索引越界就不在其范畴，对应的，动态类型检查常常是因为某些特定的值所导致的。

可变/不可变数据类型

改变一个变量：将该变 量指向另一个值的存储空间
改变一个变量的值：将 该变量当前指向的值的存储空间中写入一个新的值

不变性Immutability：一旦被创建，其值不能改变。如果是引用类型，也可以是不变的：一旦确定其指向的对象，不能再被改变，这时我们就会用final来限定，使得一个引用成为不可变类型（如果编译器无法确定final变量不会改变，就提示错误，这也是静态类型检查的一部分）

final：
final类无法派生子类
final变量无法改变值/引用
final方法无法被子类重写

不变对象：一旦被创建，始终指向同一个值/引用。比如String、LocalDateTime类型变量修改内容时需要指向一个新的内存。使用不可变类型，对其频繁修改会产生大量的临时拷贝(需要垃圾回收) ，但不可变类型更“安全”， 在其他质量指标上表现更好
可变对象：拥有方法可以修改自己的值/引用。比如StringBuilder、Date类型变量有方法可以对其内容修改而不改变指向。可变类型最少化拷贝以提高效率和性能，也适合于在多个模块之间共享数据

防御式拷贝：返回一个可变类型复制的新对象，大部分时候该拷贝不会被客户端修改， 可能造成大量的内存浪费。

如果有多个引用（别名），使用可变类型就非常不安全，应安全的使用可变类型：局部变量，不会涉及共享；只有一个引用

Snapshot图

Snapshot图用于描述程序运行时的内部状态（栈中的方法和局部变量以及堆中的引用），便于刻画各类变量随时间变化和解释设计思路

对于基本类型的值，箭头指向一个常量代表引用指向一个具体的值
对于对象类型的值，我们加一个圈表示如下图：

对于不可变类型，我们用双线椭圆：

下图是可变类型的画法：

不可变的引用：一旦创建后不可再次赋值，我们可以用final修饰引用，此时会导致一个静态类型检查，引用是不可变的，但指向的值却可以是可变的（常量指针），对应的，可变的引用，也可指向不可变的值（指向常量的指针）。我们用双线箭头表示不可变引用：

复杂数据类型：Arrays和Collections

Array:

数组是另一种类型的固定长度序列
定义：int[] a = new int[100];
操作：索引、赋值、求长度

List:
列表是另一种类型的可变长度序列
定义：List list = new ArrayList();
操作：索引（get）、赋值（set）、求长度（size）
List是一个接口，其成员必须是对象类型

Set:
集合是零个或多个唯一对象的无序集合
操作：
s1.contains(e):查询是否包含该元素
s1.containsAll(s2):是否s2是s1的子集
s1.removeAll(s2):把s1中所有s2的元素移除
Set是一个抽象接口

Map:
映射是一个键-值对目录
操作：
m.put(k,v)：添加
m.get(k)：索引
m.containsKey(k)：查询是否包含该键值
m.remove(k)：删除对应的键-值对
Map是一个抽象接口

Iterator迭代器：

Iterator是一个可变类型对象，它遍历元素集合并逐个返回元素
方法：
next():可变方法，返回下一个迭代对象
hasNext():检测迭代是否到终点

突变会破坏迭代器，应调用iter.remove()方法

有用的不可变类型

基本类型及其封装对象类型都是不可变的，而Collections类静态方法可以获取可变对象例如List/Set/Map的不可变特性（Collections.unmodifiableList/Set/Map）,这种包装器得到的结果是不可变的（只能看），但是这种“不可变”是在运行阶段获得的，编译阶段无法据此进行静态检查，例如编译阶段调用sort方法时Java不会报错

3.2 设计规约

编程语言中的函数/方法

参数/返回值类型是否匹配，在静态类型检查阶段完成
“方法”是程序的“积木”，可以被独立开发、测试、复用，使用“方法”的客户端，无需了解方法内部具体如何工作—“抽象”
一个已完成的方法包含规约和实现体

规约概述

规约的作用：
规约可以隔离“变化”，无需通知客户端
规约也可以提高代码效率
扮演“防火墙”角色
解耦，不需了解具体实现

规约只讲“能做什么”，不讲 “怎么实现”

行为等价性：
站在客户端视角看行为等价性，根据规约判断是否行为等价，如果两个函数都符合同一规约，则它们等价

规约由以下部分组成：
前置条件：对客户端的约束，在使用方法时必须满足的条件 @param
后置条件：对开发者的约束，方法结束时必须满足的条件 @return
异常处理：因规约违反而进行的处理 @throws
注意，如果前置条件满足了，后置条件必须满足，如果前置条件不满足，则方法可做任何事情。
静态类型声明是一种规约，可据此进行静态类型检查，方法前的注释也是一种规约，但需人工判定其是否满足

除非在后置条件里声明过，否则方法内部不应该改变输入参数，应尽量遵循此规则，尽量不设计 mutating的spec，否则就容易引发bugs；且尽量避免使用mutable的对象，因为程序中可能有很多变量指向同一个可变对象（别名），我们无法强迫类的实现体和客户端不保存可变变量的“别名”

规约的设计

spec的强度：如果相较于s1，s2的前置条件更弱、后置条件更强，则s2规约强度大于s1，s2可以代替s1

越强的规约，意味着implementor的*度和责任越重，而client的责任越轻。

图表示：
每一个点代表一个方法的实现，一个规约划定了一片区域，某个具体实现，若满足规约，则落在其范围内；否则，在其之外。更强的规约，表达为更小的区域（更弱的前置条件意味着实现时要处理更多的可能输入，更强的后置条件意味着实现的*度更低了）

好规约的标准：
内聚的： Spec描述的功能应单一、简单、易理解
信息丰富的：不能让客户端产生理解的歧义
足够强的：太弱的spec，client不放心、不敢用 (因为没有给出足够的承诺)。开发者应尽可能考虑各种特殊情况，在post-condition给出处理措施
足够弱的：太强的spec，在很多特殊情况下难以达到，给开发者增加了实现的难度（client当然非常高兴）
使用抽象类型：在规约里使用抽象类型，可以给方法的实现体与客户端更大的*度
是否使用前置条件：是否使用前置条件取决于(1) check的代价；(2) 方法的使用范围
– 如果只在类的内部使用该方法(private)，那么可以不使用前置条件，在使用该方法的各个位置进行check——责任交给内部client；
– 如果在其他地方使用该方法(public)，那么必须要使用前置条件，若client端不满足则方法抛出异常。

3.3 抽象数据类型ADT

抽象和用户自定义类型

除了编程语言所提供的基本数据类型和对象数据类型，程序员可定义自己的数据类型
传统的类型定义：关注数据的具体表示
数据抽象：由一组操作所刻画的数据类型
抽象类型：强调“作用于数据上的操作”，程序员和client无需关心数据如何具体存储的，只需设计/使用操作即可
ADT是由操作定义的，与其内部如何实现无关

ADT中类型和操作的分类

可变和不可变数据类型：
可变类型的对象：提供了可改变其内部数据的值的操作
不变数据类型： 其操作不改变内部值，而是构造新的对象

操作分类：
构造器：创建该类型的一个新对象（t* → T ）可能实现为构造函数或静态函数（又叫工厂方法）
生产器：由旧的对象产生出该类型的一个新对象（ T+, t* → T ）
观察器：接受抽象类型的对象，并返回不同类型的对象（T+, t* → t ）
变值器：改变对象属性的方法 （T+, t* → void | t | T）变值器通常返回 void ，也可能返回非空类型，如果返回值为void，则必然意 味着它改变了对象的某些内部状态

（T为该抽象类型，t为其他类型，+为一次及以上，*为零次及以上）

ADT设计原则

设计好的ADT，靠“经验法则”，提供一组操作，设计其行为规约 spec
设计简洁、一致的操作
要足以支持client对数据所做的所有操作需要，且用操作满足client需要的难度要低

表示独立性RI

表示独立性：client使用ADT时无需考虑其内部如何实现，ADT内部表示的变化不应影响外部spec和客户端。
除非ADT的操作指明了具体的pre和post-condition，否则不能改变ADT的内部表示——spec规定了 client和implementer之间的契约。

测试ADT

测试creators, producers, 和 mutators：调用observers来观察这些operations的结果是否满足spec
测试observers：调用creators, producers, 和 mutators等方法产生或改变对象，来看结果是否正确
风险：如果被依赖的其他方法有错误，可能导致被测试方法的测试结果失效
对测试的不同操作进行划分，分别集中进行测试

不变量

一个好的ADT有一个重要的性质：它能保持它的不变量恒为真，无论程序运行的状态如何；immutability就是一个典型的“不变量” ，由ADT来负责其不变量，与client端的任何行为无关。不变量可以保持程序的“正确性”，容易发现错误，因为我们总是要假设client有“恶意”破坏ADT的不变量

表示暴露：类之外的代码可以直接访问到类中的属性表示
不仅影响不变性，也影响了表示独立性：无法在不影响客户端的情况下改变其内部表示
因此，我们可以使用private阻止外部访问，用final防止再赋值

除非迫不得已，否则不要把希望寄托于客户端上，ADT有责任保证自己的不变量，并避免“表示泄露”，最好的办法就是使用immutable的类型，彻底避免表示泄露

解决方案：
不要将可变参数合并到对象中，创建防御副本
返回可变属性的防御性副本或不可变化的对象
真正的教训——使用不可变属性，以消除防御性复制的需要

表示不变量RI和抽象函数AF

表示空间保存真实实体的值，抽象空间保存client看到和使用的值，一般情况下ADT的表示比较简单，有些时候需要复杂表示，ADT开发者关注表示空间R，client关注抽象空间A。R到A的映射一定是满射，但未必是单射或双射。

抽象函数：R和A之间映射关系的函数，即如何去解释R中的每一个值为A中的每一个值 AF:R->A R中的部分值并非合法的，在A中无映射值

表示不变量：RI : R → boolean
某个具体的“表示”是否是“合法的”
所有表示值的一个子集，包含了所有合法的表示值
一个条件，描述了什么是“合法”的表示值

不同的内部表示，需要设计不同的AF和RI，选择某种特定的表示方式R，进而指定某个子集是“合法”的(RI)，并为该子集中的每个值做出“解释”(AF)——即如何映射到抽象空间中的值；即使是同样的R、同样的RI，也可能有不同的AF，即“解释不同”

设计ADT：(1) 选择R和A；(2) RI — 合法的表示值； (3) 如何解释合法的表示值 —映射AF做出具体的解释：每个rep value如何映射到abstract value，而且要把这种选择和解释明确写到代码当中

随时用checkRep()检查RI是否满足要求，在所有可能改变rep的方法内都要检查 ，Observer方法可以不用，但建议也要检查，以防止你的“万一”

有益的可变性

不可变类型：A空间的值恒不变，但R空间的值可以变化，只要还映射到A空间的同一个值就行，这个操作是对客户端不可见的。这种mutation只是改变了R值，并未改变A值，对client来说是 immutable的。“AF并非单射”，从一个R值变成了另一个R值 ，但这并不代表在immutable的类中就可以随意出现mutator

AF、RI和表示暴露的安全声明文档编写

在代码中用注释形式记录AF和RI
要精确的记录RI：rep中的所有fields何为有效
要精确记录AF：如何解释每一个R值
表示泄漏的安全声明要给出理由，证明代码并未对外泄露其内部表示——自证清白

ADT的规约里只能使用client可见的内容来撰写，包括参数、返回值、异常等。如果规约里需要提及“值”，只能使用A空间中的“值”。 ADT的规约里也不应谈及任何内部表示的细节，以及R空间中的任何值；ADT的内部表示(私有属性)对外部都应严格不可见；故在代码中以注释的形式写出AF和RI而不能在Javadoc文档中，防止被外部看到而破坏表示独立性/信息隐藏

不变量的建立：
在对象的初始状态不变量为true，在对象发生变化时，不变量也要为true。换言之，构造器和生产器在创建对象时要确保不变量为true、变值器和观察器在执行时必须保持不变性、在每个方法return之前，用checkRep()检查不变量是否得以保持。

表示泄漏的风险：一旦泄露，ADT内部表示可能会在程序的任何位置发生改变（而不是限制在ADT内部），从而无法确保ADT的不变量是否能够始终保持为true

一个好的ADT保持它自己的不变量。不变量必须由构造器和生产器建立，并由观察器和变值器保存

ADT不变量替换前置条件

用ADT不变量取代复杂的Precondition，相当于将复杂的precondition封装到了ADT内部——这样做更安全，因为所需的条件可以在一个地方强制执行，而且Java静态检查可以防止不满足此条件的值在编译时被使用，从而避免出现错误。