Subtitles section Play video Print subtitles [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. And of course, we can do multiplication in the same way.