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 evaluated6.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