6.001 Notes: Section 5.3-5.4

6.001 Notes: Section 5.3 Slide 5.3.1 So how do we use the idea of pairs to help us in creating computational entities? To illustrate this, let’s stick with our example of points and segments. Suppose we construct a couple of points, using the appropriate constructor, and we then glue these points together into a segment. Slide 5.3.2 Now suppose we want to think about the operation of stretching a point, that is, pulling (or pushing) it along a line from the origin through the point. Ideally, we would just think about this in terms of operations on elements of a point, without worrying about how the point is actually implemented. We do this with the code shown. Note how this code creates a new data object. If we stretch point P1, we get a new point. Also note, as an aside, how a cons pair prints out, with open and close parentheses, and with the values of the two parts within those parentheses, separated by a dot. Thus, the point created by applying our stretch procedure has a different value for the x and y parts than the original point, which is still hanging around. Thus, as we might expect from the actual code, we get out the values of the parts of P1, but then make a new data object with scaled versions of those values as the parts. Slide 5.3.3 And we can generalize this idea to handle operations on segments, as well as points. Note how each of these procedures builds on constructors and selectors for the appropriate data structure, so that in examining the code, we have no sense of the underlying implementation. These structures happen to be built out of cons pairs, but from the perspective of the code designer, we rely only on the contract for constructors and selectors for points and segments. Slide 5.3.4 Now, suppose we decide that we want to take a group of points (which might have segments defined between adjacent points) and manipulate these groups of points. For example, a figure might be defined as a group of ordered points, with segments between each consecutive pair of points. And we might want to stretch that whole group, or rotate it, or do something else to it. How do we group these things together? Well, one possibility is just to use a bunch of cons pairs, such as shown here. But while this is a perfectly reasonable way to glue things together, it is going to be a bear to manipulate. Suppose we want to stretch all these points? We would have to write code that would put together the right collections of car’s and cdr’s to get out the pieces, perform a computation on them, and then glue them back together again. This will be a royal pain! It would be better if we had a more convenient and conventional way of gluing together groups of things, and fortunately we do. Slide 5.3.5 Pairs are a nice way of gluing two things together. However, sometimes I may want the ability to glue together arbitrary numbers of things, and here pairs are less helpful. Fortunately, Scheme also has a primitive way of gluing together arbitrary sets of objects, called a list, which is a data object with an arbitrary number of ordered elements within it. Slide 5.3.6 Of course, we could make a list by just consing together a set of things, using however many pairs we need. But it is much more convenient to think of a list as a basic structure, and here is more formally how we define such a structure. A list is a sequence of pairs, with the following properties. The car part of a pair in the list holds the next element of the list. The cdr part of a pair in the list holds a pointer to the rest of the list. We will also need to tell when we are at the end of the list, and we have a special symbol, nil, that signals the fact that there are no more pairs in the list. Slide 5.3.7 Another way of saying this is that lists are sequences of pairs ending in the empty list. Under that view, we see that lists are closed under the operations of cons and cdr. To see this, note that if we are given a sequence of pairs ending in the empty list, and we cons anything onto that sequence, we get another sequence of pairs ending in the empty list, hence a list. Similarly, if we take the cdr of a sequence of pairs ending in the empty list, we get a smaller sequence of pairs ending in the empty list, hence a list. This property of closure says we can use lists as primitives within other lists. The only trick is what happens when I try to take the cdr of an empty list. The result depends on the Scheme implementation, as in some cases it is an error, while for other Schemes it is the empty list. The latter view is nice when considering the closure property as it preserves the notion that the cdr of a list is a list. Slide 5.3.8 To visualize this new conventional way of collecting elements, called a list, we use box-and-pointer notation. First, a cons pair is represented by a pair of boxes. The first box contains a pointer to the value of the first argument to cons and the second box contains a pointer to the value of the second argument to cons. The pair also has a pointer into it, and that pointer is the value returned by evaluating the cons expression, and represents the actual pair. Slide 5.3.9 A list then simply consists of a sequence of pairs, or boxes, which we conventionally draw in a horizontal line. The car element of each box points to an element of the sequence, and the cdr element of each box points to the rest of the list. The empty list is indicated by a diagonal line in the last cdr box. One can see that the list is much like a skeleton. The cdrs define the spine of the skeleton, and hanging off the cars are the ribs, which contain the elements. Also notice how this visualization clearly defines the closure property of lists, since taking the cdr of a list gives us a new sequence of boxes ending the empty list. Slide 5.3.10 To check if something is a list, we need two things. First, we have a predicate, null? that checks to see if an object is the empty list. Then, to check if a structure is a list, we can just use pair? to see if the structure is a sequence of pairs. Actually, we really should check to see that the sequence ends in the empty list, but conventionally we just check to see that the first element is a pair, that is, something made by cons. Slide 5.3.11 Since we have built lists out of cons pairs, we can use car and cdr to get out the pieces. But just for today, we are going to separate the operations on lists from operations on pairs, by defining special selectors and constructor for lists, as shown. Thus we have a way of getting the first and rest of the elements of a list, and for putting a new element onto the front of a list. Notice how these operations inherit the necessary closure properties from their implementation in terms of cons, car and cdr. Slide 5.3.12 A key point behind defining a new data abstraction is that it should make certain kinds of operations easy to perform. We expect to see that with lists, and in what follows we are going to explore that idea, looking for standard kinds of operations associated with lists. One common operation is the creation of lists. Here is a simple example of this, which generates a sequence (or list) of numbers between two points. Notice the nice recursive call within this procedure. It says, to generate such a list, cons or glue the value of from onto whatever I get by creating the interval from from + 1 to to. This is reducing things to a simpler version of the same problem, terminating when I just have an empty list. Notice how the constructor relies on the data abstraction contract. If this procedure works correctly on smaller problems, then the adjoin operation is guaranteed to return a new list, since it is gluing an element onto a list, and by closure this is also a list. This kind of inductive reasoning allows us to deduce that the procedure correctly creates the right kind of data structure. Slide 5.3.13 Here is a trace of the substitution model running on an example of this. Notice how the if clause unwinds this into an adjoining of an element onto a recursive call to the same procedure with different arguments. Since we must get the values of the subexpressions before we can apply the adjoin operation, we expand the recursive call out again, creating another deferred adjoin operation. And we keep doing this until we get down to the base case, returning the value of the empty list. Notice that this now leaves us with an expression that will create a list, a sequence terminating in the special symbol for an empty list. Slide 5.3.14 Now we are ready to evaluate the innermost expression, which actually creates a cons pair. To demonstrate this, we have drawn in the pair to show that this is the value returned by adjoin. Notice how it has the correct form for a list. Slide 5.3.15 The next evaluation adjoins another element onto this list, with the cdr pointer of the newly created cons pair pointing to the value of second argument, namely the previously created list. Slide 5.3.16 And this of course then leads to this structure. This prints out as shown, which is the printed form for a list. Notice the order in which the pairs are created, and notice the set of deferred operations associated with the creation of this list. Slide 5.3.17 In addition to procedures that can "cons up" a list, we have procedures that can walk down a list, also known as "cdring down" a list. Here is a simple example, which finds the nth element of a list, where by convention a list starts at 0. Notice how we use the recursive property of a list to do this. If our index is 0, then we want the first element. Otherwise, we know that the nth element of a list will be the n-1st element of the rest of the list, by the closure property of lists. So we can recursively reduce this to a simpler version of the same problem. For the example shown, we will first check to see if n=0. Since it does not, we take the list pointed to by joe, extract the rest of that list by literally taking the pointer out of the cdr part of the first box, and call list-ref on that structure, with a decrement of n. This recursive call will now have n=0, so we return the first element of the new list, namely the element 3. Slide 5.3.18 A related procedure is to count up the number of elements in a list, using the same sort of recursive reasoning. Length of a list is defined as 1 more than the length of the rest of a list, which by the closure property is also a list. The base case is the empty list, which has zero length. Slide 5.3.19 Now we can put the two ideas together, cdring down one list while consing up a new one as the return value. Here is an example, which creates a copy of a list. Notice the form. If we are given an empty list, we just return an empty list and are done. If not, then we use the recursive property of lists. We adjoin the first element of the input list onto whatever we get by copying the rest of the list. But by closure, the rest of the input list is a list, so copy is guaranteed by induction to give us back a list. And by what we just saw, we see that copy will create a copy of the list in exactly the same order. Slide 5.3.20 Well copying is boring, but here is how we can use this idea. Suppose we want to glue two lists together into one long list, as shown in the example. Let's just use the same strategy, implemented in a handy procedure called append. For the base case, notice that if we do not have anything in the first list, we just want the second list. Otherwise, we use the same idea as before. We adjoin the first element of the first list onto whatever we get by appending the rest of the first list onto the second list. Using the same closure properties, we see that this will create a list, and adjoin will then put the first element on the front of this new list. Notice how we are using the recursive properties of lists to build this procedure, and in particular notice how the recursive structure of the procedure nicely mimics the recursive structure of the data object. Slide 5.3.21 So now we can put these ideas to work in handling more complex structures. Let’s group together a set of points using a list. Then we can easily write a procedure to stretch the entire group, by building on the wonderfully recursive nature of the list. Here it is. Note how we subdivide the problem of stretching a group into the operation of stretching a point (using the procedure appropriate for points), and then adding that to the result we would get by stretching the rest of the group. Because of the recursive nature of a list, we know that the rest of a list is a list, so we can use induction to conclude that stretch-group applied to the smaller collection will return a new group, and thus adjoining the new element to the front of this will clearly give us back a group. Slide 5.3.22 And if we want to find the midpoint (or centroid) of the group, we can put together the pieces we built earlier, as shown here. Add-x and add-y have a structure very similar to our earlier examples: they simply cdr down the list, gathering up information as they go in a set of deferred additions. Each of these will get the sum of the x and y values of all the points in a group. To find the midpoint we need to get the average x and y value, so we need to know how many elements are in the group, which we get using length. We can combine this information to create a new point at the middle of the group. Note the new form let. You can find the details in the textbook, but it suffices to think of this as an expression in which each of the names in the first set of expressions (x-sum, y-sum and how-many) are bound to the values of the expressions following those names. Then within the confines of the let expression, those names are simply local names for those values, and are substituted for just as we would in the standard substitution model. Slide 5.3.23 So to summarize: we have seen that languages often provide conventional ways of grouping data elements into structures, here either in pairs or as arbitrarily long collections. Associated with these conventional structures are methods for operating on them, and these procedures often have a form that mimics the structure. For example, in procedures that convert lists into lists, we see that the recursive step usually involves using the selectors to get out the parts of the list, operating on each, and then using the constructor to reassemble the parts into a list. This form means that the same inductive proofs we used to reason about our recursive procedures will also apply here. We can often deduce properties of our procedures and their associated data structures by relying on the fact that inductively the procedure operates correctly on smaller sized data structures. 6.001 Notes: Section 5.4 Slide 5.4.1 So let's step back and examine what we have built so far. We've basically built a hierarchy of data abstractions, each of which is constructed out of simpler ones. At the bottom are pairs where we have a basic contract from Scheme, about how cons, car and cdr interact as a data abstraction. On top of that, we have built lists, but where the user can take advantage of the fact that lists are also pairs. In fact, we do this directly by using car and cdr as our selectors for lists. On top of that, we have just built groups, but again the user can take advantage of the knowledge that groups are constructed as lists of lists, but where she is shielded from the fact that lists are implemented as pairs. Slide 5.4.2 In essence, we have built a set of abstraction barriers in which the implementation details of a data structure are only weakly separated from the use of that structure. This means that we rely on the user showing discipline when applying procedures to data structures, expecting them not to use procedures that directly take advantage of the implementation of the structure. Sometimes we are much better off imposing strong abstraction barriers between structures, thereby not allowing a user to take advantage of the underlying representation. Said another way, we have tried to separate out data structures that have different conventions for usage, enabling us to think about the structures as ways of organizing data, but we've allowed the user to cross over the barrier between those structures to get at the underlying implementation. What happens if we decide to make those barriers much stronger, thereby shielding the people who use the abstractions from the underlying representation? Slide 5.4.3 This then leads us to the notion of a rigorous data abstraction. For example, for pairs here is what we expect in such an abstraction. We'll have a constructor for gluing pieces together, and it will have a contract between the types of the inputs and the type of the data structure constructed. We'll have selectors or accessors for getting back out the pieces that are glued together. And most importantly, we will have a contract between the constructor and the selectors, so that whatever we glue together with the constructor we can get back out using the appropriate selector. Notice that this contract says nothing about how the abstraction is implemented, only that its behavior is as documented. We will have some standard operations on the abstraction, typically predicates for identifying an instance of the data abstraction. All of this is separated from the actual implementation by what we call an abstraction barrier. Think of this as a wall that separates the use of an abstraction from the implementation of an abstraction. This means that a user of the abstraction can freely write procedures to manipulate the structures, just relying on the constructor and selectors, without any knowledge of how the structure is actually made. Slide 5.4.4 Now, let's drive this point home with a more extended example, and remember that the point we are trying to drive home is the separation of the details of implementation of an abstraction from the use of that abstraction. We are going to place this solid barrier between the implementation and use of an abstraction, and we are going to see why having that barrier makes it much easier for us to create useful systems. The example we are going to consider is that of rational numbers and simple arithmetic operations on rationals. I'll remind you that a rational number is just a ratio of two integers, a numerator over a denominator. Associated with rationals are certain operations, for example we can add two rationals together, or multiply two rationals together, using the rules shown in the slide. Notice that we are really cheating here, and in fact I have put the operation on the rationals in red to distinguish that these are operations on rationals, as opposed to operations on integers. In fact, the rules for operations on rationals really decompose into simpler operations on integers. The operations on the right hand side are just operations on normal integers, followed by the creation of a rational (which is what the division sign denotes here). Now, let's see how we can use the ideas of data abstractions to build a system for manipulating rational numbers. Slide 5.4.5 First, here's our data abstraction for rational numbers, which has the form we expect. It has a constructor, make-rat which takes two integers as input, and produces a rational, with some kind of internal representation that we haven't specified. We'll need selectors for getting back out the pieces of a rational. Notice the type associated with numer and denom. Most important is the contract between these parts. We can apply either of the selectors to the object created by the constructor, and be guaranteed to get back the appropriate piece, independent of how the object is actually represented. We will also have some operations that apply to rationals, such as rational addition or rational multiplication, and notice the types of these operations. They take two rationals as input, and produce a rational as output. Of course, we are going to separate all of this from the actual implementation of rationals. We should ideally be able to take any implementation of rationals that satisfies these contracts and build our own procedures to use those objects, just by relying on the constructor and selectors, and the contract between them. Slide 5.4.6 Now let's think about actually building an implementation for rationals. How do we go about building an implementation that satisfies the contract defined in the previous slide, while providing all the pieces we laid out? Slide 5.4.7 Well here is a simple implementation for rationals. We could use pairs as our underlying representation for rationals. Using this, we can easily construct the constructor and selectors for rationals, using cons, car and cdr. While this seems like an obvious way to build rationals, there is an important point here. In particular, we can enforce the contract that we require between make-rat, numer and denom by inheriting the contract between cons, car and cdr. At the same time, by relying on separate constructors and selectors for rationals, we shield the user from the implementation details, and we will see shortly why that is important. Slide 5.4.8 In fact, here is one reason why this is important. Here is an alternative implementation of rationals, using list as the constructor, and car and cadr (which gets the second element of a list or the car or the cdr of the list) as the selectors. Does this satisfy our contract? Sure! Can a user tell which implementation we are using, the list or the pair version? No. The whole point of shielding the user from the implementation is to separate out those issues from the use of the abstraction. Why would we want alternative representations? We'll see some advantages shortly, but the key point here is that from the user's perspective each implementation is equally valid, as each satisfies the contract. Slide 5.4.9 For example, here is a useful procedure for rationals, which will print out the value of a rational by separating the numerator and denominator by a "slash". The key question is can this procedure tell which implementation of rationals we are using? The answer, of course, is no. The procedure uses the selectors to get out the pieces, and cannot tell which implementation is being used so long as the right selector for that implementation is employed. Slide 5.4.10 My operations for arithmetically manipulating rationals have a common form that we are going to see many times. Look at the first one carefully. The type contract says that given two rationals as input, we return a rational as output. The body of the procedure uses the selectors to extract out simpler objects, (in this case integers) then applies more primitive procedures to those objects (for example, multiplying integers and adding integers) then uses the constructor to glue these more primitive elements together into the complex object that needs to be returned. This is an important and common process. When manipulating data abstractions, we tend to use the selectors to get out simpler pieces, execute more primitive operations on those pieces, then use the constructor to glue the new pieces together into a new complex object. Slide 5.4.11 Also, notice how types can help us reason through these procedures. Remember my contract for the selectors numer and denom, which said that given rationals as input, they would return integers. Thus in the body of these procedures I can see that I am safe in using integer arithmetic operations on the values returned by these selectors. And the contract for make-rat says that given two integers (as specified by the bodies of these procedures), we will return a rational number; hence my contract for these procedures is met, given that the contracts for the constructors and selectors are met. Slide 5.4.12 Okay, let's use this little system. We can create a couple of simple rationals as shown, making one-half and three- fourths to be the expected rationals. Let's define new to be the rational obtained by adding these two together, and we know by our previous work, that this should pull apart these two rationals, manipulate the underlying integer pieces, then reassemble a new rational that is the sum of these two. Slide 5.4.13 This sounds pretty straightforward. What happens if we look at the pieces of new? The numerator is 10, and the denominator is 8, so this rational is 10/8. But wait a minute! Shouldn't this be 5/4? We would expect to get 5/4 here, but we got an equivalent, but not identical answer. If we look at the details of how we implemented rational addition, we see that in fact this is the answer we should get, since we simply take the cross products of the numerators and denominators and form their ratio. So in this case we get the "right" answer but not the "correct" answer (or the answer we were expecting). Slide 5.4.14 And in fact that is exactly the point of this whole exercise! Given that we can shield the user from the implementation of an abstraction, we should be able to fix this problem without affecting procedures created by the user. So what is the "problem" here? We are not "rationalizing" the rationals, that is, we are not reducing our constructed rationals to simplest terms. Suppose we were to compute the greatest common divisor between the numerator and the denominator, and reduce both by this term. This would give us a simpler rational. The point, however, is to do this in a way that is invisible to the user. Slide 5.4.15 To do that, we will just use an implementation of gcd, which computes the greatest common divisor of two integers, as shown here. Let's use this to make "better" rationals. Slide 5.4.16 ... and here we have a choice. The first strategy is to use gcd when we access the parts of a rational. Thus, we will construct rationals the normal way, just gluing together the parts. But when we ask for the parts of the rational, we will first compute the gcd of the numerator and denominator, then reduce the selector part by that amount. This will fix the problem we saw in the previous slide, always reducing a rational to its lowest possible form. But notice that since we built all of our operations just using the constructor and selectors, they will all continue to work, even with this change underneath them. That was exactly the point of separating the implementation of the abstraction from its use. So long as our constructors and selectors satisfy the contract, and so long as we always use them constructor and selectors in creating procedures to manipulate the abstractions (i.e. the only procedures that cross that abstraction barrier), we are free to create new implementations of the abstraction without having to recode any of those procedures. Slide 5.4.17 And to drive that point home, here is an alternative way to create "rational" rationals. In this case, we will reduce rationals to lowest possible terms when we construct them, that is, when we apply make-rat. Here, the selectors can just be the straightforward implementation, since the constructor now takes care of the reduction. As before, the contract is still satisfied, and thus any procedure that uses these abstraction interfaces will still work without any change. Why have these alternatives? Well, if we expect to have a system that creates relatively few rationals but accesses them a lot, then for efficiency we should do the reduction at construction time. But if we expect the opposite load, we can use the other implementation. Slide 5.4.18 To finish making this point, think about what would happen if we didn't use the data abstractions. For example, here is our version of +rat built on top of the abstraction. Suppose instead we had directly implemented this procedure by relying on knowledge that rationals were constructed as pairs, thus directly using cons, car and cdr. Slide 5.4.19 ...then here is that implementation. It looks exactly like the original ; we have simply stripped off the abstraction barrier. Slide 5.4.20 But now, suppose we decide to implement the idea of incorporating the reduction by the gcd into the creation of rationals. In this case, we have to somehow figure out which parts of this code correspond to the numerator and denominator and replacing them with this grungy looking code. And it is not just the amount of work that is a problem here, it is that we have to do this with every procedure that manipulates rationals, and we have to do it in a way that guarantees we correctly identify the pieces to change. In the previous case, we just had to change the interface to the abstraction, not all the procedures that used them. Slide 5.4.21 Thus the key point is the following: By isolating the details of an abstraction from the use of that abstraction, and by maintaining a discipline in which we never violate that abstraction barrier, we can cleanly separate changes to the implementation from use of the implementation. Thus, instead of having to change every procedure that uses rationals, we can obtain different systems just by changing the underlying representation and ensuring that the constructor and selectors (the only procedures that cross the abstraction barrier) satisfy the abstraction's contract.