《Structure and Interpretation of Computer Programs》lecture 11 webhan

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 10.1 Slide 1o.1.1 Table: a set of bindings Over the past few lectures, we have introduced the concepts of data abstractions, types and aggregate structures. In this lecture we want to explore the idea of pulling those pieces together to explore data abstractions in more depth. to do this we will examine a couple of particular examples, but we want you to step away from these details to see how in design data structure we have a tradeoff to consider That tradeoff is between onstructing concrete structures that are very efficient but open to misuse versus abstract structures that nicely separate the implementation from its use but which may suffer in efficiency This may sound a bit odd. The typical instinct for a less experienced programmer is to opt for efficiency. But in fact, if one is writing code for a large system that will be used over extended periods of time and will involve components from a large number of coders, then robustness modularity and ease of use and maintenance are typically much more important that speed In this lecture we are going to do an initial exploration of these ideas. We are going to examine three different kinds of data structures that move from concrete to abstract. culminating in the creation of a table data abstraction We will also see how design choices influence the implementation of an abstract data structure, with different kinds of performance. And we will see that the fundamental issue in designing abstract data types is using this methodology to hide information, both in the types and in the code Slide 10.1.2 Table: a set of bindings So here is where we are headed. We would like to build an abstract binding: a pairing of a key and a value data structure of a table. Conceptually a table is just a collection of bindings, and we are free to consider different ways of structuring that collection. What's a binding? It is just a pairing of a key and a value, or in other words, the key tells us the entry into the table, or how to find the binding in the table and the value is the thing actually associated with that key

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 10.1 Slide 10.1.1 Over the past few lectures, we have introduced the concepts of data abstractions, types and aggregate structures. In this lecture, we want to explore the idea of pulling those pieces together to explore data abstractions in more depth. To do this we will examine a couple of particular examples, but we want you to step away from these details to see how in designing any data structure we have a tradeoff to consider. That tradeoff is between constructing concrete structures that are very efficient but open to misuse versus abstract structures that nicely separate the implementation from its use but which may suffer in efficiency as a consequence. This may sound a bit odd. The typical instinct for a less experienced programmer is to opt for efficiency. But in fact, if one is writing code for a large system that will be used over extended periods of time and will involve components from a large number of coders, then robustness, modularity and ease of use and maintenance are typically much more important that speed. In this lecture we are going to do an initial exploration of these ideas. We are going to examine three different kinds of data structures that move from concrete to abstract, culminating in the creation of a table data abstraction. We will also see how design choices influence the implementation of an abstract data structure, with different kinds of performance. And we will see that the fundamental issue in designing abstract data types is using this methodology to hide information, both in the types and in the code. Slide 10.1.2 So here is where we are headed. We would like to build an abstract data structure of a table. Conceptually a table is just a collection of bindings, and we are free to consider different ways of structuring that collection. What's a binding? It is just a pairing of a key and a value, or in other words, the key tells us the entry into the table, or how to find the binding in the table, and the value is the thing actually associated with that key

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 10.1.3 We can define the behavior that we want a table to have without Table: a set of bindings having to consider the specifics of the implementation. In binding a pairing of a key and a value particular, we want the following abstract interface between the user of a table and the actual table itself. .Abstract interface to a table First, we need a constructor for building a table. We will just call that constructor, make. we ignore the details of how make works . put! key value insert a new binding We can just use make as a black box to construct a table for us replaces any previous binding of that key We need a way of inserting a binding into a table. We will assume look up the key, return the corresponding value that inserting a binding replaces any previous binding for that key in the table. Note that we don 't specify whether that old binding is actually removed from the table, or only if the old binding will longer be found by procedures that search the table old bindings around)versus efficiency in time(how quickly we can add new bindings and whether keeping old Why is this relevant? Well, notice that there is likely to be a tradeoff between efficiency in space(whether we ke bindings in the table will affect the speed of searching the table for bindings) Note that at this stage of our design, we have simply specified that put should take a key and a value, create a binding of those two pieces of information, and install that binding into the table in such a way that searching the table for that key will find this binding and not any previous ones We will also need a way of getting values out of the table. Thus, we will have another abstract interface, called get that takes as input a key, looks up the key in the table, and returns the corresponding value. Note again that we have said nothing about how to implement this operation, only what behave we expect as a user of tables Slide 10.1. 4 Table: a set of bindings This is a very important point. The definition we have just binding: a pairing of a key and a value data type of a table. From the user's perspective, using these cr provided of an interface to a table really does define the abstrac interface abstractions is sufficient to allow them to use the table eate a new table The details(the code we are about to show will be an .put! key valu implementation of this abstract data type, but there can be many alternatives that also satisfy the contract inherent in this description ok up the key return the corresponding value of the behavior of bindings in a table .This definition Is the table abstract data type .Code shown later is an implementation of the ADT Slide 10.1.5 Before we start exploring different kinds of data structures that willExamples of using tables lead to the implementation of a table, let's first think about why People tables might be of value to a user An obvious example is keeping track of personnel information. For example, suppose you have just started a new "dot com" company You will want to keep track of your employees, and a table is an obvious way to store data about them. You might start with information keyed by the names of the employees

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 10.1.3 We can define the behavior that we want a table to have, without having to consider the specifics of the implementation. In particular, we want the following abstract interface between the user of a table and the actual table itself. First, we need a constructor for building a table. We will just call that constructor, make. We ignore the details of how make works. We can just use make as a black box to construct a table for us. We need a way of inserting a binding into a table. We will assume that inserting a binding replaces any previous binding for that key in the table. Note that we don't specify whether that old binding is actually removed from the table, or only if the old binding will no longer be found by procedures that search the table. Why is this relevant? Well, notice that there is likely to be a tradeoff between efficiency in space (whether we keep old bindings around) versus efficiency in time (how quickly we can add new bindings and whether keeping old bindings in the table will affect the speed of searching the table for bindings). Note that at this stage of our design, we have simply specified that put! should take a key and a value, create a binding of those two pieces of information, and install that binding into the table in such a way that searching the table for that key will find this binding and not any previous ones. We will also need a way of getting values out of the table. Thus, we will have another abstract interface, called get, that takes as input a key, looks up the key in the table, and returns the corresponding value. Note again that we have said nothing about how to implement this operation, only what behave we expect as a user of tables. Slide 10.1.4 This is a very important point. The definition we have just provided of an interface to a table really does define the abstract data type of a table. From the user's perspective, using these interface abstractions is sufficient to allow them to use the table. The details (the code we are about to show) will be an implementation of this abstract data type, but there can be many alternatives that also satisfy the contract inherent in this description of the behavior of bindings in a table. Slide 10.1.5 Before we start exploring different kinds of data structures that will lead to the implementation of a table, let's first think about why tables might be of value to a user. An obvious example is keeping track of personnel information. For example, suppose you have just started a new "dot com" company. You will want to keep track of your employees, and a table is an obvious way to store data about them. You might start with information keyed by the names of the employees

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 10.1.6 Examples of using tables Associated with each name key, we might have another table that People lists information about that person: their age, their salary, and so on. And associated with each of those pieces of information might be other tables, for example, the salary information for previous Slide 10.1.7 Not only do our table data abstractions need to be flexible enoughExamples of using tables to allow for other tables to be entries in a table, we may have other ways of gathering information together in a table. For example, we might have another table that lists employees by age Slide 10.1.8 Examples of using tables Clearly we can build a table where the keys are the ages of the employees. Here, however, the value associated with a key should be a list whose elements point to the entries in other tables that capture all the data about each employee So our tables need to be very flexible in terms of what information 6.001 Notes: Section 10.2

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 10.1.6 Associated with each name key, we might have another table that lists information about that person: their age, their salary, and so on. And associated with each of those pieces of information might be other tables, for example, the salary information for previous years. Slide 10.1.7 Not only do our table data abstractions need to be flexible enough to allow for other tables to be entries in a table, we may have other ways of gathering information together in a table. For example, we might have another table that lists employees by age. Slide 10.1.8 Clearly we can build a table where the keys are the ages of the employees. Here, however, the value associated with a key should be a list whose elements point to the entries in other tables that capture all the data about each employee. So our tables need to be very flexible in terms of what information they can store. 6.001 Notes: Section 10.2

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 10.2.1 Let's start by looking at the idea of pairing keys and values, as Traditional LISP structure: association list this is going to be the heart of a table implementation. Our goal A list where each element is a list of the key and value is to see how different choices of implementation influence the behavior of the table A traditional structure for doing this is called an a-list or an association list This is a list in which each element is itself a list of a key and a value, or in other words, it is a list of lists, all of which are two elements long Traditional LISP structure: association list So for example, if we want to represent this table(and notice that A list where each element is a list of the key and value this is an abstract version of a table that is. a binding of x to 15 and epresent the table y to 20)as an association list, we can do so as the illustrated list of sts. Each of the inner lists is a two-element list of a key and a as the alist: ((x 15)(y 20)) alue Slide 10.2.3 Or to do this a little more concretely, we could represent this Traditional LIsP structure: association list particular table with the illustrated box-and-pointer diagram. This. A list where each element is a list of the key and value illustrates the nice structure of this system, in which each element of the top level list is a binding, and each of the bindings is just a two-element list of a name and a binding as the alist: ((x 15)(y 20) Alist operation: find-assoc If we were to make the design choice to use a-lists as our (define (find-assoc key alist) representation for a table, then we just need to add a couple of (cond ((nu11?a1ist)静f) operations. First, we will need a way to find an entry for a key in ((equal? key (caar alist))(cadar alist)) the a-list and returning the associated value else (find-assoc key (cdr alist))))) Here is one way to do this. Notice how it walks down the list ne key against the first element of the first element of the list(this is what caar extracts, which you can check by looking back at the box-and- pointer structure). If we get to the end of the dicate the key is not present. No how we use equal? to check the equality of the key and the L element. And notice that when we do find a matching key, we use cadar to extract the second element of the first element which exactly the value associated with this ke

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 10.2.1 Let's start by looking at the idea of pairing keys and values, as this is going to be the heart of a table implementation. Our goal is to see how different choices of implementation influence the behavior of the table. A traditional structure for doing this is called an a-list or an association list. This is a list in which each element is itself a list of a key and a value, or in other words, it is a list of lists, all of which are two elements long. Slide 10.2.2 So for example, if we want to represent this table (and notice that this is an abstract version of a table, that is, a binding of x to 15 and y to 20) as an association list, we can do so as the illustrated list of lists. Each of the inner lists is a two-element list of a key and a value. Slide 10.2.3 Or to do this a little more concretely, we could represent this particular table with the illustrated box-and-pointer diagram. This illustrates the nice structure of this system, in which each element of the top level list is a binding, and each of the bindings is just a two-element list of a name and a binding. Slide 10.2.4 If we were to make the design choice to use a-lists as our representation for a table, then we just need to add a couple of operations. First, we will need a way to find an entry for a key in the a-list and returning the associated value. Here is one way to do this. Notice how it walks down the list, checking the key against the first element of the first element of the list (this is what caar extracts, which you can check by looking back at the box-and-pointer structure). If we get to the end of the list, we return false to indicate the key is not present. Notice how we use equal? to check the equality of the key and the element. And notice that when we do find a matching key, we use cadar to extract the second element of the first element, which is exactly the value associated with this key

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 10. 2.5 As an example, let's give a name to our simple alist(noticd the useAlist operation: find of the quoted list structure to create this list of lists ). If we then define (find-assoc key alist) evaluate (find-assoc 'y al)(note the use of the to get the (cond symbol y rather than any value associated with it)we get out the ((equal? key (caar alist))(cadar alist)) expected value of 20. Trace through the code and the box-and else (find-assoc key (cdr alist))))) pointer structure to convince yourself that this is correct (define al ' ((x 15)(y 20))) (find-assoc 'y al) >20 Slide 10.2.6 Alist operation: add-asso Adding a new entry into this a-list is pretty easy. We'll just"cons define (add-assoc key val alist it onto the front of the existing list. All we have to do is take the (cons (list key val) alist) key and value to be associated together, put them into a list, then put that list at the front of the existing a-list. Since the a-list is a list, consing something onto the front of the list, by the closure property, gives us a new list Note that in this implementation, we don't actually remove any prior binding of a key from the representation. We simply shadow the old binding with the new one, meaning that the procedure fo looking up a binding will always find the new one first, since it is I at the beginning of the list. So what does this do to the efficiency of find-assoc? Clearly the more things we add, the more things we have to search through to find a binding different from those added Slide 10.2.7 Nonetheless, this is a nice implementation. Thus, we can add a new|Alist operation:add-assoc binding to our old table, giving it a new name(which we need to lo because we need a way to refer to the table). Now, a 2 is a list (cons (list key val) alist)) of 3 elements, with the new binding of y at the front and our original binding further down the list (define a2 (add-assoc y 10 al)) Looking up the binding of y in this a-list will give us the value 10 2 Y10)(x15)y20)) that is, the new binding value (find-assoc y a2)=> 10 Slide 10.2.8 Alists are not an abstract data type This seems like a reasonable implementation, but let's think about this structure. In particular, this is not an abstract data type. And here is why

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 10.2.5 As an example, let's give a name to our simple alist (noticd the use of the quoted list structure to create this list of lists). If we then evaluate (find-assoc 'y a1) (note the use of the ' to get the symbol y rather than any value associated with it) we get out the expected value of 20. Trace through the code and the box-and￾pointer structure to convince yourself that this is correct. Slide 10.2.6 Adding a new entry into this a-list is pretty easy. We'll just "cons" it onto the front of the existing list. All we have to do is take the key and value to be associated together, put them into a list, then put that list at the front of the existing a-list. Since the a-list is a list, consing something onto the front of the list, by the closure property, gives us a new list. Note that in this implementation, we don't actually remove any prior binding of a key from the representation. We simply shadow the old binding with the new one, meaning that the procedure for looking up a binding will always find the new one first, since it is at the beginning of the list. So what does this do to the efficiency of find-assoc? Clearly the more things we add, the more things we have to search through to find a binding different from those added. Slide 10.2.7 Nonetheless, this is a nice implementation. Thus, we can add a new binding to our old table, giving it a new name (which we need to do because we need a way to refer to the table). Now, a2 is a list of 3 elements, with the new binding of y at the front and our original binding further down the list. Looking up the binding of y in this a-list will give us the value 10 that is, the new binding value. Slide 10.2.8 This seems like a reasonable implementation, but let's think about this structure. In particular, this is not an abstract data type. And here is why:

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 a￾lists 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

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology preserving the association between a name for a table and the actual representation Slide 10.3.2 Table1 example So let's see how this works first. we will create a table with n (define ttl (make-table1)) ttl by using our constructor Slide 10.3.3 Here is what that looks like. The name ttl points to a list whoseTable1 example car is the symbol tablel(our tag)and whose cdr is just the empty list (i.e. there is nothing in our a-list yet) tablel Slide 10.3.4 Table1 example Now, let's put a new binding of a key and a value into our table, for (define ttl (make-table1)) example, the binding of y and 20 (tablel-put! ttl 'y 20) table Slide 10.3.5 What happens when we use this operation to insert something? Table a list of two elements)and finally"conses"that onto the front of (tablel-put! tt1 702) Remember that table-put! uses add -assoc which extracts the a-list from the tagged representation, (in this case an empty list), and then creates a binding of the arguments (remember that is the a-list. Since this is the empty list, it creates a top level list of one element. as shown tablel 口→

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. preserving the association between a name for a table and the actual representation. Slide 10.3.2 So let's see how this works. First, we will create a table with name tt1 by using our constructor. Slide 10.3.3 Here is what that looks like. The name tt1 points to a list whose car is the symbol table1 (our tag) and whose cdr is just the empty list (i.e. there is nothing in our a-list yet). Slide 10.3.4 Now, let's put a new binding of a key and a value into our table, for example, the binding of y and 20. Slide 10.3.5 What happens when we use this operation to insert something? Remember that table-put! uses add-assoc, which extracts the a-list from the tagged representation, (in this case an empty list), and then creates a binding of the arguments (remember that is a list of two elements) and finally "conses" that onto the front of the a-list. Since this is the empty list, it creates a top level list of one element, as shown

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 10.3.6 Table1 example And then we use this new operation, set-cdr! to take the cons (define ttl (make-tablel)) air pointed to by ttl, and mutate or change it's cdr to point to (tablel-put! tt1 'y 20) this new structure, that is to the value returned by add -assoc Notice what this gives us. We now have a new table. It has a tag or the front, and it has an a-list at the back, which currently has one binding within it table1 Slide 10.3.7 Let's add another binding, x and 15, to this same table (define ttl (make-tablel)) (tablel-put! tt1 'y 20) (tablel-put! ttl 'x 15) Slide 10.3.8 Table1 example Looking back at the code, you can see what this should do. Add- (define ttl (make-tablel)) assoc first takes the internal representation for the table(i.e (tablel- removes the tag) getting access to the structure shown in blue. It (tablel-put! t七1 15 then creates a new binding, a pairing of x and 15, creating a 2 七t1 element list, and then"conses"this onto the front of the existing a- st. This is shown in red. This new structure is our new a-list and it has within it two bindings, each a separate 2 element list 七ab1e1 Slide 10.3.9 Then we once more use the set-cdr! operation to take the pairTable1 example pointed to by ttl and change its cdr part to point to the value define ttl (make-tablel)) returned by add-assoc, i.e., this new structure. This gives us a (tablel-put! ttl 'y 20) new a-list associated with this tabl tablel

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 10.3.6 And then we use this new operation, set-cdr! to take the cons pair pointed to by tt1, and mutate or change it's cdr to point to this new structure, that is to the value returned by add-assoc. Notice what this gives us. We now have a new table. It has a tag on the front, and it has an a-list at the back, which currently has one binding within it. Slide 10.3.7 Let's add another binding, x and 15, to this same table. Slide 10.3.8 Looking back at the code, you can see what this should do. Add￾assoc first takes the internal representation for the table (i.e. removes the tag) getting access to the structure shown in blue. It then creates a new binding, a pairing of x and 15, creating a 2 element list, and then "conses" this onto the front of the existing a￾list. This is shown in red. This new structure is our new a-list, and it has within it two bindings, each a separate 2 element list. Slide 10.3.9 Then we once more use the set-cdr! operation to take the pair pointed to by tt1 and change its cdr part to point to the value returned by add-assoc, i.e., this new structure. This gives us a new a-list associated with this table

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 103.10 Table1 example If we get a value out of this table, say the pairing associated with (define ttl (make-tablel)) the key y, then table-get does a very similar thing. It removes (tablel-put! tt1 'y 20) the tag, getting the pointer to the actual a-list(shown in light blue) tablel-put! ttl 'x 15 and then uses find-assoc, the operator associated with the a ttl\ (tablel-g list, to find and return the value associated with this key 旧 Slide 10.3.1 So this gives us a simple implementation of a table. It has a tag at the front to identify it, it has some constructors and selectors to get (define ttl (make-tablel)) at the internal representation of the table, which in this case is an a (tablel-put! tt1 'y 20) ist, pairing up keys and values ( table1-put!tt1·x Slide 10.3.12 How do we know Table1 is an ADT implementation So what is it that makes this an abstract data type? Is it the fact that that it has a tag? While this is careful programming, it does not Because it has a type tag suffice to create an adt Because it has mutators and accessors No Is it the fact that it has a constructor? While having a distinct interface is good programming, this also does not suffice to create ADT Similarly, the fact that it has accessors or selectors, and mutators (the set-cdr!)is useful, but not sufficient to define an ADT. In fact, a-lists also had these properties, but we argued that they were not adt's Slide 10.3.13 In fact, the key issue is the isolation of the abstraction from its How do we know Table1 is an ADT implementation users. We can't use any list processors, like car, cdr, map Potential reason filter directly on the table Because it has Because the rest of the program does not apply any functions to Table 1 objects other than the function For example, no car, cdr, map, filter done to table

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 10.3.10 If we get a value out of this table, say the pairing associated with the key y, then table-get does a very similar thing. It removes the tag, getting the pointer to the actual a-list (shown in light blue), and then uses find-assoc, the operator associated with the a￾list, to find and return the value associated with this key. Slide 10.3.11 So this gives us a simple implementation of a table. It has a tag at the front to identify it, it has some constructors and selectors to get at the internal representation of the table, which in this case is an a￾list, pairing up keys and values. Slide 10.3.12 So what is it that makes this an abstract data type? Is it the fact that that it has a tag? While this is careful programming, it does not suffice to create an ADT. Is it the fact that it has a constructor? While having a distinct interface is good programming, this also does not suffice to create an ADT. Similarly, the fact that it has accessors or selectors, and mutators (the set-cdr!) is useful, but not sufficient to define an ADT. In fact, a-lists also had these properties, but we argued that they were not ADT's. Slide 10.3.13 In fact, the key issue is the isolation of the abstraction from its users. We can't use any list processors, like car, cdr, map or filter directly on the table