Placeholder Image

Subtitles section Play video

  • [MUSIC PLAYING]

  • PROFESSOR: Well, so far in this course

  • we've been talking about procedures,

  • and then just to remind you of this framework

  • that we introduced for talking about languages,

  • we talked about the primitive things that

  • are built into the system.

  • We mentioned some means of combination

  • by which you take the primitive things

  • and you make more complicated things.

  • And then we talked about the means of abstraction,

  • how you can take those complicated things

  • and name them so you can use them as simple building blocks.

  • And then last time you saw we went even beyond that.

  • We saw that by using higher order procedures,

  • you can actually express general methods for computing things.

  • Like the method of doing something

  • by fixed points, or Newton's method, and so

  • the incredible expressive power you

  • can get just by combining these means of abstraction.

  • And the crucial idea in all of this

  • is the one that we build a layered system.

  • So for instance, if we're writing the square root

  • procedure, somewhere the square root procedure

  • uses a procedure called good-enough,

  • and between those there is some sort of abstraction boundary.

  • It's almost as if we go out and in writing square root,

  • we go and make a contract with George,

  • and tell George that his job is to write good-enough,

  • and so long as good-enough works,

  • we don't care what it does.

  • We don't care exactly how it's implemented.

  • There are levels of detail here that are

  • George's concern and not ours.

  • So for instance, George might use an absolute value procedure

  • that's written by Harry, and we don't much care about that

  • or even know that, maybe, Harry exists.

  • So the crucial idea is that when we're building things,

  • we divorce the task of building things

  • from the task of implementing the parts.

  • And in a large system, of course,

  • we have abstraction barriers like this at lots, and lots,

  • and lots of levels.

  • And that's the idea that we've been using so far over and over

  • in implementing procedures.

  • Well, now what we're going to do is look

  • at the same issues for data.

  • We're going to see that the system has primitive data.

  • In fact, we've already seen that.

  • We've talked about numbers as primitive data.

  • And then we're going to see their means of combination

  • for data.

  • There's glue that allows you to put primitive data together

  • to make more complicated, kind of compound data.

  • And then we're going to see a methodology for abstraction

  • that's a very good thing to use when you start building up data

  • in terms of simpler data.

  • And again, the key idea is that you're

  • going to build the system in layers

  • and set up abstraction barriers that

  • isolate the details at the lower layers

  • from the thing that's going on at the upper layers.

  • The details at the lower layers, the ideas, they won't matter.

  • They're going to be George's concern

  • because he signed this contract with us for how

  • the stuff that he implements behaves,

  • and how he implements the thing is his problem.

  • All right, well let's look at an example.

  • And the example I'm going to talk about

  • is a system that does arithmetic on rational numbers.

  • And what I have in mind is that we should have something

  • in the computer that allows us to ask it, like,

  • what's the sum of 1/2 and 1/4, and somehow the system

  • should say, yeah, that's 3/4.

  • Or we should be able to say what's 3/4 times 2/3,

  • and the system should be able to say, yeah, that's 1/2.

  • Right?

  • And you know what I have in mind.

  • And you also know how to do this from, I don't know,

  • fifth grade or sixth grade.

  • There are these formulas that say

  • if I have some fraction which is a numerator over a denominator,

  • and I want to add that to some other fraction which

  • is another numerator over another denominator,

  • then the answer is the numerator of the first times

  • the denominator of the second, plus the numerator

  • of the second times the denominator of the first.

  • That's the numerator of the answer,

  • and the denominator is the product

  • of the two denominators.

  • Right?

  • So there's something from fifth or sixth grade fraction

  • arithmetic.

  • And then similarly, if I want to multiply two things,

  • n1 over d1 multiplied by n2 over d2

  • is the product of the numerators over the product

  • of the denominators.

  • So it's no problem at all, but it's absolutely no problem

  • to think about what computation you

  • want to make in adding and multiplying these fractions.

  • But as soon as we go to implement it,

  • we run up across something.

  • We don't have what a rational number is.

  • So we said that the system gives us individual numbers,

  • so we can have 5 and 3, but somehow we

  • don't have a way of saying there's

  • a thing that has both a 3 and a 4 in it, or both a 2 and a 3.

  • It's almost as if we'd like to imagine that somehow there

  • are these clouds, and a cloud somehow

  • has both a numerator and a denominator in it,

  • and that's what we'd like to work in terms of.

  • Well, how are we going to solve that problem?

  • We're going to solve that problem

  • by using this incredibly powerful design

  • strategy that you've already seen us use over and over.

  • And that's the strategy of wishful thinking.

  • Just like before when we didn't have a procedure, we said,

  • well, let's imagine that that procedure already exists.

  • We'll say, well, let's imagine that we have these clouds.

  • Now more precisely what I mean is

  • let's imagine that we have three procedures,

  • one called make-RAT.

  • make-RAT is going to take as arguments two numbers,

  • so I'll call them numerator and denominator,

  • and it'll return for us a cloud-- one of these clouds.

  • I don't really know what a cloud is.

  • It's whatever make-RAT returns, that's its business.

  • And then we're going to say, suppose

  • we've got one of these clouds, we have a procedure called

  • numer, which takes in a cloud that has an n and a d in it,

  • whatever a cloud is, and I don't know what it is, and returns

  • for us the numerator part.

  • And then we'll assume we have a procedure denom,

  • which again takes in a cloud, whatever

  • a cloud is, and returns for us the denominator [? required. ?]

  • This is just like before, when if we're

  • building a square root, we assume

  • that we have good enough.

  • Right?

  • And what we'll say is, we'll go find George,

  • and we'll say to George, well, it's your business

  • to make us these procedures.

  • And how you choose to implement these clouds,

  • that's your problem.

  • We don't want to know.

  • Well, having pushed this task off onto George,

  • then it's pretty easy to do the other part.

  • Once we've got the clouds, it's pretty easy

  • to write the thing that does say addition of rational numbers.

  • You can just say define, well, let's say +RAT.

  • Define +RAT, which will take in two rational numbers, x and y.

  • x and y are each these clouds.

  • And what does it do?

  • Well, it's going to return for us a rational number.

  • What rational number is it?

  • Well, we've got the formulas there.

  • The numerator of it is the sum of the product of the numerator

  • of x and the denominator of y.

  • It's one thing in the sum.

  • And the other thing in the numerator

  • is the product of the numerator of y and the denominator of x.

  • The star, close the plus.

  • Right, that's the first argument to make-RAT,

  • which is the numerator of the thing I'm constructing.

  • And then the rest of the thing goes

  • into make-RAT is the denominator of the answer, which

  • is the product of the denominator of x

  • and the denominator of y.

  • Like that.

  • OK?

  • So there is the analog of doing rational number addition.

  • And it's no problem at all, assuming

  • that we have these clouds.