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 ke6.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