6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 2.1 Slide 2.l.1 In the last lecture, we began looking at the programming This lecture nguage Scheme. with the intent of learning how that anguage would provide a basis for describing procedures and Adding procedures and procedural abstractions processes, and thus for understanding computational metaphors Using procedures to capture processes 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 Language elements -abstractions Well--we' ve got primitives (numbers and built in procedures) weve got means of combination(ways of creating comple 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 need another kind of abstraction--we need a way of capturing particular processes n our own procedures, and that's what we turn to next 1m003 6 001 SICP 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 Language elements--abstractions shown, an open parenthesis, the keyword lambda, followed by Need to capture ways of doing things-use some number of symbols enclosed within parentheses, followed by one or more legal expressions, followed by a close (lambda(x)(xx))
6.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 o 2004 by Massachusetts Institute of Technology Slide 2. 1. 4 The keyword lambda identifies this expression as a particular Language elements -abstractions special form. The set of symbols immediately following the lambda are called the formal parameters of the lambda, in this Need to capture ways of doing things-use case, there is just one parameter, x r parameters mbda(x)( xx)) 1m003 6 001 SICP 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 Language elements--abstractions capture a process Need to capture ways of doing things-use procedures r parameters lambda(x)(x x)h 4103 Slide 2.1.6 Language elements --abstractions The way to think about this lambda expression is that it is going to capture a common pattern of computation in a procedure--it Need to capture ways of doing th will actually build a procedure for parameters The way to read the expression is: To process (lambda(x)( xx)h- 410a3 6 001 SICP Slide 2.1.7 somethin Language elements--abstractions 6001S
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 o 2004 by Massachusetts Institute of Technology multiply it by itself, and return that value Language elements -abstractions Need to capture ways of doing things-use parameters (lambda(x)( xx)l To process something multiply it by itself 1m003 6 001 SICP 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 Language elements--abstractions the value of multiplying that value by itself. In a second we will Need to capture ways of doing things-use see how this happens procedures r parameters Notice that lambda expressions must be special forms. The (lambda(x)( x x)h-body normal rules for evaluating a combination do not apply here To process something multiply it by itself 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 Special form-creates a procedure and returns it captures the common pattern of the process, as a function of 410 60153C those formal parameters Slide 2.1.10 Language elements--abstractions Now,where can we use such a procedure? Basically anywhere in our earlier expressions that we could use a built-in Use this anywhere you would use a procedure procedure, which for now means as the first element in a ( lambda(x×)(xx)5) 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 410200 6 001 SICP ions a procedure applied to a value. The only difference is that her 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.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 o 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 Scheme basics apply a procedure to a set of arguments. When the procedure was a built-in arithmetic operator, we just did the obvious thing. 2. If amame retur value associated with name in enviroment. Now if the procedure is something built by evaluating a lambda|:出.-如 expression, we have a new rule. We take the body of the Evaluate all of the subexpressions of combina any order) b, apply the operator to the values of the operands (arguments)and procedure, substitute the value of the argument in place of the corresponding formal parameter, and then use the same rules to Rules for application evaluate the resulting expression dy of the procedure with each formal placed by the corresponding actual argument value. 6001 sICP Slide 2.1.12 Language elements --abstractions 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 Use this anywhere you would use a procedure we see the formal parameter, x. This then reduces the ((lambda(x)(*xx))5 application of the lambda expression to a simpler expression 6001 SICP Slide 2.1.13 This reduces the application of a procedure to this simpler Language elements --abstractions expression, and we can apply our rules again. The symbol* is just a name for the built-in multiplication operation, and 5 is Use this anywhere you would use a procedure just self-evaluating, so this all reduces to ((lambda(x)(xx))5) (·55) 41∞03 60015e Slide 2.1.14 Language elements--abstractions Thus we see that our rules now cover the evaluation of Use this anywhere you would use a procedure 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.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 o 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 Language elements --abstractions But we don't want to have to write out lambda expressions everywhere we need to use this procedure Use this an you would use a procedure Instead, we can combine this procedural abstraction with our ((lambda(x)(xx))5) naming abstraction--that is, we can use a define expression to (55) 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 (define lambda(x)(xx))) (square lambda Then we can use the name square wherever we want the 10003 6001 sICP 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 Lambda: making new procedures The second kind of special form we saw was a lambda expression, and lambda we said was our way of capturing rocesses inside procedures. Lambda is Greek for "procedure (lambda (x)(*x*)) maker", and is our way of saying" Take this pattern, and capture in a way that will let me reuse it multiple times". In our two world view, if we type this expression into the computer and ask it to be evaluated, the computer uses the key word lambda to determine that this is a particular special form. It will then use the rule designed for this type of expression 1 001 SICP Lambda: making new procedures Slide 2.2.2 It is important to stress that the actual value created inside the machine is some representation for the procedure itself. This (lambda (at) ( c x )) representation includes information about the parameters of the procedure, and the body of the procedure, that is, what pattern of computation is being captured, and what are the variables to be replaced in that pattern when we want to use this procedure But it is the actual procedure representation that is associated a the value of the expression
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 of special form we saw was a lambda expression, and lambda we said was our way of capturing processes inside procedures. Lambda is Greek for "procedure maker", and is our way of saying "Take this pattern, and capture in a way that will let me reuse it multiple times". In our two world view, if we type this expression into the computer and ask it to be evaluated, the computer uses the key word lambda to determine that this is a particular special form. It will then use the rule designed for this type of expression. Slide 2.2.2 It is important to stress that the actual value created inside the machine is some representation for the procedure itself. This representation includes information about the parameters of the procedure, and the body of the procedure, that is, what pattern of computation is being captured, and what are the variables to be replaced in that pattern when we want to use this procedure. But it is the actual procedure representation that is associated as the value of the expression