字幕列表 影片播放 列印英文字幕 [MUSIC-- "JESU, JOY OF MAN'S DESIRING" BY JOHANN SEBASTIAN BACH] PROFESSOR: So far in this course we've been talking a lot about data abstraction. And remember the idea is that we build systems that have these horizontal barriers in them, these abstraction barriers that separate use, the way you might use some data object, from the way you might represent it. Or another way to think of that is up here you have the boss who's going to be using some sort of data object. And down here is George who's implemented it. Now this notion of separating use from representation so you can think about these two problems separately is a very, very powerful programming methodology, data abstraction. On the other hand, it's not really sufficient for really complex systems. And the problem with this is George. Or actually, the problem is that there are a lot of Georges. Let's be concrete. Let's suppose there is George, and there's also Martha. OK, now George and Martha are both working on this system, both designing representations, and absolutely are incompatible. They wouldn't cooperate on a representation under any circumstances. And the problem is you would like to have some system where both George and Martha are designing representations, and yet, if you're above this abstraction barrier you don't want to have to worry about that, whether something is done by George or by Martha. And you don't want George and Martha to interfere with each other. Somehow in designing a system, you not only want these horizontal barriers, but you also want some kind of vertical barrier to keep George and Martha separate. Let me be a little bit more concrete. Imagine that you're thinking about personnel records for a large company with a lot of loosely linked divisions that don't cooperate very well either. And imagine even that this company is formed by merging a whole bunch of companies that already have their personnel record system set up. And imagine that once these divisions are all linked in some kind of very sophisticated satellite network, and all these databases are put together. And what you'd like to do is, from any place in the company, to be able to say things like, oh, what's the name in a personnel record? Or, what's the job description in a personnel record? And not have to worry about the fact that each division obviously is going to have completely separate conventions for how you might implement these records. From this point you don't want to know about that. Well how could you possibly do that? One way, of course, is to send down an edict from somewhere that everybody has to change their format to some fixed compatible thing. That's what people often try, and of course it never works. Another thing that you might want to do is somehow arrange it so you can have these vertical barriers. So that when you ask for the name of a personnel record, somehow, whatever format it happens to be, name will figure out how to do the right thing. We want name to be, so-called, a generic operator. Generic operator means what it sort of precisely does depends on the kind of data that it's looking at. More than that, you'd like to design the system so that the next time a new division comes into the company they don't have to make any big changes in what they're already doing to link into this system, and the rest of the company doesn't have to make any big changes to admit their stuff to the system. So that's the problem you should be thinking about. Like it's sort of just your work. You want to be able to include new things by making minimal changes. OK, well that's the problem that we'll be talking about today. And you should have this sort of distributed personnel record system in your mind. But actually the one I'll be talking about is a problem that's a little bit more self-contained than that. that'll bring up the issues, I think, more clearly. That's the problem of doing a system that does arithmetic on complex numbers. So let's take a look here. Just as a little review, there are things called complex numbers. Complex number you can think of as a point in the plane, or z. And you can represent a point either by its real-part and its imaginary-part. So if this is z and its real-part is this much, and its imaginary-part is that much, and you write z equals x plus iy. Or another way to represent a complex number is by saying, what's the distance from the origin, and what's the angle? So that represents a complex number as its radius times an angle. This one's called-- the original one's called rectangular form, rectangular representation, real- and imaginary-part, or polar representation. Magnitude and angle-- and if you know the real- and imaginary-part, you can figure out the magnitude and angle. If you know x and y, you can get r by this formula. Square root of sum of the squares, and you can get the angle as an arctangent. Or conversely, if you knew r and A you could figure out x and y. x is r times the cosine of A, and y is r times the sine of A. All right, so there's these two. They're complex numbers. You can think of them either in polar form or rectangular form. What we would like to do is make a system that does arithmetic on complex numbers. In other words, what we'd like-- just like the rational number example-- is to have some operations plus c, which is going to take two complex numbers and add them, subtract them, and multiply them, and divide them. OK, well there's little bit of mathematics behind it. What are the actual formulas for manipulating such things? And it's sort of not important where they come from, but just as an implementer let's see-- if you want to add two complex numbers it's pretty easy to get its real-part and its imaginary-part. The real-part of the sum of two complex numbers, the real-part of the z1 plus z2 is the real-part of z1 plus the real-part of z2. And the imaginary-part of z1 plus z2 is the imaginary part of z1 plus the imaginary part of z2. So it's pretty easy to add complex numbers. You just add the corresponding parts and make a new complex number with those parts. If you want to multiply them, it's kind of nice to do it in polar form. Because if you have two complex numbers, the magnitude of their product is here, the product of the magnitudes. And the angle of the product is the sum of the angles. So that's sort of mathematics that allows you to do arithmetic on complex numbers. Let's actually think about the implementation. Well we do it just like rational numbers. We come down, we assume we have some constructors and selectors. What would we like? Well let's assume that we make a data object cloud, which is a complex number that has some stuff in it, and that we can get out from a complex number the real-part, or the imaginary-part, or the magnitude, or the angle. We want some ways of making complex numbers-- not only selectors, but constructors. So we'll assume we have a thing called make-rectangular. What make-rectangular is going to do is take a real-part and an imaginary-part and construct a complex number with those parts. Similarly, we can have make-polar which will take a magnitude and an angle, and construct a complex number which has that magnitude and angle. So here's a system. We'll have two constructors and four selectors. And now, just like before, in terms of that abstract data we'll go ahead and implement our complex number operations. And here you can see translated into Lisp code just the arithmetic formulas I put down before. If I want to add two complex numbers I will make a complex number out of its real- and imaginary-parts. The real part of the complex number I'm going to make is the sum of the real-parts. The imaginary part of the complex number I'm going to make is the sum of the imaginary-parts. I put those together, make a complex number. That's how I implement complex number addition. Subtraction is essentially the same. All I do is subtract the parts rather than add them. To multiply two complex numbers, I use the other formula. I'll make a complex number out of a magnitude and angle. The magnitude is going to be the product of the magnitudes of the two complex numbers I'm multiplying. And the angle is going to be the sum of the angles of the two complex numbers I'm multiplying. So there's multiplication. And then division, division is almost the same. Here I divide the magnitudes and subtract the angles. Now I've implemented the operations. And what do we do? We call on George. We've done the use, let's worry about the representation. We'll call on George and say to George, go ahead and build us a complex number representation. Well that's fine. George can say, we'll implement a complex number simply as a pair that has the real-part and the imaginary-part. So if I want to make a complex number with a certain real-part and an imaginary-part, I'll just use cons to form a pair, and that will-- that's George's representation of a complex number. So if I want to get out the real-part of something, I just extract the car, the first part. If I want to get the imaginary-part, I extract the cdr. How do I deal with the magnitude and angle? Well if I want to extract the magnitude of one of these things, I get the square root of the sum of the square of the car plus the square of the cdr. If I want to get the angle, I compute the arctangent of the cdr in the car. This is a list procedure for computing arctangent. And if somebody hands me a magnitude and an angle and says, make me a complex number, well I compute the real-part and the imaginary-part, or our cosine of a and our sine of a, and stick them together into a pair. OK so we're done. In fact, what I just did, conceptually, is absolutely no different from the rational number representation that we looked at last time. It's the same sort of idea. You implement the operators, you pick a representation. Nothing different. Now let's worry about Martha. See, Martha has a different idea. She doesn't want to represent a complex number as a pair of a real-part and an imaginary-part. What she would like to do is represent a complex number as a pair of a magnitude and an angle. So if instead of calling up George we ask Martha to design our representation, we get something like this. We get make-polar. Sure, if I give you a magnitude and an angle we're just going to form a pair that has magnitude and angle. If you want to extract the magnitude, that's easy. You just pull out the car or the pair. If you want to extract the angle, sure, that's easy. You just pull out the cdr. If you want to look for real-parts and imaginary-parts, well then you have to do some work. If you want the real-part, you have to get r cosine a. In other words, r, the car of the pair, times the cosine of the cdr of the pair. So this is r times the cosine of a, and that's the real-part. If you want to get the imaginary-part, it's r times the sine of a. And if I hand you a real-part and an imaginary-part and say, make me a complex number with that real-part and imaginary-part, well I figure out what the magnitude and angle should be. The magnitude's