软件构造课堂笔记

发表于 | 更新于 | 阅读次数：

注：本文章按照哈工大老师讲的顺序编写，图片截取自王忠杰老师的PPT(同样也是MIT的PPT)，其中缺少第一章内容。

软件构造的过程、系统和工具

软件构造的过程

  • 编码 programming
  • 重构 refactoring
  • 调试 debugging
  • 测试 testing
  • 动态代码分析
  • 代码评审
  • 构建 build

build
Validate Compile Link Test Package Install Deploy

编码

编程语言
IDE
建模语言: UML
UML Class Diagram:
UML Class Diagram

静态代评审

  • pair programming 结对编程
  • informal walkthrough 走查
  • 正式会议评审
  • 自动化评审

静态代码分析工具: CheckStuyle，SpotBugs, PMD for Java

动态代码分析

动态分析：要执行程序并观察现象、收集数据、分析不足，对代码的运行时状态和性能进行度量，发现代码中的潜在问题。

build - 狭义软件构造

build-time to run-time
使用build的典型场景:

  • 编译
  • 打包、测试
  • 自动生成文档


使你的程序在目标机器上可以运行
Jenkins

Build tools for Java:

  • Make
  • Ant
  • Maven
  • Gradle
  • Eclipse IDE

测试和测试优先的编程

设计顺序

spec $\rightarrow$ test $\rightarrow$ coding

测试分类

  • 单元测试：本课程关注
  • 集成测试
  • 系统测试：在最终配置环境下运行
  • 回归测试
  • 验收测试

白盒测试和黑盒测试

白盒测试：关注内部代码结构的测试
黑盒测试：不关注代码，只关注输入输出

基于样本的测试没有意义

Project A：Test-First Programming

用尽可能少的测试用例，找到尽可能多的错误

根据spec写测试用例，spec没提到的可以不用考虑

example:
BigInteger.multiply()的测试
(a, b)

  1. 基于等价类的划分
    • a+ b+
    • a+ b-
    • a- b+
    • a- b-
  2. 特殊情况
    1, -1, 0
  3. 边界
    a or b很大或很小

所以测试用例划分（方案不唯一）如下：

测试覆盖

  1. 笛卡儿积：全覆盖（如上边的BigInteger.multiply()）
    特点：特使完备，但代价高
  2. 覆盖每个取值
    特点：测试用例少，代价低，但覆盖度未必低

测试策略

测试时写注释，说明测试

数据类型与类型检验

基本数据类型（左）和变量数据类型（右）

能用 Primitives就不要用Object

静态类型语言和动态类型语言

静态类型语言在编译时进行类型检查

动态类型语言在运行时进行类型检查

静态类型检查和动态类型检查

静态类型检查

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

动态类型检查

  • 非法参数(如除以0)
  • 非法返回值
  • 空指针
  • 越界

可变对象和不可变对象

能用不可变就不用可变，不可变更安全。

collection都是可变对象。

可变对象的潜在危险：
A和B都是指向一个位置的对象，如果A改变了，那么B也会改变。

不得已用可变对象，那么我们通过防御性拷贝来避免这种危险。

1
return new StringBuilder("abc");


潜在危险，客户端调用Period.start()，得到的start和Period内部的start是同一个内存地址，客户端该边他得到的start，也就相当于改变了Period里的start。

举个例子List<String>类型的一个list，我们修改该list中的第一个String，List本身是改变了的，而内存不变；而一个String，我们修改他，他就会新建一个对象，内存自然就改变了。

Snapshot Diagram

基本数据类型

​ 直接指向值。

对象数据类型

单箭头/圆表示可变的，双箭头/圆表示不可变的（final & immutable object）。

复杂数据类型Arrays/Collections

Iterator - 可变数据类型 迭代器

用途：遍历List

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
	List<String> list = new ArrayList<String>();
	list.add("100");
	list.add("200");
	list.add("100");
	Iterator iter = list.iterator();
	for(;iter.hasNext();) {
		System.out.println(iter.next());
	}
}

Iterator是可变的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {
	List<String> list = new ArrayList<String>();
	list.add("100");
	list.add("100");
	list.add("200");
	list.add("100");
	Iterator<String> iter = list.iterator();
	for(;iter.hasNext();) {
		String s = iter.next();
		if(s.equals("100")) {
			iter.remove();
		}
	}
	System.out.println(list);
}

用iterator遍历的同时删除。

foreach遍历+list的remove会报错：

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
	List<String> list = new ArrayList<String>();
	list.add("100");
	list.add("100");
	list.add("200");
	list.add("100");
	for(String s : list) {
		if(s.equals("100"))
			list.remove(s);
	}
	System.out.println(list);
}
1
2
3
4
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
	at java.util.ArrayList$Itr.next(Unknown Source)
	at test.test.main(test.java:13)

ADT设计规约

Spec概述

Spec 给“供需双方”都确定了责任，在调用的时候要遵守。

用户和实现者的关系，用户不关心内部实现

spec不需要有函数实现细节。

行为等价性

客户端只关心输入输出，不关心内部实现，那么两个实现可以相互替换，并都遵循spec，他们就是行为等价的。

Spec结构

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

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

契约：如果前置条件满足 了，后必须

1
2
3
4
5
/**
 * @param precondition
 * @throws postcondition
 * @return postcondition
 */

对于mutable methods 或 parameters，除非在后置条件里声明过，否则方法内部不应该改变输入参数。

尽量要用immutable，而不要有以下这样的Spec。

Spec强弱

$S1 \geq S2$：

S2的前置条件s更弱，S1的后置条件更强。

spec 变强：更放松的前置条件 +更严格的后置条件

但二者强弱无法比较。

抽象数据类型ADT

再谈mutable和immutable

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

类型和操作的分类

  • 创建者creator：创建一个该类型的新对象。一个创建者可能会接受一个对象作为参数，但是这个对象的类型不能是它创建对象对应的类型。
  • 生产者producer：通过接受同类型的对象创建新的对象。例如， String类里面的 concat 方法就是一个生产者，它接受两个字符串然后据此产生一个新的字符串。
  • 观察者observer：接受一个同类型的对象然后返回一个不同类型的对象/值。例如List的 size方法，它返回一个 int。
  • 改造者mutator：改变对象的内容，例如 List的 add 方法，它会在列表中添加一个元素，只有mutable类有改造者。

构造者通常都是用构造函数实现的，例如 new ArrayList() ，但是有的构造体是静态方法（类方法），例如 Arrays.asList()和 String.valueOf() ，这样的静态方法也称为工厂方法。

例子

Integer.valueOf() creator

BigInteger.mod() producer

List.addAll() mutator

String.toUpperCase() producer

Set.contains() observer

Map.keySet() observer

BufferedReader.readLine() mutator

设计抽象类型

表示独立

这意味着它的使用和它的内部表示（实际的数据结构和实现）无关，所以内部表示的改变将对外部的代码没有影响。

表示泄露的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Represents a family that lives in a household together.
 * A family always has at least one person in it.
 * Families are mutable.
 */
class Family {
    // the people in the family, sorted from oldest to youngest, with no duplicates.
    public List<Person> people;

    /**
     * @return a list containing all the members of the family, with no duplicates.
     */
    public List<Person> getMembers() {
        return people;
    }
}

void client1(Family f) {
    // get youngest person in the family
    Person baby = f.people.get(f.people.size()-1);
    ...
}
  1. people 应为 private。
  2. getMembers()应该防御性拷贝。

如何测试ADT

  • 测试creators, producers, and mutators：调用observers来观察这些operations的结果是否满足spec；
  • 测试observers：调用creators, producers, and mutators等方法产生或改变对象，来看结果是否正确。
    等价类划分

    Rep Invariant and Abstraction Function

    R：表示空间（for programmer）

A：抽象空间（for user）

RI : R to True if R to A; R to False if R not to A;

表示不变性RI：某个具体的“表示”是否是“合法的”

也可将RI看作：所有表示值的一个子集，包含了所有合法的表示值

也可将RI看作：一个条件，描述了什么是“合法”的表示值 ->经常这么写

选择某种特定的表示方式R，进而指定某个子集是“合法”的(RI)，并为该子集中的每个值做出“解释”(AF)——即如何映射到抽象空间中的值。

RI : rep invariant

AF: abstract function

利用RI和AF设定规则，并写出checkRep()，来检查自己写的方法。

表示泄露的安全声明：

两种方法：

Spec of Methods:

1
2
3
4
5
6
// Rep invariant:
//    声明什么样的field是合法的，也就是R中什么样的变量会映射到A中
// Abstraction function:
//    AF(field1, field2, ...) = ... 声明R到A的映射方法
// Safety from rep exposure:
//    自证清白，你写的类为什么没有表示泄露

面向对象编程

Interface

Override 重写：

super() 调用父类的方法

抽象类

多态

特殊多态

function overloading

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class OverloadExample {
	public static void main(String args[]) {
		System.out.println(add("C","D"));
		System.out.println(add("C","D","E"));
		System.out.println(add(2,3));
	}
	public static String add(String c, String d) {
		return c.concat(d);
	}
	public static String add(String c, String d, String e){
		return c.concat(d).concat(e);
	}
	public static int add(int a, int b) {
		return a+b;
	}
}

重载

overload要有不同的参数列表

父类和子类的overload

Which overridden version of the method to call is decided at runtime based on object type, but which overloaded version of the method to call is based on the reference type of the argument passed at compile time.

重写在运行阶段基于对象类型来决定执行哪个版本，但重载在编译阶段基于引用类型来执行哪个版本。

Overriding Object methods

equals() hasCode() toString()

参数化多态：generics 泛型

子类型多态、包含多态

Equality

不可变类的equals()

equals()满足自反、对称、传递性。

  • 利用AF定义equals()，即AF(a) = AF(b) 则 a.equals(b)
  • 站在外部观察者(客户端)角度，观察到相同值的相等

1554099094662

== vs. equals()

  • == 引用等价性
  • equals() 对象等价性

重写equals()

Object.equals()

1
2
3
boolean equals(Object obj) {
    return this == obj;
}

重写equals()

1
2
3
boolean equals(Object obj) {
    ...
}

不要重载equals()

1
2
3
boolean equals(Name obj) {
    ...
}

因为set的contains()等方法，都是基于equals(Object obj)的。

1554102076705

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Name {
	private final String first, last;
	public Name(String first, String last) {
		if (first == null || last == null)
			throw new NullPointerException();
		this.first = first;
		this.last = last;
	}
	public boolean equals(Name o) {
		return first.equals(o.first) && last.equals(o.last);
	}
	public int hashCode() {
		return 31 * first.hashCode() + last.hashCode();
	}
	public static void main(String[] args) {
		Set<Name> s = new HashSet<>();
		s.add(new Name("Mickey", "Mouse"));
		System.out.println(s.contains(new Name("Mickey", "Mouse")));
		Name a = new Name("Mickey", "Mouse");
		Name b = new Name("Mickey", "Mouse");
		System.out.println(a.equals(b));
	}
}
// 输出为 false \n true

重载equals()使用getClass()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Name {
	private final String first, last;
	public Name(String first, String last) {
		if (first == null || last == null)
			throw new NullPointerException();
		this.first = first;
		this.last = last;
	}
	@Override public boolean equals(Object o) {
		if (this.getClass() != o.getClass())
			return false;
		Name n = (Name) o;
		return n.first.equals(first) && n.last.equals(last);
	}
	public int hashCode() {
		return 31 * first.hashCode() + last.hashCode();
	}
	public static void main(String[] args) {
		Set<Name> s = new HashSet<>();
		s.add(new Name("Mickey", "Mouse"));
		System.out.println(s.contains(new Name("Mickey", "Mouse")));
	}
}

1554102827264

重写hashCode()

重写equals()就一定要重写hashCode()。

考虑我们如何从向一个容器内添加一个元素，首先要判断这个元素是否在容器中已经存在了，低效率的做法是一次equals()比较。高效率的做法是我们对于每个ADT定义一个hashCode()，之和相同的hashCode()值的进行比较。

设计ADT的原则：

  • 如果两个对象根据equals()比较是相等的，那么调用两个对象的hashCode()必须返回相同的整数结果。
  • 如果两个对象根据equals()比较是不等的，则hashCode()不一定得返回不同的整数。

不相等的对象，也可以映射为同样的hashCode()，但性能会变差。

可变对象的equals()和hasCode()

可复用性的度量、形态与外部表现

1、

1554683225042

2、

1554683254001

Delegation委托

委托：一个对象请求另一个对象的功能

在运行时建立关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Edge {
	private int weight;
	public int getWeight() {
		return weight;
	}
	public void sort(List<Edge> edges) {
		EdgeComparator comparator = new EdgeComparator();
		Collections.sort(edges, comparator);
	}
}
class EdgeComparator implements Comparator<Edge>{
	@Override
	public int compare(Edge o1, Edge o2) {
		if(o1.getWeight() > o2.getWeight())
			return 1;
		else if (o1.getWeight() == o2.getWeight()) return 0;
		else return -1;
	}
}

Edge委托Comparator

何时继承 何时委托

如果A只需要复用B中的一小部分方法，用委托

如果A复用B中的大部分方法，用继承

设计模式

Adaptor pattern

例如：

已有接口adaptee，给定左下角左边和长宽，画出长方形

客户端要求给定左下角、右上角坐标，画出长方形

1554855890452

1554855997805

Decorator pattern

假设我们要设计三个类：

  • UndoStack 可撤销的栈
  • SecureStack 需要密码的栈
  • SynchronizedStack 可同步当前操作的栈

但我们现在要设计可撤销且需要密码的栈，我们的做法是如下

设计模式：运用delegate

1554856758353

1554856774934

这个Delegation的stack可以为上述三个stack的任意一个

1554856789413

1
SecureStack s = new SecureStack(new SynchronizedStack(new UndoStack(s));

可撤销、需要密码、可同步当前操作的栈

Façade pattern

对于类似的、复杂的ADT的接口，我们将它封装为一个简单的接口，通过传入参数，在内部我们通过case/if来判断调用哪个接口，这样的话，方便了客户（苦逼了程序员）。

Strategy Pattern

1554857465233

ShopingCart的pay传入PaymentStrategy参数，确定调用哪个子类。

1554857610286

Template Method

若干方法待实现，但这些方法的执行顺序固定

1554858678016

例如：

1554858749859

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public abstract class OrderProcessTemplate {
	public boolean isGift;
	public abstract void doSelect();
	public abstract void doPayment();
	public final void giftWrap() {
		System.out.println("Gift wrap done.");
	}
	public abstract void doDelivery();
	public final void processOrder() {
		doSelect();
		doPayment();
		if (isGift)
			giftWrap();
		doDelivery();
	}
}

Iterator pattern

让自己的集合类实现Iterable接口，并实现自己的独特Iterator迭代器(hasNext, next, remove)，允许客户端利用这个迭代器进行显式或隐式的迭代遍历.

工厂模式

健壮性和正确性

错误与异常处理

1557101843523

内部错误：程序员通常无能为力，一旦发生，想办法让程序优雅的结束

异常：你自己程序导致的问题，可以捕获、可以处理

try catch finally

  • Declaring exceptions (throws) 声明“本方法可能会发生XX异常”
  • Throwing an exception (throw) 抛出XX异常
  • Catching an exception (try, catch, finally) 捕获并处理XX异常

checked exception or unchecked exception

unchecked异常，如RuntimeException，一般不会throw和catch，但是可以throw和catch

checked异常，必须throw catch

  • 如果客户端可以通过其他的方法恢复异常，那么采用checked exception；
  • 如果客户端对出现的这种异常无能为力，那么采用unchecked exception；
  • 异常出现的时候，要做一些试图恢复它的动作而不要仅仅的打印它的信息。

有异常抛出的Spec比没有异常抛出的更弱

Spec中写写抛出的checked异常

throws哪些异常

  • 你所调用的其他函数抛出了一个checked exception——从其他函数传来的异常

  • 当前方法检测到错误并使用throws抛出了一个checked exception——你自己造出的异常

LSP：子类重写的方法抛出的异常不能多于父类方法（子类可以无条件取代父类）

定义一个异常：

1557104038303

finally

不管是否有异常，都会执行finally。

正常执行：

1557105370511

遇到IOException：

1557105292676

遇到其他异常：

1557105414459

finally一定会执行

1
2
3
4
5
try {
    return true;
} finally {
    return false;
}

返回false

stack trace

1557105825736

stack：

1557105836918

JAVA内存管理

堆和栈

1557709995078

堆和栈

每个进程有一个栈，堆上创建的对象可被所有线程共享引用

堆

堆上保存的数据：

  • 对象类型
  • 数组类型

栈

栈上保存的数据：

  • 局部基本数据类型

堆的其他作用：

  • 传参数以及返回参数（的reference）
  • 计算表达式的中间结果
  • 局部变量（的reference）

method area

  • 用于存储被VM加载的类信息、常量、静态变量等

Perm(Java7之前的method area)在堆上，Metaspace独立。

本地方法栈

“A native method is a Java method whose implementation is provided by non-java code.”

用于支持native方法的执行，存储了每个native方法的执行状态。本地方法栈和虚拟机栈他们的运行机制一致，唯一的区别是，虚拟机栈执行Java方法，本地方法栈执行native方法。在很多虚拟机中（如Sun的JDK默认的HotSpot虚拟机），会将虚拟机栈和本地方法栈一起使用。

1557711102277

1557711126749

垃圾回收

传统垃圾回收算法

  • 引用计数
  • 标记-整理
  • 标记-清除
  • 复制

分“代”回收的GC算法

按照存活周期来分配他在堆上的位置

存活周期短的在Young，长的在Old

1557880073764

  1. 绝大多数刚刚被创建的对象会存放在伊甸园空间。

  2. 在伊甸园空间执行了第一次GC之后，存活的对象被移动到其中一个幸存者空间。

  3. 此后，在伊甸园空间执行GC之后，存活的对象会被堆积在同一个幸存者空间。

  4. 当一个幸存者空间饱和，还在存活的对象会被移动到另一个幸存者空间。之后会清空已经饱和的那个幸存者空间。

  5. 在以上的步骤中重复几次依然存活的对象，就会被移动到老年代。

1557880170862

  • 针对年轻代：只有一小部分对象可较长时间存活，故采用copy算法减少GC代价，Minor GC
  • 针对年老代：这里的对象有很高的幸存度，使用Mark-Sweep或Mark-Compact算法，full GC
  • 只有当某个区域不能再为对象分配内存时（满）,才启动GC，full GC

如果old generation满了，则启动full GC

1557880398612

IO/算法性能