6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 9.1 Slide 9.1.1 Manipulating complex numbers In the last lecture, we introduced symbols into our language And we showed how to intermix them with numbers to create magnitude mixed expressions. We saw how to use that idea to create a mbolic differentiation program that could reason about algebraic expressions, rather than just numeric expressions. In this lecture, we are going to take the idea of symbols, and combine them with lots of different data structures to create tagged data structures Why do we need a tag?. and what is a tag? We'll answer these questions by considering an example. Suppose I want to build a 6001 SICP system to manipulate complex numbers. Remember that a complex number is a number with two parts, standardly epresented as a real and an imaginary part. Think of these as two axes in a vector space, or as a point in the plane (though we will see that there are special rules for how to manipulate such points that are different from normal vectors) Because we can represent a complex number as a vector, we can also think about representing such numbers in terms of a magnitude(or length) and an angle(typically with respect to the real axis) Manipulating complex numbers Slide 9.1.2 Now, let's assume we have some data abstractions for complex numbers. We have a constructor, and appropriate selectors, Real, imag, mag angle ncluding selectors for both the real and imaginary part, and for he magnitude and angle As we saw earlier, given such constructors and selectors, we can proceed to write code to manipulate complex numbers, without worrying about internal details. So let's do that C001 SICP
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 9.1 Slide 9.1.1 In the last lecture, we introduced symbols into our language. And we showed how to intermix them with numbers to create mixed expressions. We saw how to use that idea to create a symbolic differentiation program that could reason about algebraic expressions, rather than just numeric expressions. In this lecture, we are going to take the idea of symbols, and combine them with lots of different data structures, to create tagged data structures. Why do we need a tag? .. and what is a tag? We'll answer these questions by considering an example. Suppose I want to build a system to manipulate complex numbers. Remember that a complex number is a number with two parts, standardly represented as a real and an imaginary part. Think of these as two axes in a vector space, or as a point in the plane (though we will see that there are special rules for how to manipulate such points that are different from normal vectors). Because we can represent a complex number as a vector, we can also think about representing such numbers in terms of a magnitude (or length) and an angle (typically with respect to the real axis). Slide 9.1.2 Now, let's assume we have some data abstractions for complex numbers. We have a constructor, and appropriate selectors, including selectors for both the real and imaginary part, and for the magnitude and angle. As we saw earlier, given such constructors and selectors, we can proceed to write code to manipulate complex numbers, without worrying about internal details. So let's do that
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 9.1.3 When manipulating complex numbers, I can take advantage ofManipulating complex numbers the fact that some things are easy to do in Cartesian(or real and magnitude Complex number has maginary)coordinates, and some things are easy to do in polar (or magnitude and angle)coordinates. For example, adding two m TRAs o eal, imag. mag, angle complex numbers is most easily conceptualized in Cartesian (define (+e z1 22) coordinates, while multiplying two complex numbers is most Eron-rect ( (real z1)(real easily conceptualized in polar coordinates. Addition is in fact just vector addition, so I use the selectors to get the parts of each (define(+o a 2) complex number, add them together using standard addition, make-comp1ex-Ex。np。1ax《 (nag 32)) (angle z2)))) Here i will need to use a constructor that is making a compler a then glue the two parts together to make a new complex number 6001 SICP number given Cartesian coordinates as input. For multiplication, I will use the polar selectors to get out the parts, so that I can just use normal multiplication on the magnitudes, and normal addition on the angles to get the new components. Here, I will use a constructor to make a new complex number that knows its inputs are provided in p of a data abstraction from its impementation. I can write code that lar coordinates Note once more how we are separating the use uses complex numbers, while assuming that someone else will eventually provide a specific implementation. And note the standard form of such procedures: we use selectors to get out the parts, apply more primitive operations to those parts, then reglue the parts back into a data abstraction Berts data structure Slide 9. 1. 4 While it is convenient to separate data abstraction implementation from data abstraction use, ultimately we will have to provide a detailed implementation, that is, we will need to build the "guts " of this abstraction Suppose we ask our friend Bert to provide an implementation for complex numbers 6001 SICP Slide 9.1.5 Bert's data structure First, Bert will need a way of gluing things together. He decides (define(make-complex-from-rect rl im)(list ni im)) rather naturally, just to use lists to glue pieces together. He still (define(make-complex-from-polar mg an) has a choice, though, and being a rather "square"guy, Bert (ist (mg(cos an)) simply opts to use rectangular coordinates as his basis. That means that Bert's representation of a complex number is as a list of a real and imaginary part Note what this means. If we hand bert a real and imaginary part for a new complex number, he can simply glue them together using list as this directly meets his representation. On the other hand, if we hand Bert a magnitude and angle, he will needd 6001联0 to convert these to real and imaginary equivalents(using the these numbers. Thus, Bert's internal representation is always as a list of real and imaginary part ow he represents appropriate trigonometry)so that he can then make a list of the real and imaginary part, which is
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 9.1.3 When manipulating complex numbers, I can take advantage of the fact that some things are easy to do in Cartesian (or real and imaginary) coordinates, and some things are easy to do in polar (or magnitude and angle) coordinates. For example, adding two complex numbers is most easily conceptualized in Cartesian coordinates, while multiplying two complex numbers is most easily conceptualized in polar coordinates. Addition is in fact just vector addition, so I use the selectors to get the parts of each complex number, add them together using standard addition, then glue the two parts together to make a new complex number. Here I will need to use a constructor that is making a complex number given Cartesian coordinates as input. For multiplication, I will use the polar selectors to get out the parts, so that I can just use normal multiplication on the magnitudes, and normal addition on the angles to get the new components. Here, I will use a constructor to make a new complex number that knows its inputs are provided in polar coordinates. Note once more how we are separating the use of a data abstraction from its implementation. I can write code that uses complex numbers, while assuming that someone else will eventually provide a specific implementation. And note the standard form of such procedures: we use selectors to get out the parts, apply more primitive operations to those parts, then reglue the parts back into a data abstraction. Slide 9.1.4 While it is convenient to separate data abstraction implementation from data abstraction use, ultimately we will have to provide a detailed implementation, that is, we will need to build the "guts" of this abstraction. Suppose we ask our friend Bert to provide an implementation for complex numbers... Slide 9.1.5 First, Bert will need a way of gluing things together. He decides, rather naturally, just to use lists to glue pieces together. He still has a choice, though, and being a rather "square " guy, Bert simply opts to use rectangular coordinates as his basis. That means that Bert's representation of a complex number is as a list of a real and imaginary part. Note what this means. If we hand Bert a real and imaginary part for a new complex number, he can simply glue them together using list as this directly meets his representation. On the other hand, if we hand Bert a magnitude and angle, he will need to convert these to real and imaginary equivalents (using the appropriate trigonometry) so that he can then make a list of the real and imaginary part, which is how he represents these numbers. Thus, Bert's internal representation is always as a list of real and imaginary parts
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 9.1.6 Bert's data structure To complete the representation, Bert just has to ensure that he (define( make-complex-from-rect rl im)(list ri im)) implements selectors that together with the constructors meet (define(make-complex-from-polar mg an) the contract for complex number abstractions For real and (st ( mg(cos an)) C mg(sin an)))) imag parts, this is easy, as we can just rely on the contract for lists For mag and angle, however, we must get out the real (define(imag cx)(cadr cx)) and imaginary parts(since these are the underlying representational pieces )using the appropriate selectors, then (define (angle cx)(atan o(real cx) compute the appropriate values from those parts This then complete Bert's implementation DOt sIcP Slide 9.1.7 Notice that bert made a design choice. He made a decision to Ernie s data structure represent complex numbers by a list of their real and imaginary(define(make-complex-from-rect rl im) (list (sqrt(+(square rl)(square im))) parts. Let's suppose at the same time we also asked Bert's friend (atan im rl))) Ernie, to create an implementation of complex numbers. Since (define( make-complex-from-polar mg an)(list mg an)) Ernie is Canadian he likes cold weather. and thus decides to implement complex numbers in polar form. Thus, his basic representation is a list of magnitude and angle, which means his constructor for polar form is just a list, but if he is given a real and imaginary part, he will first have to convert them to polar form then store those values as a list Ernies data structure Slide 9. 8 (define(make-complex-from-rect rl im) Completing Ernie's task is similar to Berts. For the magnitude (list(sqrt(+(square rl)(square im))) and angle selectors, we can just use the underlying list selectors (atan im rl))) to complete the contract. For selectors for Cartesian coordinates, ( define(make-complex-from-polar mg an)(list mg an)) I we will need to select out the underlying parts, convert using some trigonometry to the appropriate values, and then return 仰(m those values Notice that Ernie's implementation for complex numbers thus also meets the contract for such objects. All that has changed with respect to Bert's implementation is the choice of how to 6001 SICP glue basic components together Slide 9. 1.9 Whose number is it? So far this sounds fine. We have two different implementations of complex numbers, one in Cartesian coordinates and one in uppose we pick up the following object lar coordinates, but both seem to satisfy the contract for data abstraction. what's the big deal? I, suppose we find a complex number lying on the floor, such as the one shown
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 9.1.6 To complete the representation, Bert just has to ensure that he implements selectors that together with the constructors meet the contract for complex number abstractions. For real and imag parts, this is easy, as we can just rely on the contract for lists. For mag and angle, however, we must get out the real and imaginary parts (since these are the underlying representational pieces) using the appropriate selectors, then compute the appropriate values from those parts. This then completes Bert's implementation. Slide 9.1.7 Notice that Bert made a design choice. He made a decision to represent complex numbers by a list of their real and imaginary parts. Let's suppose at the same time we also asked Bert's friend, Ernie, to create an implementation of complex numbers. Since Ernie is Canadian, he likes cold weather, and thus decides to implement complex numbers in polar form. Thus, his basic representation is a list of magnitude and angle, which means his constructor for polar form is just a list, but if he is given a real and imaginary part, he will first have to convert them to polar form, then store those values as a list. Slide 9.1.8 Completing Ernie's task is similar to Bert's. For the magnitude and angle selectors, we can just use the underlying list selectors to complete the contract. For selectors for Cartesian coordinates, we will need to select out the underlying parts, convert using some trigonometry to the appropriate values, and then return those values. Notice that Ernie's implementation for complex numbers thus also meets the contract for such objects. All that has changed with respect to Bert's implementation is the choice of how to glue basic components together. Slide 9.1.9 So far this sounds fine. We have two different implementations of complex numbers, one in Cartesian coordinates and one in polar coordinates, but both seem to satisfy the contract for the data abstraction. What's the big deal? Well, suppose we find a complex number lying on the floor, such as the one shown
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 9.1.10 Whose number is it? then here is the key question. What actual number does this Suppose we pick up the following object object represent? This may sound odd, as after all, it is just a complex number. But suppose this is a complex nu 1+「 by Bert. Then what number would this represen( amber made What number does this represent 0O1 sIcP Slide 9.1.11 Whose number is it? In that case, we know that the first part of this list represents the real part of the number, and the second part of the list represents uppose we pick up the following object the imaginary part. Thus, in this case, this number would correspond to the vector or point shown on the diagram What number does this represent? 4 Whose number is it? Slide 9. 1.12 Suppose we pick up the following object On the other hand, if this were a complex number made by Ernie, we know that the first part of the list is the magnitude and is the angle of the vector. In that this number represents the red vector or point shown on the Thus, we have a problem. Depending on who made the complex number we found, we get a different answer to the question of What number does this represent? what number this is so how do we tell who made it? That is exactly the problem we are raising. Given what we have shown OI SICP "designer"complex numbers let's have the designer of eachate so far, we can't tell. Fortunately the solution is easy. Let's crea kind of complex number sign his work on the back. That means we will have each creator of complex numbers but a label on the object that either says this is a"Bert"or Cartesian number, or this is an"Ernie"or polar number
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 9.1.10 .. then here is the key question. What actual number does this object represent? This may sound odd, as after all, it is just a complex number. But suppose this is a complex number made by Bert. Then what number would this represent? Slide 9.1.11 In that case, we know that the first part of this list represents the real part of the number, and the second part of the list represents the imaginary part. Thus, in this case, this number would correspond to the vector or point shown on the diagram. Slide 9.1.12 On the other hand, if this were a complex number made by Ernie, we know that the first part of the list is the magnitude and the second part of the list is the angle of the vector. In that case, this number represents the red vector or point shown on the diagram. Thus, we have a problem. Depending on who made the complex number we found, we get a different answer to the question of what number this is. So how do we tell who made it? That is exactly the problem we are raising. Given what we have shown so far, we can't tell. Fortunately the solution is easy. Let's create "designer" complex numbers, let's have the designer of each kind of complex number sign his work on the back. That means we will have each creator of complex numbers but a label on the object that either says this is a "Bert" or Cartesian number, or this is an "Ernie" or polar number
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 9.1.13 How do we add a label to our complex numbers? Let's just glue Labeled complex numbers it onto the front We can change our constructor to have the ( define(make-complex-from-rect rl im) following behavior. Given two parts, we will just glue them list ' rect rl im)) together into a list. But if the parts represent real and imaginary ( define( make-complex-from-polar mg an) components, we will put a symbolic label at the front to tell us(define (tag obj)(car obi) this, while if the parts are magnitude and angle, we will still just( define(contents obi) (edr objy glue them together but we'll put a different label at the front to tell us this What else do I need? I'll want a selector to pull the labels off of hese new abstractions, as well as a selector to get out the actual contents of the abstraction Notice the use of cdr in this cased 6001 SCP to get the remaining list of elements from the representation Note that in this case we are not doing any work to convert representations. We just glue the parts together, and put label on it so we know what those parts mean Labeled complex numbers Slide 9.1.14 ( define(make-complex-from-rect rl im To make sure my contract holds, I'll need to adjust my selectors Here is where I am going to bury the work I just saved in (define(make-complex-from-polar mg an constructing numbers. i will have a single selector real that (define(tag obj)(car obj) works with numbers represented in either form. This selector (define(contents obj)(cdr obj)) will first rip the tag off of the number to see who made it. Notice how we use eq? to test equality of symbols, and how we use (cond ((eq?(tag z)rect)(car(contents z))) the selector tag to get out the tag, and how we use the quoted (eq?(tag 2)polan( e lf adr (contents z2):angle symbols to represent the things to check against the tag (else (error "unknown for object ))) If this is in fact a Cartesian number. we use contents to 03P get everything but the tag, then can use car to get the real part since that is where it is stored in this representation, just as Bert did it If this is a polar number, then we have to do the work to convert the underlying representation from polar form to the real part. In this case, contents will get the actual representation, and the car of that list we know is the magnitude of the vector. Similarly the cadr gets us the angle, and we can then do the trigonometry to convert to the real part Thus in this case, my constructor just glues pieces together, with an appropriate label. My selectors use the label to tell me how to interpret the pieces, and thus what additional work I may have to do to convert those pieces to the esired value Slide 9.1.15 Labeled complex numbers Note the key point here. It's not that I am dealing with complex (define(make-complex-from-rect rl im numbers,they simply provide the motivation. The key point is(list rect rd im) that now I can use any of the procedures I wrote to manipulate (define(make-complex-from-polar mg an complex numbers on any kind of complex number. Thus (list polar mg an)) independent of whether a complex number is actually glued (define(tag obj)(car ob)) together in Cartesian or polar form, the same procedure applies To make this happen, I use tags(or types)to tell the selectors (cond ((eq?(tag z)rect)(car(contents z))) which pieces to pull out, and what to do to convert the pieces to (eq?(tag z)polar)((car(contents z)'mag the right form. And these tags are exactly what support the idea (else (error "unknown form of object)))) of having different versions of the same abstraction be handled 6001联0 by the same procedures
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 9.1.13 How do we add a label to our complex numbers? Let's just glue it onto the front. We can change our constructor to have the following behavior. Given two parts, we will just glue them together into a list. But if the parts represent real and imaginary components, we will put a symbolic label at the front to tell us this, while if the parts are magnitude and angle, we will still just glue them together but we'll put a different label at the front to tell us this. What else do I need? I'll want a selector to pull the labels off of these new abstractions, as well as a selector to get out the actual contents of the abstraction. Notice the use of cdr in this case to get the remaining list of elements from the representation. Note that in this case we are not doing any work to convert representations. We just glue the parts together, and put a label on it so we know what those parts mean. Slide 9.1.14 To make sure my contract holds, I'll need to adjust my selectors. Here is where I am going to bury the work I just saved in constructing numbers. I will have a single selector real that works with numbers represented in either form. This selector will first rip the tag off of the number to see who made it. Notice how we use eq? to test equality of symbols, and how we use the selector tag to get out the tag, and how we use the quoted symbols to represent the things to check against the tag. If this is in fact a Cartesian number, we use contents to get everything but the tag, then can use car to get the real part, since that is where it is stored in this representation, just as Bert did it. If this is a polar number, then we have to do the work to convert the underlying representation from polar form to the real part. In this case, contents will get the actual representation, and the car of that list we know is the magnitude of the vector. Similarly the cadr gets us the angle, and we can then do the trigonometry to convert to the real part. Thus in this case, my constructor just glues pieces together, with an appropriate label. My selectors use the label to tell me how to interpret the pieces, and thus what additional work I may have to do to convert those pieces to the desired value. Slide 9.1.15 Note the key point here. It's not that I am dealing with complex numbers, they simply provide the motivation. The key point is that now I can use any of the procedures I wrote to manipulate complex numbers on any kind of complex number. Thus, independent of whether a complex number is actually glued together in Cartesian or polar form, the same procedure applies. To make this happen, I use tags (or types) to tell the selectors which pieces to pull out, and what to do to convert the pieces to the right form. And these tags are exactly what support the idea of having different versions of the same abstraction be handled by the same procedures