Placeholder Image

字幕列表 影片播放

  • [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