6.001 Notes: Section 5.1-5.2

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 abstractions: the idea of capturing a common pattern of computation within a procedure, and isolating the details of that computation from the use of the concept within some other 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 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 Let's review what we have been looking at so far in the course, in particular, the idea of procedural abstraction to capture 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, using our define expression, then treat the whole thing as a primitive by just referring to the name, and use it without worrying 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 box. Slide 5.1.4 We need to provide it with inputs of a specified type. Slide 5.1.5 We know by the contract associated with the procedure, that if we provide inputs of the appropriate type, the procedure will produce an output of a specified type... Slide 5.1.6 ... and by giving the whole procedure a name, we create this black box abstraction, in which we can use the procedure without knowing details. This means that the procedure will obey the contract that specifies the mapping from inputs to outputs, but the user is not aware of the details by which that contract is enforced. Slide 5.1.7 So let's use this idea to look at a more interesting algorithm than the earlier ones we've examined. Here, again, is Heron of Alexandria's algorithm for computing good approximations to the square root of a positive number. Read the steps carefully, as we are about to implement them. 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. Slide 5.1.11 And here is how to do this. Note that the definition of sqrt bind this name to a lambda. Within the bounds of that lambda we have moved the definitions for improve, good-enuf?, and sqrt­ iter (which is what we have renamed try). By moving these procedures inside the body of the lambda, they become 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 expressions that exist within the scope of this lambda. The rules of evaluation say that when we apply sqrt 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. Slide 5.1.12 In fact we can stress this by drawing a box around the boundary of the outermost lambda. Clearly that boundary exactly scopes the black box abstraction that I wanted. This is called block structure, which you can find, discussed in more detail in the textbook. Slide 5.1.13 Schematically, this means that sqrt contains within it only those internal procedures that belong to it, and behaves according to the contract expected by the user, without the user knowing how those procedures accomplish this contract. This provides another method for abstracting ideas and isolating them from other abstractions. 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 procedures associated with the manipulation of those data structures. We will see that data abstractions mirror many of the properties of procedural abstractions, and we will thus generalize the ideas of compound data into data abstractions, to complement our procedural abstractions. Slide 5.2.2 So far almost everything we've seen in Scheme has revolved around numbers and computations associated with numbers. This has been partly deliberate on our part, because we wanted to focus on the ideas of procedural abstraction, without getting bogged down in other details. There are, however, clearly problems in which it is easier to think in terms of other elements than just numbers, and in which those elements have pieces that need to be glued together and pulled apart, while preserving the concept of the larger unit. Slide 5.2.3 So our goal is to create a method for taking primitive data elements, gluing them together, and then treating the result as if it were itself a primitive element. Of course, we will need a way of "de-gluing" the units, to get back the constituent parts. What do we mean when we say we want to treat the result of gluing elements together as a primitive data element? Basically we want the same properties we had with numbers: we can apply procedures to them, we can use procedures to generate new versions of them, and we can create expressions that include them as simpler elements. Slide 5.2.4 The most important point when we "glue" things together is to have a contract associated with that process. This means that we don't really care that much about the details of how we glue things together, so long as we have a means of getting back out the pieces when needed. This means that the "glue" and the "unglue" work hand in hand, guaranteeing that however, the compound unit is created, we can always get back the parts we started with. Slide 5.2.5 And ideally we would like the process of gluing things together to have the property of closure, that is, that whatever we get by gluing things into a compound structure can be treated as a primitive so that it can be the input to another gluing operation. Not all ways of creating compound data have this property, but the best of them do, and we say they are closed under the operation of creating a compound object if the result can itself be a primitive for the same compound data construction process. Slide 5.2.6 Scheme's basic means for gluing things together is called cons, short for constructor, and virtually all other methods for creating compound data objects are based on cons. Cons is a procedure that takes two expressions as input. It evaluates each in turn, and then glues these values together into something called a pair. Note that the actual pair object is the value returned by evaluating the cons. The two parts of a cons pair are called the car and the cdr, and if we apply the procedures of those names to a pair, we get back the value of the argument that was evaluated when the pair was created. Note that there is a contract here between cons, car and cdr, in which cons glues things together in some arbitrary manner, and all that matters is that when car, for example, is applied to that object, it gets back out what we started with. Slide 5.2.7 Note that we can treat a pair as a unit, that is, having built a pair, we can treat it as a primitive and use it anywhere we might use any other primitive. So we can pass a pair in as input to some other data abstraction, such as another pair. Slide 5.2.8 In this way, we can create elements that are naturally thought of as simple units that happen to themselves be created out of elements that are also thought of as simple units. This allows us to build up levels of hierarchy of data abstractions. For example, suppose we want to build a system to reason about figures drawn in the plane. Those figures might be built out of line segments that have start and end points, and those points are built out of x and y coordinates. Notice how there is a contract between make-point and point-x or point-y, in which the selectors get out the pieces that are glued together by the constructor. Because they are built on top of cons, car and cdr, they inherit the same contract that holds there. And in the case of segments, these pieces are glued together as if they are primitives, so that we have cons pairs whose elements are also cons pairs. Thus we see how cons pairs have the property of closure, in which the result of consing can be treated as primitive input to another level of abstraction. Slide 5.2.9 We can formalize what we have just seen, in terms of the abstraction of a pair. This abstraction has several standard parts. First, it has a constructor, for making instances of this abstraction. The constructor has a kind of contract, in which objects A and B are glued together to construct a new object, called a Pair, with two pieces inside. Second, it has some selectors or accessors to get the pieces back out. Notice how the contract specifies the interaction between the constructor and the selectors, whatever is put together can be pulled back apart using the appropriate selector. Typically, a data abstraction will also have a predicate, here called pair?. Its role is to take in any object, and return true if the object is of type pair. This allows us to test objects for their type, so that we know whether to apply particular selectors to that object. The key issue here is the contract between the constructor and the selectors. The details of how a constructor puts things together are not at issue, so long as however the pieces are glued together, they can be separated back out into the original parts by the selectors. Slide 5.2.10 So here we just restate that idea, one more time, stressing the idea of the contract that defines the interaction between constructor and selectors. And, we stress one more time the idea that pairs are closed, that is, they can be input to the operation of making other pairs.