• Would be great if our code always workedproperly the first $me we run it! 如果我们的代码总能在第一次运行就完美运行，那就太棒了
• But life ain’t perfect, so we need: 但是人生不完美的，所以我们需要
– Testing methods 测试方法
• Ways of trying code on examples to determine if running correctly 使用不同的例子测试代码并查看他是否正确
– Debugging methods 调试方法
• Ways of fixing a program that you know does not work as intended 修改不正常程序的方法
• Design your code for ease of testing anddebugging 提前弄清楚我们的代码将使我们测试和调试变得简单
– Break program into components that can be tested and debuggedindependently 它们将代码分解成独立的模块，从而独立的进行测试和调试
– Document constraints on modules 写出好的文档
• Expectations on inputs, on outputs 我对输入和输出的期望是什么
• Even if code does not enforce constraints, valuable for debuggingto have description 即使通过测试，代码没有超过限制，这对我们调试的描述也是有用的，特别是当你准备追查一段代码为啥没有按照预期执行时
• Ensure that code will actually run 保证代码可以正常运行
– Remove syntax errors 剔除语法错误
– Remove static semantic errors 删除静态语义错误
– Both of these are typically handled by Python interpreter python程序会发现这些东西
• Have a set of expected results (i.e.input-output pairings) ready 提前摸索出一套预期的结果对于一个特定的输入，我们会期待程序有怎样的输出
• Goal:
– Show that bugs exist 证明错误却是存在
– Would be great to prove code is bug free, but generally hard 如果能证明代码没问题，那非常棒，但是那是非常难以做到的没有错误的
• Usually can’t run on all possible inputs to check 一个原因是我们无法做到所有的测试
• Formal methods sometimes help, but usually only on simpler code 有一些正式的方法，它们基于数学，有时候会帮我们证明代码没有错误，但是通常只对简单代码有效
• Want to find a collection of inputs thathas high likelihood of revealing bugs, yet is efficient 找到一系列输入，它们很有可能会暴露错误，这样的测试实际上非常有效，这就是所谓的测试套件
– Partition space of inputs into subsets that provide equivalentinformation about correctness 其思想史我们将输入分解成子集，为代码的正确性提供等效信息
• Partition divides a set into group of subsets such that eachelement of set is in exactly one subset 我们要做的就是将所有可能的输入集分割成一系列的子集，并保证每一个元素都现在一个子集里
– Construct test suite that contains one input from each element ofpartition 然后我将构建一个测试集，其中至少包含每个子集的一个元素
– Run test suite 运行测试集，并检查它能否成功运行
def isBigger(x, y):
“““Assumes x and y are ints returns True if xis less than y else False”””
假定x和y是整数，如果x比y小返回真否则返回假
• Input space is all pairs of integers 输入空间包含所有成对的指数
• Possible partition 可能的分区
– x positive, y positive xy都是正数
– x negative, y negative xy都是负数
– x positive, y negative x正y负
– x negative, y positive x负y正
– x = 0, y = 0 xy都是0
– x = 0, y != 0 x是0 y不是0
– x != 0, y = 0 x不是0 y是0
• Lots of other choices 我们有很多其他的选择
– E.g., x prime, y not; y prime, x not; both prime; both not 例如，x是质数而y不是，y是质数而x不是，xy都是质数，xy都不是质数（但是这与问题不相关）
• Space of inputs often have naturalboundaries 一些输入空间经常有些自然界限
– Integers are positive, negative or zero 整数 要么是正数 要么是负数 要么是0
– From this perspective, have 9 subsets 但是从这个方面考虑，应该有九种可能性啊
• Split x = 0, y != 0 into x = 0, y positive and x =0, y negative 但是例如我们数的下是0 y不是0就包含了两种，x是0 y是正数和x是0 y是负数的可能性
• Same for x != 0, y = 0 还有 x不是0 y是0也包含两种可能性
• What if no natural partition to inputspace? 输入空间没有自然分区怎么办
– Random testing – probability that code is correct increases withnumber of trials; but should be able to use code to do better 我可以做随机测试，用一大堆例子来不断尝试，试验次数越多，代码的正确率越高，但是这种情况我们可以使用代码来达到更好的效果
两类测试
– Use heuristics based on exploring paths through the specifications– black-box testing 一是通过特定分类使用启发式的方法探索路径，我们称之为黑盒测试
– Use heuristics based on exploring paths through the code –glass-box testing 二是通过代码本身使用启发式的方式探索路径，我们称之为白盒测试
• Test suite designed without looking atcode 这个测试套件的设计使人们无需查看代码
– Can be done by someone other than implementer 他的优点在于制作代码以外的人可以用它来测试代码
– Will avoid inherent biases of implementer, exposing poten.al bugsmore easily 让其他人来进行测试可以避开制作代码的人的固有偏见
– Testing designed without knowledge of implementation, thus can bereused even if implementation changed 另一个好处是，测试不需要知道编写代码的知识，因此我们可以重复使用测试套件即使代码改变了
• Paths through specification: 规范的路径有两种情况
– x = 0
– x > 0
• But clearly not enough 清晰，但还不够
• Also good to consider boundary cases 还要考虑边界情况
– For lists: empty list, singleton list, many element list 对于列表：空列表，单例列表，多元素列表
– For numbers, very small, very large, “typical” 对于数字来说 数字很小或者数字很大还有其他非常“典型”的情况（对于不同的情况，典型的情况是不同的）:
• For our sqrt case, try these: 对于上面的平方根例子，试试这些输入值（图在下面）
– First four are typical 前四个是典型的
• Perfect square 完美的平方数
• Irrational square root 没有整数平方根的数
• Example less than 1 小于1的小数
– Last five test extremes 后五个输入值
• If bug, might be code, or might be spec (e.g. don’t try to findroot if eps tiny) 如果出现bug了，可能是由于代码的原因，也可能是由于规格（输入值）的原因（比如本例中，如果eps（精确度）太小了，可能会找不到平方根
• Use code directly to guide design of testcases 使用代码本身来引导测试用例的设置
• Glass-box test suite is path-complete if every potential paththrough the code is tested at least once 一个好的白盒检验套件也被称为 穷举路径测试，其中代码片段每一条可能的路径都会被至少检测了一次
– Not always possible if loop can be exercised arbitrary times, orrecursion can be arbitrarily deep 这经常是不可能的比如一个循环被执行了任意次，或者递归被执行了任意深度
• Even path-complete suite can miss a bug, depending on choice ofexamples 特别注意即使是穷举路径测试，也可能会错过一个bug，这基于例子的选择
• Test suite of {-2, 2} will be pathcomplete 测试套件是{-2.2}的情况就可以包含所有测试路径 -2是if函数后的路径，+2是else函数后的路径
• But will miss abs(-1) which incorrectlyreturns -1 但是会错过一个bug -1的绝对值在本例中仍然是-1 而不是我们周知的+1 （边界条件）
– Testing boundary cases and typical cases would catch this {-2 -1, 2} 测试边界条件和典型条件 (-2，-1，2)
• Exercise both branches of all ifstatements 确保测试了if语句的所有分支
• Ensure each except clause is executed 确保每一个except语句都被测试了
• For each for loop, have tests where: 对于for循环语句，我不能执行所有的例子，但我可以执行三个案例
– Loop is not entered 没有进入循环
– Body of loop executed exactly once 循环主体只执行了一次
– Body of loop executed more than once 循环主体被执行了好多次
• For each while loop, 对while语句
– Same cases as for loops 和for循环一样的例子
– Cases that catch all ways to exit loop 额外的方面（ 捕捉所有的跳出循环的不同路径
• For recursive functions, test with norecursive calls, one recursive call, and more than one recursive call 对于递归函数，我们可以测试如果没有递归会发生什么，如果递归了一次会发生什么，如果递归了不止一次会发生什么
• Start with unit testing 从单元测试的方法入手
– Check that each module (e.g. function) works correctly 单元测试会检测一个模块(比如函数)检测他是否正确 (算法错误)
• Move to integration testing 接着进行集成测试，
– Check that system as whole works correctly 检验作为整体的系统是否正常工作 （集成错误）
• Cycle between these phases 修改完成后再倒回去进行单元测试和集成测试，直到找到所有的bug
• Drivers are code that 驱动就是代码
– Set up environment needed to run code 我们将建立环境，，也就是说我们将建立一段代码，从而绑定全局变量、数据结构以及其他需要我做测试的东西
– Invoke code on predefined sequence of inputs 在每一种检测手段都运行一遍这段代码（输入序列）
– Save results, and 保存结果
– Report 输出报告
• Drivers simulate parts of program thatuse unit being tested 驱动的好处是他基本会模拟正在进行测试的单元
• Stubs simulate parts of program used byunit being tested 存根仅仅模仿了程序的一部分，这部分被正在进行测试的单元所使用
– Allow you to test units that depend on softwarenot yet written 存根的好处在于它可以测试一些依赖于软件的单元，即便你未曾写过他，可以做到这点
• Start with unit testing 从单元测试开始
• Move to integration testing 然后进行集成测试
• After code is corrected, be sure to do regression testing: 当我完成调试并且纠正完所有的错误的时候，记得做回归测试
– Check thatprogram still passes all the tests it used to pass, i.e., that your code fixhasn’t broken something that used to work 返回去，测试一下程序是否仍然能通过所有它之间已经通过的检验，即使之前的代码片段已经通过检验。
因为我已经进行了修改，我不确定是否改乱了之前的代码
• The “history” of debugging 调试的历史
– Often claimed that first bug was found by team at Harvard that wasworking on the Mark II Aiken Relay Calculator 第一个bug是被哈佛的一个小组发现的，它们的项目后来被称为马克II型艾肯中继器计算机
– A set of tests on a module had failed; when staff inspected theactually machinery (in this case vacuum tubes and relays), they discoveredthis: 在这个计算机的里的模块测试总是失败，当时的工作人员爬进了电脑里，找到了bug的原因，是一只飞蛾（飞蛾英文bug）
• However, the term bug dates back evenearlier: 然后bug这个词出现的可能更早
– Hawkin’s New Catechism of Electricity, 1896 1896年的一本教科书中说
• “The term ‘bug’ is used to a limited extent to designate any faultor trouble in the connections or working of electrical apparatus.” “bug”这个词从某种程度上是指电子器械链接或者工作过程中出现的任何错误或麻烦
下面先讲一下bug的类型
• Overtvs. covert: 显性错误和隐形错误
– Overt has an obviousmanifestation – code crashes or runs forever 显性意味着一个很明显的变化，代码崩溃了或者代码一直运行
– Covert has no obviousmanifestation – code returns a value, which may be incorrect but hard todetermine 隐形错误更加不易察觉，它没有明显的变化，代码返回一个值，但是这个值不好判断他正不正确，
•Persistent vs. intermittent: 永久性错误和间歇性错误
– Persistent occurs everytime code is run 永久性错误在代码每次运行时都会发生
– Intermittent onlyoccurs some times, even if run on same input 间歇性错误仅仅在有些时候发生，有时候它仅仅在特定输入时发生，有时候输入相同还是会偶尔发生错误
• Overt and persistent 显性永久代码
– Obvious to detect 很容易发现
– Good programmers use defensiveprogramming to try to ensure that if error is made, bug will fall into thiscategory 好的程序员会使用防御性编程，来确保如果错误发生了，错误将会落入到一个显而易见的范畴里
• Overt and intermittent 显性间歇性代码
– More frustrating, can be harder to debug, but if conditions thatprompt bug can be reproduced, can be handled 很不幸，更难通过调试来解决，但是如果可以重现出现错误的情况，我们也就可以试着解决它
• Covert 隐形错误
– Highly dangerous, as users may not realize answers are incorrectuntil code has been run for long period 隐形错误非常危险，不明显不易察觉，它可能是间歇性错误，那就更麻烦了！
• Treat as a search problem: looking forexplanation for incorrect behavior 将调试看作搜索问题：我想找到一种解释，解释代码中为什么会出错
– Study available data – both correct test cases and incorrect ones 研究手头的数据，正确的测试用例和错误的测试用例都要看
– Form an hypothesis consistent with the data 建立一个和数据一致的假设
– Design and run a repeatable experiment with potential to refutethe hypothesis 设计和运行一个可重复的试验，但会包含驳回假设的可能性
– Keep record of experiments performed: use narrow range ofhypotheses 保持在试验中纪录，使用范围更小的假设
• Want to narrow down space of possiblesources of error 选出可能出现错误的范围，然后把他不断缩小
• Design experiments that exposeintermediate stages of computation (use print statements!), and use results tofurther narrow search 设计一些东西，帮我们暴露代码计算的中间环节（通过使用print语句（将我期望的信息和实际输出的信息对比）），然后使用结果缩小搜索范围
• Binary search can be a powerful tool forthis 二分法对于调试搜索来说是个好办法
这个函数的功能是想问一个字符串是不是回文结构
Ps assert是断言函数，我们将在下一章详细学习他
• Suppose we run this code: 假设我们开始运行这段代码了（silly）
– We try the input ‘abcba’, which succeeds 我们运行abcba 正确！
– We try the input ‘palinnilap’, which succeeds 我们输入 palinnilap 正确
– But we try the input ‘ab’, which also ‘succeeds’ 我们输入ab 他却不正确了
• Let’s use binary search to isolate bug(s) 我们可以用二分法分离出错误的具体位置
• Pick a spot about halfway through code,and devise experiment 在代码的中间的位置，并设计一个试验
– Pick a spot where easy to examine intermediate values 选择这点，因为很容易检测他的中间值，在这里放置一个print语句
在代码中间（循环之后）加了一个print（result）语句
• At this point in the code, we expect (forour test case of ‘ab’), that result should be a list [‘a’, ‘b’] 这个时候代码中我们期待的结果是输出一个列表[”a”，”b”]（我们输入的是ab）
• We run the code, and get [‘b’]. 我们运行程序，却只得到了[“b”]
• Because of binary search, we know that atleast one bug must be present earlier in the code 由于二分搜索，我们知道了至少一个bug在print语句之前的代码中
• So we add a second print 所以我们添加第二个print语句
在循环中添加一个print语句
• When we run with our example, the printstatement returns 当我们运行这个例子的时候，输出语句会返回
– [‘a’] 第一次输入a，返回a
– [‘b’] 第二次输入b 返回b (应该返回a，b的列表)
• This suggests that result is not keepingall elements 这个现象说明，result没有保留有所有的元素 经过观察我们发现 result在每次循环都会重新定义
– So let’s move the initialization of result outside the loop andretry 所以我们将结果的初始化移动到循环之外，然后重试
现在我们第二次输入b后显示的是正确的值（值是[a,b]）了
但是程序依然返回了yes，说明ab结构仍然是回文结构，说明这段代码仍然有问题
• So this now shows we are getting the datastructure result properly set up, but we still have a bug somewhere 它表示数据结构已经构建完毕，但是我们仍然有一个bug在一些地方
– A reminder that there may be more than one problem! 这是一个很好的提醒，意味着仅仅修正了一个代码的问题，其他地方就没有错误了
– This suggests second bug must lie below print statement; let’slook at isPal 这其实也暗示了第二个代码一定在输出语句的下面，那其实应该是ispal的定义有问题
– Pick a point in middle of code, and add print statement again 重复上述过程，选择一个代码的中点，把输出语句加入进去
我们把输出语句 print(temp,x)加入到了代码中，这个输出语句可以表示出两个变量，而且这两个变量应该是相反的。
但是事实上并不是这样的，x和temp这两个变量是完全一样的
• At this point in the code, we expect (forour example of ‘ab’) that x should be [‘a’, ‘b’], but temp should be [‘b’,‘a’], however they both have the value [‘a’, ‘b’] 在这个地方，x应该是[“a”,”b”]，temp应该是[“b”,”a”]，但是他们的值却都是[“a”,”b”]
• So let’s add another print statement,earlier in the code 所以让我们继续添加print语句，在代码更往前的地方
在temp = x之后，temp.reverse之前
添加了一个print（temp,x）语句，继续检测变量的值
我们发现两个print语句输出的值是一样的，temp和x的值也都是一样的
• And we see that temp has the same valuebefore and after the call to reverse 我们可以看到temp和x的值是一样上，无论reverse之前还是之后
• If we look at our code, we realize wehave committed a standard bug – we forgot to actually invoke the reverse method 让我们看一看代码，我们就发现了代码，我们用错了代码，reverse语法应该是这样的， 列表名.reverse（）
– Need temp.reverse() 语句需要改成这样temp.reverse（）
• So let’s make that change and try again 把这个错误改正过来然后重试一下
现在我们改正了错误再来运行一下代码，看看有没有问题
我们又发现了问题，第二次print语句输出的temp值和x的值都反向了，这不对了啊
• But now when we run on our simpleexample, both x and temp have been reversed!! 但是现在我们运行我们的例子的时候，x和temp都反向了啊！！！
• We have also narrowed down this bug to asingle line. The error must be in the reverse step 我们可以确定错误一定处在两个print语句中夹着那句反向语句中，因为它们之前的语句正确，之后的语句却错误
• In fact, we have an aliasing bug –reversing temp has also caused x to be reversed 事实上，我们可能遇到了别名错误，，反转temp变量，也把x变量反转了
– Because they are referring to the same object 因为他们指向了同样的变量
（当我对某物进行反向时，我创建的另一个名称却指向了同样的东西，这就导致了另一个反向）
我们修复一下它（用的是列表的克隆的方法），即不让temp指向x的值，而让temp指向x的副本，把temp=x这个语句换位 temp=x[:]
然后我们再来运行一下他
这次的输出结果是 第一次 [“a”,”b”]，[“a”,”b”]
第二次[“a”,”b”] ，[“b”,”a”]
正确啦~~
• And now running this shows that beforethe reverse step, the two variables have the same form, but afterwards onlytemp is reversed. 这次的运行显示，反向之前两个变量有相同的值，反向之后却是不同的值了
• We can now go back and check that ourother tests cases still work correctly 我们要返回去，用其他的值检测一下他是不是依然正确
• Look for the usual suspects 查看最长犯错误的地方，（典型错误）（忘了边缘条件，传入的参数是错误的，反向参数的顺序，忘记了调用函数的方法，到底是调用还是仅仅访问了一下）
• Ask why the code is doing what it is, notwhy it is not doing what you want 不要问代码为什么没有做你想做的事，而是问代码正在做什么事（尝试关注代码正在做什么，而不是尝试找出错误发生的地方）
• The bug is probably not where you thinkit is – eliminate locations bug可能不在你想象的位置（排除错误可能出现的位置，通常是用二分法）
• Explain the problem to someone else 试一试跟别人解释这个问题，（对问题的说明常常会帮助你发现错误可能的位置
• Don’t believe the documentation 不要相信说明文档! (这是一类很糟糕的文档，它很容易延迟你的调试时间，而且有时说明文档也是错误的)
• Take a break and come back to the buglater 如果有困难的话，可以休息一下出去散散心，再回来解决它
这一节我们学习了测试和调试，测试分为黑盒测试和白盒测试，
黑盒测试我们通过特定规范的执行路径，而白盒测试我们通过代码内部的结构来确定我们的输出序列
我们还讨论了调试的相关知识，也就是说，定位出我们代码错误的位置
特殊之处在于，我们将会调试做为一个搜索，并使用二分搜索的方法，并检测错误的来源
