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