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 why6.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: