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