《Structure and Interpretation of Computer Programs》lecture 5 webhand.pdf

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 5.1 Slide 5.1.1 In this lecture we are going to continue with the theme of building abstractions. Thus far, we have focused entirely on Procedural procedural abstractions the idea of capturing a common pattern of computation within a procedure, and isolating the details of Relationship between data abstraction and procedures that that computation from the use of the concept within some other Isolating use of data abstraction from details of computation. Today we are going to turn to a complementary issue, namely how to group together pieces of information,or data, into abstract structures. We will see that the same general theme holds: we can isolate the details of how the data are glued together from the use of the aggregate data structure as a 6001 SICP primitive element in some computation. We will also see that the procedures we use to manipulate the elements of a data structure often have an inherent structure that mimics the data structure, and we will use this idea to help us design our data abstractions and their associated procedures Slide 5.1.2 Define fomal praers, caue rces in body o procedure in particular, the idea of procedural abstraction to capture ss Let's review what we have been looking at so far in the col Process of procedural abstract Hde implementation detal fom user, who us invokes name to computations. Our idea is to take a common pattern of computation, then capture that pattern by formalizing it with a set of parameters that specify the parts of the pattern that change, while preserving the pattern inside the body of a procedure. This encapsulates the computation associated with the pattern inside a lambda object. Once we have abstracted that computation inside the lambda, we can then give it a name DOI SICP using our define expression, then treat the whole thing as a primitive by just referring to the name, and use it without worry ing about the details within the lambda Slide 5.1.3 This means we can treat the procedure as it if is a kind of black Hide implementation de om user, who just invokes name to procedure OL SCP

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.1.8 Procedural abstraction example: sqrt Now, let's use the tools we seen so far to implement this method To find an approximation of square root ofx: Notice how the first procedure uses the ideas of wishful Improve the guess by averaging G and x/G thinking, and recursive procedures to capture the basic idea of ( define try (lambda (guess x) Herons method. Try is a procedure that takes a current guess quers s and the x, and captures the top-level idea of the method. It try improve gues (define improve (lambda (guoss checks to see if the guess is sufficient. If it is, it simply returns (define average (lambda (a b)(/(+a b)2))) the value of that guess. If it is not, then it tries again, with a new t ats (1 souare wues) m)o oo)) Note how we are using wishful thinking to reduce the problem (det ine sort (lambda (x) (try 1 x))) to another version of the same problem, and to abstract out the DOt sIcP m idea of both getting a new guess and checking for how good the guess is. These are procedures we can subsequently write, for example, as shown. Finally, notice how the recursive call to try will use a different argument for guess, since we will evaluate the expression before substituting into the body Also notice the recursive structure of try and the use of the special form if to control the evolution of this procedure The method for improve simply incorporates the ideas from the algorithm, again with a procedure abstraction to separate out idea of averaging from the procedure for improving the guess Finally, notice how we can build a square root procedure on top of the procedure for try Slide 5.1.9 The universe of procedures for sqrt If we think of each of these procedures as its own black box abstraction, then we can visualize the universe containing these orocedures as shown. Each procedure exists with its own contract, but each is accessible to the user, simply by referring to it by name improVe Good-enut? While this sounds fine in principle, there is a problem with this viewpoint. Some of these procedures are general methods, such as average and sart, and should be accessible to the user who might utilize them elsewhere Some of t however,such as try or good-enuf?, are really specific e to the computation for square roots. Ideally we would like to capture those procedures in a way that they can only be used by sgrt but not by other methods The universe of procedures for sqrt Slide 5.1.10 Abstractly, this is what we would like to do. We would like to move the abstractions for the special purpose procedures inside of the abstraction for sart so that only it can use them while generally useful procedures available to the Improve In this way, these internal procedures should become part of the implementation details for sgrt but be invisible to outside Good-enu? sers

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 5.1.8 Now, let's use the tools we seen so far to implement this method. Notice how the first procedure uses the ideas of wishful thinking, and recursive procedures to capture the basic idea of Heron's method. Try is a procedure that takes a current guess and the x, and captures the top-level idea of the method. It checks to see if the guess is sufficient. If it is, it simply returns the value of that guess. If it is not, then it tries again, with a new guess. Note how we are using wishful thinking to reduce the problem to another version of the same problem, and to abstract out the idea of both getting a new guess and checking for how good the guess is. These are procedures we can subsequently write, for example, as shown. Finally, notice how the recursive call to try will use a different argument for guess, since we will evaluate the expression before substituting into the body. Also notice the recursive structure of try and the use of the special form if to control the evolution of this procedure. The method for improve simply incorporates the ideas from the algorithm, again with a procedure abstraction to separate out idea of averaging from the procedure for improving the guess. Finally, notice how we can build a square root procedure on top of the procedure for try. Slide 5.1.9 If we think of each of these procedures as its own black box abstraction, then we can visualize the universe containing these procedures as shown. Each procedure exists with its own contract, but each is accessible to the user, simply by referring to it by name. While this sounds fine in principle, there is a problem with this viewpoint. Some of these procedures are general methods, such as average and sqrt, and should be accessible to the user, who might utilize them elsewhere. Some of them, however, such as try or good-enuf?, are really specific to the computation for square roots. Ideally we would like to capture those procedures in a way that they can only be used by sqrt but not by other methods. Slide 5.1.10 Abstractly, this is what we would like to do. We would like to move the abstractions for the special purpose procedures inside of the abstraction for sqrt so that only it can use them, while leaving more generally useful procedures available to the user. In this way, these internal procedures should become part of the implementation details for sqrt but be invisible to outside users

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.1.11 And here is how to do this sqrt-Block Structure Note that the definition of sart bind this name to a lambda Within the bounds of that lambda we have moved the (define good-enut? (lambda (guess) (square quess) x) definitions for improve, good-enuf?, and sart (det ine inprove (lambda (guess) iter(which is what we have renamed try). By moving (detine sqrt-iter (lambda (guess) (if (goodl-enur? guess) these procedures inside the body of the lambda, they become (sgrt-iter (inprove quess)))) sgrt-iter1.0〕) internal procedures, accessible only to other expressions within the body of that lambda. That is, if we try to refer to one of these names when interacting with the evaluator, we will get an unbound variable error. But these names can be referenced by 4 6001 SCP expressions that exist within the scope of this lambda The rules of evaluation say that when we apply sgrt to some argument, the body of this lambda will be evaluated. At that point, the internal definitions are evaluated The final expression of the lambda is the expression (sqrt-iter 1. 0)which means when sqrt is applied to some argument, by the substitution model it will reduce to evaluating this expression, meaning it will begin the recursive evaluation of guesses for the square root sqrt-Block Structure Slide 5.1.12 In fact we can stress this by drawing a box around the boundary ine good-enuf? (lambda (guess) of the outermost lambda. Clearly that boundary exactly scopes the black box abstraction that i wanted define inprove (lambda (guess) (average gsess ( x guess))) This is called block structure, which you can find, discussed in if《good-muf? quess more detail in the textbook sgrt-iter (improve guess))))) 1.0〕 600I SIcp Slide 5.1.13 qrt-Block Structure Schematically, this means that sqrt contains within it only those internal procedures that belong to it, and behaves t ine good-eauf?(⊥ anda《9uess square quess) x) according to the contract expected by the user, without the user det ine inprove lambda (guess knowing how those procedures accomplish this contract (det ine sqrt-iter (lambda (guess) his provides another method for abstracting ideas and isolating them from other abstractions (sgrt-iter (iprove guess))))) 6001 sCP

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.1. 14 Summary of part 1 So here is the summary of what we have seen in this section Isolate details of process from its use Designer has choice of which ideas to isolate, in order to support general patterns of computati 0O1 sIcP 6.001 Notes: Section 5.2 Slide 5.2.1 Language Elements So let's take that idea of abstraction and build on it to set the stage for what we are about to do, it is useful to think about how.mitives pnm. data: numbers, strings, booleans the language elements can be group together into a hierarchy rimitive procedures At the atomic level, we have a set of primitives. In Scheme these include primitive data objects: numbers, strings and compound data(today) Means of Abstraction Booleans. And these include built-in, or primitive, procedures for numbers, things like, +,=,>, for strings, things like block structure string=?, substring, for Booleans, things like and, or, not higher order procedures (next time To put these primitive elements together into more interesting conventional interfaces-lists(today data abstraction expressions, we have a means of combination, that is, a way of 6001 SICP combining simpler pieces into expressions that can themselves be treated as elements of other expressions. The most common one, and the one we have seen in the previous lectures, is procedure application. This is the idea of creating a combination of subexpressions, nested within a pair of parentheses the value of the first subexpression is a whic me, asas wepsesseen Chatwe s uhe ete healie f thep ts for e cer es ond ingerexpmesersni th body of the procedure, and proceed with the evaluation. We know that these combinations can themselves be included within other combinations, and the same rules of evaluation will recursively govern the computation Finally, our language has a means of abstraction: a way of capturing computational elements and treating them as if they were primitives; or said another way, a method of isolating the details of a computation from the use of a computation. Our first means of abstraction was define, the ability to give a name to an element, so that we could just use the name, thereby suppressing the details from the use of the object. This ability to give a name to something is most valuable when used with our second means of abstraction, capturing a computation within a procedure. This means of abstraction dealt with the idea that a common pattern of computation can be generalized into a single procedure, which covered every possible application of that idea to an appropriate value. When coupled with the ability to give a name to that procedure, we engendered the ability to create an important cycle in our language: we can now create procedures, name them, and thus treat them as if they were themselves primitive elements of the language. The whole goal of a high-level language is to allow us to suppress unnecessary detail in this manner, while focusing on the use of a procedural abstraction to support some more complex computational Today, we are going to generalize the idea of abstractions to include those that focus on data, rather than procedures. So we are going talk about how to create compound data objects, and we are going to examine standard

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 5.1.14 So here is the summary of what we have seen in this section. 6.001 Notes: Section 5.2 Slide 5.2.1 So let's take that idea of abstraction and build on it. To set the stage for what we are about to do, it is useful to think about how the language elements can be group together into a hierarchy. At the atomic level, we have a set of primitives. In Scheme, these include primitive data objects: numbers, strings and Booleans. And these include built-in, or primitive, procedures: for numbers, things like *, +, =, >; for strings, things like string=?, substring; for Booleans, things like and, or, not. To put these primitive elements together into more interesting expressions, we have a means of combination, that is, a way of combining simpler pieces into expressions that can themselves be treated as elements of other expressions. The most common one, and the one we have seen in the previous lectures, is procedure application. This is the idea of creating a combination of subexpressions, nested within a pair of parentheses: the value of the first subexpression is a procedure, and the expression captures the idea of applying that procedure to the values of the other expressions, which means as we have seen that we substitute the values of the arguments for the corresponding parameters in the body of the procedure, and proceed with the evaluation. We know that these combinations can themselves be included within other combinations, and the same rules of evaluation will recursively govern the computation. Finally, our language has a means of abstraction: a way of capturing computational elements and treating them as if they were primitives; or said another way, a method of isolating the details of a computation from the use of a computation. Our first means of abstraction was define, the ability to give a name to an element, so that we could just use the name, thereby suppressing the details from the use of the object. This ability to give a name to something is most valuable when used with our second means of abstraction, capturing a computation within a procedure. This means of abstraction dealt with the idea that a common pattern of computation can be generalized into a single procedure, which covered every possible application of that idea to an appropriate value. When coupled with the ability to give a name to that procedure, we engendered the ability to create an important cycle in our language: we can now create procedures, name them, and thus treat them as if they were themselves primitive elements of the language. The whole goal of a high-level language is to allow us to suppress unnecessary detail in this manner, while focusing on the use of a procedural abstraction to support some more complex computational design. Today, we are going to generalize the idea of abstractions to include those that focus on data, rather than procedures. So we are going talk about how to create compound data objects, and we are going to examine standard