《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