6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.3.23 So to summarize: we have seen that languages often provide conventional ways of grouping data elements into structures routing elements together here either in pairs or as arbitrarily long collections. Associated into compound data str these data structures tend with these conventional structures are methods for operating on to have a form that mimics the actual data structure them, and these procedures often have a form that mimics the ompound data structures rely on an inductive format in structure. For example, in procedures that convert lists into lists, we see that the recursive step usually involves using the analogy to our analysis of recursive procedures by using electors 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 6001 SCP 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 Pairs, Lists, Other Beasts 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 roups user knows groups are also lists constructed out of simpler ones. At the bottom are pairs where user knows lists are also pairs we have a basic contract from Scheme, about how cons, car and cdr interact as a data abstraction On top of that, we contract for cons, car, cdr 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 4 6001 SCP the knowledge that groups are constructed as lists of lists, but where she is shielded from the fact that lists are implemented as Pairs, Lists, Trees Slide 5.4.2 In e. we have built a set of abstraction barriers in which Groups user knows groups are also lists the implementation details of a data structure are only weakly Lists user knows lists are also pair separated from the use of that structure. This means that we rely on the user showing discipline when applying procedures to data contract for cons, car, cdr structures, expecting them not to use procedures that directly take advantage of the implementation of the structure Conventions that enable us to think about lists and groups much better off imposing strong abstraction Specified the implementations for lists and groups barriers between structures, thereby not allowing a user to take weak data abstraction How build stronger abstractions? Said another way, we have tried to separate out data structures NI sCP that have different conventions for usage enabling us to think about the structures as ways of organizing data, but we've6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 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