6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 3.1 Slide 3.1.1 This Lecture In this lecture, we are going to put together the basic pieces of Scheme that we introduced in the previous lecture, in order to Substitution mode An example using the substitution model start capturing computational processes inside procedures. To Designing recursive procedures do this we will introduce a model of computation, called the substitution model. We will show how that model helps us relate the choices we make in designing a procedure to the actual process of evaluation that will occur when we use that Thus we will first look at an example of the substitution model to make sure you understand its mechanics, and then we will 7803 60015e use to that examine two different approaches to creating procedures Substitution model Slide 3.1.2 a way to figure out what happens during evaluation Now that we have the ability to create procedures and use them not really what happens in the ve need some way of figuring out what happens during the olution of a For that we h something called the substitution model. You' ve actually seen this, but we just didn' t call it that, and now we are going to make it quite expl The role of the substitution model is to provide us with a means of determining how an expression evolves In examining the substitution model, we stress that this is not a perfect model of 4781208 rm we 1001 SICP what goes on inside the computer. In fact, later in the ter will see a much more detailed and accurate model of computation, but this model suffices for our purposes. Indeed, nding in designing pi can work backwards, using a desired pattern of evaluation to help us design the correct procedure to generate that evaluation pattern
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 3.1 Slide 3.1.1 In this lecture, we are going to put together the basic pieces of Scheme that we introduced in the previous lecture, in order to start capturing computational processes inside procedures. To do this, we will introduce a model of computation, called the substitution model. We will show how that model helps us relate the choices we make in designing a procedure to the actual process of evaluation that will occur when we use that procedure. Thus we will first look at an example of the substitution model, to make sure you understand its mechanics, and then we will use to that examine two different approaches to creating procedures. Slide 3.1.2 Now that we have the ability to create procedures and use them, we need some way of figuring out what happens during the evolution of a procedure application. For that we have something called the substitution model. You've actually seen this, but we just didn't call it that, and now we are going to make it quite explicit. The role of the substitution model is to provide us with a means of determining how an expression evolves. In examining the substitution model, we stress that this is not a perfect model of what goes on inside the computer. In fact, later in the term we will see a much more detailed and accurate model of computation, but this model suffices for our purposes. Indeed, we don't really care about using the substitution model to figure out the actual value of an expression. We can use the computer to do that. Rather, we want to use the substitution model to understand the process of evaluation, so that we can use that understanding to reason about choices in designing procedures. Given that understanding, we can work backwards, using a desired pattern of evaluation to help us design the correct procedure to generate that evaluation pattern
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 3.1.3 So here are the rules for the substitution model. given an Substitution model expression, we want to determine its value. If the expression is way to figure out what happens during evaluation a simple expression there are several possibilities. If it is a self- evaluating expression, like a number, we just return that value If the expression is a name(something we created with a define expression) then we replace the name with the corresponding or evaluating value associated with it If the expression is a special form, there are also several possibilities. If the expression is a lambda then we replace the expression with some representation of the actual pre ocedure If procedure parameter in body of proce en repeat on body the expression is some other special form(such as an if expression) then we follow specific rules for evaluating the ubexpressions of that special form Otherwise the expression is a compound expression(one of those expressions nested in parentheses that contains several subexpressions). Here we apply exactly the same set of rules to each of the subexpressions of the compound expression, in some arbitrary order. We then look at the value of the first subexpression. If it is a primitive procedure(one of the built-in procedures, like or + then we just apply that procedure to the values of the other expressions. On the other hand, if the value of the first subexpression is a compound procedure (something we created by evaluating a lambda expression) then we substitute the value of each subsequent subexpression for the corresponding procedure parameter in the body of the procedure. We replace the entire expression ly, and repeat the proces Substitution model-a simple example Slide 3. 1. 4 (define square (lambda (x)(* x *))) So here is a simple example. Suppose we have defined square to be the obvious procedure that multiplies a value by itself. 1.( ttion model to trace out the evolution of applying that procedur The substitution model says that to trace the evaluation of square 4), we first determine that this is a compound expression. Since it is, we evaluate each of the subexpression just a name, and we look up its value, getting back the are,is using the same rules. Thus, the first subexpression, sq 7103 I procedure we created when we evaluated the lambda. The second subexpression is just a number so that is its value. Now the rule says to substitute 4 everywhere we see the formal parameter x in the body of the procedure and replace the original expression with this instantiated body expression, sho This reduces the evaluation of (square 4)to the evaluation of the expression (44). This is also a compound expression, so again we get the values of the subexpressions. In this case, the application is of a primitive procedure, so we simply apply it to reduce the expression to its final value, 16
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 3.1.3 So here are the rules for the substitution model. Given an expression, we want to determine its value. If the expression is a simple expression there are several possibilities. If it is a selfevaluating expression, like a number, we just return that value. If the expression is a name (something we created with a define expression) then we replace the name with the corresponding value associated with it. If the expression is a special form, there are also several possibilities. If the expression is a lambda then we replace the expression with some representation of the actual procedure. If the expression is some other special form (such as an if expression) then we follow specific rules for evaluating the subexpressions of that special form. Otherwise the expression is a compound expression (one of those expressions nested in parentheses that contains several subexpressions). Here we apply exactly the same set of rules to each of the subexpressions of the compound expression, in some arbitrary order. We then look at the value of the first subexpression. If it is a primitive procedure (one of the built-in procedures, like * or +) then we just apply that procedure to the values of the other expressions. On the other hand, if the value of the first subexpression is a compound procedure (something we created by evaluating a lambda expression) then we substitute the value of each subsequent subexpression for the corresponding procedure parameter in the body of the procedure. We replace the entire expression with this instantiated body, and repeat the process. Slide 3.1.4 So here is a simple example. Suppose we have defined square to be the obvious procedure that multiplies a value by itself. Now, let's use the substitution model to trace out the evolution of applying that procedure. The substitution model says that to trace the evaluation of (square 4), we first determine that this is a compound expression. Since it is, we evaluate each of the subexpressions using the same rules. Thus, the first subexpression, square, is just a name, and we look up its value, getting back the procedure we created when we evaluated the lambda. The second subexpression is just a number, so that is its value. Now the rule says to substitute 4 everywhere we see the formal parameter x in the body of the procedure and replace the original expression with this instantiated body expression, as shown. This reduces the evaluation of (square 4) to the evaluation of the expression (* 4 4). This is also a compound expression, so again we get the values of the subexpressions. In this case, the application is of a primitive procedure, so we simply apply it to reduce the expression to its final value, 16
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 3.1.5 Here is a more detailed example. First, let's create two Substitution model details procedures. These expressions will each generate a procedure, (define square (lambda (*)(* xx))) ough the lambda expressions, and the defines will then define average(1 ambda(xy)《/什+xy)2}) associate a name with each of them Thus in our environment we have pairings of square and average to the associated procedure objects, each with its own parameter list and body 6001 sICP Substitution model details Slide 3. 1.6 Here is an example using these procedures. To evaluate this (计:m222 first expression using the substitution model, I first need to get the values of the sub-expressions. The value of average I get by looking this name up in the environment, giving me the 3)) associated procedure object. The value of 5 is easy. The last sub- verage 5(*33) (average 5 9) square and the value 3, then substitute 3 into the body of square for x. This reduces to another combination which i can 47108 601 SICP ecognize is an application of a primitive procedure, so this reduces to the number 9. Thus the recursive application of the substitution model yields a simpler combinatio Note the format here. I first evaluate the sub-expressions, then substitute and apply the procedure. This is called an applicative order evaluation model Slide 3.1.7 Substitution model details Notice in particular that under this model I need to get the value of the operands first, which caused me to evaluate that interior (define square.(ambda (x y)(/(+ x y) 2))) (define average compound expression before I got around to applying average Once I have simple values, I can continue the substitution In this e the body of the procedure associated with rage 5 (square 3) average, now substituting 5 and 9 for x and y in that body rage5(33)) Note that there is no confusion about which x I am referring to, it's the one in the procedure associated with age, not the if operator is a primitive procedure. replace by result of operation 600SC the case of a compound expression, I must reduce this to a pler value before I can continue with the rest of the expression. Also note that when the application involves a primitive procedure, I just do the associated operation, eventually reducing this to the final answer The key idea is to see how this notion of substitution lets us trace out the evolution of an expression s evaluation reducing an application of a procedure to the evaluation of a simpler expression
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 3.1.5 Here is a more detailed example. First, let's create two procedures. These expressions will each generate a procedure, through the lambda expressions, and the defines will then associate a name with each of them. Thus, in our environment, we have pairings of square and average to the associated procedure objects, each with its own parameter list and body. Slide 3.1.6 Here is an example using these procedures. To evaluate this first expression using the substitution model, I first need to get the values of the sub-expressions. The value of average I get by looking this name up in the environment, giving me the associated procedure object. The value of 5 is easy. The last subexpression is itself a combination, so I recursively apply the rules. By the same reasoning I get the procedure associated with square and the value 3, then substitute 3 into the body of square for x. This reduces to another combination, which I can recognize is an application of a primitive procedure, so this reduces to the number 9. Thus the recursive application of the substitution model yields a simpler combination. Note the format here. I first evaluate the sub-expressions, then substitute and apply the procedure. This is called an applicative order evaluation model. Slide 3.1.7 Notice in particular that under this model I need to get the value of the operands first, which caused me to evaluate that interior compound expression before I got around to applying average. Once I have simple values, I can continue the substitution. In this case, I use the body of the procedure associated with average, now substituting 5 and 9 for x and y in that body. Note that there is no confusion about which x I am referring to, it's the one in the procedure associated with average, not the one in square. As before, I substitute into the body of this procedure, and then continue. I recursively apply the rules to each subexpression. In the case of a compound expression, I must reduce this to a simpler value before I can continue with the rest of the expression. Also note that when the application involves a primitive procedure, I just do the associated operation, eventually reducing this to the final answer. The key idea is to see how this notion of substitution lets us trace out the evolution of an expression's evaluation, reducing an application of a procedure to the evaluation of a simpler expression
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 3.2 Slide 3.2.1 A less trivial procedure: factorial Now let's look at a little less trivial example. Suppose I want to Compute n factorial, defined as nl =n(n-1)(n-2)(n-3),1 compute factorial of n, which is defined as the product of n n-1 and so on down to 1 note that i am assuming that n is integer and is greater than or equal to 1 A less trivial procedure: factorial Slide 3.2.2 So how do i create a procedure to compute factorial of n? Wel . Notice that nl=n"[(n-1)(n-2).=n"(n-1) ifn>1 I need to think careful choice in de procedure will impact the evolution of the process when I use One way to look at factorial is to group the computation into multiply ing n by all the other multiplications, but I can recognize that this latter computation is just factorial of n-1 So notice what this does, it reduces a computation to a simpler operation, multiplication, and a simpler version of the same I problem, in this case factorial of a smaller number. So I have reduced one version of a problem to a simpler version same problem, plus some simple operations. This is a common pattern that we are going to use a lot in designing procedures Slide 3.2.3 A less trivial procedure: factorial In fact, given this common pattern, we can write a procedure to Compute n factorial, defined as n! =n(n-1)(n-2)(n-3),1 capture this idea. Here it is. The first part says to give the name Notice that n!=n (n-1)(n-2) l=n*(n-1)!ifn>1 fact to the procedure created by the lambda, which has a single|(define fact argument n and a particular body. Now, what does the lambda lambda (n) say to do? It has two different parts, which we need to look at carefully n(fact(-n1)))))) 41∞03
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 3.2 Slide 3.2.1 Now let's look at a little less trivial example. Suppose I want to compute factorial of n, which is defined as the product of n by n-1 and so on down to 1. Note that I am assuming that n is an integer and is greater than or equal to 1. Slide 3.2.2 So how do I create a procedure to compute factorial of n? Well I need to think carefully here, since my choice in designing this procedure will impact the evolution of the process when I use it. One way to look at factorial is to group the computation into multiplying n by all the other multiplications, but I can recognize that this latter computation is just factorial of n-1. So notice what this does, it reduces a computation to a simpler operation, multiplication, and a simpler version of the same problem, in this case factorial of a smaller number. So I have reduced one version of a problem to a simpler version of the same problem, plus some simple operations. This is a very common pattern that we are going to use a lot in designing procedures. Slide 3.2.3 In fact, given this common pattern, we can write a procedure to capture this idea. Here it is. The first part says to give the name fact to the procedure created by the lambda, which has a single argument n and a particular body. Now, what does the lambda say to do? It has two different parts, which we need to look at carefully
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 3. 2.4 A less trivial procedure: factorial First of all, it has a new kind of expression in the interior, the Compute n factorial, defined as n =n(n-1)(n-2)(n-3),1 his is an example of a predicate, a procedure that takes some .Notice that n!=n [(n-1(n-2)=n"(n-1)! ifn>1 arguments and returns either true or false. in this case based on (define fact (lambda (n) the test for numerical equality (f(=n1) *n(fact(-n1))})) numerical equality 4)=>#t (=45)=>#f 6 001 SICP Slide 3.2.5 The more interesting part is the body of the lambda, and it is a A less trivial procedure: factorial new special form called an if. Because this is a special form,it Notice that n!=n [(n-1)(n-2)=n"(n-1) ifn>1 means that evaluation does not follow the normal rules for (define fact combinations. Ifs are used to control the order of evaluation (lambda (n) and contain three pieces (f(=n1) merical (f=44)23)=>2 if(=45)23)=>3 470∞03 A less trivial procedure: factorial Slide 3.2.6 Its first subexpression we call a predicate .Notice that n!=n"[(n-1(n-2).]=n"(n-1) ifn> (define fact (lambda (n) (act(-n1))}))) f(=44)2 (f(45)23 731(003 predic Slide 3.2.7 A less trivial procedure: factorial Its second subexpression we call a consequent .Notice that n!=n(n-1)(n-2),J=n (n-1) ifn>1 tact (=45)>静E (false) (f(=44)23
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 3.2.4 First of all, it has a new kind of expression in the interior, the =. This is an example of a predicate, a procedure that takes some arguments and returns either true or false, in this case based on the test for numerical equality. Slide 3.2.5 The more interesting part is the body of the lambda, and it is a new special form called an if. Because this is a special form, it means that evaluation does not follow the normal rules for combinations. If's are used to control the order of evaluation, and contain three pieces. Slide 3.2.6 Its first subexpression we call a predicate. Slide 3.2.7 Its second subexpression we call a consequent