《Structure and Interpretation of Computer Programs》lecture4webhand.pdf_大学文库

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, in

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology the asymptotic limit. We say that r(n) has order of growth, Theta of f of n if we can find a function f(n) that is oughly of the same order as the needed resource, where the more formal definition is shown in the Slide 4.1.8 Partial trace for (fact 4) In more common terms, this says that when measuring the amount of space we need, we want to find a function that measures the number of deferred operations, as a function of the size of the problem, up to a constant factor. For measuring the amount of time we want to find a function that measures the number of basic or primitive steps that the rewrite rules go through, again as a function of the size of the problem 6001 SKP Slide 4.1.9 Partial trace for(fact 4) So let's use our rewrite rule idea, together with this notion of measuring the amount of resource we need as an order of a(if (=n 1)i bda(n) n(act(-n1)))) growth in the size of the problem. Here is our recursive factorial 1)1《·4《aet(-41)))) 4(·3(·2(11)1(·1《tact(-11))))))) 4(·32)) 6 001 SICP Partial trace for (ifact 4) Slide 4.1.10 (define ifact -helper (lambda (product count n) and here is a partial trace of fact using those rewrite rules We start with (fact 4). That reduces to evaluating an if detine ifact (lambda (n) (ifact-helper 11 n))) expression. Since the predicate is not true, this reduces to 1per 11 4) evaluating the alternative statement, which is a combination of (f14)1( ifact- helper(*11)(+11)4) e 6 2 4) i difaot-helper (+1 2)(214) a multiplication and another evaluation of fact (if (3 4)2 (afaat-helper ( 2 3)(31) 4)) Notice how the orange colored lines capture the evolution of the rewrite rules. Note how(fact 4 )reduces to a deferred operation ft44)6 helper(64)(+41)4)) and an evaluation of (fact 3)and this further reduces to another irc>54)24( ifact- helper(*245)(+51)4) deferred operation and a subsequent call to fact. Notice the shape of this process: it grows out with a set of deferre operations until it reaches a base case, and then it contracts back in, completing each deferred operation. Using this, we can see that the amount of space grows linearly with the size of the argument. That is, with each increase in the argument size, I add a constant amount of space requirement. In terms of the number of operations, we can see that we basically need twice as many steps as the size of the problem, one to expand out, and one to reduce back down. This is also a linear growth, since the constant 2 does not change with problem size

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. the asymptotic limit. We say that R(n) has order of growth, Theta of f of n if we can find a function f(n) that is roughly of the same order as the needed resource, where the more formal definition is shown in the Slide 4.1.8 In more common terms, this says that when measuring the amount of space we need, we want to find a function that measures the number of deferred operations, as a function of the size of the problem, up to a constant factor. For measuring the amount of time, we want to find a function that measures the number of basic or primitive steps that the rewrite rules go through, again as a function of the size of the problem. Slide 4.1.9 So let's use our rewrite rule idea, together with this notion of measuring the amount of resource we need as an order of growth in the size of the problem. Here is our recursive factorial procedure ... Slide 4.1.10 ..and here is a partial trace of fact using those rewrite rules. We start with (fact 4). That reduces to evaluating an if expression. Since the predicate is not true, this reduces to evaluating the alternative statement, which is a combination of a multiplication and another evaluation of fact. Notice how the orange colored lines capture the evolution of the rewrite rules. Note how (fact 4) reduces to a deferred operation and an evaluation of (fact 3) and this further reduces to another deferred operation and a subsequent call to fact. Notice the shape of this process: it grows out with a set of deferred operations until it reaches a base case, and then it contracts back in, completing each deferred operation. Using this, we can see that the amount of space grows linearly with the size of the argument. That is, with each increase in the argument size, I add a constant amount of space requirement. In terms of the number of operations, we can see that we basically need twice as many steps as the size of the problem, one to expand out, and one to reduce back down. This is also a linear growth, since the constant 2 does not change with problem size

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 4.1.1 So why have we done this? The primary goal is to allow you to start to recognize different kinds of behaviors, and the associated procedure forms that give rise to those behaviors This will start to allow you to work backwards, in designing a procedure, by enabling you to visualize the consequences of performing a computation in different ways 6.001 Notes: Section 4.2 Slide 4.2.1 Com puting Fi Having seen two different kinds of processes, one linear, and Consider the following function one constant, we want to fill out our repertoire of processes, by. F(m)=0 if n=0 looking at other kinds of processes. The next one is an example|.F(n)=1 ifn=1 of an exponential process, and deals with a classic function F(n)= F(n-1)+ F(n-2)otherwise called Fibonacci. Its definition is that if its argument is 0, its value is 0, if its argument is 1, its value is 1, and for all other positive integer arguments, its value is the sum of its values for the two preceding arguments We would like to write a procedure to compute Fibonacci, and in particular see how it gives rise to a different kind of behavior Fibonacci Slide 4.2.2 o solve this problem, let's use our tool of wishful thinking Here, that wishful thinking says, lets assume that given an (oand (( n 0) 0) n1)1) argument n, we know how to solve Fibonacci for any smaller (else ( (fib ("n 1)) (1b(n2))))))) sized argument. Using that idea, we can then work out a solution to the problem. With this in hand, it is clear that the (cond ( solution to the general problem is just to solve two smaller sized problems, then just add the results together. Note that in Else <consequent) this case we are using wishful thinking twice, not once, as in our previous examples I Here is a procedure that captures this idea First, we introduce a new expression, called a cond expression. Cond uses the following rules of evaluation. The cond consists of a set of clauses, each of which has within it, a predicate clause, and one or more subsequent expressions. Cond proceeds by first evaluating the predicate of the first clause, in this case(= n 0). If it is true, then we evaluate in turn each of the other expressions in this clause, returning the value of the last one as the value of the whole cond. In the case of the first clause of this cond that is the expression 0. If the predicate of the first clause is false we move to the next

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 4.1.14 So why have we done this? The primary goal is to allow you to start to recognize different kinds of behaviors, and the associated procedure forms that give rise to those behaviors. This will start to allow you to work backwards, in designing a procedure, by enabling you to visualize the consequences of performing a computation in different ways. 6.001 Notes: Section 4.2 Slide 4.2.1 Having seen two different kinds of processes, one linear, and one constant, we want to fill out our repertoire of processes, by looking at other kinds of processes. The next one is an example of an exponential process, and deals with a classic function called Fibonacci. Its definition is that if its argument is 0, its value is 0, if its argument is 1, its value is 1, and for all other positive integer arguments, its value is the sum of its values for the two preceding arguments. We would like to write a procedure to compute Fibonacci, and in particular see how it gives rise to a different kind of behavior. Slide 4.2.2 To solve this problem, let's use our tool of wishful thinking. Here, that wishful thinking says, let's assume that given an argument n, we know how to solve Fibonacci for any smaller sized argument. Using that idea, we can then work out a solution to the problem. With this in hand, it is clear that the solution to the general problem is just to solve two smaller sized problems, then just add the results together. Note that in this case we are using wishful thinking twice, not once, as in our previous examples. Here is a procedure that captures this idea. First, we introduce a new expression, called a cond expression. Cond uses the following rules of evaluation. The cond consists of a set of clauses, each of which has within it, a predicate clause, and one or more subsequent expressions. Cond proceeds by first evaluating the predicate of the first clause, in this case (= n 0). If it is true, then we evaluate in turn each of the other expressions in this clause, returning the value of the last one as the value of the whole cond. In the case of the first clause of this cond that is the expression 0. If the predicate of the first clause is false, we move to the next

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology clause of the cond and repeat the process. This continues for however many clauses are contained in the cond until either a true predicate is reached or we reach a clause with the special keyword e lse. In this latter case, that predicate is treated as true, and the subsequent expressions are evaluated Given that form for cond, we can see how our fibonacci procedure captures the idea we expressed. We keep recursively solving smaller sized problems until we get to a base case. Notice that here we have two base cases. not one Also notice that while this is a recursive procedure, it is different from our earlier ones. Here, there are two recursive calls to the procedure in the body, rather than just one. Our question is whether this leads to a different kind of behavior, or a different order of growth Slide 4.2.3 A tree recursion This does give rise to a different kind of behavior, which we can easily see with the illustrated diagram. To solve a problem of size 4, notice that we have to solve two problems, one of size 3 and one of size 2, and each of these requires solving two smaller problems, and so on This gives rise to a kind of tree of things we have to do, and Fib 1 Fib each recursive call gives rise to two subproblems of smaller size. This leads to a different order of growth Fib1 Fib o 6001 sICP Orders of growth for Fibonacci Slide 4.2.4 Let ta be the number of steps that we need to take to solve the case o measure the order of growth, let,'s let t of n denote the for size n. Then number of time steps we need to solve a problem of size n t=tnt+t,2=25,2=454=8 From our tree. we see that to do this we need to solve In space, we have one defered operation for cach increment of the problem of size n-1, and a problem of size n-2.We could stack of -e(n)-linear actually work out a detailed analysis of this relationship, but for our purposes, we can approximate this as roughly the same as solving two problems of size n-2. Expanding a step further, this is roughly the same as solving 4 problems of size n-4 and roughly the same as solving 8 problems of size n-6. A little I math shows that in general this reduces to 2 to the power of n/2 This is an example of an exponential order of growth, and this is very different from what we saw earlier. To convince yourself of this, assume that each step takes one second and see how much time it would take for an exponential process as compared to a linear one, as n gets large In terms of space, our tree shows us that we have basically one deferred operation for step, or in other words, the maximum depth of that tree is linear in the size of the problem, and the maximum depth exactly captures the maximum number of deferred operations 6.001 Notes: Section 4.3

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. clause of the cond and repeat the process. This continues for however many clauses are contained in the cond until either a true predicate is reached, or we reach a clause with the special keyword else. In this latter case, that predicate is treated as true, and the subsequent expressions are evaluated. Given that form for cond, we can see how our fibonacci procedure captures the idea we expressed. We keep recursively solving smaller sized problems until we get to a base case. Notice that here we have two base cases, not one. Also notice that while this is a recursive procedure, it is different from our earlier ones. Here, there are two recursive calls to the procedure in the body, rather than just one. Our question is whether this leads to a different kind of behavior, or a different order of growth. Slide 4.2.3 This does give rise to a different kind of behavior, which we can easily see with the illustrated diagram. To solve a problem of size 4, notice that we have to solve two problems, one of size 3 and one of size 2, and each of these requires solving two smaller problems, and so on. This gives rise to a kind of tree of things we have to do, and each recursive call gives rise to two subproblems of smaller size. This leads to a different order of growth. Slide 4.2.4 To measure the order of growth, let's let t of n denote the number of time steps we need to solve a problem of size n. From our tree, we see that to do this, we need to solve a problem of size n-1, and a problem of size n-2. We could actually work out a detailed analysis of this relationship, but for our purposes, we can approximate this as roughly the same as solving two problems of size n-2. Expanding a step further, this is roughly the same as solving 4 problems of size n-4 and roughly the same as solving 8 problems of size n-6. A little math shows that in general this reduces to 2 to the power of n/2 steps. This is an example of an exponential order of growth, and this is very different from what we saw earlier. To convince yourself of this, assume that each step takes one second, and see how much time it would take for an exponential process as compared to a linear one, as n gets large. In terms of space, our tree shows us that we have basically one deferred operation for step, or in other words, the maximum depth of that tree is linear in the size of the problem, and the maximum depth exactly captures the maximum number of deferred operations. 6.001 Notes: Section 4.3

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 4.3.1 Lets take another quick look at how we can create procedures Using different processes for the same goal ith different orders of growth to compute the same function We want to compute a b, just using multiplication and As a specific example, suppose we want to compute exponentials, such as a raised to the b power but to do so only using the simpler operations of multiplication and addition How might we use the tools we have been developing to accomplish this? Using different processes for the same goal Slide 4.3.2 We want to compute a b, just using multiplication and So, recall the stages we used to solve problems like this:w will use some wishful thinking to assume that solutions to Remember our stages: Wishful thinking simpler versions of the problem exist; we will then decompose the problem into a simpler version of the same problem, plus some other simple operations, and we will use this to construct a solution to the more general problem; and finally, we will determine the smallest sized subproblem into which we want to do decomposition. Let's look at using these tools on the problem of exponentiation 6001 SICP Slide 4.3.3 Using different processes for the same goal wishful thinking is our tool for using induction. It says, let's assume that some procedure my-expt exists, so that we can. Assume that the procedure my-expt exists, but only use it, but that it only solves smaller versions of the same solves smaller versions of the same problem problem Using different processes for the same goal Slide 4.3.4 Wishful thinking Given that assumption, we can then turn to the tricky part, Assume that the procedure mry-expt exists, but only which is determining how to decompose the problem into a soles smaller versions of the same problem simpler version of the same problem Decompose problem into soking smaller version and using Here is one method: Notice that a to the power b result b=a*a*,*a=a*a^{b-1 mathematically is just b products of a. But this we can also group as a times b-l products of a, and that latter we ecognize as a smaller version of the same exponentiation problem. Thus, we can reduce a to the bth power as a times 1001 SICP I to the b-1st power. Thus we can reduce the problem to a simpler version of the same problem, together with some simple operations, in this case, an additional multiplication