6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 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 Com pound data 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 gettin 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 Slide 5.2.3 Com pound data So our goal is to create a method for taking primitive data elements, gluing them together, and then treating the result as if that can be treated as a simple data element into a unit it were itself a primitive element. Of course, we will need a way Need ways of getting the pieces back out 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 6001 SICP Com pound data Slide 5.2. 4 into a unit 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 .Need a contract between the "glue" and the " unglue 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
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 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
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology And ideally we would like the process of gluing things together Compound data to have the property of closure, that is, that whatever we get by Need a way of gluing data ele together into a unit gluing things into a compound structure can be treated as a that can be treated as a simple Need ways of getting the piece primitive so that it can be the input to another gluing operation Not all ways of creating compound data have this property, but Need a contract between the "glue"and the "unglue the best of them do, and we say they are closed under the operation of creating a compound object if the result can itself of clos ined by creating a compound data be a primitive for the same compound data construction process he e treat f othem itive object and Slide 5.2.6 (cons <x-exp> <y-exp>) Scheme's basic means for gluing things together is called cons, short for constructor, and virtually all other methods andrv -exp evaluates te a valve uv> for creating compound data objects are based on cons Returns a pair <p>whose Cons is a procedure that takes two expressions as input. It (eax<P>)=><x-a1> evaluates each in turn, and then glues these values together into eturns the car-part of the pair <P> something called a pair. Note that the actual pair object is the value returned by evaluating the cons. The two parts of a cons (cdr<>)·><-va Returns the cdr-part af the pair <P pair are called the car and the edr, and if we apply the DOI SICP argument that was evaluated when the pair was cia e ocedures of those names to a pair, we get back the value of the 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 Com pound Data Note that we can treat a pair as a unit, that is, having built a pair, .T ye 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 6001 SICP
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 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
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.2.8 Com pound Data In this way, we can create elements that are naturally thought of Treat a PAIR as a single unit as simple units that happen to themselves be created out of Can return as a value elements that are also thought of as simple units. This allows us (det ine (make-point x y 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 0O1 sIcP I 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 Pair Abstraction We can formalize what we have just seen, in terms of the abstraction of a pair. This abstraction has several standard parts A xB 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 c出:n王,B→B Second, it has some selectors or accessors to get the pieces back (cd》=>y> out. Notice how the contract specifies the interaction between Predicate the constructor and the selectors, whatever is put together can be 1xx2)0b02 -->#t if <z> evaluates to a pair, else #f 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 Note how there exists a contract between the constructor So here we just restate that idea, one more time, stressing the idea of the contract that defines the interaction between car(cons<a><b>)→<> constructor and selectors. And we stress one more time the idea car(cons<a><b>)→<b> Note how pairs have the property of closure -we can us that pairs are closed, that is, they can be input to the operation of the result of a pair as an element of a new pair. making other pairs (cons(cons 1 2)3)
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 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