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 (<predicate <consequent <consequent> solution to the general problem is just to solve two smaller sized problems, then just add the results together. Note that in Else <consequent><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 next6.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