manipulation, and we wrote a rather stylized program to

implement a pile of calculus rule from the calculus book.

Here on the transparencies, we see a bunch of calculus rules

from such a book.

And, of course, what we did is sort of translate these rules

into the language of the computer.

But, of course, that's a sort of funny strategy.

Why should we have to translate these rules into the

language of the computer?

And what do I really mean by that?

These are--the program we wrote

yesterday was very stylized.

It was a conditional, a dispatch on the type of the

expression as observed by the rules.

What we see here are rules that say if the object being

the derivative is being taken of, if that expression is a

constant, then do one thing.

If it's a variable, do another thing.

If it's a product of a constant times a variable, do

something and so on.

There's sort of a dispatch there on a type.

Well, since it has such a stylized behavior and

structure, is there some other way of writing this program

that's more clear?

Well, what's a rule, first of all?

What are these rules?

Let's think about that.

Rules have parts.

If you look at these rules in detail, what you see, for

example, is the rule has a left-hand side and a

right-hand side.

Each of these rules has a left-hand side and the

right-hand side.

The left-hand side is somehow compared with the expression

you're trying to take the derivative of.

The right-hand side is the replacement for that

expression.

So all rules on this page are something like this.

I have patterns, and somehow, I have to produce, given a

pattern, a skeleton.

This is a rule.

A pattern is something that matches, and a skeleton is

something you substitute into in order to get a new

expression.

So what that means is that the pattern is matched against the

expression, which is the source expression.

And the result of the application of the rule is to

produce a new expression, which I'll call a target, by

instantiation of a skeleton.

That's called instantiation.

So that is the process by which

these rules are described.

What I'd like to do today is build a language and a means

of interpreting that language, a means of executing that

language, where that language allows us to directly express

these rules.

And what we're going to do is instead of bringing the rules

to the level of the computer by writing a program that is

those rules in the computer's language--

at the moment, in a Lisp--

we're going to bring the computer to the level of us by

writing a way by which the computer can understand rules

of this sort.

This is slightly emphasizing the idea that we had last time

that we're trying to make a solution to a class of

problems rather than a particular one.

The problem is if I want to write rules for a different

piece of mathematics, say, to simple algebraic

simplification or something like that, or manipulation of

trigonometric functions, I would have to write a

different program in using yesterday's method.

Whereas I would like to encapsulate all of the things

that are common to both of those programs, meaning the

idea of matching, instantiation, the control

structure, which turns out to be very complicated for such a

thing, I'd like to encapsulate that separately from the rules

themselves.

So let's look at, first of all, a representation.

I'd like to use the overhead here.

I'd like-- there it is.

I'd like to look at a representation of the rules of

calculus for derivatives in a sort of simple language that

I'm writing right here.

Now, I'm going to avoid--I'm going to avoid

worrying about syntax.

We can easily pretty this, and I'm not interested in making--

this is indeed ugly.

This doesn't look like the beautiful text set dx by dt or

something that I'd like to write,

but that's not essential.

That's sort of an accidental phenomenon.

Here, we're just worrying about the fact that the

structure of the rules is that there is a left-hand side

here, represents the thing I want to match against the

derivative expression.

This is the representation I'm going to say for the

derivative of a constant, which we will call c with

respect to the variable we will call v. And what we will

get on the right-hand side is 0.

So this represents a rule.

The next rule will be the derivative of a variable,

which we will call v with respect to the same variable

v, and we get a 1.

However, if we have the derivative of a variable

called u with respect to a different variables

v, we will get 0.

I just want you look at these rules a little bit and see how

they fit together.

For example, over here, we're going to have the derivative

of the sum of an expression called x1 and an

expression called x2.

These things that begin with question marks are called

pattern variables in the language that we're inventing,

and you see we're just making it up, so pattern variables

for matching.

And so in this--

here we have the derivative of the sum of the expression

which we will call x1.

And the expression we will call x2 with respect to the

variable we call v will be-- here is the right-hand side:

the sum of the derivative of that expression x1 with

respect to v-- the right-hand side is the skeleton--

and the derivative of x2 with respect to v. Colons here will

stand for substitution objects.

They're--we'll call them skeleton evaluations.

So let me put up here on the blackboard for a second some

syntax so we'll know what's going on

for this rule language.

First of all, we're going to have to worry about the

pattern matching.

We're going to have things like a symbol like foo matches

exactly itself.

The expression f of a and b will be used to match any list

whose first element is f, whose second element is a, and

whose third element is b.

Also, another thing we might have in a pattern is that--

a question mark with some variable like x.

And what that means, it says matches anything, which we

will call x.

Question mark c x will match only constants.

So this is something which matches a constant colon x.

And question mark v x will match a variable,

which we call x.

This is sort of the language we're making up now.

If I match two things against each other, then they are

compared element by element.

But elements in the pattern may contain these syntactic

variables, pattern variables, which will be used to match

arbitrary objects.

And we'll get that object as the value in the name x here,

for example.

Now, when we make skeletons for instantiation.

Well, then we have things like this.

foo, a symbol, instantiates to itself.

Something which is a list like f of a and b,

instantiates to--

well, f instantiates to a 3-list, a list of three

elements, okay, which are the results of instantiating each

of f, a, and b.

And x well--we instantiate to the value of x as in the

matched pattern.

So going back to the overhead here, we see--we see that all

of those kinds of objects, we see here a pattern variable

which matches a constant, a pattern variable which matches

a variable, a pattern variable which will match anything.

And if we have two instances of the same name, like this is

the derivative of the expression which is a variable

only whose name will be v with respect to some arbitrary

expression which we will call v, since this v appears twice,

we're going to want that to mean they have to be the same.

The only consistent match is that those are the same.

So here, we're making up a language.

And in fact, that's a very nice thing to be doing.

It's so much fun to make up a language.

And you do this all the time.

And the really most powerful design things you ever do are

sort of making up a language to solve problems like this.

Now, here we go back here and look at some of these rules.

Well, there's a whole set of them.

I mean, there's one for addition and one for

multiplication, just like we had before.

The derivative of the product of x1 and x2 with respect to v

is the sum of the product of x1 and the derivative x2 with

respect to v and the product of the

derivative of x1 and x2.

And here we have exponentiation.

And, of course, we run off the end down here.

We get as many as we like.

But the whole thing over here, I'm giving this--this list of

rules the name "derivative rules."

What would we do with such a thing once we have it?

Well, one of the nicest ideas, first of all, is I'm going to

write for you, and we're going to play with it all day.

What I'm going to write for you is a program called

simplifier, the general-purpose simplifier.

And we're going to say something like define dsimp to

be a simplifier of the derivative rules.

And what simplifier is going to do is, given a set of

rules, it will produce for me a procedure which will

simplify expressions containing the things that are

referred to by these rules.

So here will be a procedure constructed for your purposes

to simplify things with derivatives in them such that,

after that, if we're typing at some list system, and we get a

prompt, and we say dsimp, for example, of the derivative of

the sum of x and y with respect to x--

note the quote here because I'm talking about the

expression which is the derivative--

then I will get back as a result plus 1 0.

Because the derivative of x plus y is the derivative of x

plus derivative y.

The derivative of x with respect to x is 1.

The derivative of y with respect to x is 0.

It's not what we're going to get.

I haven't put any simplification at that level--

algebraic simplification--

yet.

Of course, once we have such a thing, then we can--then we

can look at other rules.

So, for example, we can, if we go to the slide, OK?

Here, for example, are other rules that we might have,

algebraic manipulation rules, ones that would be used for

simplifying algebraic expressions.

For example, just looking at some of these, the left-hand

side says any operator applied to a constant e1 and a

constant e2 is the result of evaluating that operator on

the constants e1 and e2.

Or an operator, applied to e1, any expression e1 and a

constant e2, is going to move the constant forward.

So that'll turn into the operator with

e2 followed by e1.

Why I did that, I don't know.

It wouldn't work if I had division, for example.

So there's a bug in the rules, if you like.

So the sum of 0 and e is e.

The product of 1 and any expression e is e.

The product of 0 and any expression e is 0.

Just looking at some more of these rules, we could have

arbitrarily complicated ones.

We could have things like the product of the constant e1 and

any constant e2 with e3 is the result of multiplying the

result of--multiplying now the constants e1 and e2 together

and putting e3 there.

So it says combine the constants that I had, which