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 <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
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 8.1.1 a useful property of the quote special form In fact, our Scheme evaluator is smart, and it keeps track of list (quote delta) (quote delta)) what symbols have been created so far. As a consequence, when we refer to a symbol, Scheme gives us a pointer to the unique instance of that symbol. We can illustrate that as shown, by evaluating this ex This will create a list of two elements, both of which happen to be the symbol delta 4 Slide 8.1.19 A useful property of the quote special form Scheme will create a box-and-pointer structure for a two- element list. But the car of both cons pairs in this list now (list (quote delta) (quote delta)) point to exactly the same object inside of the machine, namely the data structure for the symbol delta symbol delta A useful property of the quote special form Slide 8.1. 20 This is valuable, because it gives us a way of creating (list (quote delta) (quote delta) predicates for testing equality of symbols, and indeed other more complicated objects, as we will see a bit later on symbol delta Two quote expressions with the same name return the same Slide 8. 1.21 The operation eq? tests for the same object Our predicate for testing equality of symbols is eg? This is a very powerful procedure, used to test equality of a range of returns #t if its two arguments are the same object structures, as we will see. Ea? is a primitive procedure (i.e something built into Scheme), and it returns the boolean value true"if its two arguments are the same object. For our context, that says that since we create only one instance of each symbol using eq? to test equality of symbols will return true if the two expressions evaluate to a pointer to the same symbol data structure 600SC
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 8.1.18 In fact, our Scheme evaluator is smart, and it keeps track of what symbols have been created so far. As a consequence, when we refer to a symbol, Scheme gives us a pointer to the unique instance of that symbol. We can illustrate that as shown, by evaluating this expression. This will create a list of two elements, both of which happen to be the symbol delta. Slide 8.1.19 Scheme will create a box-and-pointer structure for a twoelement list. But the car of both cons pairs in this list now point to exactly the same object inside of the machine, namely the data structure for the symbol delta. Slide 8.1.20 This is valuable, because it gives us a way of creating predicates for testing equality of symbols, and indeed other more complicated objects, as we will see a bit later on. Slide 8.1.21 Our predicate for testing equality of symbols is eq?. This is a very powerful procedure, used to test equality of a range of structures, as we will see. Eq? is a primitive procedure (i.e. something built into Scheme), and it returns the Boolean value "true" if its two arguments are the same object. For our context, that says that since we create only one instance of each symbol, using eq? to test equality of symbols will return true if the two expressions evaluate to a pointer to the same symbol data structure
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 8.1.22 The operation eq? tests for the same object Here is an example of what we mean by that. If we apply eg a primitive procedure returns #t if its two arguments are the same object to two arguments that evaluate to the same symbol, we get a very fast true" value returned otherwise a "false" value is returned ote e te delta)(quote eps))==> Slide 8.1.23 The operation eq? tests for the same object Finally, here is the type of eq? It accepts two arguments of a primitive procedure any type other than a number or a string, and returns a boolean returns #t if its two arguments are the same object value. based on the rules described above (eq? s)(cue e delta) For those who are interested otype, EQtype b。o1ea e= any type except number or string The operation eq? tests for the same object Slide 8.1.24 For numbers, we have a separate procedure to test equality, and if its two arguments are the same object a different procedure to testing equality of strings. Everything very fast else uses eq? (eg? (quote eps)(quote ep te delta)(quote ->#t This now completes our method for creating and dealing with )==> eq?: E&type, etype boolean i Etype any type except number or string 6.001 Notes: Section 8.2
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 8.1.22 Here is an example of what we mean by that. If we apply eq? to two arguments that evaluate to the same symbol, we get a "true" value returned, otherwise a "false" value is returned. Slide 8.1.23 Finally, here is the type of eq?. It accepts two arguments of any type other than a number or a string, and returns a Boolean value, based on the rules described above. Slide 8.1.24 For numbers, we have a separate procedure to test equality, and a different procedure to testing equality of strings. Everything else uses eq?. This now completes our method for creating and dealing with symbols. 6.001 Notes: Section 8.2
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 8.2.1 Having the ability to intermix numbers and symbols in ing other expressions expressions is a very useful thing, and as a consequence w would like to be able to generalize this to all sorts of data structures. Since our primary data structure is a list, it would be nice if we had the ability to quote list structure, in addition to simple names 6001S Slide 8.2.2 Generalization: quoting other expressions In fact, our reader and evaluator will do this for us. Since the Reader converts to Prints out as fundamental representation of expressions in our language is in terms of lists and list structure, the reader is set up to convert every typed in expression into list structure. This is true for any 2.《quot。(ab) expression created out of parentheses, which denote the boundaries of the list structure few lectures, the evaluator is then set up te 3.《quot1) take that list structure and manipulate it according to the rules of evaluation, to determine the meaning of the expression In general, (quote DATUM)is converted to DATUM In the case of the special form quote, however, the evaluator 6001 SICP I simply passes on the list structure, without any evaluation. Thus in general, quoting a printed representation of a list structure including sublists of numbers and symbols, gets converted to the appropriate list structure internally, and then returned. Its printed representation will then match the original expression Slide 8.2.3 names of things and their values. for virtually every kindon nis is nice, because quote now let's us distinguish between Shorthand: the single quote mark structure. Of course, writing out long expressions involving the shorthand for (quote a) special symbol quote is a bit tedious, so we have a nice shorthand in Scheme, namely the single quote mark. Thus, 'a is just a shorthand for (quote a). And ' (1 2)is just a shorthand notation for (quote (1 2))which we already saw is shorthand for (list (quote 1)(quote 2)). This means in general that placing a'in front of the printed representation for any list structure will cause the evaluator to create the corresponding list structure 6m: SICP
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 8.2.1 Having the ability to intermix numbers and symbols in expressions is a very useful thing, and as a consequence we would like to be able to generalize this to all sorts of data structures. Since our primary data structure is a list, it would be nice if we had the ability to quote list structure, in addition to simple names. Slide 8.2.2 In fact, our reader and evaluator will do this for us. Since the fundamental representation of expressions in our language is in terms of lists and list structure, the reader is set up to convert every typed in expression into list structure. This is true for any expression created out of parentheses, which denote the boundaries of the list structure. As we will see in a few lectures, the evaluator is then set up to take that list structure and manipulate it according to the rules of evaluation, to determine the meaning of the expression. In the case of the special form quote, however, the evaluator simply passes on the list structure, without any evaluation. Thus in general, quoting a printed representation of a list structure, including sublists of numbers and symbols, gets converted to the appropriate list structure internally, and then returned. Its printed representation will then match the original expression. Slide 8.2.3 This is nice, because quote now let's us distinguish between names of things and their values, for virtually every kind of structure. Of course, writing out long expressions involving the special symbol quote is a bit tedious, so we have a nice shorthand in Scheme, namely the single quote mark ' . Thus, 'a is just a shorthand for (quote a). And '(1 2) is just a shorthand notation for (quote (1 2)) which we already saw is shorthand for (list (quote 1) (quote 2)). This means in general that placing a ' in front of the printed representation for any list structure will cause the evaluator to create the corresponding list structure
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 8.2.4 Your turn: what does evaluating these print out? So let's take a quick break to see if you are getting this idea. Here are a set of expressions. What gets printed out as a result of evaluating each of these? When you think you have the answers go to the next slide (+x3) (list (quote +)x '3 (1st'+x3 (list 3 Slide 8.2.5 So here are the solutions. First, notice that we have defined x to Your turn what does evaluating these print out? have the value 20, creating a pairing of that value with that name Evaluating the first expression just gives us a normal (define x 20) combination, resulting in the addition of 3 to the value of x, or 23.(+x 3) The next expression, with the single quote, says to just return a list whose printed representation is equivalent to this, i.e. the list =>(+x3) of'+, 'x and3, or the list of the symbol + the symbol x and the (1st( quote+)x3)=>(+203) number 3. Thus what is printed out is the same expression as what was quoted >(+203) The next expression draws a distinction with this example. It says (list+* 3y =>(procedure #...]20 3) to create a list of a quoted +, the value of x, and the quoted value 4 of 3. Thus we get a list of the symbol +(because we quoted it), the number 20. since we asked for the value of x. and the number 3 The next expression returns the same value, since quoting a number just returns the number Finally, what happens if we just ask for the list of+, x and 3? Well, we get a list of the values of each of these expressions, as shown Thus, these examples show the variations in the use of quotation within list structure, determining when the values of expressions are returned and when the names are simply returned 6.001 Notes: Section 8.3 Slide 8.3.1 mbolic differentiation Let's take the idea of symbols, and combine it with some of the other lessons we' ve seen so far, to see how symbols add to the expressive power of our language. To do this, we'll look at the Algebraic expression Representation example of symbolic derivatives, in particular, creating a system to compute symbolic derivatives. By that, I mean returning symbolic expressions, much as you do in calculus Thus, I want a system that takes some representation for the algebraic expression x 3 and some representation for the variable x, and returns the derivative of this expression with respect to that variable
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 8.2.4 So let's take a quick break to see if you are getting this idea. Here are a set of expressions. What gets printed out as a result of evaluating each of these? When you think you have the answers, go to the next slide. Slide 8.2.5 So here are the solutions. First, notice that we have defined x to have the value 20, creating a pairing of that value with that name. Evaluating the first expression just gives us a normal combination, resulting in the addition of 3 to the value of x, or 23. The next expression, with the single quote, says to just return a list whose printed representation is equivalent to this, i.e. the list of '+, 'x and '3, or the list of the symbol +, the symbol x and the number 3. Thus what is printed out is the same expression as what was quoted. The next expression draws a distinction with this example. It says to create a list of a quoted +, the value of x, and the quoted value of 3. Thus we get a list of the symbol + (because we quoted it), the number 20, since we asked for the value of x, and the number 3. The next expression returns the same value, since quoting a number just returns the number. Finally, what happens if we just ask for the list of +, x and 3? Well, we get a list of the values of each of these expressions, as shown. Thus, these examples show the variations in the use of quotation within list structure, determining when the values of expressions are returned and when the names are simply returned. 6.001 Notes: Section 8.3 Slide 8.3.1 Let's take the idea of symbols, and combine it with some of the other lessons we've seen so far, to see how symbols add to the expressive power of our language. To do this, we'll look at the example of symbolic derivatives, in particular, creating a system to compute symbolic derivatives. By that, I mean returning symbolic expressions, much as you do in calculus. Thus, I want a system that takes some representation for the algebraic expression x + 3 and some representation for the variable x, and returns the derivative of this expression with respect to that variable
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology To do this, I am going to need a way of representing expressions, which I will do using lists. Thus the algebraic expression 3 I choose to represent as the list(+ x 3), that is a list of the symbol, +, the symbol, x, and the number 3. For base cases, I will just represent a variable by its symbol Products I will represent in a similar fashion. And given an expression involving more than two terms i will break into recursive pieces each of which involves at most two terms Thus, I am going to restrict my system to sums and products of at most two terms. I haven,'t said how to build the ystem, of course, but only how I am going to represent expressions in my system Symbolic differentiation Bide 8.3.2 (deriv swith-respecl-to-var) aa> snew-expr2 As we have already said, we would like to build a procedure deriv that takes as input some representation of an algebraic (+X3) expression, and a representation of the variable with respect to which we want to take the derivative. and returns a 5y) epresentation of the new expression that represents the (+x(+y3) derivative of that algebraic expression 4 Slide 8.3.3 mbolic differentiation So, for example, here is the behavior I would like. I would like (donly cepra owith-respece-tovarpy) -- snewexpn to differentiate x t 3 with respect to x and get back the Algebraic expression Representation value 1. Notice the use of the single quote to indicate that I want the list structure itself as the value of the argument, creating a representation of the algebraic expression. Thus, we want our system to take a symbolic algebraic expression input, and return a new symbolic algebraic expression as output, satisfying the rules of calculus +K3) Building a system for differentiation Slide. 3. 4 Example of To build this system, I am going to stitch together several idea I using lists of lists to represent expressions, using symbols to s, How to use the symbol type symbolic manipulation capture algebraic expressions, and using procedural abstractions to manipulate the list structures corresponding to those get started expressions. To build the system, I am going to consider several stages focusing on how to initially get things going, then how to build a direct implementation, and finally how to learn from the direct method to create a better implementation. Throughout we will see how these ideas of data structures and pi ocedure abstractions work together to implement this system
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. To do this, I am going to need a way of representing expressions, which I will do using lists. Thus the algebraic expression x + 3 I choose to represent as the list (+ x 3), that is a list of the symbol, +, the symbol, x, and the number 3. For base cases, I will just represent a variable by its symbol. Products I will represent in a similar fashion. And given an expression involving more than two terms I will break into recursive pieces each of which involves at most two terms. Thus, I am going to restrict my system to sums and products of at most two terms. I haven't said how to build the system, of course, but only how I am going to represent expressions in my system. Slide 8.3.2 As we have already said, we would like to build a procedure deriv that takes as input some representation of an algebraic expression, and a representation of the variable with respect to which we want to take the derivative, and returns a representation of the new expression that represents the derivative of that algebraic expression. Slide 8.3.3 So, for example, here is the behavior I would like. I would like to differentiate x + 3 with respect to x and get back the value 1. Notice the use of the single quote to indicate that I want the list structure itself as the value of the argument, creating a representation of the algebraic expression. Thus, we want our system to take a symbolic algebraic expression as input, and return a new symbolic algebraic expression as output, satisfying the rules of calculus. Slide 8.3.4 To build this system, I am going to stitch together several ideas, using lists of lists to represent expressions, using symbols to capture algebraic expressions, and using procedural abstractions to manipulate the list structures corresponding to those expressions. To build the system, I am going to consider several stages, focusing on how to initially get things going, then how to build a direct implementation, and finally how to learn from the direct method to create a better implementation. Throughout, we will see how these ideas of data structures and procedural abstractions work together to implement this system