6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 10.2.9 first,we have no constructor. We are just building a list using list Alists are not an abstract data type operations or quotes. This may seem like a neat efficient hack, but it has an important impact (define a1 '((x 15)(y 20))) Slide 10.2.10 Alists are not an abstract data type In particular, there is no abstraction barrier. That means there is no Missing a constructor. way of separating out the implementation and manipulating of a- Use quote or list to construct lists from the use of the a-list as a table. In fact a-lists are designed (define al '((x 15)(y 20))) that way and the definition from the scheme manual clearly states There is no abstraction barrier. this. A-lists are intended to just be exposed lists association. the car of an association is called the Slide 10.2.11 As a consequence, the implementation of the table is exposed, Alists are not an abstract data type meaning that the user can operate on the a-list just using list Missing a constructor. operations, rather than being required to use operations designed Use quote or list to construct for tables. The example shown seems very convenient, using filter directly on the list, but this is a dangerous thing to do There is no abstraction barrier. An alist is a list of pairs, each of which is called an ssociation. The car of an association is called the herefore, the implementation is exposed. User may operate (filter oda (a)(< (cadr a) 16))a1)) 【x15)) Slide 10.2.12 Why do we care that Alists are not an ADT? So why should we care that a-lists are not an abstract data type? Modularity is essential for software engineering The primary reason is the loss of modularity. Good software design Build a program by sticking modules together always involves programs that are created from units that are easily Can change one module without affecting the rest glued together, are easily replaced with other small sized units, and can be treated as black box abstractions If done right, we can easily change one module without having to change anything else
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 10.2.9 ...first, we have no constructor. We are just building a list using list operations or quotes. This may seem like a neat efficient hack, but it has an important impact. Slide 10.2.10 In particular, there is no abstraction barrier. That means there is no way of separating out the implementation and manipulating of alists from the use of the a-list as a table. In fact, a-lists are designed that way and the definition from the Scheme manual clearly states this. A-lists are intended to just be exposed lists. Slide 10.2.11 As a consequence, the implementation of the table is exposed, meaning that the user can operate on the a-list just using list operations, rather than being required to use operations designed for tables. The example shown seems very convenient, using filter directly on the list, but this is a dangerous thing to do. Slide 10.2.12 So why should we care that a-lists are not an abstract data type? The primary reason is the loss of modularity. Good software design always involves programs that are created from units that are easily glued together, are easily replaced with other small sized units, and can be treated as black box abstractions. If done right, we can easily change one module without having to change anything else in the system
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, while
6.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