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.