【软件构造】——复习篇 软件构造的理论基础(ADT到OOT)

本期是软件构造第4-8讲的自我总结，这部分是考试中最重要的一部分，分值占比最大，从软件构造的基本组成：数据和行为说起，再将二者联合构成ADT，之后讲述了ADT的实现方法：OOT，最终回归到对象间的相互关系中来。不得不感叹MIT教学的逻辑性之强，知识连贯性之高。

第四讲：数据类型与类型检验

这一讲从软件最基本的组件：数据讲起，并根据数据类型的划分进行不同的检验

数据类型（一组值以及可以对其执行的操作）

• 基本数据类型

  • 不可变

  • 栈中分配内存

  • int/long/boolean/double/char

• 对象数据类型

  • 可变
  • 堆中分配内存

对象间可以用继承（extends）形成层次结构

静态/动态检查/非检查错误

静态和动态的区分关键在于阶段。静态往往是在程序运行前的阶段就已经确定，比如静态变量、静态检查亦如此，无需在程序运行的时候就可以对代码中的数据潜在错误进行检测；而动态恰恰相反，也正如其名，是需要程序在运行的动态环境中进行检测的。这个本质我们后续会经常用到。而程序中某些bug并不会引起检查错误，但是会导致得到的结果并不尽我们所意。

就重要性而言：静态检查》》动态检查》》无检查

常见的静态检查

其实正如静态的定义，由于这类错误是代码中类型/符号的匹配是显式的标出的，因此可以用这种方法进行辅助定义

• 语法错误
• 类名/函数名错误
• 参数类型错误
• 返回值类型错误

常见的动态检查

• 非法的参数值（除零错误！）
• 非法的返回值
• 越界
• 空指针引用

常见的非检查错误但是结果不正确

• 整数除法：整数除会去掉小数，没啥特别的
• 整数溢出：计算得到的结果超过了类型的边界，计算机系统中反复提及
• 浮点数中的特殊类型：NaN(负数开根号)

可变性与不变性

改变一个变量的值和改变一个变量的区别：

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

不变数据类型：一旦被创建其值不可改变；如果是引用类型，一旦确定指向的对象，不能再改指向

编译器进行静态类型检查时，如果final变量首次赋值后发生改变则提示错误

有关final的注意事项：

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

这里有一个典型的一对例子：String和StringBuilder。String是不变量，StringBuilder是变量

可变类型的优势：最少化拷贝，不需垃圾回收，提高效率

防御式拷贝的思路

如何安全的使用可变类型？设计为局部变量，免去共享的问题；或者只有一个引用

给客户端一个全新的对象

不可变类型不需要防御式拷贝

Snapshot图

软件中的视图

• code-level
• run-time
• moment view

这里主要是各种概念和画法，我截取了几条规则：

 

引用不可变但是指向的值可变

引用可变也可指向不可变的值

迭代器：

• 迭代器是一个对象，遍历一组元素并逐个返回元素
• for形式的遍历调用的是被遍历对象所实现的迭代器

 

第五讲：设计规约

规约及其相关基本概念

规约是程序与客户端达成的一致，给双方都确定了责任，调用时双方都要遵守

规约可以起到隔离的作用，客户端不需要知道实现，实现者不需要知晓如何被调用。

行为等价性：根据规约判断两个方法的行为等价性

前置条件与后置条件

前置条件：对客户端的约束，使用方法时必须满足的条件

后置条件：对开发者的约束，方法结束时必须满足的条件

前置条件满足，则后置条件必须满足

静态类型声明是一种规约，据此进行静态类型检查；方法前注释也是一种规约，但需人工判定

设计规约

更强的规约：前置条件更弱或相等；或满足同一前置条件下，后置条件更强或相等

图像化规约

• 某个具体实现若满足规约则落在其范围内，否则在其之外
• 更强的规约区域面积更小

规约设计原则

• 内聚性：规约描述的功能单一、简单、易理解
• 信息丰富：不能让客户端产生歧义
• 规约足够强
• 适当保持弱，否则难以实现
• 规约中使用抽象类型

是否使用前置条件取决于对于输入参数检查的代价以及方法的适用范围。如果方法是private的可以适当不用前置条件，如果是public则需要设计较好的前置条件

 

第六讲：抽象数据类型（ADT）

前两讲针对两大组成部分：数据以及数据的操作（方法）分别进行了理论性的阐述和设计思想。而ADT就是这二者的集大成者，通过定义一系列数据的组合及其对应的数据操作，使得开发者可以更好的设计程序，将实际问题抽象出来。

抽象类型的操作分类

T :抽象类型；

t :其他类型；

+ :表明类型可能出现至少一次；

* :出现≥0次；

| :或

构造器（从无到有）Creators [ t* -> T ]

可能实现为构造函数或静态函数

实现为静态方法的构造器通常为工厂方法

String.valueof(Object) ：一种特殊的creator

生产器（从有到新）Producers [ T+, t* -> T ]

concat()

观察器 Observers [ T+, t* -> t ]

size()

变值器（改变对象属性）Mutators [ T+, t* -> void | t | T ]

通常返回void，改变了对象的某些内部状态，也可以返回非空类型

设计抽象类型

1. 设计简洁一致的操作
2. 要足以支持client对数据所做的所有操作需要，且用操作满足client需要的难度要低
   1. 对象每个需要被访问到的属性是否都可以被访问到
3. 要么抽象、要么具体

表示独立性

含义：client使用ADT时无需考虑其内部如何实现，ADT内部表示变化不应影响外部规约和客户端

抽象类型的测试

针对creator：构造对象后用obeserver去观察是否正确

针对observer：用其他三类方法构造对象，然后调用observer判断观察结果是否正确

针对producer：produce新对象后用observer判断结果是否正确

针对mutator：用observer查看调用mutator后的结果是否正确

不变量与表示不变量

一个良好的数据结构需要始终保持其不变量

不变量就是一个程序任何运行时状态都为true的性质

不变性就是一个不变量的invariant。这里的invariant有一点抽象，其实是指一个抽象类型的一些一直保持的性质，比如刚才的例子，一个immutable 对象，他的一个invariant就是它的不变性。一个ADT保持了它自身的invariant就是指有它自身来负责这些性质，与client的行为无关。

保持invariant的意义在于让程序更容易被检测出错误

ADT的一个最重要的invariant就是保持不变性（immutability）和避免表示泄露

表示不变性RI

用来衡量某个具体的”表示“是否是”合法的“；

或者看作所有合法表示值得合集

或看作一个描述了”合法“表示值的条件

应该在所有可能改变rep的方法内部都检查（checkRep()）;Observer建议也检查

记录表示中的field何为有效

表示空间、抽象空间与AF

表示空间（R）：实现者看到和使用的值

抽象空间（A）：client看到和使用的值

抽象函数（AF）：R和A之间映射关系的函数，

• 满射：所有抽象值都有被映射的表示值
• 非单射：多个表示值映射到同一个抽象值
• 未必双射：不是所有的表示值都有映射（存在不合法表示值！）

选定某种特定的表示方式后，进而指定某个子集的合法性（RI），并为该子集中的每个值做出解释（AF）

精确记录AF：如何解释每个值

第七讲：面向对象的编程

学习了ADT之后，使用面向对象的编程方法来实现ADT的创造

接口、抽象类、具体类

类中的static和instance的变量和方法：静态方法无法直接调用非静态成员，调用静态方法不需要创建对象。

接口中只有方法的定义而没有实现，接口之间可以继承与拓展。

一个类可以实现多个接口而一个接口可以有多种实现类

接口：确定ADT规约；类：实现ADT

通过default方法，在接口中统一实现某些功能，从而无需在各个类中重复实现。

抽象类

只有定义没有实现，抽象类不可以实例化，继承某个抽象类的子类在实例化时，所有父类中的抽象方法必须已经实现

继承与override(重写)

方法的重写中的参数、返回类型都保持不变

如果父类型中的某个函数实现体为空意味着所有子类型都需要这个功能

重写之后利用super()复用父类型中函数的功能。对于一个构造器来说，super必须放在方法的第一部分

 override在run-time进行动态检查

• 必须有相同的参数列表
• 可以有相同/不同的返回值类型
• 可以改变修饰符类型
• 可以改变异常类型

多态与overload(重载)

特殊多态

重载：多个方法具有同样的名字，但有不同的参数列表或返回值类型

overload在编译阶段进行静态类型检查

• 必须有不同的参数列表
• 可以有相同/不同的返回值类型
• 可以改变修饰符类型
• 可以改变异常类型

 而针对重载和重写的区别，我们可以看这个表格：

参数化多态

泛型类

泛型接口

泛型方法

子类型多态：不同类型的对象可以统一的处理而无需区分

子类型的规约不能弱化超类型的规约

 

第八讲：ADT和OOT的等价性

如果AF映射到同样的结果，则等价

如果对两个对象调用任何相同的操作都会得到相同的结果，则认为两个对象等价

等价性equals()与==

对基本数据类型使用==判定相等（判断对象时看是否指向内存里的同一段空间）

对对象类型使用equals()

在使用时，可以先用instanceof判断对象类型，再判断属性值

instanceof是动态类型检查

equals()的自反、传递与对称

hashCode()

程序中多次调用同一对象的hashCode方法，都要返回相同值；

等价的对象必须有相同的hashCode

不可变对象的引用等价性、对象等价性

equals()比较抽象值、用行为等价性判断

hashCode()将抽象值映射至整数

两个函数都应该重写

可变对象的观察等价性、行为等价性

观察等价性：在不改变状态的情况下，两个可变对象看起来是否一致

行为等价性：调用对象的任何方法都展示出一致的结果

对于可变类型，往往倾向于使用严格的观察等价性

可变类型行为等价需要引用相等

观察等价性需要通过观察器判断

equals()比较引用、用行为等价性判断

hashCode()将引用映射为一个函数

不应重写这两个函数