Local Disk6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. All rights reserved6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 8.1 Slide 8.1.1 In this lecture we are going to introduce a new data type, specifically to deal with symbols. This may sound a bit odd, but if you step back, you may realize that everything we have done so far in the course has focused on procedures to manipulate numbers. While we have used names for things, we have treated them as exactly that: names associated with values. Today we are going to create a specific data type for symbols, and see how having the notion of a symbol as a unit to be manipulated will lead to different kinds of procedures. To set the stage for this, recall what we have when we deal with data abstractions. We said a data abstraction in essence consisted of a constructor (for building instances of the abstraction), selectors or accessors (for getting out the pieces of an abstraction), a set of operations (for manipulating the abstraction, while preserving the barrier between the use of the abstraction and the internal details of its representation), and most importantly, a contract (specifying the relationship between the constructor and selectors and their behaviors). Slide 8.1.2 For example, if I want to create an abstraction for manipulating points in the plane, I could create a constructor like this. Make-point is a procedure that glues together two parts into a list. Slide 8.1.3 Here is one of the associated selectors, which in this case takes a data object as built by the constructor, and pulls out the first (or x coordinate) part of that object.6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 8.1.4 Given that I can build objects of this type, I can define operations on them. Notice that the key point about these things is that they use the selectors to get at the pieces of the data object. For example, in this case we do not use car to get the piece of the object, we use the defined selector. Slide 8.1.5 ... and then the key piece, the contract, the thing that relates the constructor and selectors together. For this example, the contract states that however we glue pieces together using the constructor, applying the first selector to that result will cause the value of the first piece to be returned. So, with these ideas of abstractions in mind, let's turn to introducing a new kind of data structure. Slide 8.1.6 Let's first motivate why we need a new data type. Suppose I ask you the following question. Think for a second about how you might respond. I, personally, would probably respond by saying "blue". Slide 8.1.7 Now, what about this question? If you are thinking carefully about this, you ought to respond by saying "your favorite color". So, we say two different things in response to these two questions. What's the difference in the questions?6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 8.1.8 If you think carefully about it, you should see that in the first case, I got the meaning associated with the expression "your favorite color", much like getting the value associated with a name. In the second case, I got the actual expression. The "double quotation marks" in the second case indicated that I wanted the actual expression, while in the first case I want the value associated with it (i.e. the actual favorite color vs. the phrase "favorite color"). So in many cases we may want to be able to make exactly this distinction, between the value associated with an expression, and the actual symbol or expression itself. This is going to lead us to introduce a new data type. Slide 8.1.9 Now, the question is how do I create symbols as data objects? Well, we already saw one way of doing this, when we defined a name for a value. And we saw that if we wanted to get back the value associated with that symbol (or name) we could just reference it, and the evaluator would return the associated value. But suppose I want to reference the symbol itself. How do I do that? In other words, how do I distinguish between "your favorite color" and "blue" as the value of "your favorite color". Slide 8.1.10 Basically, we need to back up and think about what the Scheme interpreter is doing. When we type in an expression and ask for it to be evaluated, the reader first converts that expression into an internal form, and the evaluator then applies its set of rules to determine the value of the expression. Here, we need a way of telling the reader and evaluator that we don't want to get the value. Scheme provides this for us with a special form, called quote. If we evaluate the example expression using this special form, it returns for us a value of the type symbol that somehow captures that name. Note that it makes sense for quote to be a special form. We can't use normal evaluation rules because that would cause us to get the value associated with the name alpha but in fact our goal is to simply keep the name, not its value.6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 8.1.11 So what kind of object is a symbol? We can think of it as a primitive data object. Hence it doesn't really have a constructor or selectors, though quote serves to help us distinguish between the symbol and its value. It does, however, have some operations. In particular, the predicate symbol? takes in an object of any type, and returns true if that object is a symbol. The operation eq? is used to compare two symbols (among other things) and we will return to that in a second. So here is our new data type for creating symbols, that is, data objects that refer to the name itself, rather than the value with which it is associated. Slide 8.1.12 To see how this data structure is handled, let's go back to our "two worlds" view of evaluation, separating the visible world of the user from the internal execution world of computation. What happens when we consider symbols in this context? Slide 8.1.13 First, remember what happened when we evaluated other expressions. For example, if the expression were a lambda expression, then the evaluator checked the type of this expression, realized it was a
View Full Document
Unlocking...