6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 8.1 Slide 8.1.1 Review: data abstraction In this lecture we are going to introduce a new data type, a data abstraction consists of: 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 selectors 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 contract manipulated will lead to different kinds of procedures To set the stage for this recall what we have when we deal with 60015e 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) Review: data abstraction Slide 8.1.2 a data abstraction consists of For example, if I want to create an abstraction for manipulating constructors points in the plane, I could create a constructor like this Make mbda (x y) (list x y))) point is a procedure that glues together two parts into a list operations contract Slide 8.1.3 eview ta abstraction Here is one of the associated selectors which in this case takes a data abstraction consists of a data object as built by the constructor, and pulls out the first constructors (or x coordinate) part of that object (lambda (x y) (list x y))) (lambda (pt) t})) operations
6.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. Makepoint 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 o 2004 by Massachusetts Institute of Technology Review: data abstraction Given that I can build objects of this type, I can define a data abstraction consists of operations on them. Notice that the key point about these things constructors (define make-point is that they use the selectors to get at the pieces of the data (lambda (x y) (list x y))) object. For example, in this case we do not use car to get the electors define x-coor ce of the object, we use the defined selector operations (define on-y-axis? (lambda (pt)(=(x-coor pt)0))) Slide. 1.5 Review: data abstraction constructor and selectors together. For this example, the the d then the key piece, the contract, the thing that relates t a data abstraction consists of constructors contract states that however we glue pieces together using the (define make-point (lambda (x y) (list x y))) 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 pt})) operations introducing a new kind of data structure (lambda (pt)(=(x-coor pt)0)) (xx-coor (make-point <x> <y)) 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 nd by Slide 8.1.7 bols? Now, what about this question? If you are thinking carefully Say your favorite color about this, you ought to respond by saying" your favorite color". So, we say two different things in response to these two Say your favorite color" 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.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 o 2004 by Massachusetts Institute of Technology Slide 8.1.8 If you think carefully about it, you should see that in the Say your favorite color case, I got the meaning associated with the ey Say "your favorite color favorite color", much like getting the value as pressiOn foA>t ociated with a What is the difference? name. In the second case, I got the actual expression. The In one case, we want the meaning associated with the double quotation marks"in the second case indicated that I In the other case, we want the actual words (or symbols) wanted the actual expression, while in the first case I want the f the expres value associated with it(i.e. the actual favorite color vs the hrase favorite color ) So in many cases we may want to b able to make exactly this distinction, between the value ed with an ex and the actual symb L expression itself. This is going to lead us to introduce a new data type Slide 8.1.9 Creating and Referencing Symbols 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 (define alpha 27) name for a value And we saw that if we wanted to get back the value associated. How do I reference a symbol's value? ith that symbol (or name)we could just reference it, and the yue: 27 valuator would return the associated value But suppose I want to reference the symbol itself. How do i do How do I reference the symbol itseif? that? In other words, how do i distinguish between"your ??? favorite color"and"blue"as the value of your favorite color" 600SC Slide 8.1.10 y of telling interpreter: "I want the following Basically, we need to back up and think about what the scheme data structure, not as an expression to be 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 I 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.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 o 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 Symbol: a primitive type primitive data object. Hence it doesn't really have a constructor.constructors or selectors, though quo te serves to help us distinguish None since really a primitive not an object with parts between the symbol and its value It does, however, have some operations. In particular, the None returns true if that object is a symbol any type, and dicate symbol? takes in an object of any type, and symbol? i type: anytype (symbol? (quote alpha))=>#t The operation eq? is used to compare two symbols(among discuss in a minute other things)and we will return to that in a second So here is our new data type for creating symbols, that is, data 4 6001S objects that refer to the name itself, rather than the value with which it is associated Symbol: printed representation Slide 8.1.1 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? 6 001 SICP Slide 8.1.13 Symbol: printed representation 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 special form, a lambda, and used the rule for that particular special form. In this case, it would create the compound procedure represented by that expression, and return a pointer to that created object, causing the computer A compound proc to print out information identifying that pointer, i.e. some value associated with such an object
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 special form, a lambda, and used the rule for that particular special form. In this case, it would create the compound procedure represented by that expression, and return a pointer to that created object, causing the computer to print out information identifying that pointer, i.e. some value associated with such an object
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 8.1.14 Symbol: printed representation Something different happens with quotes. If we type in an xpression involving the special name quote, the evaluator [quote beta) r)(*xx}} checks the type of this expression, recognizes the special form #[compound-.1 beta and uses a rule designed for such special expressions In the case of quote, we simply take the second subexpression and create an internal representation for it. The reader symbol ecognizes this as a sequence of characters and creates a symbol with that sequence of characters, like a name. The evaluator then returns to the visible world something to print out, simply he name that we just quoted, beta in this case Slide 8.1.15 object, note that we can use it anywhere we would expect to use(ist1, e ordinary values Now that we have the ability to create this new kind of data =>(12) such primitive objects. For example, we can certainly create a list of normal things, like numbers. Remember that creating the list of I and 2 returns a printed representation of that list structure, written as (1 2) 601h Symbols are ordinary values Slide 8.1.16 but I could also create a list of quoted things we evaluate the 1st12) arguments to list, getting two symbols, then create the list of (list (quote delta) (quote gamma) 【de1 ta garma) those symbols, finishing with a printed representation of the structure created by gluing those symbols together 6 001 SICP Slide 8.1.17 Symbols are ordinary values What does that list look like? Well. list creates a box-and- =>(12) pointer structure just as in the case of numbers Thus at the top mist (quote detal (u (dez ra bomma)) level of that structure. we will have a skeleton containing two things, ending in the special"empty list"symbol. And what hangs off of this spine? a pointer to the data structure of a symbol! Thus we can use symbols in the same places we might have earlier used numbers within other data structures de1七a ganna 6001S
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 8.1.14 Something different happens with quotes. If we type in an expression involving the special name quote, the evaluator checks the type of this expression, recognizes the special form, and uses a rule designed for such special expressions. In the case of quote, we simply take the second subexpression and create an internal representation for it. The reader recognizes this as a sequence of characters and creates a symbol with that sequence of characters, like a name. The evaluator then returns to the visible world something to print out, simply the name that we just quoted, beta in this case. Slide 8.1.15 Now that we have the ability to create this new kind of data object, note that we can use it anywhere we would expect to use such primitive objects. For example, we can certainly create a list of normal things, like numbers. Remember that creating the list of 1 and 2 returns a printed representation of that list structure, written as (1 2). Slide 8.1.16 ... but I could also create a list of quoted things. We evaluate the arguments to list, getting two symbols, then create the list of those symbols, finishing with a printed representation of the structure created by gluing those symbols together. Slide 8.1.17 What does that list look like? Well, list creates a box-andpointer structure just as in the case of numbers. Thus at the top level of that structure, we will have a skeleton containing two things, ending in the special "empty list" symbol. And what hangs off of this spine? A pointer to the data structure of a symbol! Thus we can use symbols in the same places we might have earlier used numbers within other data structures