6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 4.1.4 Rules for evaluation If our expression is a name that we created ourselves, we will Elementary expressions"are left alone: Elementary expressions are rewrite in place of it the value that was associated with that name during the definition A name bound by DEFINE: Rewrite the name as the value it is Slide 4.1.5 For the special form if we use the rule we just saw. We Rules for evaluation Elementary expressions"are left alone: Elementary expressions are evaluate the predicate clause and based on its value, we either rewrite the i f expression by its consequent or its alternative write the name as the value it is associated with by the definiti IF: If the evaluation of the predicate expression terminates in non-false Rules for evaluation Slide 4.1.6 And finally: combinations. We use the rule that we first inital names of primtive procedures evaluate the operator expression to get the procedure, and we Rssaosetn n e pese a era reme etse ate primitive procedure, we are just going to "do the right thing 9 A name bound by DEFINE Rewmte the name as the value it I evaluate the operands to get the set of arguments. If we have Otherwise we are going to replace this entire expression with Evaluate the operator expression to get the procedure, and the body of the compound expression, with the arguments if the operator names a primitive procedure, do whatever m: substituted for their associated parameters operator names a compound procedure, evaluate the body of the compound procedure wth the arguments substituted for the formal parameters in the body 8200 Slide 4.1.7 Orders of growth of processes Given that model, we can more formally capture the evolution Suppose n is a parameter that measures the size of a of a process. We can talk about the order of growth of a process problem these rewrite rules evolve. This measures how much of a Let r(n) be the amount of resources needed to compute a procedure of size n particular resource a process is going to take as these rules We say R(n) has order of growth e(f(n)if there are evolve, where typically we measure either space or time as the onstants k, and kz such that k,f(n)<=R(n)<=kf(n) for large n More formally, let n be a parameter that measures the size of number of deferred operations, and time, measured by the the problem of interest. In the case of factorial, this would be number of primitive steps the size of the input argument. We let r(n)denote the amount of resources we will need to solve a problem of this size, where 842003 600SC as noted, the resources are usually space and time. We are interested in characterizing R(n) for large values of N, that is, in6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 4.1.4 If our expression is a name that we created ourselves, we will rewrite in place of it the value that was associated with that name during the definition. Slide 4.1.5 For the special form if we use the rule we just saw. We evaluate the predicate clause, and based on its value, we either rewrite the if expression by its consequent or its alternative. Slide 4.1.6 And finally: combinations. We use the rule that we first evaluate the operator expression to get the procedure, and we evaluate the operands to get the set of arguments. If we have a primitive procedure, we are just going to “do the right thing”. Otherwise we are going to replace this entire expression with the body of the compound expression, with the arguments substituted for their associated parameters. Slide 4.1.7 Given that model, we can more formally capture the evolution of a process. We can talk about the order of growth of a process as these rewrite rules evolve. This measures how much of a particular resource a process is going to take as these rules evolve, where typically we measure either space or time as the resource. More formally, let n be a parameter that measures the size of the problem of interest. In the case of factorial, this would be the size of the input argument. We let R(n) denote the amount of resources we will need to solve a problem of this size, where as noted, the resources are usually space and time. We are interested in characterizing R(n) for large values of N, that is, in