《Structure and Interpretation of Computer Programs》lecture 7 webhand.pdf_大学文库

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 7.1 Slide 7.1.1 In the past few lectures, we have seen a series of tools for helping us create procedures to compute a variety of Good programming practices computational processes. Before we move on to more complex issues in computation, it is useful to step back and look at more general issues in the process of creating procedures In particular, we want to spend a little bit of time talking about good programming practices. This sounds a little bit like lecturing about"motherhood and apple pie", that is, a bit like lking about things that seem obvious, apparent, and boring in that everyone understands and accepts them. However, it is surprising how many"experienced" programmers don't execute Le 8n20 60015e good programming practices, and we want to get you started on the right track Slide 7.1.2 Good programming practices Thus, in this lecture we are going to look briefly at several methodological aspects of creating procedures: designing the Code design components of our code, debugging our code when it doesnt Debugging run correctly, writing documentation for our code, and testing · Documentation our code. We will highlight some standard practices for each stage, and indicate why these practices lead to efficient and Types as tools for debugging effective generation of code 6001 SICP Slide 7.1.3 Lets start with the issue of how to design code, given a problem statement. There are many ways to do this, but most Code layout and design of them involve some combination of the following steps Design of Design of data structures Data structures Design of computational modules Natural collections of information Design of interfaces between modules Suppression of detail from use of data Procedural modules Once we have laid out the general design of these stages, we follow by creating specific instantiations of the actual components. We have not yet talked about data structures in Scheme, and will return to this issue in a few lectures. For our e mnao 60015e purposes here, the key thing to note is that when designing a computational system, it is extremely valuable to decide what kinds of information naturally should be grouped together, and to then create structures that perform that grouping, while maintaining interfaces to the structures that hide the details. For example, one thinks naturally of a vector as a pairing of an x and y coordinate. One wants to

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 7.1 Slide 7.1.1 In the past few lectures, we have seen a series of tools for helping us create procedures to compute a variety of computational processes. Before we move on to more complex issues in computation, it is useful to step back and look at more general issues in the process of creating procedures. In particular, we want to spend a little bit of time talking about good programming practices. This sounds a little bit like lecturing about "motherhood and apple pie", that is, a bit like talking about things that seem obvious, apparent, and boring in that everyone understands and accepts them. However, it is surprising how many "experienced" programmers don't execute good programming practices, and we want to get you started on the right track. Slide 7.1.2 Thus, in this lecture we are going to look briefly at several methodological aspects of creating procedures: designing the components of our code, debugging our code when it doesn't run correctly, writing documentation for our code, and testing our code. We will highlight some standard practices for each stage, and indicate why these practices lead to efficient and effective generation of code. Slide 7.1.3 Let’s start with the issue of how to design code, given a problem statement. There are many ways to do this, but most of them involve some combination of the following steps: • Design of data structures • Design of computational modules • Design of interfaces between modules Once we have laid out the general design of these stages, we follow by creating specific instantiations of the actual components. We have not yet talked about data structures in Scheme, and will return to this issue in a few lectures. For our purposes here, the key thing to note is that when designing a computational system, it is extremely valuable to decide what kinds of information naturally should be grouped together, and to then create structures that perform that grouping, while maintaining interfaces to the structures that hide the details. For example, one thinks naturally of a vector as a pairing of an x and y coordinate. One wants to

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology be able to get out the coordinates when needed but in many cases, one thinks naturally of manipulating a vector as a unit. Similarly, one can imagine aggregating together a set of vectors, to form a polygon, and again one can think of manipulating the polygon as a unit. Thus, a key stage in designing a computational system is determining the natural data structures of the system Slide 7. 1. 4 Code layout and design A second stage in designing a computational system is deciding how best to break the computation into modules or pieces. This is often as much art as science but there are some general Data structures guidelines that help us separate out modules in our design. For Procedural modules example, is there part of the problem that defines a computation Computation to be reused Suppression of detail from use of procedure that is likely to be used many times? Are there parts of the problem that can be conceptualized in terms of their behavior, e.g. how they convert certain inputs into certain types of outputs, without worry ing about the details of how that is done I Does this help us focus on other parts of the computation? Or said a bit differently, can one identify parts of the computation in terms of their role, and think about that role in the overall computation, without having to know details of the computation? If one can, these parts of the computation are good candidates for separate modules, since we can focus on their use while ignoring the details of how they achieve that computation Slide 7.1.5 Finally, given that one can identify data structures, whose information is to be manipulated; and stages of computation, in Code layout and design which that information is transformed: one wants to decide the Design of overall flow of information between the modules. What types Data structures of inputs does each module need? What types of data does each Procedural modules module return? How does one ensure that the correct types are Interfaces provided, in the correct order "types"of inputs and outputs These kinds of questions need to be addressed in designing the overall flow between the computational modules 48m0 601h Slide 7.1.6 An example of code modules This is perhaps more easily seen by thinking about an example and in fact you have already seen one such example, our Finding the sqrt of X Make a guess, G implementation ofs grt. When we implemented our If it is good enough, stop Otherwise, get a new guess by averaging G and method for square roots, we actually engaged in many of these stages. We didn t worry about data structures, since we were simply interested in numbers. We did, however, spend some Good-enur effort in separating out modules. Remember our basic Average computation: we start with a guess; if it is good enough, we 6 001 SICP I guess, and the ratio of the target number and the guess, and r guess by averaging the curren continue To design this system, we separated out several modules: the notion of averaging, the notion of measuring enough". We saw that some of these modules might themselves rely on other procedural abstractions; for

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. be able to get out the coordinates when needed, but in many cases, one thinks naturally of manipulating a vector as a unit. Similarly, one can imagine aggregating together a set of vectors, to form a polygon, and again one can think of manipulating the polygon as a unit. Thus, a key stage in designing a computational system is determining the natural data structures of the system. Slide 7.1.4 A second stage in designing a computational system is deciding how best to break the computation into modules or pieces. This is often as much art as science, but there are some general guidelines that help us separate out modules in our design. For example, is there part of the problem that defines a computation that is likely to be used many times? Are there parts of the problem that can be conceptualized in terms of their behavior, e.g. how they convert certain inputs into certain types of outputs, without worrying about the details of how that is done. Does this help us focus on other parts of the computation? Or said a bit differently, can one identify parts of the computation in terms of their role, and think about that role in the overall computation, without having to know details of the computation? If one can, these parts of the computation are good candidates for separate modules, since we can focus on their use while ignoring the details of how they achieve that computation. Slide 7.1.5 Finally, given that one can identify data structures, whose information is to be manipulated; and stages of computation, in which that information is transformed; one wants to decide the overall flow of information between the modules. What types of inputs does each module need? What types of data does each module return? How does one ensure that the correct types are provided, in the correct order? These kinds of questions need to be addressed in designing the overall flow between the computational modules. Slide 7.1.6 This is perhaps more easily seen by thinking about an example – and in fact you have already seen one such example, our implementation ofsqrt. When we implemented our method for square roots, we actually engaged in many of these stages. We didn’t worry about data structures, since we were simply interested in numbers. We did, however, spend some effort in separating out modules. Remember our basic computation: we start with a guess; if it is good enough, we stop; otherwise we make a new guess by averaging the current guess, and the ratio of the target number and the guess, and continue. To design this system, we separated out several modules: the notion of averaging, the notion of measuring “good enough”. We saw that some of these modules might themselves rely on other procedural abstractions; for example

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology our particular version of good enough"needed to use the absolute value procedure, though other versions might ot Slide 7.1.7 Once we had separated out these notions of different computations: average and good-enough, we considered the An example of code modules overall flow of information through the modules. Note by the Finding the sqrt of x Make a guess, G way that we can consider each of theses processes as a black If it is good enough, stop ox abstraction, meaning that we can focus on using these Otherwise, get a new guess by averaging G and procedures without having to have already designed the specific implementation of eacl Now what about the flow between these modules? In our case Good-enur? average G we began with a guess, and tested to see if it was good enough If it was, we could then stop, and just return the value of the 600SC Slide 7.1.8 An example of code modules If it was not, then we needed to average the current guess and Finding the sqrt ofX the ratio of our target number to the guess Make a guess, G -If it is good enough, stop Otherwise, get a new guess by averaging G and G Good-enuf? Average 82003 Slide 7.1.g And then we need to repeat the entire process, with this new alue as our new guess An example of code modules The point of laying out these modules, or black boxes, is that Finding the sqrt of X Make a guess, G we can use them to decide how to divide up the code, and how If it is good enough, stop to isolate details of a procedure from its use. As we saw when Otherwise, get a new guess by averaging G and we implemented our sgrt procedure, we can change details of a procedure, such as average, without having to Good-enur? change any of the procedures that use that particular Abs omponent. As well, the flow of information between the modules helps guide us in the creation of the overall set of Thus, when faced with any new computational problem, we want to try to engage in the same exercise: block out hunks of the computation that can be easily isolated; identify the inputs and outputs from each chunk; and lay out the overall flow of information through the system. Then we can turn to implementing each of the units separately and testing the entire system while isolating the effects of each unit

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 7.1.10 A second key element to good programming practice is code Documenting code documentation. Unfortunately, this is one of the least well practiced elements- far too often programmers are in such a supporting code maintenance hurry to get things written that they skip by the documentation Can you read your code a year after writing it and still understand why you made particular stage. While this may seem reasonable at the time of code design decisions? Identifying input/output behaviors creation, when the design choices are fresh in the program, vne creators mind, six months later when one is trying to read code(even one's own), it may be very difficult to reconstruct why certain choices were made. Indeed, in many commercial programming settings, more time is spent on code maintenance <: 8n2003 6 001 SICP and modification than on code generation, yet without good documentation it can be very difficult or inefficient to understand existing code and change it As well, good documentation can serve as a valuable source of information about the behavior of each module enabling a programmer to maintain the isolation of the details of the procedural abstraction from the use of that abstraction. This information can be of help when debugging procedures Slide 7.1.ll As with designing procedural modules, the creation of good documentation is as much art as science. Nonetheless here are Documenting code some standard elements of well-documented code. We are Description of input/output behavior going to illustrate each of these with an example Expected or required types of arg List of constraints that must be satisfied by arguments or stages of computation Expected state of computation at key points in 8m2m03 6 001 SICP Slide 7.1.12 An example of code documentation First, describe the goal of the procedure. Is it intended to part 1 ambda《xkgu approxinate square root by of some other computation(as this helper function is)? If so vh。s。 aquare the rough descript ::: root we are seeking have been a bit cryptic (in order to fit things on the slide)and we might well want to say more about"successive refinement f(ood-enuf?xgue器 (though we could defer that to the documentation under the qrrt-helper x (inprove x que improve procedure). We also identify the role of each argument to the procedure 48m0

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 7.1.13 Second, describe the types of values used in the computation An example of code documentation In this case, the inputs or parameters are both numbers, and the returned value is also a number. Actually, if we were more 7 compute approxinate square root by nement,ques⊥ g curre careful here, we would require that X be a positive number, and ;:appx。x⊥mat。n,X⊥8 number who器e8 quare we would place a check somewhere to ensure that this is true ot we are seek⊥ng Type: (number, number)> number E(good-enuf?宮gues 6001 sICP An example of code documentation Slide 7.1.14 Third, describe constraints, either desired or required, on the 1 ambda《xgu it: compute approxinate square root by computation. Here, we know that squaring the guess should get ve refinement, guess is current ;:;apx。 ximation, x is nunber wh。 Go square us something close to the target value, although we really don't i root we are seekins guarantee this until we reach the termination stage ood-enaf?xgue器 qrrt-helper x 48m0 6001 SICP Slide 7.1.15 An example of code documentation And fourth, describe the expected state of the computation ar the goal at each stage in the process. For example, here we indicate what good-enuf? should do, namely test if 77:ucc容 ve refinement,日ue器 current quaro our approximation is sufficiently accurate. Then we indicate 7: Type: (number, number)- number that if this is the case, we can stop and what value to return to (ood-enuf?xque器器); can we stop? satisfy the contract of the entire procedure. And we indicate f yes, return how to continue the process, though we could probably say a it more about what improve should do then get better cue图s Notice how we can use the documentation to check some aspects of our procedure's"contract". Here, we have indicated 8n003 60015e that the procedure should return a number. By examining the f expression, we can see that in the consequent clause, if the input parameter guess is a number, then we are guaranteed to return a number. For the alternative clause, we can use induction to reason that given numbers as input, we also return a number, and hence the entire procedure returns a value of the correct type

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 7.2.3 Sometimes, however, we are using a legal variable(that is, one that we intended to hold some value) but the evaluator still Common errors complains that this variable is unbound. How can that be? Remember that in Scheme a variable gets bound to a value in Unbound variable may directly tell the interpreter to give a variable some valie e one of several ways. We may define it at top level", that is, we Cause: typo olution search for instance We may define it internally within some procedure. Or, we Unbound variable may use it as a formal parameter of a procedure, in which case Solution it gets locally bound to a value when the procedure is applied In the last two cases, if we attempt to reference the variable Use debugging tools to isolate instance outside the scope of the binding, that is, somewhere outside the 4 6001 sICP bounds of the lambda expression in which the variable is being used. we will get an unbound variable error. This means that we have tried to use a variable outside its le domain, and we need to correct this. This probably means we have a coding error, but we can isolate the problem either by searching for instances of the variable in the code file, or by using the debugger Slide 7.2.4 The Debugger So what does a debugger do to help us find errors? Each programming language will have its own flavor of debugger Places user inside state of computation at time of for an interpreted language like Scheme, the debugger actually places us inside the state of the computation. That is, when an error occurs, the debugger provides us access to the state of the Reductions computation at the time of the error, including access to the Can examine bindings of variables and parameters aues of the variables within the computation. Moreover, we can step around inside the environment of the computation: we can work back up the chain of computational steps, examining I what values were produced during reductions(where computation is reduced to a simpler expression), and examin what values were produced during substitutions(where the computation was converted to a simpler version or ng itself Side.2.5 Debugger example For example, here is a simple procedure, which we have called nea.dentify atack fran with argument 2. Notice what happens when we hit the be⊥0M unbound variable error and enter the debugger. We are placed The "TRS at the spot in the computation at which the error occurred. If /=so baena varaszst bes 4f(=n0 see what expressions were reduced to get to this point, and what =1 ne c a w/ aE t te c-a 1) we choose to step back through the chain of evaluations, we can mo baf a a oI bar (e a to ( all 4+n(fon(-n1))) recursive versions of the same problem were invoked in reaching this stage In this case. we note that foo initially called with Foo (-n 1 rgument 2, and after a reduction through an if expression, 4 mm we arrived at an expression that contained within it a simpler coming from within the body of foo and is in the base case of the decision process a version of the same problem. This reduction stage repeated again, until we apparently reached the base case of the if expression, where we hit the unbound variable. We can see in this simple case that our unbound error is

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 7.2.3 Sometimes, however, we are using a legal variable (that is, one that we intended to hold some value) but the evaluator still complains that this variable is unbound. How can that be? Remember that in Scheme a variable gets bound to a value in one of several ways. We may define it at “top level”, that is, we may directly tell the interpreter to give a variable some value. We may define it internally within some procedure. Or, we may use it as a formal parameter of a procedure, in which case it gets locally bound to a value when the procedure is applied. In the last two cases, if we attempt to reference the variable outside the scope of the binding, that is, somewhere outside the bounds of the lambda expression in which the variable is being used, we will get an unbound variable error. This means that we have tried to use a variable outside its legal domain, and we need to correct this. This probably means we have a coding error, but we can isolate the problem either by searching for instances of the variable in the code file, or by using the debugger. Slide 7.2.4 So what does a debugger do to help us find errors? Each programming language will have its own flavor of debugger; for an interpreted language like Scheme, the debugger actually places us inside the state of the computation. That is, when an error occurs, the debugger provides us access to the state of the computation at the time of the error, including access to the values of the variables within the computation. Moreover, we can step around inside the environment of the computation: we can work back up the chain of computational steps, examining what values were produced during reductions (where computation is reduced to a simpler expression), and examining what values were produced during substitutions (where the computation was converted to a simpler version of itself). Slide 7.2.5 For example, here is a simple procedure, which we have called with argument 2. Notice what happens when we hit the unbound variable error and enter the debugger. We are placed at the spot in the computation at which the error occurred. If we choose to step back through the chain of evaluations, we can see what expressions were reduced to get to this point, and what recursive versions of the same problem were invoked in reaching this stage. In this case, we note that foo was initially called with argument 2, and after a reduction through an if expression, we arrived at an expression that contained within it a simpler version of the same problem. This reduction stage repeated again, until we apparently reached the base case of the if expression, where we hit the unbound variable. We can see in this simple case that our unbound error is coming from within the body of foo and is in the base case of the decision process

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 7.2.6 a second class of errors deals with mistakes in syntax Syntax errors creating expressions that do not satisfy the programming language's rules for creating legal expressions. A simple rong number of argume of these is an expression in which the wrong number ofone Source: programming en arguments is provided to the procedure. If this occurs while Solution: use debugger to isolate instance attempting to evaluate the offending expression, we will usually be thrown into the debugger -a system intended to help us determine the source of the error. In Scheme the debugger provides us with information about the environment in which he offending expression occurred. It supplies tools for 6 001 SICP examining the values associated with variable names, and for examining the sequence of expressions that have been evaluated leading up to this error. By stepping through the frames of the debugger, we can often isolate where in our code the incorrect expression resides Slide 7.2.7 A more insidious syntax error occurs when we use an expression of the wrong type somewhere in our code Syntax errors If we use an expression whose value is not a procedure as the Wrong number of arguments first subexpression of a combination, we will get an error that Source: programming error indicates we have tried to apply a non-procedure object. As Solution: use debugger to isolate instance before, the debugger can often help us isolate the location of errors this error, though it may not provide much insight into why an As procedure incorrect object was used as a procedure. For that, we may As arguments have to trace back through our code. to determine how this Source: calling error The harder error to isolate is one in which one of the argument 4 maor Solution: trace back through chain of call value was supplied to the offending expression expressions to a combination is of the wrong type. The reason this is harder to track down is that the cause of the creation of an incorrect object type may have occurred far upstream, that is, some other part of our code may have created an incorrect object, which has been passed through several levels of procedure calls before causing an error. Tracking down the original source of this error can be difficult, as we need to chase our way back through the sequence of expression evaluations to find where we accidentally created the wrong type of argument Slide 7. 2.8 Structure errors The most common sorts of errors, though, are structural ones his means that our code is syntactically valid-composed of Wrong initialization of parameters correctly phrased expressions, but the code does not compute what we intended because we have made an error somewhere Wrong end test in the code design. This could be for a variety of reasons and so on started a recursive process with the wrong initial values, or we are ending at the wrong place, or we are updating parameters incorrectly, or we are using the wrong procedure somewhere and so on. Finding these errors is tougher, since the code may run without causing a language error, but the results we get are

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 7.2.6 A second class of errors deals with mistakes in syntax – creating expressions that do not satisfy the programming language’s rules for creating legal expressions. A simple one of these is an expression in which the wrong number of arguments is provided to the procedure. If this occurs while attempting to evaluate the offending expression, we will usually be thrown into the debugger – a system intended to help us determine the source of the error. In Scheme, the debugger provides us with information about the environment in which the offending expression occurred. It supplies tools for examining the values associated with variable names, and for examining the sequence of expressions that have been evaluated leading up to this error. By stepping through the frames of the debugger, we can often isolate where in our code the incorrect expression resides. Slide 7.2.7 A more insidious syntax error occurs when we use an expression of the wrong type somewhere in our code. If we use an expression whose value is not a procedure as the first subexpression of a combination, we will get an error that indicates we have tried to apply a non-procedure object. As before, the debugger can often help us isolate the location of this error, though it may not provide much insight into why an incorrect object was used as a procedure. For that, we may have to trace back through our code, to determine how this value was supplied to the offending expression. The harder error to isolate is one in which one of the argument expressions to a combination is of the wrong type. The reason this is harder to track down is that the cause of the creation of an incorrect object type may have occurred far upstream, that is, some other part of our code may have created an incorrect object, which has been passed through several levels of procedure calls before causing an error. Tracking down the original source of this error can be difficult, as we need to chase our way back through the sequence of expression evaluations to find where we accidentally created the wrong type of argument. Slide 7.2.8 The most common sorts of errors, though, are structural ones. This means that our code is syntactically valid – composed of correctly phrased expressions, but the code does not compute what we intended, because we have made an error somewhere in the code design. This could be for a variety of reasons: we started a recursive process with the wrong initial values, or we are ending at the wrong place, or we are updating parameters incorrectly, or we are using the wrong procedure somewhere, and so on. Finding these errors is tougher, since the code may run without causing a language error, but the results we get are erroneous

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 7.2.9 This is where having good test cases is important. For example, when testing a recursive procedure, it is valuable to Evaluation and verification try it using the base case values of the parameters, to ensure that the procedure is terminating at the right place, and Choosing good test cases returning the right value. It is also valuable to select input Pick values for input parameters at limits of parameter values that sample or span the range of legal values legal range does it work with small values, with large values, does Pick values that span legal range of parameters hanging the input value by a small increment cause the Retest prior cases after making code changes expected change in output value? Slide 7.2.10 Debugging tools And what do we do if we find we have one of these structure 6? Well, our goal is to isolate the location of our The ubiquitous print/display expression misconception within the code, and to do this, there are two Tracing standard tools Stepping The most common one is to use a print or display expression that is, to insert into our code, expressions that will print out for us useful information at different stages of the computation For example, we might insert a display expression within the recursive loop of a procedure, which will print out information 6001 SICP about the values of parameters. This will allow us to check that parameters are being updated correctly, and that end cases are correctly seeking the right termination point. We might similarly print out the values of intermediate computations within recursive loops, again to ascertain that the computation is operating with the values we expect, and is computing the values we expect A related tool, supplied for example with Scheme, is a tracer This allows us to ask the evaluator to inform us about the calling conventions of procedures-that is, to print out the values of the parameters supplied before each application of the procedure we designate, and the value returned by each such procedure call. This is similar to our use of display expressions, but is handled automatically for us. It applies only to parameters of procedure calls however, so that if we want to examine for detailed states of the computation, we need to fall back on the display tactIc In some cases, it may help to actually walk through the substitution model, that is, to see each step of the evaluation. Many languages, including Scheme, provide a means for doing this -in our case called the stepper obviously tedious, but works best when we need to isolate a very specific spot at which an error is occurring, and t This is a mechanism that lets us control each step of the substitution model in the evaluation of the expression. It we don't want to insert a ton of display expressions Perhaps the best way to see the role of these tools is to look at an example, which we do next 6.001 Notes: Section 7.3

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 7.2.9 This is where having good test cases is important. For example, when testing a recursive procedure, it is valuable to try it using the base case values of the parameters, to ensure that the procedure is terminating at the right place, and returning the right value. It is also valuable to select input parameter values that sample or span the range of legal values – does it work with small values, with large values; does changing the input value by a small increment cause the expected change in output value? Slide 7.2.10 And what do we do if we find we have one of these structure errors? Well, our goal is to isolate the location of our misconception within the code, and to do this, there are two standard tools. The most common one is to use a print or display expression – that is, to insert into our code, expressions that will print out for us useful information at different stages of the computation. For example, we might insert a display expression within the recursive loop of a procedure, which will print out information about the values of parameters. This will allow us to check that parameters are being updated correctly, and that end cases are correctly seeking the right termination point. We might similarly print out the values of intermediate computations within recursive loops, again to ascertain that the computation is operating with the values we expect, and is computing the values we expect. A related tool, supplied for example with Scheme, is a tracer. This allows us to ask the evaluator to inform us about the calling conventions of procedures – that is, to print out the values of the parameters supplied before each application of the procedure we designate, and the value returned by each such procedure call. This is similar to our use of display expressions, but is handled automatically for us. It applies only to parameters of procedure calls, however, so that if we want to examine for detailed states of the computation, we need to fall back on the display tactic. In some cases, it may help to actually walk through the substitution model, that is, to see each step of the evaluation. Many languages, including Scheme, provide a means for doing this – in our case called the stepper. This is a mechanism that lets us control each step of the substitution model in the evaluation of the expression. It is obviously tedious, but works best when we need to isolate a very specific spot at which an error is occurring, and we don’t want to insert a ton of display expressions. Perhaps the best way to see the role of these tools is to look at an example, which we do next. 6.001 Notes: Section 7.3

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 7.3.1 Let's use an example of a debugging session to highlight these ideas. This will be primarily to fix a structural error, but A debugging example will see how the other tools come into play as we do this uppose we want to compute an approximation to the sine We want to compute sing the mathematical function. Here is a mathematical approximation that will give approximation us a pretty good solution. So let's try coding this up 6001 sICP Slide 7.3.2 Initial code example So here is a first attempt at some code to do this. We will define (sine x) assume that fact and small-enuf? already (define (aux x n current) exist. The basic idea behind this procedure is quite similar to (let ((next (/(expt x n)(fact n)))) what we did for square roots. We start with a guess. We then :: compute next term if (small-enuf? next) ; if small see how to improve the guess, in this case by computing the current::just return current guess next term in the approximation, which we would like to add (aux x (+ n 1) (+ current next) i otherwise, create new guess If this improvement is small enough, we are done and can ))) return the desired value. If not, we repeat the process with a (aux x 1 0)) better guess, by adding in the improvement to the current 6001 SICP Slide 7.3.3 Now, let's try it out on some test cases. One nice test case is st cases the base case, of x equal to 0. That clearly works. Another ice test case is when x is equal to pi, where we know the result (sine o should also be close to 0. Oops! That didn t work. Nor does the code work for x equal to pi half. Both of these latter cases sine3.1415927 give results that are much too large Vaue:22.140666527138016 Vaue:3,8104481565660486 8n003 60015e Slide 7.3.4 Chasing down the error Okay, we need to figure out where our conceptual error lies define (sine x) ts try to isolate this by tracing through the computation. In (newline) particular, we will add some display expressions that will show (display "n is " us the state of the computation each time through the recursion (display n) dsp1ay" current is”) let ((next (/(expt x n)(fact n)))) iE《sma11-enuf?next) aux * (+n 1)(+ current next)))) (aux x 1 0))