Functional Programming in Swift(五)

最近事情多多,拖了两周,终于写完了。

Chapter 6 QuickCheck

本文是《Functional Programming in Swift》中第六章的笔记,如果你感兴趣,请购买英文原版。

近些年 testing 变得非常盛行,很多流行的库都能用自动持续集成工具进行测试,本章我们用 swift 来构建一个很小的测试库,并采用迭代的方式一步步地增强功能。我们写单元测试的时候,输入的数据通常是由程序员定义的静态数据,比如写一个加法操作的单元测试,验证 1 + 1 = 2,如果加法操作出问题了,测试就会 fail 掉,再进一步,我们测试加法交换率,也就是 a + b 等于 b + a,为了测试我们需要写出 42 + 7 等于 7 + 42 这样的测试例。

QuickCheck 是 Haskell 的一个用来随机测试的库,相对于单元测试,QuickCheck 每一个测试函数都能应对特殊的输入。QuickCheck 允许你描述你函数的抽象属性,并生成测试来验证这些属性。QuickCheck 的目标是找出每个独立于这些属性的条件边界。这一章我们来创建一个 Swift 版本的 QuickCheck。

同样是用例子来阐述,假设我们要验证加法交换率,先来写个函数来检查:

func plusIsCommutative(x: Int, y: Int) -> Bool {  
    return x + y == y + x
}

用 QuickCheck 来测试只需要调用 check 函数即可

check("Plus should be commutative", plusIsCommutative)

> "Plus should be commutative" passed 100 tests.
> ()

check 方法通过一遍又一遍地传递给 plusIsCommutative 函数两个随机值的方式进行调用。如果 plusIsCommutative 返回 false,则测试失败。这里需要理解的是:我们可以描述代码的抽象属性,就如同这里的加法交换率一样(用函数来描述),check 函数使用这个抽象属性来进行单元测试,比使用手写的单元测试能达到更好的代码覆盖率。

当然不是所有的测试都能通过,比如我们要测试减法交换率:

func minusIsCommutative(x: Int, y: Int) -> Bool {  
    return x - y == y - x
}

这个时候在运行 QuickCheck,测试就会 failing

check("Minus should be commutative", minusIsCommutative) 

> "Minus should be commutative" doesn't hold: (0, 1)
> ()

改用 swift 的尾随闭包来写,就不需要定义抽象属性了:

check("Additive identity") { (x: Int) in x + 0 == x } 

> "Additive identity" passed 100 tests.
> ()

下面来介绍一些 QuickCheck 实现的细节。

1. Building QuickCheck

为了实现 swift 版本的 QuickCheck ,我们需要做下面一些工作:

  • 首先,需要为不同类型生成随机值
  • 把这些随机值作为参数传递给 check 函数
  • 如果测试失败,我们需要尽量缩小测试数据的范围。比如,在测试 100 个元素的数组时失败了,我们需要缩小数组的范围,然后查看到底是哪里出错了。
  • 最后,我们需要做一些工作使 check 函数更加通用(泛型)

Generating Random Values

首先来声明一个 protoocol 来定义如何生成随机值,该协议只有一个方法,返回一个 self:

protocol Arbitrary {  
    class func arbitrary() -> Self
}

我们先来写一个 Int 的实例(这里的 arc4random 函数只能生成正数,而真正的实现应该也能生成负数)

extension Int: Arbitrary {  
    static func arbitrary() -> Int {
        return Int(arc4random()) 
    }
}

现在能生成随机整数了:

Int.arbitrary()

> 4135064904

为了生成随机字符串,我们需要做更多的工作,我们先从随机字符开始:

extension Character: Arbitrary {  
    static func arbitrary() -> Character {
        return Character(UnicodeScalar(random(from: 65, to: 90))) 
    }

    func smaller() -> Character? { return nil } 
}

我们使用上面的随机函数生成一个长度 x(0 ~ 40)之间。接着生成 x 个随机字符,然后把他们连成一个字符串。

func tabulate<A>(times: Int, f: Int -> A) -> [A] {  
    return Array(0..<times).map(f)
}
// 给定一个范围,生产一个随机整数
func random(#from: Int, #to: Int) -> Int {  
    return from + (Int(arc4random()) % (to-from))
}

extension String: Arbitrary {  
    static func arbitrary() -> String {
    // 生成 0 到 40 的随机整数
        let randomLength = random(from: 0, to: 40)
        // 生成数量为 randomLength 的字符,每个字符都是随机的
        let randomCharacters = tabulate(randomLength) { _ in
            Character.arbitrary() 
        }
        // 将数组中所有的字符组合成一个字符串
        return reduce(randomCharacters, "") { $0 + String($1) } 
    }
}

上面我们先使用 tabulate function 来填充一个长度从 0 到 times - 1 的数组,使用 map 函数来生成数组元素:f(0), f(1),...,f(times-1)。而 String 的 arbitrary extension 使用 tabulate 函数来组成包含随机字符的数组。这样就能通过调用 String 的类方法来实现随机字符串:

String.arbitrary()

> VPWSHMNM

Implementing the check Function

先实现第一个 check 函数,该函数遍历输入的参数,如果找到反例,打印并返回,否则测试通过

func check1<A: Arbitrary>(message: String, prop: A -> Bool) -> () {  
    for _ in 0..<numberOfIterations {
        let value = A.arbitrary() 
        if !prop(value) {
            println("\"\(message)\" doesn't hold: \(value)")
            return
        } 
    }
    println("\"\(message)\" passed \(numberOfIterations) tests.") 
}

这里虽然可以使用 map 或 reduce ,但用 for loop 显然更加明了。下面我们这样来测试:

func area(size: CGSize) -> CGFloat {  
    return size.width * size.height
}

check1("Area should be at least 0") { size in area(size) >= 0 }

> "Area should be at least 0" doesn't hold: (4403.19046829901,-3215.23175766115)
> ()

这个例子使用 QuickCheck 找出条件边界,如果 size 中有一部分为负值,最终结果就返回一个负值。当作为 CGRect 的一部分使用,CGSize 是可以有负值的,当我们写原始的单元测试,可以很容易的检视到这种情况,因为sizes一般通常都为正值。

2. Making Values Smaller

使用 check1 在 字符串上,将会收到很长的错误信息

check1("Every string starts with Hello") { (s: String) in  
    s.hasPrefix("Hello")
}

> "Every string starts with Hello" doesn't hold: 
> ()

通常,更小的 counterexample ,更容易定位代码中的错误。一个主要原则是,尝试缩减输入来把问题定位在一个较小的范围之内。我们使用程序来自动完成这一缩减过程,而不是将重担抛给用户。要做到这一点,我们需要创建一个额外的 Smaller protocol,它只做一件事情,尝试缩减 counterexample:

protocol Smaller {  
    func smaller() -> Self?
}

注意返回类型是一个可选类型。

在我们的实例中,对于整数,我们尝试用 2 来整除,直到接近 0:

extension Int: Smaller {  
    func smaller() -> Int? {
    // 削减一半
        return self == 0 ? nil : self / 2  
    }
}

// 测试一下
100.smaller()

> Optional(50)

对于字符串,我们仅仅丢弃首字符(触发字符为空)

extension String: Smaller {  
    func smaller() -> String? {
        return self.isEmpty ? nil : dropFirst(self)
    } 
}

为了使用在 check 函数中使用 Smaller protocol,我们需要缩减由 check 函数所产生的 test data,要做到这一点,我们需要重新定义我们的 Arbitrary protocol 来扩展 Smaller protocol:

protocol Arbitrary: Smaller {  
    class func arbitrary() -> Self
}

Repeatedly Shrinking

我们现在重定义 check 函数,来缩减触发失败 test data 的范围。

要做到这一点首先需要一个 iterateWhile 函数,该函数带一个条件和一个初始值,然后反复的递归调用。

func iterateWhile<A>(condition: A -> Bool, initialValue: A, next: A -> A?) -> A {  
    if let x = next(initialValue) { 
        if condition(x) {
            return iterateWhile(condition, x, next) 
        }
    }
    return initialValue 
}

使用 iterateWhile 我们可以反复缩减 counterexamples

func check2<A: Arbitrary>(message: String, prop: A -> Bool) -> () {  
    for _ in 0..<numberOfIterations {
        let value = A.arbitrary() 
        // 不断削减直到找出不满足 prop 的
        if !prop(value) {
            let smallerValue = iterateWhile({ !prop($0) }, value) { 
                $0.smaller()
            }
            println("\"\(message)\" doesn't hold: \(smallerValue)") 
            return
        } 
    }
    println("\"\(message)\" passed \(numberOfIterations) tests.") 
}

这个函数生成随机输入值,检查是否满足属性参数,并且对反复缩减直到找出那个不满足的反例。使用 iterateWhile 而不是 简单的 loop 是因为可以保持 code 更加易读。

3. Arbitrary Arrays

当前,check2 只支持 Int 和 String,我们定义一个新的 extensions 来扩展到更多的类型。比如 Bool 以及生成更复杂类型的随机数组。作为启发,我们先写一个快排

func qsort(var array: [Int]) -> [Int] {  
    if array.isEmpty { return [] }
    let pivot = array.removeAtIndex(0)
    let lesser = array.filter { $0 < pivot }
    let greater = array.filter { $0 >= pivot } 
    return qsort(lesser) +  [pivot] + qsort(greater)
}

可以写一个属性来检查我们这个 快排

check2("qsort should behave like sort") { (x: [Int]) in  
    return qsort(x) == x.sorted(<)
}

编译器会警告上面的 [Int] 没有遵守 Arbitrary protocol,再实现他之前,我们先来实现 Smaller。

extension Array: Smaller {  
    func smaller() -> [T]? {
        if !self.isEmpty {
        // 去掉数组的第一个元素
            return Array(dropFirst(self))
        }
        return nil
    } 
}

再写一个函数,能够生成一个随机长度的数组,包含任意类型,且都遵守 Arbitrary protocol

func arbitraryArray<X: Arbitrary>() -> [X] {  
    let randomLength = Int(arc4random() % 50)
    return tabulate(randomLength) { _ in return X.arbitrary() }
}

现在,我们想要定义一个 extension,使用上面的 arbitraryArray 来提供随机数组。但是,为了定义这个数组实例,需使数组内的所有元素类型都要是 Arbitrary 的实例。也就是说,为了生成一个包含随机数的数组,我们第一步需要确认的是:我们有能力生成随机数,要满足这些理论上需这么写:数组的这些元素都应该遵循 arbitrary protocol:

extension Array<T: Arbitrary>: Arbitrary {  
    static func arbitrary() -> [T] {
    ... 
    }
}

不幸的是,写出这样的 extension 让是不大可能的,我们可以让数组元素遵守Arbitrary 但没办法说让数组类型遵守Arbitrary。我们需要另辟蹊径,比如说修改 check2

我们已经明确问题的所在:check2<A> 需要 A 的 type 是 Arbitrary,一个解决方案是放弃这一类型要求,而用声明必要( necessary )函数来解决,这里是 smaller and arbitrary,他们将作为参数传递。

第一步先定义一个辅助结构体包含这两个函数:

struct ArbitraryI<T> {  
    let arbitrary: () -> T 
    let smaller: T -> T?
}

第二步,写一个 helper function ,并且将上面的 ArbitraryI 作为参数。这个 checkHelper 与之前的 check2 非常相似,唯一不同的是 arbitrary 和 smaller 函数定义的位置,在 check2 中,他们被限定在 泛型 中,而在 checkHelper 中,他们被明确地通过 ArbitraryI 结构体进行传递。

func checkHelper<A>(arbitraryInstance: ArbitraryI<A>,  
                        prop: A -> Bool, message: String) -> () {
    for _ in 0..<numberOfIterations {
        let value = arbitraryInstance.arbitrary() 
        if !prop(value) {
            let smallerValue = iterateWhile({ !prop($0) }, 
                    value, arbitraryInstance.smaller)
            println("\"\(message)\" doesn't hold: \(smallerValue)")
            return
        } 
    }
    println("\"\(message)\" passed \(numberOfIterations) tests.") 
}

这也算是一项标准技术:我们将需要的信息明确地通过参数传递,而不是使用 protocol 中定义的 functions。这样做的好处是,不再依赖 Swift 去推断所有必需信息,而是拥有完全的控制权。

第三步当然是用 checkHelper 来重新定义 check2 函数。如果明确需要定义的 Arbitrary ,那么我们就能用 ArbitraryI 结构体来封装然后调用 checkHelper

func check<X: Arbitrary>(message: String,  
                        prop: X -> Bool) -> () {
    let instance = ArbitraryI(arbitrary: { X.arbitrary() }, 
                                smaller: { $0.smaller() })
    checkHelper(instance, prop, message) 
}

如果有个类型无法定义成所渴望的 Arbitrary 实例,比如数组,我们可以覆盖 check 函数然后构造我们需要的 ArbitraryI 结构体:

func check<X: Arbitrary>(message: String,  
                            prop: [X] -> Bool) -> () {

    let instance = ArbitraryI(arbitrary: arbitraryArray,
                                smaller: { (x: [X]) in x.smaller() })   checkHelper(instance, prop, message)
}

现在,我们最终可以运行验证我们的快排实现了,生产大量的随机数组并传递给我们的测试:

check("qsort should behave like sort") { (x: [Int]) in  
    return qsort(x) == x.sorted(<)
}

> "qsort should behave like sort" passed 100 tests. 
> ()

4. Using QuickCheck

虽然 TDD 有点违反直觉,但有证据表明人们依赖测试驱动开发不仅仅是验证代码的正确性,他还影响代码的设计风格,能够使代码趋于简单明了。有这么一个结论:如果能针对某个类写出简单的测试代码,那么意味着这个类是充分去耦合的。

对于我们的 QuickCheck 来说一样适用,通常利用现有代码事后添加 QuickCheck 测试并不是很容易,尤其当你使用面向对象架构,要依赖其他类或使用可变状态时。但是一旦反转顺序,利用 QuickCheck 驱动开发,你将会看到,他是如何影响你的代码设计的。 QuickCheck 强迫你去思考那些 functions 必须满足的抽象属性。单元测试只能够断言 3 + 0 是否等于 3 + 0,而使用 QuickCheck 检查则更加通用。

一开始就在 high-level 的 QuickCheck,能够使你的代码更加 模块化引用透明referential transparency

QuickCheck 在有状态的函数和 APIs 下工作的并不好。更适合函数式编程么?

这样一来,把你的测试代码写在 QuickCheck 前面能够使你的最终代码保持简洁。

5. Next Steps

这个库虽然远没有完成,但目前已经相当有用了,下面有几个地方今后可以持续改进一下:

  • 缩减还是太简单了:比如对于数组,我们仅仅移除了第一个元素,但想要移除某个元素呢,再或要使数组中的元素变得更小呢。当前是返回了一个可选的被缩减过的值,但要想生产一系列值呢,在之后本书最后一章,我们看到如何生成一个 lazy list 的结果,这里我们可以使用同样的技术。
  • 随机实例太简单:对于不同的数据类型,我们想要更复杂的随机实例,比如当生成随机枚举类型时,我们想要根据某种频率生成特定的 cases。另外,我们想要生成一些限定的实例,比如排过序的非空数组。当我们写这些随机实例( Arbitrary instances )时,可以定义一些 help function 来帮助我们达成目标。
  • 为生成的测试数据分类:如果我们生成了很多长度为 1 的数组,我们可以将其归为 “trivial” (无价值)的测试例下,Haskell 的类库提供了这样的分级,所以这些想法可以直接进行移植。
  • 我们想要更好地控制生成的随机对象的尺寸。在 Haskell 版本中的 QuickCheck,Arbitrary 协议拥有一个额外的 size 参数,用来限制生成的随机对象尺寸。这样 check function 一开始就从测试 small values 开始,随着测试的深入,check function 逐步增大输入参数的尺寸,寻找更大的边界和反例(这和我们本章找到反例再逐步缩小定位不同)
  • 我们想要用特定 seed 初始化随机函数,这样就能重复地生成 test case,方便我们更容易地找出令程序失败的测试例。

-EOF-

如果感觉此文对你有帮助,请随意打赏支持作者 😘

chengway

认清生活真相之后依然热爱它!

Subscribe to Talk is cheap, Show me the world!

Get the latest posts delivered right to your inbox.

or subscribe via RSS with Feedly!