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.

Define how to get the product of two rational numbers,

call it *RAT.

Takes in two of these clouds, x and y, it returns

a rational number, make-RAT, whose numerator

is the product of the numerators-- numerator of x

times the numerator of y.

And the denominator of the thing it's going to return

is the product of the denominators.

Well, except that I haven't told you what these clouds are,

that's all there is to it.

See, what did I do?

I assumed by wishful thinking that I

had a new kind of data object.

And in particular, I assumed I had ways

of creating these data objects.

Make-RAT creates one of these things.

This is called a constructor.

All right, I have a thing that constructs such data objects.

And then I assume I have things that, having made these things,

I have ways of getting the parts out.

Those are called selectors.

And so formally, what I said is I assumed

I had procedures that are constructors

and selectors for these data objects,

and then I went off and used them.

That's no different in kind from saying

I assume I have a procedure good-enough,

and I go use it to implement square root.

OK, well before we go on, let's ask

the question of why do we want to do this in the first place?

See, why do we want a procedure like +RAT that takes in two

rational numbers and returns a rational number?

See, another way to think about this is, well,

here's this formula.

And I've also got to implement something

that adds rational numbers.

One other way to think about is, well, there's this thing,

and I type in four numbers, an n1, and a d1,

and an n2, and a d2.

And it sets some registers in the machine

to this numerator and this denominator.

So I might say, well, why don't I

just add rational numbers by I type in four

numbers, numerators and denominators,

and get out two numbers, which is

a numerator and a denominator.

Why are we worrying about building things

like this anyway?

Well, the answer is, suppose you want

to think about expressing something like this,

suppose I'd like to express the idea of taking

two rational numbers, x plus y, say,

and multiplying that by the sum of two other rational numbers.

Well, the way I do it, having things like +RAT and *RAT,

is I'd say, oh yeah, what that is is just the product.

That's *RAT of the sum of x and y and the sum of s and t.

So except for syntax, I get an expression

that looks like the way I want to think

about it mathematically.

I want to say there are two numbers.

There's a thing which is the sum of them,

and there's a thing which is the sum of these two.

That's this and this.

And then I multiply them.

So I get an expression that matches this expression.

If I did the other thing, if I said,

well, the way I want to think about this

is I type into my machine four numbers, which

are the numerators and the denominators of x and y,

and then four more numbers, which are the numerators