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 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 © 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 © 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
View Full Document
Unlocking...