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
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 3.2.8 A less trivial procedure: factorial and its third subexpression we call an alternative. now here hy an if is An ifex first evaluates its .Notice that n!=n [(n-1(n-2)=n"(n-1)! ifn>1 predicate, using the same set of rules recursively on this (define fact (lambda (n) expression. It does this before it ever looks at either of the two (f(=n1) other expressions. Now, if the predicate evaluates to a true *n(fact(-n1))})) value, then the if expression takes the consequent, and evaluates . predicate- tests mumerical equality it, returning that value as the value of the overall if expression (=44)=># (=45)=>#f On the other hand, if the predicate evaluates to a false value, special fo then the if expression takes the alternative expression, evaluates f(=44)23)=>2 (af45)=>3 it, and returns that value. Notice that only one of the consequent 7103 obsequent altemative and alternative expressions is evaluated during an if In the case of our fact procedure, we can now see how the evaluation will proceed. When we apply fact to some argument, we first test to see if that value is 1. The if expression does this by first evaluating the predicate, before ever considering the other expressions, thus changing the order of evaluation. If the predicate is true, then we simply return the value 1. If it is false, then we will evaluate the last expression with appropriate substitution, thus unwinding factorial of n into the multiplication of the value of n by the result of evaluating factorial of n-1 Slide 3. 2.9 (define fact (lambda (n) Here is a tracing of the substitution model in action. To (if(=n1)1(*n(fact(-n1)))))) evaluate factorial of 3, we substitute into the body of fact (fact 3) 主f仁=31)1(*3(act(-31)})) leading to the next expression. The if first evaluates the 主f#1(*3(fact(-31)))) predicate, leading to the next expression. Since the predicate 's (3 (act 2031)1) value is false, the entire if expression is replaced by the (3(iE(=21)1(*2(fact(-21))) alternative, with appropriate substitutions *3(E1(*2(Eact(-21)))) *3(*2(Eact(-21)})} To evaluate this expression we need to get the values of the fact 1)) multiplication of 3 by the value of(fact 2). Notice how this has (32)2i*ei i, 1/1(act(-11253)) subexpressions, so this entire expression reduces to a unwound the computation into a particular form, a deferred 600SC multiplication and a recursive call to a simpler version of the same problem his process repeats, using the if to unwind another level of the computation, and this continues, just using the substitution model rules, until finally the predicate is true. In this case, we are left with an expression just involving primitives, and we can complete the multiplications, thus reducing the computation to a simple answer Note the form shown in red, in which an expression is reduced to this pattern of a simpler operation and a simpler of the same problem. This unwrapping continues until we are left with a nested expression whose innermost subexpression only involves simple expressions and operations, at which point the deferred operations are evaluated
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 3.2.8 ... and its third subexpression we call an alternative. Now here is why an if is a special form. An if expression first evaluates its predicate, using the same set of rules recursively on this expression. It does this before it ever looks at either of the two other expressions. Now, if the predicate evaluates to a true value, then the if expression takes the consequent, and evaluates it, returning that value as the value of the overall if expression. On the other hand, if the predicate evaluates to a false value, then the if expression takes the alternative expression, evaluates it, and returns that value. Notice that only one of the consequent and alternative expressions is evaluated during an if. In the case of our fact procedure, we can now see how the evaluation will proceed. When we apply fact to some argument, we first test to see if that value is 1. The if expression does this by first evaluating the predicate, before ever considering the other expressions, thus changing the order of evaluation. If the predicate is true, then we simply return the value 1. If it is false, then we will evaluate the last expression with appropriate substitution, thus unwinding factorial of n into the multiplication of the value of n by the result of evaluating factorial of n-1. Slide 3.2.9 Here is a tracing of the substitution model in action. To evaluate factorial of 3, we substitute into the body of fact, leading to the next expression. The if first evaluates the predicate, leading to the next expression. Since the predicate's value is false, the entire if expression is replaced by the alternative, with appropriate substitutions. To evaluate this expression we need to get the values of the subexpressions, so this entire expression reduces to a multiplication of 3 by the value of (fact 2). Notice how this has unwound the computation into a particular form, a deferred multiplication and a recursive call to a simpler version of the same problem. This process repeats, using the if to unwind another level of the computation, and this continues, just using the substitution model rules, until finally the predicate is true. In this case, we are left with an expression just involving primitives, and we can complete the multiplications, thus reducing the computation to a simple answer. Note the form shown in red, in which an expression is reduced to this pattern of a simpler operation and a simpler version of the same problem. This unwrapping continues until we are left with a nested expression whose innermost subexpression only involves simple expressions and operations, at which point the deferred operations are evaluated
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 3.2.10 The fact procedure is a recursive algorithm That means that fact gives rise to what we call a recursive process. In the substitution model we can see that this is In the substitution mode, the expression keeps growing characterized by a set of deferred operations, in which the multiplication is deferred while we go off to get the sub- ★3(fact2)) (*3(*2(fact1))) computation of the simpler version of fact. Once we get to a Other ways to identify will be described next time simple case, we can start accumulating those stacked up operations. We will come back to this idea next time 7103 6 001 SICP 10n0 6.001 Notes: Section 3.3 Slide 3.3.1 How to design recursive algorithms Now that we have seen our first more interesting procedure, follow the general pattern fact, let's step back and generalize the ideas we used to capture this computation in a procedure 2. decompose the problem What are the general steps that we use in creating a recursive 3. identify non-decomposable(smallest)problems procedure like this? We have three stages: as shown her 1. wishful thin kin The first stage is called wishful thinking. The idea is as Assume the desired procedure exists follows. If I want to create a solution to some problem, I first assume that I have available a procedure that will solve the want to implement fact? oK, assume it exists BUT, only solves a smaller version of the proble oblem, but only for versions of the problem smaller than the current one. In the case of factorial, I assume(wishfully) that I 71003 can solve factorial for problems of size smaller than n se the problem Slide 3.3.2 Solve a problem by Given that assumption, the second stage proceeds to design 1. sole a smaller instance sing wishful thinking) solution to the problem. In particular, I can use the existence of 2. convert that solution to the desired solution a solution to the smaller sized problem, plus a set of simple operations, to design the solution to the larger sized problem Must design the strategy before coding We this with factorial where mbined the solution to n=nn1)n2=n(n1)(n2)]=n*(n-1) a smaller version of factorial, plus a multiplication, to create the solve the smaller instance, multiply it by n to get solution solution to the full version of factorial (define fact Notice that the second step here requires some ingenuit (Lambda (n)(*n (fact (-n 1)))) should be careful to think through this strategy, betony.One I beginning to code up a solution. In the case of factorial, we saw how we did this decomposition into a multiplication and a maller version of factorial With this, we can build a first version of the procedure as shown at the bottom of the slide
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 3.2.10 That means that fact gives rise to what we call a recursive process. In the substitution model we can see that this is characterized by a set of deferred operations, in which the multiplication is deferred while we go off to get the subcomputation of the simpler version of fact. Once we get to a simple case, we can start accumulating those stacked up operations. We will come back to this idea next time. 6.001 Notes: Section 3.3 Slide 3.3.1 Now that we have seen our first more interesting procedure, fact, let's step back and generalize the ideas we used to capture this computation in a procedure. What are the general steps that we use in creating a recursive procedure like this? We have three stages: as shown here. The first stage is called wishful thinking. The idea is as follows. If I want to create a solution to some problem, I first assume that I have available a procedure that will solve the problem, but only for versions of the problem smaller than the current one. In the case of factorial, I assume (wishfully) that I can solve factorial for problems of size smaller than n. Slide 3.3.2 Given that assumption, the second stage proceeds to design a solution to the problem. In particular, I can use the existence of a solution to the smaller sized problem, plus a set of simple operations, to design the solution to the larger sized problem. We saw this with factorial, where we combined the solution to a smaller version of factorial, plus a multiplication, to create the solution to the full version of factorial. Notice that the second step here requires some ingenuity. One should be careful to think through this strategy, before beginning to code up a solution. In the case of factorial, we saw how we did this decomposition into a multiplication and a smaller version of factorial. With this, we can build a first version of the procedure as shown at the bottom of the slide
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 3.3.3 Of course you already know that this won,t quite work, but let's3 Identify non-decomposable problems think about why. If we apply that version of fact to some argument, it will keep unwinding the application of factorial Must identify the " smallest"problems and solve directly into a multiplication and a smaller version of factorial. But Define 1!=1 before we can compute that multiplication, we have to get the value of the smaller version of factorial. and that will continue (define fact (lambda (n) to unwind to another version ad infinitum (if(=n1)1 The problem is that I didn't use my third step; I didn't consider *n(fact(-n1)))}) the smallest sized problem that I can solve directly, without using wishful thinking. In the case of factorial, that is just knowing that factorial of 1 is just 1. Once I find that smallest 471∞03 6001 sICP sized problem, I can control the unwinding of the computation by checking for that case and doing the direct computation when appropriate. In this way, I will terminate the recursive unwinding of the computation and accumulate all the deferred operations General form of recursive algorithms Slide 3.3. 4 test, base case, recursive case This in fact is a very common form, a common pattern for a recursive algorithm that has a test. a base case and a recursive (define fact case. The if controls the order of evaluation to decide whether (lambda (n) (f(= test for base case ve have the base case or the recursive case. the recursive case 1 base case controls the unwinding of the computation, doing so until we (-n 1)) i recursive case reach the base case ))) base case: smallest (non-decomposable) problem recursive case: larger(decomposable) problem 4:a03 6 001 SICP Slide 3.3.5 Summary of recursive processes To summarize. we have now seen how to design recursive algorithms, by using this idea of wishful thinking to separate the problem into a simpler version of the same problem, do that decomposition and identify the smallest version of the problem 3. identify non-decomposable(smallest)problems that will stop the unwinding of the computation into simpler Recursive algorithms have versions of the same problem. As a consequence, algorithms associated with this kind of approach have a test, a base case 2. recursive case and a recursive case to control the order of evaluation in order to unwind the computation into simpler versions of the same 6001S 6.001 Notes: Section 3. 4
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 3.3.3 Of course you already know that this won't quite work, but let's think about why. If we apply that version of fact to some argument, it will keep unwinding the application of factorial into a multiplication and a smaller version of factorial. But before we can compute that multiplication, we have to get the value of the smaller version of factorial, and that will continue to unwind to another version, ad infinitum. The problem is that I didn't use my third step; I didn't consider the smallest sized problem that I can solve directly, without using wishful thinking. In the case of factorial, that is just knowing that factorial of 1 is just 1. Once I find that smallest sized problem, I can control the unwinding of the computation, by checking for that case and doing the direct computation when appropriate. In this way, I will terminate the recursive unwinding of the computation and accumulate all the deferred operations. Slide 3.3.4 This in fact is a very common form, a common pattern for a recursive algorithm that has a test, a base case and a recursive case. The if controls the order of evaluation to decide whether we have the base case or the recursive case. The recursive case controls the unwinding of the computation, doing so until we reach the base case. Slide 3.3.5 To summarize, we have now seen how to design recursive algorithms, by using this idea of wishful thinking to separate the problem into a simpler version of the same problem, do that decomposition and identify the smallest version of the problem that will stop the unwinding of the computation into simpler versions of the same problem. As a consequence, algorithms associated with this kind of approach have a test, a base case, and a recursive case to control the order of evaluation in order to unwind the computation into simpler versions of the same problem. 6.001 Notes: Section 3.4
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 3.4.1 So we have introduced recursive procedures, and we have nowIterative algorithms een an example of building a recursive procedure to implement factorial. Now, let's look at a different kind of procedure, an iterative procedure for computing factorial. In doing this, we are going to see how we can develop procedures with different evolutions that compute the same basic computation 471∞03 6001 sICP Slide 3.4.2 In a recursive algorithm, bigger operands => more space To set the stage for this, here is our factorial procedure from last time. Remember that this was a nice little procedure that *n(fact(-n1)))))) first checked to see if we were in the base case. and if we were (*4(Eact3)) 3 (fact 2) eturned the answer 1. If we were not, the procedure reduced (*4(*3(*21)0 the problem to multiplying n by a recursive call to factorial of n-1. One of the properties of this procedure was that it held set of deferred operations. To compute factorial of n, it had to hold onto a multiplication while it went off to compute the subproblem of a simpler version of factorial, and that in turn 601 SICP I required another deferred operation. Thus, the procedure had to keep track of something to do, once it was done computing a subproblem, and this meant that as the argument to the procedure gets larger, we would have more things to keep track of. We would like to see if there is another way of computing factorial, without all of those deferred operations Slide 3.4.3 rative algorithms The specific question we want to consider is whether we can In a recursive algorithm, bigger ope design an algorithm for factorial that uses only constant space efine fact (lambda (n By this we mean that the computation does not require keeping *nact(-n1)))))) fact 4) track of any deferred operations, but rather can perform its work without using up any additional memory to keep track of (*4(3 things to do An iterative algorithm uses constant space
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 3.4.1 So we have introduced recursive procedures, and we have now seen an example of building a recursive procedure to implement factorial. Now, let's look at a different kind of procedure, an iterative procedure for computing factorial. In doing this, we are going to see how we can develop procedures with different evolutions that compute the same basic computation. Slide 3.4.2 To set the stage for this, here is our factorial procedure from last time. Remember that this was a nice little procedure that first checked to see if we were in the base case, and if we were, returned the answer 1. If we were not, the procedure reduced the problem to multiplying n by a recursive call to factorial of n-1. One of the properties of this procedure was that it held a set of deferred operations. To compute factorial of n, it had to hold onto a multiplication while it went off to compute the subproblem of a simpler version of factorial, and that in turn required another deferred operation. Thus, the procedure had to keep track of something to do, once it was done computing a subproblem, and this meant that as the argument to the procedure gets larger, we would have more things to keep track of. We would like to see if there is another way of computing factorial, without all of those deferred operations. Slide 3.4.3 The specific question we want to consider is whether we can design an algorithm for factorial that uses only constant space. By this we mean that the computation does not require keeping track of any deferred operations, but rather can perform its work without using up any additional memory to keep track of things to do
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 3.4.4 Intuition for iterative factorial So thats our goal, to compute factorial in a different way that not characterized by those deferred multiplications 7103 6 001 SICP Slide 3. 4.5 Intuition for iterative factorial and here is the intuition behind this different approach. Let's. same as you would do if calculating 4l by hand think about how you might do this if you were executing the 1. multiply 4 by 3 first two numbers, and keep track of that temporary produ o computation by hand. One way to do this is to multiply out 2. multiply 12 by 2 gives 24 3. multiply 24 by 1 plus the next stage in the computation. For example, for factorial of 4, you would multiply out 4 by 3, keep track of the result, 12, and the fact that the next thing to multiply is 2. You would then multiply the current result, 12, by 2, keeping track of that result and the next thing to multiply by < s1403 Intuition for iterative factoria Slide 3. 4.6 same as you would do if calculating 4 by hand Notice that in this version, we only need to keep track of 2 1. multiply 4 by 3 gives 12 things, the current product, and the next thing to do. This is 2. multiply 12 by 2 different from the recursive case, where we were blindly multiply 24 by gives 24 .At each step, only need to remember keeping track of each pending multiplication. Here, we replac the previous product by the new one, and the next multiplier by the new one, whereas in the previous case we had to keep track of each deferred operation, i.e. I have to multiply by 2, then I have to multiply by 3, then Slide 3. 4.7 Intuition for iterative factorial hus, we only need a constant amount of space. To stress, think same as you would do if calculating 4! by hand about the recursive case. There. we had to write down that i 1. multiply 4 by 3 gives 12 have a pending operation of multiplication by some number, 2. multiply 12 by 2 plus another pending operation of multiplication by another 3. multiply 24 by 1 gives 24 number, and so on. Keeping track of each such pending . At each step, only need to remember previous product, next multiplier operation takes a bit more space. In this case, I only need two pieces of information, the current product and the next multiplier
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 3.4.4 So that's our goal, to compute factorial in a different way that is not characterized by those deferred multiplications Slide 3.4.5 ... and here is the intuition behind this different approach. Let's think about how you might do this if you were executing the computation by hand. One way to do this is to multiply out the first two numbers, and keep track of that temporary product, plus the next stage in the computation. For example, for factorial of 4, you would multiply out 4 by 3, keep track of the result, 12, and the fact that the next thing to multiply is 2. You would then multiply the current result, 12, by 2, keeping track of that result and the next thing to multiply by. Slide 3.4.6 Notice that in this version, we only need to keep track of 2 things, the current product, and the next thing to do. This is different from the recursive case, where we were blindly keeping track of each pending multiplication. Here, we replace the previous product by the new one, and the next multiplier by the new one, whereas in the previous case we had to keep track of each deferred operation, i.e. I have to multiply by 2, then I have to multiply by 3, then ... Slide 3.4.7 Thus, we only need a constant amount of space. To stress, think about the recursive case. There, we had to write down that I have a pending operation of multiplication by some number, plus another pending operation of multiplication by another number, and so on. Keeping track of each such pending operation takes a bit more space. In this case, I only need two pieces of information, the current product and the next multiplier