Subtitles section Play video Print subtitles [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.