6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 10.2.13 And why does that matter here? Because a-lists have poor Why do we care that Alists are not an ADT? modularity. Since we have exposed the"guts"of the Modularity is essential for software engineering implementation of tables to the outside, this means that other users Build a program by sticking modules together can write operations using filter and map directly on the a-lists Can change one module without affecting the rest There is no way of separating the use of the table from the . Alists have poor modularity implementation of the table. If we later decide to change the Programs may use list ops like filter and map on alists These ops will fail if the implementation of alists change implementation of the table, we will be in trouble because these . Must change whole program if you want a different table operations are defined based on an assumption about how things are implemented, and changing the representation will require that we find and change all the operations that manipulate tables Ide Why do we care that Alists are not an ADT? To achieve modularity, we need to hide information. In particular Modularity is essential for software engine we want to hide the fact that the table is implemented as an a-list from the use of the table itself. Can change one module without affecting the rest This has two parts. The first part is that we will create abstraction Alists have poor modularity and maponaists for getting at the parts of the data structure (ie. constructors and These ops wil alif the implementation of alists change selectors)and we will insist that anything outside of the abstraction Must change whole program if you want a different table cannot use list operations but must go through the abstract .To achieve modularity, hide information selectors and constructors .Hide the fact that the table is implemented as a list ADT techniques exist in order to do this 6.001 Notes: Section 10.3 Slide 10.3.1 Table1: Table ADT implemented as an Alist So lets build on this idea we know that we should be able to use a-lists to represent the internal structure of the table but we need to accomplish this hiding of information, that is, the (define (make-tablel)(cons tablel-tag nil)) separation of the internal aspects of the table from the outside ind-assoe key (cdr tbl))) Here is how we will do that first we will need a constructor (define (tablel-put! tbl key val) make-tablel(we give it this name in order to distinguish (set-cdr! tbl (add-assoc key val (cdr tbl)))) different versions of our table abstraction). This simply puts a tag at the front of a table structure. notice how we have separately given a name to that tag, a point we will come back to 4 Now we can create a get operation on this table by: given a table remove the tag to get the actual table implementation, and then use the procedure designed for a-lists to extract that actual entry in the table. This builds on the choice of an a-list as the actual internal representation of the table To put something new into the table, we can again extract the internal representation minus the tag, use the a-list operations to add a new value to this internal representation. This returns a new a-list as a value, so we can then glue the tag back onto the front of the table. We do this using an unusual operation, set-cdr! which we will discuss in detail in a few lectures. Think of this operation as taking the box-and-pointer structure pointed to by the value of the first argument, finding the cdr of that structure, and changing it to point to the value of the second argument. Dont worry about the details of this new operation. We simply will use it create a new version of a tagged table, while6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 10.2.13 And why does that matter here? Because a-lists have poor modularity. Since we have exposed the "guts" of the implementation of tables to the outside, this means that other users can write operations using filter and map directly on the a-lists. There is no way of separating the use of the table from the implementation of the table. If we later decide to change the implementation of the table, we will be in trouble because these operations are defined based on an assumption about how things are implemented, and changing the representation will require that we find and change all the operations that manipulate tables. Slide 10.2.14 To achieve modularity, we need to hide information. In particular, we want to hide the fact that the table is implemented as an a-list from the use of the table itself. This has two parts. The first part is that we will create abstractions for getting at the parts of the data structure (i.e. constructors and selectors) and we will insist that anything outside of the abstraction cannot use list operations but must go through the abstract selectors and constructors. 6.001 Notes: Section 10.3 Slide 10.3.1 So let's build on this idea. We know that we should be able to use a-lists to represent the internal structure of the table, but we need to accomplish this hiding of information, that is, the separation of the internal aspects of the table from the outside world. Here is how we will do that. First, we will need a constructor, make-table1 (we give it this name in order to distinguish different versions of our table abstraction). This simply puts a tag at the front of a table structure. Notice how we have separately given a name to that tag, a point we will come back to shortly. Now we can create a get operation on this table by: given a table, remove the tag to get the actual table implementation, and then use the procedure designed for a-lists to extract that actual entry in the table. This builds on the choice of an a-list as the actual internal representation of the table. To put something new into the table, we can again extract the internal representation minus the tag, use the a-list operations to add a new value to this internal representation. This returns a new a-list as a value, so we can then glue the tag back onto the front of the table. We do this using an unusual operation, set-cdr! which we will discuss in detail in a few lectures. Think of this operation as taking the box-and-pointer structure pointed to by the value of the first argument, finding the cdr of that structure, and changing it to point to the value of the second argument. Don't worry about the details of this new operation. We simply will use it create a new version of a tagged table, while