Placeholder Image

Subtitles section Play video

  • [MUSIC PLAYING]

  • 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.