Local Disk6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. All rights reserved6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 2.1 Slide 2.1.1 In the last lecture, we began looking at the programming language, Scheme, with the intent of learning how that language would provide a basis for describing procedures and processes, and thus for understanding computational metaphors for controlling complex processes. In this lecture, we look at how to create procedural abstractions in our language, and how to use those abstractions to describe and capture computational processes. Slide 2.1.2 Well -- we've got primitives (numbers and built in procedures); we've got means of combination (ways of creating complex expressions); and we've got our first means of abstraction (a way of giving a name to something). But we are still stuck just writing out arithmetic expressions, as the only procedures we have are the built in ones. We need a way to capture our own processes in our own procedures. So we need another kind of abstraction -- we need a way of capturing particular processes in our own procedures, and that's what we turn to next. Slide 2.1.3 In Scheme, we have a particular expression for capturing a procedure. It's called a lambda expression. It has the form shown, an open parenthesis, the keyword lambda, followed by some number of symbols enclosed within parentheses, followed by one or more legal expressions, followed by a close parenthesis.6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 2.1.4 The keyword lambda identifies this expression as a particular special form. The set of symbols immediately following the lambda are called the formal parameters of the lambda, in this case, there is just one parameter, x. Slide 2.1.5 The subsequent expression we refer to as the body of the procedure. This is the particular pattern we are going to use to capture a process. Slide 2.1.6 The way to think about this lambda expression is that it is going to capture a common pattern of computation in a procedure -- it will actually build a procedure for us. The way to read the expression is: To process ... Slide 2.1.7 ... something ...6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 2.1.8 ... multiply it by itself, and return that value. Slide 2.1.9 So in fact this particular lambda expression captures the process of "squaring". It says, if you give me a value for x I will return the value of multiplying that value by itself. In a second we will see how this happens. Notice that lambda expressions must be special forms. The normal rules for evaluating a combination do not apply here. Instead, the value returned by evaluating a lambda expression is the actual procedure that it captures. Contained within that procedure will be a set of formal parameters, and a body that captures the common pattern of the process, as a function of those formal parameters. Slide 2.1.10 Now, where can we use such a procedure? Basically anywhere in our earlier expressions that we could use a built-in procedure, which for now means as the first element in a combination. For example, here is a compound expression, with two subexpressions. What is the value or meaning associated with it? The value of the first subexpression we just saw was a procedure. The value of the second subexpression is just the number 5. Now we have something similar to our earlier cases, a procedure applied to a value. The only difference is that here we have a procedure we built, rather than a pre-existing one. We need to specify how such a procedure is applied to a set of arguments.6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 2.1.11 So here is a summary of our earlier rules for evaluating expressions. The only change is to amplify what it means to apply a procedure to a set of arguments. When the procedure was a built-in arithmetic operator, we just did the obvious thing. Now if the procedure is something built by evaluating a lambda expression, we have a new rule. We take the body of the procedure, substitute the value of the argument in place of the corresponding formal parameter, and then use the same rules to evaluate the resulting expression. Slide 2.1.12 So let's go back to our example. Our rule says to replace the value of the second expression, 5, everywhere in the body that we see the formal parameter, x. This then reduces the application of the lambda expression to a simpler expression ... Slide 2.1.13 This reduces the application of a procedure to this simpler expression, and we can apply our rules again. The symbol * is just a name for the built-in multiplication operation, and 5 is just self-evaluating, so this all reduces to ... Slide 2.1.14 ... 25. Thus we see that our rules now cover the evaluation of compound expressions that include the application of procedures created by lambda expressions. In particular, the rules tell us to substitute into the body of a procedure for the formal parameters, reducing to a new expression, and then apply the same set of rules all over again, until we reach a final answer.6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 2.1.15 Thus, lambda gives us the ability to capture procedure abstractions -- patterns of computation in a single procedure. But we don't want to have to write out lambda expressions everywhere we need to use this procedure. Instead, we can combine this procedural abstraction with our naming abstraction -- that is, we can use a define expression to give a name to a procedure. In this case, the name square will be paired with the value of the lambda expression, or quite literally with the actual procedure created by evaluating that lambda. Then we can use the name square wherever we want the procedure, since its value is the actual procedure. If you follow the rules of evaluation for the last expression, you will see that we get a procedure applied to a number, and the substitution of the argument into the body of the procedure reduces to a simpler expression, just as we saw earlier. 6.001 Notes: Section 2.2 Slide 2.2.1 The second kind
View Full Document
Unlocking...