ADT+OOP
数据类型和数据检查
编程语言中的数据类型
java基本数据类型（不可变）：小写开始：int long boolean double char
对象数据类型：大写开始，eg：String
- 基本数据类型的包装类：将基本数据类型封装成对象，如collections，尽可能少用，语言会自动切换，但效率低
静态和动态数据类型
java是静态类型语言：
编译时需要知道所有变量的类型，编译器可自动推断所有表达式的类型
IDE支持输入时语法检查
动态类型语言：eg：Python，只有程序运行时才能进行语法检查
类型检查
静态检查(编译时，运行前)：动态类型的语言也会进行此类检查(best)
安全、易于理解和改变
动态检查(代码被执行)：非法的参数、越界、调用空对象的方法(better)
不检查
静态检查针对类型，与变量特定值无关；动态检查针对由特定值引起的错误
可变性和不可变性
对变量赋值是在改变变量的指向，指向不同的值
改变可变变量的内容时 ，是在改变变量内部内容的引用
采用不可变类型，可通过内存共享相同的值，降低复制带来的内存空间占用
快照图
代码级、运行时和时刻视图
复杂数据类型：数组和集合
通过数据构建list：Arrays.asList(new String[] { “a”, “b”, “c” })
- 迭代器是一个对象，遍历时默认调用迭代器
有用的不可变类型
原始类型和原始包装器都是不可变的: BigInteger 、 BigDecimal
Date可变、java的集合类型(List、Set、Map)都是可变的，得到不可修改视图的方法：Collections.unmodifiableList 、Collections.unmodifiableSet、Collections.unmodifiableMap
不可修改的包装器通过拦截修改集合的所有操作并抛出一个UnsupportedOperationException来取消修改集合：使集合在构建后不可修改，只运行客户读取数据
空指针
非空的collection可以包含null值
设计规范
大纲
1、编程语言中的函数/方法
2、规范：通信编程
为什么需要规范
行为等价
规格结构：前置和后置条件
3、设计规范
分类规范
图表规范
规格质量
编程语言中的函数/方法
方法的用户不需要知道方法是如何工作的—称之为抽象
规范：通信编程
1）文档
- 文档约定：
- 定义变量时声明其类型是一种文档约定(编译器会进行检查以确保正确性)
- 声明变量未final类型也是一种文档约定
- 编程目标：语法正确和类型正确、使程序利于理解
2）规格和契约
规格说明是团队开发的关键，是分配责任的基础
规格说明是实现者和使用者间的一种契约，实现者有责任满足契约，使用者可以信赖契约
- 优点
- 准确的规格说明利于确定错误的位置和责任
- 客户端不需要阅读代码，通过说明了解程序
- 规格说明给了实现者实现的自由，在保证约定下，可以自由修改实现
- 通过在说明中增加对输入的限定，省略掉耗时的正确性检查工作，提升效率。(保证输入正确性的责任由调用者承担)
- 契约分离了客户端和实现者
注：规格说明不应涉及实现的内部变量和私有域
3）行为等价
- 确定行为的等价，关键是一个规格说明实现是否可以替换另一个
- 等价的判定由调用者视角确定
- 判定可替换与否，需要对调用端依赖内容的准确描述
4）规范结构：前置和后置条件
- 方法的规范包含以下方面：
- 前置条件:由关键字require表示
- 后置条件：由关键字effects表示
- 异常行为：如果违反了前置条件，会如何
- 前置条件是客户端的义务，是调用方法的状态的条件
- 后置条件是方法实现者的义务。若调用状态的先决条件成立，则方法必须遵守后置条件，方法包括返回适当的结果，抛出异常的指定、可变或不可变对象等
- 若前置条件满足，则后置条件必须满足；若前置条件不满足，则后置条件无需满足
- 前置和后置条件中对类型的声明由编译器进行检查，其余部分通过注释的形式进行描述，由人来保证正确性
- 若无明确说明，默认输入值不可变。
- 可变：
- 对可变对象的引用，需要程序维护其一致性
- 可变使对象具有全局属性，导致难于理解和确保正切性
- 优点是性能和便利，但是需要额外的确保无错的成本
- 可变对象使代码难以变化
5）测试和验证规范
- 正式合同规格：
- 优点：自动生成的运行时检查、形式验证依据、自动分析工具
- 缺点：工作量大、不合实际、行为的某些方面不符合正式规范
- 文本规范–Javadoc
- 实际方法
- 记录每个参数、返回值、每个异常、方法的功能、包括用途、副作用、任何线程安全问题、性能问题等
- 不记录具体的实现细节
- 契约的语言正确性
- 编译器确保类型正确
- 静态分析工具识别常见bug
- 语义正确性
- 形式验证
- 使用数学方法证明形式规范的正确性
- 正式的证明所有可能执行的都符合规范
- 手动工作、部分自动化、不能自动化决定的
- 测试：揭示bug、评估质量、阐明规范和文档
设计规范
1）规格说明分类
确定性：唯一的输出或多个合法的输出
声明程度：单纯的描述输出还是给出了具体的计算
健壮性：限制实现方式的多少
确定性与欠定
- 确定性规格：
- 满足先决条件后，结果是完全确定的。即：只有一个返回值和一个最终状态，不存在有效输入对应多个有效输出
- 低确定的：允许同一输入存在多个有效输出
- 非确定的：输出结果不确定
注：将不确定的规格统一定义为欠定的；规格说明的不确定性，为实现者提供了在实现时选择方案的机会（欠定的规格说明通常是通过完全确定的实现来实现的）
声明性
- 操作规范给出了方法执行的一系列步骤（伪代码）
- 声明性规范不给出实现的细节，而是给出最终结果的属性及与初始状态的关系
注：声明性规范更可取：简短，易于理解，不会暴露内部实现细节
操作规范：为维护人员提供解释；如果必须，可放到内部的注释中
健壮性
规格说明比较：
规格S2>=S1: (1）S2的前提条件小于等于S1（2）对于满足S1前提的状态，S2d 后置条件大于等于S1的后置条件
则S2可替换S1
更强：要求的更少，承诺的更多
2）图表规范
加强后置条件，实现自由变少，弱化前置条件，实现需要处理更多情况，规格越强，区域越小
3）设计规格说明
没有通用的准则，但存在一些有用的指导
内聚：不能有很多不同的情况
结果是有用的信息
健壮性：对不合理参数抛出异常处理后，不允许随意修改
弱化性：必要的细节
使用抽象类型：例List或Set，为客户机和实现者提供更多自由
前置和后置条件：
- 对程序员：检查条件的正确性代价很高时，应通过前置条件处理
- 对用户：javaAPI倾向采用后置条件处理，参数不合适时抛出未检查异常
选择前置或后置的关键因素是检查的代价及方法的作用范围：如果仅在类的内部调用，则可通过仔细检查调用该方法的所在位置来确保前提条件的满足；如果是public方法，则事宜采用后置条件（抛出异常）
小结
- 规格说明实现了实现者与客户机的分离
- 使单独开发成为可能：客户端不需看源代码即可使用，开发人员可自由编写实现过程而无需考虑如何实现
- 安全无bug
- 好的规范可以清楚的记录下用户和实现者的相互假设，bug通常在接口处产生，而规范的存在弥补了这一点
- 规范中使用机器检查语言的特性，如静态检查和异常，而不仅仅是人可读的注释，可进一步减少bug
- 通过静态检查、仔细的推理、测试和代码评审，结构良好、一致的规范可以最大限度的减少误解，并最大限度的提高编写准确代码的能力
- 易于理解：客户机不必阅读或理解代码
- 易于改变：适当的弱规范给实现者以自由，适当的强规范给客户机以自由
- 声明性规范最有用
- 先决条件（削弱了规范）使客户端的应用更加困难，但是开发人员适当的应用，允许开发者做出必要的假设
抽象数据类型
抽象和用户定义的类型
- 抽象的意义：
- 抽象
- 模块化
- 封装
- 信息隐藏
- 关注点分离：模块具有单独的责任，不能将一个责任分散在不同的模块中
- 数据抽象：一个类型的特征由可对其执行的操作刻画
- 抽象类型的新颖性和以往不同之处在于对操作的关注
类型和操作的分类
抽象数据类型的操作分类：
创造者(Creators)：产生类型的新对象
t* → T
制造者(Producers)：在已有对象的基础上产生新的对象
T+, t* → T
观察者(Observers)：输入抽象类型的对象，返回其他类型的对象
T+, t* → t
突变(Mutators)：改变对象
T+, t* → void | t | T
注：
创建者要么作为构造函数实现，比如new，或者只是一个静态方法（作为静态方法实现的创建者通常称为工厂方法）
突变体通常不返回，但并非所有的突变体都是void(),eg: Set.add()返回boolean类型
抽象数据类型示例
1）int
creators:0,1,2…..
producers:+,-,*,/
observers:==,!=,<,>
mutators:不存在，因为int不可变
2）List
creators:ArrayList和LinkedList的构造函数或集合、Collections.singletonList()
producers:Collections.unmodifiableList
observers:size,get
mutators:add,remove,addAll,Collections.sort
3）String
creators:string的构造器
producers:concat,substring,toUppercase
observers:length,charAt
mutators:不存在，string不可变
java实现ADT
| ADT概念 | java的实现方式 | 例子 |
|---|---|---|
| 创造者 | Constructor、Static(factory) method、Constant | ArrayList()、Collections.singletonList()、Arrays.asList()、BigInterger.Zero() |
| 观察者 | Instance method、Static method | List.get()、Collections.max() |
| 制造者 | Instance method、Static method | String.trim()、Collections.unmodifiableList() |
| 突变体 | Instance method、Static method | List.add()、Collections.copy() |
| 表示(representation) | 私有字段 |
- 抽象数据类型是由其操作定义的，类型是由其操作集及规格说明所表征的
- 抽象数据类型的值是不透明的，隐藏了数据和实现，除非操作允许，否则无法检查内部数据
设计抽象类型
ADT的设计需要选择良好的操作以及确定操作的行为
- 规则一：
- 设计一组简单操作，通过简单操作的组合实现复杂的操作
- 操作的行为内聚(单一职责)
- List中不能添加sum方法，缺乏通用性
- 规则二：操作集要完备，覆盖该类型所有支持的行为
- 规则三：类型不应该混合领域无关(通用的)和领域特定的特征
表示独立
抽象类型的使用独立于表示
只有通过前置条件和后置条件充分明确了ADT的操作，使用者知道可以依赖哪些内容，实现者知道可以安全更改哪些内容，此时才可以修改内部表示
测试抽象数据类型
测试创造者、生产者和突变体的唯一方式是对结果对象调用观察者，测试观察者的唯一方式是创建供其观察的对象
不变量
ADT自身有责任确保其不变性，而不是依赖于调用者或者其他模块
Rep不变量和抽象函数
两个值空间：
R:实现时用的的值空间
A:需要支持的值空间
AF: R$\rightarrow$ A,一定是满射
RI : R → boolean
- RI说明空间R中的r是否被映射到了空间A,RI形成了空间R的一个子集（子集中的所有元素均被AF映射到了空间A中)
- AF 和 RI 既不由选定的表示值空间决定，也不由抽象值空间单独决定；表示值空间确定后，AF和RI也不是确定的
- 即使相同的表示值空间和相同的 表示不变性RI，我们仍然可以用不同的抽象函数AF来映射。
- ADT设计的关键：不仅是选择两个空间(面向规格说明的抽 象值空间和面向实现的表示值空间), 而且要决定表示值(RI)和如何映 射(AF)。
有益的突变
抽象值永远不可改变
在确保其映射的抽象值不变前提下，表示值可以变化
记录Rep的AF,RI和安全性
在类中定义Rep的 位置 说明AF、RI、不变性
- 保存不变性：
- 在初始化时使之为真 ；
- 所有修改都使不 变性得到保持
- 在ADT操作中：
- Creators and producers必须为新创建的对象建立不变性
- Mutators and observers必须保持不变性。
- 总结，抽象数据的不变量：
- 只通过creators and producers创建
- 通过mutators and observers保持
- 没有表示泄露发生
ADT不变量代替前置条件
良好设计的ADT，可以替代spec 中的部分preconditions
小结：
- 抽象数据类型有操作集决定
- 操作可分为：创建者，生产者，观察者和突变
- ADT的规格是由其操作和规格说明构成
- 好的ADT:简单，一致，丰富，具有表示独立性
- 测试中，需要将创建者，生产者，观察者和突变放在一起使用
- 安全不易出bug：好的ADT为数据类型定义了良好的契约，客户了解该数据结构，实现者有限制性的改变自由
- 易于理解：好的ADT隐藏实现的细节，使用ADT的程序员只需有理解操作，有实现的自由
- 易于改变：表示独立性允许抽象数据类型的实现可不通过客户端进行更改
- 不变量是一种属性，在对象的生命周期内都为真
- 好的ADT保留自己的不变量。不变量必须由创造者和生产者创建，由观察者和突变体保持
- rep不变量指定表示的合法值，应该在运行时checkRep
- 抽象函数将具体的表示映射到所表示的抽象值
- 表示暴露威胁到表示独立性和不变性的保持
- 安全无bug：一个好的保留自己的不变量，这样不易受到客户端的影响，并且ADT本身的实现可以更容易的隔离对不变量的改变威胁。显式的生命rep不变量并且在运行时checkRep检查，可以更早的捕获误解和bug
- 易于理解：rep不变量和抽象函数解释了数据类型的表示以及与抽象的关系
- 易于改变：抽象数据类型将抽象与具体分离，使得不需要改变客户端代码就可以更改表示。
ADT和OOP
大纲
- 面向对象准则
- 基本概念：对象、类、属性、方法和接口
- OOP的不同特性
- 封装和信息隐藏
- 继承和重写
- 多态、子类型和重载
- 静态和动态分派
- 成分和代表
- java编程中重要的对象方法
- 不可变类
- OOP的历史
将抽象数据类型的接口与其现实分离，并使用java接口来实现这种分离
用接口定义ADT，并用类实现该接口
面向对象准则
- OOP以类为核心概念
- 应该通过断言（前置、后置条件和不变量）和异常处理来增强类及其特性，使用工具将这些断言生成文档，且在运行时可实时监控
- 静态类型：定义良好的类型系统应该通过强制执行许多类型生命和兼容性规则来确保系统运行时类型安全
- 易于改变和可重用的通用性：使用泛型编写类
- 继承
- 多态
- 动态分派/绑定：调用实体的特性时应触发与当前运行对象的类型相对应的特性，执行不同调用时不一定相同
概念
- 对象包括状态和行为
- 每个对象都对应一个类，类中定义成员变量和成员方法，类的方法就是其应用程序接口
- 类变量和类方法与一个类关联，并且每个类只关联一次。
- 使用类需创建实例对象
- 静态方法无法调用非静态成员（方法和变量）
接口
一个接口可以扩展其他接口
一个类可以实现多个接口
API由接口或类实现，接口只一个一个API，接口定义但不实现API，类提供API和实现
接口不能有构造方法，java8之后，接口允许包含静态方法
好处：1）除非只有一个实现，否则对变量和参数使用接口；接口支持实现的改变；接口可防止依赖细节； 2）调用者理解ADT时只需理解接口即可；调用者不能在ADT的表示上创建无意的依赖；不同实现可在不同类中； 3）抽象数据类型的多个不同表示可以共存于同一个程序中，作为接口的不同类
总结：
- ADT的规格说明中，对方法的实现未明确指定，为实现提供了自由，可有多种实现方式
- 一个类可以实现多个接口，展现多个视图，是对java不支持多继承的一种补偿
- 通过多多个实现在性能和bug free方面的比较，进行实现的选择
封装和信息隐藏
API同实现分离，模块间只通过API通讯
信息隐藏的好处：1）解耦组成系统的类，运行独立地开发、测试、优化、使用、理解和修改 ；2）加快系统开发：类可并行开发；3）减轻维修负担：更快理解类，模块分离；4）有效的性能调优：“热”类可在隔离的情况下调优；5）提供软件复用：松耦合类在其他上下文中都有用
注：可在不妨碍调用者的情况下在后期将私有变成公有，但不能进行相反操作
继承和重写
1）重写
子类可重新实现父类中的方法：方法名、参数名、返回值（签名）均相同
默认父类中的方法是可被重写的，但是严格的继承不能重写（final）
子类可通过super关键字调用父类中被重写的方法，调用父类的构造方法时，super（）必须是子类构造方法的第一行
2）抽象类
抽象方法：只有定义没有实现
抽象类：不能实例化，继承某个抽象类的子类在实例化时，所有父类中的抽象方法必须已经实现
多态、子类型和重载
1）三种多态
多态性是指为不同类型的实体提供一个接口，或者使 用一个符号来表示多个不同的类型：方法重载、参数多态(泛型)、子类型：一个类的名字可代表多个类的实例
2）Ad hoc 多态和重载
特别的多态性：参数不同，返回值不同
重载： 重载是指在一个类中存在多个同名函数，必须具有不同的参数 列表，返回值类型可同可不同
- 重载是静态的多态：通过参数列表决定依赖哪个实现，方法调用时静态类型检查，在编译时决定调用哪个方法
- 重载规则：
- 必须更改参数列表
- 可更改返回类型
- 可更改访问修饰符
- 可声明新的或更广泛的已检查类型
- 对某个方法 的重载可以在一个类中进行，也可以在子类中进行。此时需要注意同重写 的区别：如果父类和子类中两个方法的签名相同，则为重写；名称一样， 参数列表不一样时，则为重载
子类重载了父类的 方法后，子类仍然继承了被重载的方法
3）参数多态性和泛型编程
未完待续~