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, 166.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 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 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