（计算机软件与理论专业论文）函数式程序设计语言haskell的测试数据系统生成.pdf

中山人学硕士论文 函数式程序设计语言h 鹊k d l 的测试数据系统生成 函数式程序设计语言h a s k e l l 的测试数据系统生成 专业：计算机软件与理论 硕士生：章金平 指导老师：乔海燕副教授 摘要 软件测试作为软件开发过程中的重要一环，对于保障软件质量起着至关重要 的作用，而测试数据生成方法的正确性和有效性，又是一个成功测试的根本。因 此，测试数据生成方法的研究，对于测试技术乃至整个软件工程来说，都有着非 常重要的意义。 本文从函数式程序设计语言h a s k e l l 入手，提出了一种能够系统生成h a s k e l l 下各种基本类型及用户自定义类型数据元素的方法，并且提供了一些函数供用户 选择，从而使得用户定义某类型元素的生成器变得很简单。然后，在此方法的基 础上，开发了一个能够用于做系统化测试的h a s k e l l 程序自动化测试工具，并利 用该工具对现有函数库进行了一定的测试。最后，文章讨论了随机测试和系统化 测试存在的优缺点及各自的适用场合。 关键词：函数式程序设计，程序测试，h a s k e l l ，系统生成 中山大学硕士论文函数式程序设计语言h 豁k c l i 的测试数据系统生成 s y s t e m a t i c a lg e n e r a t i o no f t e s td a t ai n 向n c t i o n a lp r o g r a 衄i n g 1 a n g u a g eh a s k e u m a j o r ： s o f t w a r ea n dt h e o r e 戗c a lc o m p u t e rs c i 蚰c e n a m e ：z h a n gj i n p i n g s u p e r 、，i s o r ：q i a oh a i y 柚 a b s t r a c t a sa ni m p o r t a n tp a no ft h es 0 r w a r ed e v e l o p m e n t ，s o 俞w a r et e s t i l l gi sc m c i a l t ot h ea s s u r a n c e o fs o f t 、) i r a r eq u a l i t y w h i l et 1 1 ec o r r e c 缸l e s sa n dv a l i d i t ) ，o ft h et e s td a t aa r et h eb a s eo fas u c c 船s 如l t e s t i i l g h c et l l es t u d yo ft e s td a t ag 铋e r a t i o ni se s s e n t i a l t ot h et e s t i i l gt e c l l l l o l o g ya n d e v e nm e w h o l es o f 细a r ep r o j e c t h lt h i sn l e s i sw ep p o s ean e wm e m o dt og e n e r a t ea l le l e m e n t so fat y i ) es y s t 锄a t i c a l l yi n h 勰k e l l ，a 向n c t i o n a lp r o g r a m m i n gl 强g u a g e ，i n c l u d i n gb a s i ct e sa n du s e r - d e f i n e dt y p e s ，a n dw e p r 0 、，i d es o m e 如n c t i o n sw h i c hm a k ei tv e f ye a s yt od e f i n et e s td a t ag e i l e r a t o r s f u r t h e rm o r e ，w e d e v e l o p c dat e s tt o o lf o l l o w i n gt h i sm e t l l o dw h i c hc a l lb eu s e df o rs y s t e m a t i c a l t e s t i n g ，a n d 、 t 懿t e ds o m el i b f a 叫如n c t i o n su s i i l gt h i st 0 0 1 f i i l a l l y w ed i s c u s st h ea d v a n t a g e sa n dd i s 酞i v a n t a g e s o f 瑚m d o mt e s t i i l ga n ds y s t e m a t i c a lt e s 如g k e yw o r d s ：f i l n c t i o n a lp r 0 铲锄 1 i i l i l l g ，p r o g m mt c s t i n g ，h a s k e l l ，s y s t 锄a t i c a lg e m t i o n i u 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 签名： 醐：进年月亨日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名举辛 日期：扣年够月0 7 日 导师签名：香晦数 日期：沙。序，月7 日 中山大学硕士论文 函数式程序设计语言h 船k e i l 的测试数据系统生成 1 1 引言 第1 章绪论 自从软件诞生的那天起，如何保证软件的质量似乎就成为软件开发者及用户 无法逃避的话题。历史上也不乏“劣质”软件所带来的惨痛教训：1 9 6 7 年8 月 2 3 日前苏联著名宇航员弗拉迪米尔科马洛夫驾驶的“联盟1 ”号宇宙飞船，经过 一天一宿的太空飞行之后，圆满完成了任务，然而由于软件质量问题而使得航天 飞机无法返回地球，给整个国家和人民带来巨大损失和悲痛；1 9 9 4 年英特尔最 新一代的奔腾处理器投入全面生产，公司为此在全球投放大量广告。然而，在使 用过程中有人发现：由于芯片上的一个微小设计偏差，导致浮点运算在9 0 亿次 除法运算后会出现1 次错误，但就是这么一个在有些人看来微乎其微的偏差，导 致英特尔公司不得不从全世界召回由其生产的这种芯片，损失惨重! 类似的例子 可以说是不胜枚举! 这一切让人们意识到：提高软件质量是极其重要的! 经过几十年的发展历程，人们发现，软件测试对于提高软件质量来说，是行 之有效的，而且是我们主动发现缺陷和修改错误的最重要的方法，软件测试作为 保证软件质量的重要一环，其作用已经得到了业界人士的普遍认可，在测试方面 的投入占整个软件开发投入的比重也日益提高，在某些项目中甚至达到8 0 。 测试数据的科学性和有效性，是一个成功测试的前提。这些测试数据不仅应 包括那些在人们看来“合理”的数据，还应该包括那些“不合理”的数据，这里 所谓的不合理数据，指的是那些人们在正常的情况下不会碰到，但在某种特定的 环境或情况下( 比如误操作) 可能输入的数据。我们要保证软件在正确的输入下正 确工作，我们更应该确保软件在错误的输入下也能稳定地、正常地工作。因为这 些错误的操作往往是隐蔽的，不容易被发现的，但其带来的后果却可能是极其严 中山大学硕士论文函数式程序设计语言h 弱k e l l 的测试数据系统生成 重的，甚至可以说是灾难性的! 然而，对于一个程序来说，由于其输入数据是无 穷的，我们无法对所有有效和无效的输入都测试一遍，这就涉及到测试数据选择 的问题。因此，讨论如何有效地生成测试数据，对于软件测试来说，是非常有意 义的1 1 2 国内外研究现状 某种类型测试数据的生成指的是从诸多该类型的数据元素中选择一部分或 全部元素来作为我们的测试数据。因此，该类型测试数据的生成过程实质上就是 对该类型数据的一个选择过程。在函数式程序的测试过程中，一个输入类型测试 数据的选择是由一个函数来完成的，即由这个函数来生成测试用的数据。我们把 这样的函数称为测试数据生成函数。 当前关于函数式程序测试数据的生成方法，国内外诸多著名专家已经做了大 量的杰出的工作，并已取得了很好的成果。在这些方法当中，我们通常可以把它 们归结为二类：一类是随机生成，另一类便是系统化生成。 随机生成方法的主要思想是用一个随机种子，来随机生成各个测试数据，其 主要特点便是其测试数据的随机性，也就是说，从理论上讲，任何数据都有可能 被生成。在对用函数式程序设计语言h a s k e l l 所编写程序的各种现有测试方法 中，q u i c k c h e c k 【3 】方法是一种最典型和迄今为止使用最广泛的随机测试方法， 它是由j o h nh u g h e s 和k o e nc l a e s s e n 等人于2 0 0 0 年提出的，其主要思想是随 机产生一个数据类型的元素，然后把该元素作为待测函数的输入，从而判断对于 该输入待测函数的输出是否正确。 系统化测试方法是按照某种规则，系统地列出某种类型的所有可能元素或取 值来作为测试数据。其主要特点就是它生成测试数据的系统性和可预测性。在采 用该方法生成测试数据的测试工具中，具有代表性的是由c 0 1 i nr u n c i m a n 于 2 0 0 7 年初发布的s m a l1 c h e c k h l ，s m a l l c h e c k 是在q u i c k c h e c k 基础上开发的系统 化测试工具，充分继承了q u i c k c h e c k 使用方便的优点，并且在类型定义及使用 风格上都和q u i c k c h e c k 很相似，不同的是q u i c k c h e c k 采用的随机生成测试数据， 而s m a l l c h e c k 采用的却是系统化生成测试数据。在使用的时候，s m a l l c h e c k 要 2 中山大学硕士论文函数式程序设计语言h 硒k d l 的测试数据系统生成 求用户输入一个深度，那么，它可以系统生成该深度以内的所有测试数据，并用 这些数据来进行相应的测试。 1 3 研究的主要内容 由于一方面q u i c k c h e c k 中测试数据的生成方法已经被实践证明为一种良好 的、有效的随机生成测试数据的方法，另一方面随机测试本身也存在着不足，因 此，本文主要从系统化角度，提出了一种能够系统生成h a s k e l l 语言各种类型数 据元素的方法，包括基本数据类型及各种用户自定义类型。在此方法的基础上， 开发了一个能够系统生成测试数据的h a s k e l l 程序自动化测试工具，并利用该工 具对现有函数库进行了一定的测试，从而验证了这种生成数据方法的有效性。最 后，文章讨论了随机测试和系统化测试存在的优缺点及各自的适用场合。 1 4 论文的组成 本论文共分为五章。 第一章为绪论，主要介绍论文研究的目的和意义，当前国内外的研究现状及 本论文的主要工作。 第二章为相关知识介绍，包括软件测试的相关概念，函数式程序设计的概念， 以及当前h a s k e l l 程序的主流测试工具的详细介绍。 第三章为系统化生成测试数据，是本论文的中心。详细介绍了一种新的系统 化生成h a s k e l l 程序下各种类型数据元素的方法，包括基本数据类型及用户自定 义类型等。并提供了一些用于方便用户定义其自定义类型数据元素生成器的函 数。 第四章为测试工具s y s t e s t 。主要介绍了在利用前面提到的系统化生成 h a s k e l l 程序各种类型数据元素的基础上，开发的一个h a s k e l l 程序自动化测试 工具，用户利用该工具可以对h a s k e l l 程序进行系统化测试或随机测试；然后我 们利用该工具对现有函数库进行一些测试，通过这些测试从一定程度上验证这种 系统化生成测试数据的方法的有效性；此外，我们讨论了随机测试和系统化测试 3 中山大学硕士论文函数式程序设计语言h 弱k e l l 的测试数据系统生成 的优缺点及各自的适用场合。 第五章为总结与展望，主要是对论文工作的总结，并对我们下一步将要开展 的工作做一个展望。 4 中山大学硕士论文 函数式程序设计语言h 舔k e l l 的测试数据系统生成 第2 章相关知识介绍 2 1 软件测试相关概念 2 1 1 软件测试的定义 软件测试是以发现软件当中尚未发现的错误或缺陷为目的的执行软件的过 程n 1 。它是用来确认一个程序的品质或性能是否符合开发之前所提出的要求的最 重要的方法，是软件开发过程中的重要组成部分，是软件投入运行前，对软件需 求分析、设计规格说明和编码的最终复审，是软件质量保证的关键步骤。 一个成功的测试，应该是指那些发现了以前没有发现的错误的测试，是检测 出了软件的缺陷，而不是那些因为没有发现错误而得出“软件正确”结论的测试 因此，测试应该是以挖掘错误为己任。 2 1 2 软件测试的目的 从软件测试人员的角度来说，软件测试应该具有以下目的【： 第一：确认软件的质量。它包括二个方面，一方面是确认软件完成了我们所期望 的功能，另一方面是确认软件以正确的方式来完成这个功能。 第二：提供信息。包括提供给开发人员和项目主管的反馈信息，以及为风险评估 所准备的信息 第三：软件测试不仅是在测试软件产品的本身，而且还包括软件开发的过程。如 果一个软件产品开发完成之后发现了很多问题，这说明这个软件开发过程 5 中山大学硕士论文函数式程序设计语言h 觞k e l l 的测试数据系统生成 可能是有缺陷的，因此软件测试的第三个目的是保证整个软件开发过程是 高质量的。 2 1 3 软件质量的衡量标准 对于一个已经开发完成的软件来说，我们一般从下面几个方面来衡量软件的 质量n 1 ： 1 在正确的时间用正确的方法把一个工作做正确。 2 符合一些应用标准的要求，比如不同国家用户的不同操作习惯和要求，项 目工程中的可维护性和可测试性等要求。 3 质量本身就是软件达到了最开始所设定的要求，而代码的优美或精巧的技 巧并不代表软件的高质量。 4 质量也代表着它符合客户的需要。对软件测试这个行业来说，最重要的一 件事就是从客户的需求出发，从客户的角度去看产品，客户怎么去使用这个产品， 使用过程中会遇到什么样的问题。只有这些问题都解决了，软件产品的质量才可 以说是上去了。 2 1 4 软件测试的划分 一、从测试形态上来划分的话，软件测试可以分为以下三大项n 1 ： 1 建构性测试：又称开发测试，是程序还处于建设阶段时所进行的测试，包 括单一步骤测试、尝试性测试、单元测试、组件测试和集成测试等。 2 系统测试：开发人员集成测试后，将软件编译构成初步的测试版本，然后 对这些版本进行的测试叫做系统测试。系统测试又包括集成测试、前哨测试、功 能测试、设置测试、发行测试、验收测试等。 3 专项测试：需要额外的人力和物力来进行的测试活动。专项测试又可以分 为回归测试、性能测试、压力测试、兼容性测试、a 1 p h a 和b e t a 测试等。 二：从测试技术上来说，软件测试包括二个方面n 1 ： 1 准备工作。包括正规方式和非正规方式二种： 6 中山大学硕士论文 函数式程序设计语言h 私k e n 的测试数据系统生成 ( 1 ) 正规方式：所进行的测试是按照测试计划和测试用例运作的，所有的测 试文件从需求、设计以及以后的支持需求都必须准备完整。 ( 2 ) 非正规方式：不按照测试计划进行或没有测试计划，它所依赖的是测试 人员的经验与技巧。 2 执行方式。主要有二种执行方式 人工执行：由测试人员执行软件测试，手动记录执行过程中的行为并且自行 检查执行结果是否符合要求。 自动化执行：利用内外部所提供的测试软件，市售测试软件或自行开发的自 动测试工具进行测试，测试的行为与结果都会自动记录甚至自行分析。 三：从测试模式来说，软件测试又可以分为二种：白盒测试和黑盒测试n 1 。 1 白盒测试：也称结构性测试，主要是对程序的逻辑结构进行测试，注重的 是深度。包括数据流面和控制流面二大方面。其中，数据流面就是测试资料进出 系统的程序所经过的流程。控制流面是指测试程序在执行过程中每个阶段的流 程，包括以下四点： ( 1 ) 语句覆盖：每个程序句都被执行到。 ( 2 ) 分支覆盖：每个程序的进出点都至少被执行过一次。 ( 3 ) 条件覆盖：分支覆盖再加上所有的判断情况都至少被执行一次。 ( 4 ) 条件组合覆盖：不同的组合的判断情况都至少被执行过一次。 2 黑盒测试：也称功能测试，主要是测试软件的功能是否完善，测试人员并 不需要对软件的结构有深层的了解，注重的是广度。黑盒测试又分为以下三种： ( 1 ) 测试用例覆盖：即每个测试用例都被测试过。 ( 2 ) 输入覆盖：测试过程中所输入的数据或资料必须全部被测试。 ( 3 ) 输出覆盖：测试过程中程序所产生的行为、反应及数据都必须一再地试 验和审核。 2 2 函数式程序设计的介绍 函数式程序设计的主要思想是把一个功能独立的程序作为一个从输入到输 出函数，整个程序本身也是一个函数，不同的函数之间只要类型匹配，便可以相 7 中山大学硕士论文函数式程序设计语言h 够k e l i 的测试数据系统生成 互调用。这种函数跟我们数学当中的函数概念更为接近，即只要给定它所需要的 参数作为输入，它便可以给我们返回一个结果。举个例子，我们用函数式程序设 计语言h a s k e l l ( 本文所有的程序都是用h a s k e l l 语言来编写的) 定义一个求整数 列表中所有元素和的函数： s u m ： i n t 一 i n t 一计算一个整数列表中所有元素的和 s u m = o s u m( x ：x s ) = x+sumx s 在这个程序当中，s u m 是函数的函数名，( i n t 卜 i n t ) 是函数的类型，其中 i n t 的含义是“整数的列表”，是函数的输入类型；i n t 表示函数的输出类型为 整型。那么这个函数就是一个以整数的列表作为输入，以整数作为输出的函数。 从s u m 函数的定义我们可以看出，它和我们数学意义上的函数十分接近，即当输 入的参数为空列表的时候，返回值为o ，而当输入的参数不是空列表的时候，它 的返回值为该列表中第一个参数的值加上以这个列表的尾为输入的s u m 函数的 值，其中( x ：x s ) 表示以x 为开头，连接x s 为尾的一个列表。 2 2 1 函数式程序设计的特点 由上面的例子我们不难发现，与命令式语言相比，函数式语言主要具有以下 特点瞳1 ： 1 没有赋值语句，没有变量，没有流程的概念。 在函数式程序设计当中，一个参数一旦给定一个值，那么这个值便是不可改 变的，而程序的运行过程，也就是不断计算参数值的过程。函数式程序的这种特 性，使得我们永远不用担心它会产生什么副作用，即被调函数不会对主调函数中 原有的值进行修改。这就消除了我们程序设计当中的一个重要的安全隐患，并且 使得程序的执行顺序显得无关紧要，因为没有副作用可以改变一个表达式的值， 表达式可以在任何时候被计算。因此，程序员不需要担忧控制流的编写。因为 表达式可以在任何时候被计算，我们可以自由地将变量用其值代替，或者将值代 换为变量，也就是说，程序是“引用透明的”。这种自由度使得函数程序比传统 8 中山大学硕士论文 函数式程序设计语言h 勰k e l l 的测试数据系统生成 的程序在数学上更容易处理。 2 结构清晰，简洁明了。 与命令式语言相比，由于函数式程序设计当中没有赋值语句，这就使得程序 更加简洁，当然，抽象性也更高。 3 支持列表概括。 所谓列表概括，是指用一个列表来描述另一个列表，其中一个列表生成元素， 这些元素经过过滤和转化形成结果列表的元素。 举个例子：列表概括 2 木nin a t a i l ( 一：x s ) = x s 一求一个列表的尾，即除第一个元素 一外的其他元素 n u l l ： a 一 b 0 0 1 一判断一个列表是否为空 n u l l = t r u e n u l l ( 一：_ ) = f a l s e 5 支持惰性计算 函数式程序设计的最重要的特征之一便是惰性计算。所谓惰性计算是指一个 惰性计算器在计算一个函数的值时，只有计算过程需要参数的值时，惰性计算器 9 中山大学硕士论文函数式程序设计语言h 邪k c l l 的测试数据系统生成 才去计算它的值，而且，如果一个参数是有结构的( 例如，一个列表) ，那么惰 性计算器只计算参数中需要的部分。我们可以将惰性计算的特征归纳为以下三 点： 一个参数只有在计算过程中需要它时才被计算。 一个参数不必完全计算，只有需要的部分参加计算。 一个参数最多被计算一次。这是通过把表达式用图表示，然后在图上进行计 算实现的。 例如，我们定义如下一个函数： p m ：( i n t ，i n t ) 一 i n t p m( x ，y )=x + 1 那么，我们将这个函数应用于二元组( 3 + 2 ，4 1 7 ) 的时候，只有第 一部分参数3 + 2 会被计算，而二元组的第二个分量4 1 7 没有被计算，因为 计算过程中不需要它。 2 2 2 函数式程序的测试 和其他程序设计语言一样，在函数式程序设计中，为了保证程序的正确性， 我们也需要对我们已经构建的函数来做一些相应的测试。 在函数式程序测试中，为了测试某个函数的定义是否是正确的，我们必须首 先定义一个待测的性质，即：假设我这个函数定义是正确的，那么它应该满足什 么条件? 这个条件就是我们要测试的内容。然后，我们再根据函数所需要的参数 类型，生成相应满足条件的不同的参数值，把它( 们) 作为待测性质( 实质上也 是一个函数) 的输入。最后，通过对测试结果的观察，我们便可以判断这个程序 的定义是否存在问题。 在这里，我们涉及到以下几个方面的问题： 1 如何书写待测性质。 2 如何选择测试数据。 3 如何反馈测试结果。 在这里，待测性质的书写是极其重要的。我们首先要保证这个性质本身是正 1 0 中山大学硕士论文函数式程序设计语言h 弱k e l l 的测试数据系统生成 确的，因为假如这个性质本身都有问题的话，那么测试的结果肯定没有任何意义， 甚至可能误导我们对程序正确性的判断。另一方面，我们所写的性质还必须对原 程序具有证伪能力，即它应该是程序正确的情况下必然满足的性质，从而，如果 我们测试时发现这个性质不成立，我们便能推断出原程序的定义有错误。但是， 从某种程度上来说，即使我们写的待测性质正确，并且通过大量测试也没有发现 问题，我们也无法断定程序一定是正确的，因为待测性质成立是原程序正确的必 要条件，但非充分条件。所以，一个良好的测试性质应该能够反映原程序的正确 性。最后，在测试结束之后，测试程序还必须向测试人员反馈一些信息，以便我 们判断测试的结果。 我们前面提到，就程序测试的技术来说，主要有二种，一种是白盒测试，一 种是黑盒测试。白盒测试也称逻辑测试，主要测的是二大方面：数据流面和控制 流面，注重的是深度，包括语句覆盖，分支覆盖，条件覆盖，条件组合覆盖等等。 而黑盒测试主要是对程序的功能进行测试，注重的是广度，包括测试用例覆盖， 输入覆盖，输出覆盖等等。 由于函数式程序没有流程的概念，程序的规模一般很小，抽象性高，这就使 得白盒测试的概念在这里变得很弱，另外，函数式程序本身是一个从输入到输出 的函数，因此，对函数式程序的测试来说，我们主要是采用黑盒测试的办法，即 测试对于不同的输入，程序的运行结果是否符合我们所预期的性质。 因此，在函数式程序测试的研究当中，我们关心的一个最重要的问题就是如 何有效地生成测试数据。 在当前函数式程序的测试当中，测试数据的生成方法主要有二种：一为随机 生成，二为系统化生成。随机生成方法的主要思想是用一个随机种子，来随机生 成各个测试数据，其主要特点便是其测试数据的随机性，也就是说，从理论上讲， 在任何时候我们都不知道下个待测数据是什么。系统测试方法是按照某种规则， 系统列出某种类型的所有可能元素或取值来作为测试数据，其主要特点就是它生 成测试数据的系统性和可预测性。 下面，我们就当前h a s k e u 程序的二个主流测试工具作一个详细的介绍。 一、q u i c k c h e c k 中山大学硕士论文函数式程序设计语言h a s k e l l 的测试数据系统生成 q u i c k c h e c k 【3 1 是j o l l l lh u g l l e s 和k o e nc l a e s s e n 共同开发的一个基于 h a s k e l l 的自动化程序测试工具，采用了随机生成测试数据的方法。我们首先来 看个用q u i c k c h e c k 来进行测试的例子： 假设我们定义以下二个整数的加法运算： a d d ：h l t i i l t h l t a d dx y = x+y 为了验证我这个加法运算是否是正确的，根据加法满足交换律，我们定义下 面的待测性质： p r o p - a d d xy = a d dxy a d d y x w h e r e t y p e s = ( x ：i i l t ，y ：1 1 1 t ) 那么，我们便可以在已载入q u i c k c h e c k 包的情况下输入q u i c k c h e c k p r o p d d ，它会告诉我们：o k ，p a s s e dl o ot e s t s 如图2 - 1 所示： 图2 - l 用q u i c k c h e c k 测试p r o p d 函数 由此可见，作为一种随机测试工具，哪i c k c h e c k 在使用上是很方便的。 在介绍q u i c k c h e c k 测试数据生成方法之前，我们有必要先介绍一下函数式 程序中“类型分类 ( 简称“类 ) 和特例的概念。在函数式程序设计当中，一个 1 2 中山大学硕士论文函数式程序设计语言h a s k e l l 的测试数据系统生成 类型分类或者类( c l a s s ) 是支持某些重载运算的类型的集合，这些运算又称为类 的方法。例如，定义了相等运算和不相等运算的类型的集合称为e q ( 相等类) ， 它的定义如下： c l a s se qa w h e r e ( 一) ：a 一 a - b o o l ( _ ) ：a - a 一 b o o l 一个类的成员称为一个特例，这个特例实现了该类包含的方法。将一个类型 定义为一个类的特例的方法是：通过使用i n s t a n c e 特例说明语句并定义类的方 法。比如，b o o l 类型是e q 类的一个特例，其实现方法为： i n s t a n c ee qb o o lw h e r e t 】m e t m e = t 1 e f a l s e = = f a 】s e = t n l e = = = = f a l s e x = y = n o t ( x y ) q u i c k c h e c k 生成测试数据的主要思想是：定义一个a r b i t r a 巧类，对于任意 类型，我们要生成该类型的元素，我们只需要实现该类型对应a r b i t r a r ) ，类的实 现即可。 舶i t r a r y 类的定义如下： c l a s sa r b i 仃a 巧aw h c r e a r b i t r a r y ：g e l la 在这里，g e l la 是一个代表a 类型数据生成器的抽象数据类型。生成器的 定义既可以由用户自己来定义，也可以直接使用q u i c l ( c h e c k 中的默认定义。 g e n 的定义如下： n e w t y p eg e l la = g e l l ( r a l l d - a ) 其中，r a n d 是一个随机种子，而这个生成器的实质就是一个可以随机产生 一个a 类型数据元素的函数，但是，我们还是把这个g e n 作为一个抽象数据类 型来对待。为此，我们首先定义一个如下的生成器： c h o o s e ：r a l l d o ma = - ( a ，a ) 一 g e na c h o o s e b o l l l l d s = ( f s t r 锄d o m rb o u n d s ) ! 缸a p 、r a n d 1 3 中山大学硕士论文函数式程序设计语言h a s k e l l 的测试数据系统生成 c h o o s e 函数的作用是：给定一个a 类型的区间( 其中a 已经定义为r a n d o m 类的一个实例) ，那么它可以从这个区间中不断地随机选择一个g e i la 类型的数 据。 有了这个c h o o s e 函数，那么我们便可以很方便地给出h a s k e n 下各种类型对 应于胁i 仃a 巧类的实现了。比如： i n s t a n c ea r b i 饥u yc h a rw r h e r e a r b i t r a r y= c h o o s e ( 3 2 ，2 5 5 ) = 、i l - r 酣1 n 1 ( d l rn ) i n s t a n c ea r b i t r a r yi n tw h e r e a r b i t r a 巧= c h o o s e ( 一2 0 ，2 0 ) i n s t a i l c ea r b i 饥l i yb o o lw h e r e 抽i t r a r y = e l 锄e n t s t i m e ，f a l s e 】 e l e m e n t s ： a 一 g e i la e l e m e n t s x s = ( x s ! ! )矗n a p 、c h o o s e ( o ，l e n g t l lx s 1 ) 为了达到由简单的生成器构建复杂的生成器的目的，q u i c k c h e c k 还将g e l l 定义为m o n a d 类的一个特例，其实现方法如下： i n s t a n c em o n a dg e nw h e r e r c t u ma = g e n ( 谊r - a ) g 肌m = k = g e l l ( r o 一 1 e t ( r 1 ，r 2 ) = s p l i tr 0 g e nm = k ( m n r 1 ) i nm nr 2 ) 其中，r e t u m 函数的作用是返回一个g e i la 类型的数据，而 = 是一个顺序 运算符，用于产生一个a 类型的数据，并把它传递给它的第二个参数从而产生一 个b 类型的数据。 为了能让用户方便地定义其自定义类型的胁i 仃a r y 类的实现方法， 1 4 中山大学硕士论文 函数式程序设计语言h 勰k e l i 的测试数据系统生成 叫c k c h e c k 还提供了一些辅助函数，比如o n e o f ，丘e q u e n c y 等。 o n e o f ： g e i la 】- g e i la o n e o f g e n s = e l 既n e n t sg e n s = i d 毹q u e i l c y ： ( i n t ，g c i la ) 】- g e i la m - q u e i l c yx s = c h o o s e ( 1 ，t o t ) 、一( p i c k 、x s ) w h e r e t o t = s 吼( m a pf s tx s ) p i c kn ( ( k ，x ) ：x s ) ln a r b i 仃a r y ( t h e a ) w h e r e 曲i 缸a 巧= 仔e q u e l l c y ( 1 ， 1 i r ml e a f a 而i t r a r y ) ， ( 2 ， l i r m 2b m c ha r b i 仃a r ) ，a r b i 破叮) 】 其中，1 i f 【m ：m o n a da ( b 一 c ) - ab - ac l i a m 2 ：m o n a da = ( b 一 c 一 d ) - ab 一 ac - ad 我们再来看一下用q u i c k c h e c k 来对系统库函数r e v e r s e 的测试，其中r e v e r s e 中山大学硕士论文 函数式程序设计语言h 豁k e l l 的测试数据系统生成 函数的作用是将一个列表置逆。根据r e v e r s e 函数的功能，我们可以定义以下待 测性质： p r o p j 己e v u i l i t x = r c v e r s e x 】= = 【x 】 w h e r e t ”e s = ( x ：h l t )一单元素列表的逆和它本身相等 r e v e r s e ( x s + + y s ) = = r e v e r s e y s + + r e v e r s e x s w h e r et y p e s = ( x s ： h l t 】，y s ： i i l t 】) 一二个列表的连接的逆，等于后一个列表的逆再连接前一个列表的逆 p r o p - 尽e v r e v x s = r e v e r s e( r e v e r s e x s ) = = x s 、) l ，h e r et y p e s = ( x s ： i n t 】) 一对于一个列表来说，它的逆的逆等于它本身 测试效果如图2 2 所示： f l e 曰- t 缸t i o n s 卧o w s eh e i p 商；荔嘞岛缀固镭l 曾 l ll l ih u g s9 8 ： b a s e donc h eh a s k e l l9 8s t a n d a r d 忿 il iiii il iic o p y r i g h 七c c ) 1 9 9 4 2 0 0 5 i i v o r l d i d ev e b ： h 七c p ：h a s k e l l o r g h u g s b u 口s ：h 七七p ：h a c k a g e h a s k e l l o r g c r a c h u g s v e r 5 i o n ： s e p2 0 0 6 h a s k e l l9 8 啪d e ：r e 5 七a r 七可i 七hc o 瓤i 臣n dl i n eo p 七i o n 一9 8c oe n a b l ee x t e n s i o n s t y p e ：? f o rh e l p t e 暑c q u i c k c h e c kp r o pr e v u n i 七 o k ，p a s s e d1 0 0c e s c 5 t e 8 c q u i c k c h e c kp r o p r e v p p o k ，p a 昌s e d1 0 0t e s c 8 冀 t e 8 七q u i c k c h e c kp r o p r e v i t e v o l c ，p a 暑8 e d1 0 0 七e s 七s t e 8 七 l “ 一 。” ， ，￥、，。 图2 2 用q u i c k c h e c k 测试列表相关性质 可以看出，上面的性质都成立。然而如果我们给定下面一个待测性质 1 6 中山大学硕士论文函数式程序设计语言h a s k e l l 的测试数据系统生成 p f o pr e v e q x s= r e v e r s ex s 2 = x s w h e f et y p e s = ( x s ：圳 ( 一个列表的逆和它本身相同) 那么，我们可以得到如图2 3 测试结果： 图2 3 用q u i c k c h e c k 测试p r o p j t e v e q 函数 即通过5 次测试之后，在第六次测试中，q 晡c k c h e c k 找到了一个令上面性 质不成立的反例，这个数据便是【1 ，3 ，3 】。 从上面的例子可以看出，作为一种自动化测试工具，对于大多数程序来说， q u i c k c h e c k 是行之有效的! 然而，由于q u i c k c h e c k 采用了随机生成测试数据的 方法，这就使得它存在一些先天性的不足，即对于有些数据可能永远也生成不到! 特别是对于那些多元组类型，假如程序的b u g 就存在于某个特定的元组数据上的 话，q u i c k c h e c k 可能很难发现! 举个例子： 我们定义下面的一个函数： m y a d d ：i i l t - i n t 一 i n t - i n t 一 i n t m y a d d xymn i 觚d x 2 ，y 一2 ，瑚f ：2 ，n 一2 】= x + y 斗m + i l + 1 i 甜l e r w i s e = x + y 嘲 1 7 中山大学硕士论文函数式程序设计语言h 硒k e l l 的测试数据系统生成 p r o 叫y a d d xymn = m y a d dxymn x + y + m + n w h e r et y p e s = ( x ：i n t ，y ：i n t ，m ：i i l t ，n ：i n t ) 根据m y a d d 函数的定义，它完成的功能是输入4 个i n t 型的参数，当且仅 当这四个参数的值都为2 的时候，函数的返回值为这四个参数的和加l ，即9 。 其他情况下和普通的四个数的加法没有区别。由此看出，m y a d d 函数和普通的 四个数的加法并不完全相同，因此我们定义的待测函数p f 0 1 y a d d 应该存在 b u g ，这个b u g 就是当输入的四个数都为2 时不成立。 然而，我们利用q u i c k c h e c k 来测试这个程序的时候，却得到如图2 4 的结 果： f i j e 副i t a c t i o n s豇o w s eh e | p 匠多镌岛卜嬲囝绱曾 t e s 七 瑚y a d d1 2 3 4 1 0 t e s c m y a d d2 22z 9 t e s c 2 + z + 2 + 2 8 t e 8 七 q u i c k c h e c kp r o pm y d d o k ，p a s s e d1 0 0t e s 七s t e 。t q u i c k c h e c kp r o p 即y a d d o k ，p a s s 芒d1 0 0t e s 七s t e s t q u i c k c h e c kp r o p w d d o k ，p a s 8 e di 0 0t e s c s t e s c q u i c k c h e c kp r o p w d d o k ，p a s s e d 】0 0t e 昌七s t e s 七 l 滋 利用q 哳c k c h e c k 多次进行测试，它却并未能够发现程序中存在的b u g ，由 此可见，在某些情况下，q u i c k c h e c k 可能并不适用。 二、s m a l l c