PROFESSOR: Well, Hal just told us how you build robust

systems. The key idea was--

I'm sure that many of you don't really assimilate that

yet-- but the key idea is that in order to make a system

that's robust, it has to be insensitive to small changes,

that is, a small change in the problem should lead to only a

small change in the solution.

There ought to be a continuity.

The space of solutions ought to be continuous in this space

of problems.

The way he was explaining how to do that was instead of

solving a particular problem at every level of

decomposition of the problem at the subproblems, where you

solve the class of problems, which are a neighborhood of

the particular problem that you're trying to solve.

The way you do that is by producing a language at that

level of detail in which the solutions to that class of

problems is representable in that language.

Therefore when you makes more changes to the problem you're

trying to solve, you generally have to make only small local

changes to the solution you've constructed, because at the

level of detail you're working, there's a language

where you can express the various solutions to alternate

problems of the same type.

Well that's the beginning of a very important idea, the most

important perhaps idea that makes computer science more

powerful than most of the other kinds of engineering

disciplines we know about.

What we've seen so far is sort of how to use

embedding of languages.

And, of course, the power of embedding languages partly

comes from procedures like this one that

I showed you yesterday.

What you see here is the derivative program that we

described yesterday.

It's a procedure that takes a procedure as an argument and

returns a procedure as a value.

And using such things is very nice.

You can make things like push combinators and all that sort

of wonderful thing that you saw last time.

However, now I'm going to really muddy the waters.

See this confuses the issue of what's the procedure and what

is data, but not very badly.

What we really want to do is confuse it very badly.

And the best way to do that is to get involved with the

manipulation of the algebraic expressions that the

procedures themselves are expressed in.

So at this point, I want to talk about instead of things

like on this slide, the derivative procedure being a

thing that manipulates a procedure--

this is a numerical method you see here.

And what you're seeing is a representation of the

numerical approximation to the derivative.

That's what's here.

In fact what I'd like to talk about is instead things that

look like this.

And what we have here are rules from a calculus book.

These are rules for finding the derivatives of the

expressions that one might write in

some algebraic language.

It says things like a derivative of a constant is 0.

The derivative of the valuable with respect to which you are

taking the derivative is 1.

The derivative of a constant times the function is the

constant times the derivative of the function,

and things like that.

These are exact expressions.

These are not numerical approximations.

Can we make programs?

And, in fact, it's very easy to make programs that

manipulate these expressions.

Well let's see.

Let's look at these rules in some detail.

You all have seen these rules in your elementary calculus

class at one time or another.

And you know from calculus that it's easy to produce

derivatives of arbitrary expressions.

You also know from your elementary calculus that it's

hard to produce integrals.

Yet integrals and derivatives are opposites of each other.

They're inverse operations.

And they have the same rules.

What is special about these rules that makes it possible

for one to produce derivatives easily and

integrals why it's so hard?

Let's think about that very simply.

Look at these rules.

Every one of these rules, when used in the direction for

taking derivatives, which is in the direction of this

arrow, the left side is matched against your

expression, and the right side is the thing which is the

derivative of that expression.

The arrow is going that way.

In each of these rules, the expressions on the right-hand

side of the rule that are contained within derivatives

are subexpressions, are proper subexpressions, of the

expression on the left-hand side.

So here we see the derivative of the sum, with is the

expression on the left-hand side is the sum of the

derivatives of the pieces.

So the rule of moving to the right are reduction rules.

The problem becomes easier.

I turn a big complicated problem it's lots of smaller

problems and then combine the results, a perfect place for

recursion to work.

If I'm going in the other direction like this, if I'm

trying to produce integrals, well there are several

problems you see here.

First of all, if I try to integrate an expression like a

sum, more than one rule matches.

Here's one that matches.

Here's one that matches.

I don't know which one to take.

And they may be different.

I may get to explore different things.

Also, the expressions become larger in that direction.

And when the expressions become larger, then there's no

guarantee that any particular path I choose will terminate,

because we will only terminate by accidental cancellation.

So that's why integrals are complicated

searches and hard to do.

Right now I don't want to do anything as hard as that.

Let's work on derivatives for a while.

Well, these roles are ones you know for

the most part hopefully.

So let's see if we can write a program which is these rules.

And that should be very easy.

Just write the program.

See, because while I showed you is that it's a reduction

rule, it's something appropriate for a recursion.

And, of course, what we have for each of these rules is we

have a case in some case analysis.

So I'm just going to write this program down.

Now, of course, I'm going to be saying something you have

to believe.

Right?

What you have to believe is I can represent these algebraic

expressions, that I can grab their parts, that I can put

them together.

We've invented list structures so that you can do that.

But you don't want to worry about that now.

Right now I'm going to write the program that encapsulates

these rules independent of the representation of the

algebraic expressions.

You have a derivative of an expression with

respect to a variable.

This is a different thing than the

derivative of the function.

That's what we saw last time, that numerical approximation.

It's something you can't open up a function.

It's just the answers.

The derivative of an expression is

the way it's written.

And therefore it's a syntactic phenomenon.

And so a lot of what we're going to be doing today is

worrying about syntax, syntax of expressions

and things like that.

Well, there's a case analysis.

Anytime we do anything complicated thereby a

recursion, we presumably need a case analysis.

It's the essential way to begin.

And that's usually a conditional

of some large kind.

Well, what are their possibilities?

the first rule that you saw is this something a constant?

And what I'm asking is, is the expression a constant with

respect to the variable given?

If so, the result is 0, because the derivative

represents the rate of change of something.

If, however, the expression that I'm taking the derivative

of is the variable I'm varying, then this is the same

variable, the expression var, then the rate of change of the

expression with respect to the variable is 1.

It's the same 1.

Well now there are a couple of other possibilities.

It could, for example, be a sum.

Well, I don't know how I'm going to express sums yet.

Actually I do.

But I haven't told you yet.

But is it a sum?

I'm imagining that there's some way of telling.

I'm doing a dispatch on the type of the expression here,

absolutely essential in building languages.

Languages are made out of different expressions.

And soon we're going to see that in our more powerful

methods of building languages on languages.

Is an expression a sum?

If it's a sum, well, we know the rule for derivative of the

sum is the sum of the derivatives of the parts.

One of them is called the addend and the

other is the augend.

But I don't have enough space on the blackboard

to such long names.

So I'll call them A1 and A2.

I want to make a sum.

Do you remember which is the sum for end or the menu end?

Or was it the dividend and the divisor or

something like that?

Make sum of the derivative of the A1, I'll call it.

It's the addend of the expression with respect to the

variable, and the derivative of the A2 of the expression,

because the two arguments, the addition with

respect to the variable.

And another rule that we know is product rule, which is, if

the expression is a product.

By the way, it's a good idea when you're defining things,

when you're defining predicates, to give them a

name that ends in a question mark.

This question mark doesn't mean anything.

It's for us as an agreement.

It's a conventional interface between humans so you can read

my programs more easily.

So I want you to, when you write programs, if you define

a predicate procedure, that's something that rings true of

false, it should have a name which ends in question mark.

The list doesn't care.

I care.

I want to make a sum.

Because the derivative of a product is the sum of the

first times the derivative of the second plus the second

times the derivative of the first. Make a sum of two

things, a product of, well, I'm going to say the M1 of the

expression, and the derivative of the M2 of the expression

with respect to the variable, and the product of the

derivative of M1, the multiplier of the expression,

with respect to the variable.

It's the product of that and the multiplicand, M2, of the

expression.

Make that product.

Make the sum.

Close that case.

And, of course, I could add as many cases as I like here for

a complete set of rules you might find in a calculus book.

So this is what it takes to encapsulate those rules.

And you see, you have to realize there's a lot of

wishful thinking here.

I haven't told you anything about how I'm going to make

these representations.

Now, once I've decided that this is my set of rules, I

think it's time to play with the representation.

Let's attack that/

Well, first of all, I'm going to play a pun.

It's an important pun.

It's a key to a sort of powerful idea.

If I want to represent sums, and products, and differences,

and quotients, and things like that, why not use the same

language as I'm writing my program in?

I write my program in algebraic expressions that

look like the sum of the product on a and the product

of x and x, and things like that.

And the product of b and x and c, whatever, make that a sum

of the product.

Right now I don't want to have procedures with unknown

numbers of arguments, a product of b and x and c.