Vintage QuickCheck 的基本要素

2023-04-27   出处: substack.com  作/译者:KURT/lukeaxu

本系列的第二篇文章将介绍原始属性测试库QuickCheck的设计和实现。第一篇文章是《属性测试#1:它到底是什么?》。即使您已经知道什么是属性测试,熟悉一下示例也是值得的。

完整的代码可以在GitHub上找到链接,特别是example.py和vintage.py文件。

上次我们讨论了为什么要编写基于属性的测试,并介绍了基于属性的测试库应提供的基本功能。现在,我们将深入探讨一个带有随机生成的基于属性的测试库的实现方式——特别是由 OG QuickCheck 提出的方法。我们将在仅有几页代码(包括注释和示例)中创建一个迷你参考实现!

在其核心,任何现代 PBT 库都提供三个相关的模块。

第一个模块允许定义和组合生成器——一些用于创建原始类型生成器的函数,限制或扭曲生成的值,并将它们组合以生成自定义类型。例如,要生成Person对象的age字段,您需要将其限制为正值,例如100。要编写Person对象的生成器,您需要将age生成器和名称生成器组合起来。我将其称为生成器模块。

第二个模块允许定义属性,这意味着指定一些参数化测试,并指定要使用的生成器。它还包括观察和记录生成值的分布的方法,以便您可以确信生成的值是合理的。我将其称为属性模块。

第三个也是最后一个模块允许根据某些配置运行一系列测试,例如要生成的测试用例数量,测试应运行的时间长度等。我将其称为运行器模块。

预先一睹为快,本文末尾我们将能够定义生成器,并为我们在上一篇文章中讨论的sort_by_age属性运行测试。回想一下,Person被定义为:

@dataclass(frozen=True)
class Person:
    name: str
    age: int

我们将能够创建一个随机Person对象的生成器,如下所示:

ages = int_between(0,100)

letters = map(chr, int_between(ord('a'), ord('z')))

simple_names = map("".join, list_of_length(6, letters))

persons = mapN(Person, (simple_names, ages))

lists_of_person = list_of(persons)

以上是五个随机生成器,用于生成随机年龄、小写字母、由6个随机小写字母组成的简单名称、人物对象和人物对象列表。我们将在下面实现和讨论int_betweenmapmapNlist_of函数,它们是我们库的生成器模块的一部分。

我们还可以通过for_all函数定义属性:

def is_valid(persons_in: list[Person], persons_out: list[Person]) -> bool:
    same_length = len(persons_in) == len(persons_out)
    sorted = all(persons_out[i].age <= persons_out[i + 1].age
                for i in range(len(persons_out)-1))
    unchanged = { p.name for p in persons_in } == { p.name for p in persons_out }
    return same_length and sorted and unchanged


prop_sort_by_age = for_all(
    lists_of_person,
    lambda persons_in: is_valid(persons_in, sort_by_age(persons_in))
)

最后,通过test函数,我们将检查该属性是否适用于100个随机生成的列表:

> test(prop_sort_by_age)
Success: 100 tests passed.

所有都是随机的。

首先,让我们专注于如何创建生成器API-因为我们将看到另外两个模块完全基于它。

首先的问题是-为什么要费心去创建生成器API,而不是直接使用内置的随机API?大多数语言都有一个,这里是Python的random module

主要原因是抽象化——虽然现在看起来可能有点过早,但在接下来的文章中,我们将多次更改生成器的实现,以添加功能和更改其行为,而我们不必更改API的用户。这是强大的,无论从用户还是维护者的角度来看——维护者有相当大的自由度来改进,而不会太过于打扰用户。一个简单的例子是更改为不同的伪随机数生成器,它更快或具有更好的属性。

另一个原因是典型的内置随机API相当差——Python的API比其他一些语言更具有特色,但是编写上述“Person”生成器仍需相当多步骤。

话不多说,让我们首先尝试一下生成器的表示应该是什么。由于生成器是可以在被要求时产生新的随机值的东西,因此最简单的表示形式是一个没有参数的函数,返回一个值。为了使代码更易读和安全,我们将其包装在一个小类中:

class Random(Generic[Value]):
    def __init__(self, generate: Callable[[], Value]):
        self._generate = generate

    def generate(self) -> Value:
        return self._generate()

非常简单——“Random”是一个类,它只是包装一个生成某种通用类型值的函数。为了使接下来的内容可见,让我们先实现一个简单的函数来从生成器中采样实际值——尽管我们还没有任何要采样的值!

def sample(gen: Random[T]) -> list[T]:
    return [gen.generate() for _ in range(5)]

sample函数接受一个Random实例,并调用其generate()方法5次,将结果收集到一个列表中。

有了这个函数,我们现在可以构建越来越强大的函数,以便创建和组合Random生成器,从而最终生成一个Person值的列表——这正是我们需要能够检查sort_by_age属性的特性。

让我们编写可能的最简单的生成器——始终生成相同的值。

对于每个新函数,我将首先给出实现和使用示例。然后我将展示采样生成器的输出。

def constant(value:T) -> Random[T]:
    return Random(lambda: value)

pie = constant(math.pi)

constant接受某个值作为参数,并创建一个Random实例,该实例始终生成该值:

> sample(pie)
[3.141592653589793,
    3.141592653589793,
    3.141592653589793,
    3.141592653589793,
    3.141592653589793]

太棒了。现在让我们来点更有趣的。

def int_between(low: int, high: int) -> Random[int]:
    return Random(lambda: random.randint(low, high))

ages = int_between(0,100)

int_between 函数创建了一个整数生成器,用于生成指定范围内的整数。它是 Python 的 random.randint 函数的简单封装。让我们使用它来生成合理的人年龄:

> sample(ages)

以上代码将生成如下年龄列表:

[37, 15, 1, 62, 21]

好了,现在我们已经完成了一个字段的生成,接下来我们该如何为 Person 生成姓名呢?生成随机字母似乎是一个不错的开始。由于我们已经知道如何生成整数,并且将整数转换为字母也很简单,因此我们应该能够在 int_between 的基础上构建出字母生成器。将生成的值转换为另一种类型是一个普遍的需求,这个想法类似于使用内置函数 map 来处理可迭代对象。因此,让我们添加 map 函数,并使用它来编写一个小写字母生成器。

def map(f: Callable[[T], U], gen: Random[T]) -> Random[U]:
    return Random(lambda: f(gen.generate()))

letters = map(chr, int_between(ord('a'), ord('z')))

map 函数接受一个函数和一个 Random 实例,然后将该函数应用于底层生成器的每个值。

> sample(letters)
['t', 'm', 's', 'u', 'c']

这很好,但是一个单独的字母并不能构成一个可信的名字。我们可以再次映射并重复相同的字母多次,但我相信你会同意,zzzzz并不是一个有趣的名字。我们想要的是一个运行给定生成器N次并组合结果的方法。

答案是:mapNmapN将一个函数应用于N个生成器,就像map将一个函数应用于单个生成器一样(因此它实际上比我们在这个特定示例中需要的更通用)。您可能更熟悉的相关函数是zip,它将输入组合成一个元组。

def mapN(f: Callable[...,T], gens: Iterable[Random[Any]]) -> Random[T]:
    return Random(lambda: f(*[gen.generate() for gen in gens]))

有了mapN,我们可以编写一个list_of_length函数,该函数生成一个给定长度的列表,其中每个元素都是从给定的Random生成器生成的:

def list_of_length(l: int, gen: Random[T]) -> Random[list[T]]:
    gen_of_list = mapN(lambda *args: list(args), [gen] * l)
    return gen_of_list

通过使用mapN,我们终于能够编写一个相当合理的Person生成器了:

simple_names = map("".join, list_of_length(6, letters))
persons = mapN(Person, (simple_names, ages))
> sample(persons)
[Person(name='vuaufc', age=38),
    Person(name='kmvmpy', age=34),
    Person(name='wiuoph', age=34),
    Person(name='cvuxbu', age=72),
    Person(name='fykqmn', age=33)]

很高兴见到你,vuaufc先生!

好吧,也许这些名字并不是最可信的,但是它们对于我们的目的来说已经足够了,我们最终要测试sort_by_age

作为谜题的最后一部分,我们想要生成Person列表。目前,我们只能使用list_of_length生成给定长度的列表。不破坏抽象(例如直接使用random),我们还不能生成具有随机长度和随机元素的列表。这是因为我们没有办法编写一个生成器,它依赖于另一个生成器生成的随机值 - 我们根本无法将它们组合在一起。(如果你愿意,可以尝试只使用到目前为止的函数来编写它)

这就是以下函数的用处:

def bind(f: Callable[[T], Random[U]], gen: Random[T]) -> Random[U]:
    return Random(lambda: f(gen.generate()).generate())

在深入讨论其实现细节之前,让我们先看看如何使用它:

def list_of(gen: Random[T]) -> Random[list[T]]:
    # 生成长度为0到10之间的随机整数
    length = int_between(0, 10)
    # 返回一个随机列表,列表长度为上面生成的随机整数,列表中的元素由传入的随机生成器生成
    return bind(lambda l: list_of_length(l, gen), length)

# 生成一个由Person对象组成的随机列表
lists_of_person = list_of(persons)

# 生成多个随机列表,每个列表中包含随机数量的Person对象
# 示例输出如下:
[[Person(name='rsgiud', age=81), Person(name='ywcelx', age=55)],
 [Person(name='bskmxa', age=99), Person(name='jaonqc', age=55),
  Person(name='igelts', age=67)],
 [Person(name='yuhtkg', age=78)],
 [Person(name='coessh', age=43), Person(name='fpjnqi', age=18),
  Person(name='fjojvw', age=86), Person(name='tbneue', age=97),
  Person(name='ejirnj', age=76)],
 [Person(name='wopfbo', age=22), Person(name='yjgfkf', age=39),
  Person(name='xsslyn', age=34), Person(name='kjpqus', age=12),
  Person(name='cjlldt', age=24), Person(name='bqthxy', age=29),
  Person(name='ttqlhx', age=20), Person(name='wyumfv', age=99),
  Person(name='ucdeqz', age=14), Person(name='eqrxir', age=41)]]

请注意,有5个列表,每个列表的长度都是随机选择的。

bind函数是如何工作的?它首先运行给定的生成器,并将结果值传递给f函数。f函数将该值作为参数,并返回一个新的生成器,然后依次运行。用户可以编写f函数并从gen中获取值,这样就可以表达我们需要的依赖关系——我们现在可以生成一个随机列表长度,然后使用bind将其连接到生成固定长度的随机列表的生成器中。

在回顾我们的生成器模块之前,有一个bind函数的实现细节值得一提。人们很容易认为实现可以简化为:

def bad_bind(f: Callable[[T], Random[U]], gen: Random[T]) -> Random[U]:
    # let's get rid of the lambda
    return Random(f(gen.generate()).generate)

不幸的是,这并不起作用——它只从gen中生成一次,并应用f函数一次,这意味着在这个例子中,它将创建一个生成器,它只会选择一个随机长度,然后永远返回该长度的随机列表。

这就是一直映射下去的道理。

通过一小部分但精美的函数库——int_betweenconstantmapmapNbind,我们可以生成所需的 Person 对象列表。通过像choice(可以在源代码中找到,是基于bind实现的)和filter这样的小改动,这些函数的组合就足以成为任何生成器模块的核心。

正如我们在上一篇文章中提到的,这些函数有时被称为“组合子”,因为它们被设计成可以无限组合。所有函数都返回一个Random对象,因此可以再次用作进一步组合子的参数——换句话说,它们是无限可组合的。这使得它成为了一种美丽而强大的API设计方法。

如果您以前使用过集合API,那么这可能会让您感到非常熟悉——大多数生成器函数都有相应的内置Python函数,可以在集合(更准确地说,是可迭代对象)上工作。

  • int_between类似于range

  • map类似于map

  • mapN类似于zip + map

  • bind类似于列表推导式中的嵌套for循环

这或许并不意外——生成器是无限的随机值流,因此任何能够处理某种值容器的 API 都可以支持类似的操作。如果 Python 允许更改生成器表达式的处理方式,我们就可以编写如下的随机生成器:

# 实际上不是 Python
lists_of_person = gen (
    pl
    for length in int_between(0, 10)
    for pl in list_of_length(length, persons)
)

这可以自动转换为上面的 bind 版本(实际上是可行的!),说明 for x in generator ... 等价于 bind(lambda x: ..., generator)

有趣的一点是,函数序列 mapmapNbind 给用户提供了越来越多的表达能力。一种理解方式是,mapmapN 可以用 bind 实现,但 bind 不能用 mapmapN 实现。对于 mapmapN,也是如此——如果你有 mapN,你就有了 map,但反之则不然。

为什么不直接实现bind呢?实际上,我们可以这样做而不会失去任何功能或表达能力。但是,bind相对于mapmapN来说,暴露的信息更少,因此bind对于意图的假设比mapmapN更少。这反映在它们的实现上的相对复杂性上。因此,通常情况下,bind的性能比mapN差,而mapN的性能比map差。如果你可以用map编写它,请不要使用bind,以便让实现有更多的工作空间。

这些函数的模式——constantmapmapNbind——在集合库、流、响应式库等各种形式中一次又一次地出现。在具有表达性类型系统的语言中,例如Haskell,存在明确的抽象或接口来封装它们——分别是FunctorApplicativeMonad。这些概念也与范畴论有着深刻的联系,范畴论是数学的一个分支,Eric Meijer将其描述为“基于接口的设计的数学家解释”。

我们只能在这里浅尝辄止——希望现在你对这些“API设计模式”有了直观的了解,并且如果你感兴趣,可以有一些学习的线索。除了PBT之外,许多库都使用这些模式,识别它们可以更容易地入门。作为一个库的设计者,了解和学习这些模式何时可以使用肯定是有用的——它们是你工具箱中的有价值的工具。

如果你已经看到这里了,现在是时候奖励自己一块山核桃派了!

现在让我们写一些测试吧

既然我们已经可以编写随机生成器,那么让我们走最后一步,编写一些函数来定义属性并运行一些测试。

首先,我们需要让用户编写一个属性。属性只是生成器和断言的组合。我们将使用随机生成的值运行100次断言。

将生成器连接到断言的函数通常称为“for all”,因为这让人想起逻辑中的“for all”量词。在表述中,我们想要写成“对于所有人的列表,按年龄排序的结果是有效的。”在某种意义上,“for all”是一个误称,因为我们当然不会真正测试或证明所有值的情况,但无论如何,让我们坚持这个称呼。

为了简单起见,我们将断言编写为返回True(如果断言成立)或False(如果不成立)的函数。更传统的方法是使用assert并在异常时失败测试,但使用这种方式可以更容易地理解实现。

我们第一次尝试定义一个属性,它是一个布尔生成器,指示测试是否失败。这意味着我们甚至不需要一个新的类——我们可以只使用Random[bool]:

Property1 = Random[bool]

def for_all_1(gen: Random[T], property: Callable[[T], bool]) -> Property1:
    return map(property, gen)

sort_by_age_1 = for_all_1(lists_of_person, lambda persons_in: is_valid(persons_in, sort_by_age(persons_in)))

# wrong_sort_by_age is sort_by_age with a bug,
# to show what a failing test looks like.
wrong_sort_by_age_1 = for_all_1(lists_of_person, lambda persons_in: is_valid(persons_in, wrong_sort_by_age(persons_in)))

我们第一次尝试实现 for_all,只是使用 map,将断言应用于每个生成的元素。由于由 for_all 创建的属性只是一个 随机 实例,我们可以对其进行 sample

> sample(sort_by_age_1)
[True, True, True, True, True]

> sample(wrong_sort_by_age_1)
[False, True, False, False, False]

但这不是用户友好的输出。在实际的 test 函数中,我们会生成 100 个值 - 如果它们全部为 True,则测试成功:

def test_1(property: Property1):
    for test_number in range(100):
        if not property.generate():
            print(f"失败:在第 {test_number} 次测试中失败。")
            return
    print("成功:通过了 100 次测试。")

使用方法:

> test_1(sort_by_age_1)
Success: 100 tests passed.

> test_1(wrong_sort_by_age_1)
Fail: at test 0.

好的,看起来这个函数可以用,但它不允许编写从两个或更多生成器中提取的属性 - 如果我们可以嵌套 for_all 就好了。这里是 for_all_2,它允许这样做:

def for_all_2(gen: Random[T], property: Callable[[T], Union[Property1,bool]]) -> Property1:
    def property_wrapper(value: T) -> Property1:
        outcome = property(value)
        if isinstance(outcome, bool):
            return constant(outcome)
        else:
            return outcome
    return bind(property_wrapper, gen)


sum_of_list_2 = for_all_2(
    list_of(int_between(-10,10)), lambda l:
        for_all_2(int_between(-10,10), lambda i: 
            sum(e+i for e in l) == sum(l) + len(l) * i))

我们允许property函数返回一个布尔值(在这种情况下它是最内层的for_all),或者一个Property1(在这种情况下它是外层的for_all函数之一)。因为我们现在可能会得到一个Property1,它是一个Random[bool],所以仅使用map是不够的:我们必须在for_all_2的实现中升级到bind

作为最后的改进,如果测试失败,让我们打印生成的参数。我们将使用与之前相同的技巧,通过利用 Random,但不是使用 bool,而是使用更丰富的类型 TestResult

@dataclass(frozen=True)
class TestResult:
    is_success: bool
    arguments: Tuple[Any,...]


Property = Random[TestResult]


def for_all(gen: Random[T], property: Callable[[T], Union[Property,bool]]) -> Property:
    def property_wrapper(value: T) -> Property:
        outcome = property(value)
        if isinstance(outcome, bool):
            return constant(TestResult(is_success=outcome, arguments=(value,)))
        else:
            return map(lambda inner_out: replace(inner_out, arguments=(value,) + inner_out.arguments), outcome)
    return bind(property_wrapper, gen)


def test(property: Property):
    for test_number in range(100):
        result = property.generate()
        if not result.is_success:
            print(f"Fail: at test {test_number} with arguments {result.arguments}.")
            return
    print("Success: 100 tests passed.")

当测试失败时,这种方式更加用户友好:

> test(prop_wrong_sort_by_age)
Fail: at test 0 with arguments ([Person(name='qqdkng', age=31), Person(name='lcqyva', age=73)],).

至少现在它告诉我们哪些参数是失败的输入!这样就可以轻松地重现和调试错误。

请注意,对于可变值,以这种方式捕获参数可能会有问题:TestResult.arguments捕获了对生成值的引用,但如果断言或测试中的函数更改了它,我们将在更改后打印该值。对于像Haskell这样的纯函数语言,这是不可能发生的,但对于Python和其他语言来说,这绝对是一个问题。解决这个问题的一个巧妙方法是存储伪随机数生成器的种子,而不是生成的值,然后使用该种子从头开始重新生成该值。我们将在下一篇文章中回到可变性问题。

这就是我想要介绍的初始实现。让我们回顾一下我们拥有什么,缺少什么,以及我们将在下一篇文章中涵盖什么。

最后

80/20法则适用于这里-这些代码总共只有几页,代表了属性测试库80%的功能。大量的工作涉及编写和维护广泛使用的类型的生成器。

简略总结:

  • 这里的属性和测试“模块”只有一个函数(分别是for_alltest)。真正的PBT库有更多的函数来收集生成值的统计信息和信息,这是通过在TestResult上添加更多字段来实现的。例如,我们可以打印诸如“20%的生成列表为空,生成值占测试时间的12%”等信息。此外,还有许多其他选项以各种方式配置测试运行。

  • QuickCheck是用Haskell编写的,它是一种 pure language,因此QuickCheck的Random.generate需要将伪随机数生成器的种子值作为输入包含在内。在上面的实现中,该种子被隐藏在random模块中,并在生成值时更新。

  • QuickCheck的generate还包括一个整数size参数。这个大小用于限制生成值的“大小”-虽然没有明确定义,但通常用于确保递归类型(如树)的生成器不会生成巨大的值,例如通过将给定的大小解释为树的最大深度。我们将在接下来的几篇文章中讨论缩小时回到大小的概念。

这就是本篇文章的全部内容,涵盖了很多内容!下一篇文章将讨论缩小-这是自QuickCheck推出以来大多数实验发生的领域。

下次再见!


声明:本文为本站编辑转载,文章版权归原作者所有。文章内容为作者个人观点,本站只提供转载参考(依行业惯例严格标明出处和作译者),目的在于传递更多专业信息,普惠测试相关从业者,开源分享,推动行业交流和进步。 如涉及作品内容、版权和其它问题,请原作者及时与本站联系(QQ:1017718740),我们将第一时间进行处理。本站拥有对此声明的最终解释权!欢迎大家通过新浪微博(@测试窝)或微信公众号(测试窝)关注我们,与我们的编辑和其他窝友交流。
190° /1906 人阅读/0 条评论 发表评论

登录 后发表评论