6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 4.1 Slide 4.1.1 Today ' s topics In this lecture, we are going to take a careful look at the kinds of procedures we can build. We will first go back to look ver Orders of growth of processes carefully at the substitution model, to see how the rules for Relating ty pes of procedures to different orders of growth evaluation help us determine the evolution of a process controlled by a procedure. We will then see how different kinds of process evolution can occur, with different demands in terms of computational resources. And we will see how to characterize those differences formally in terms of orders of growth of a process. Finally, we will explore examples of procedures from different classes of growth, helping you to 8w203 60015e egin to relate how choices in procedure design may affect performance of the actual use of the procedure Rules for evaluation Slide 4.1.2 Now that we have seen two different implementations of the ame idea, with different behaviors, we need a way of more formally characterizing why that difference occurs. To do that we are going to go back to our substitution model Now we are going to think of our model as a set of rewrite es. that set of rules that formally specify, given expression of a particular form, rewrite it in the following form Slide 4.1.3 Rules for evaluation So elementary expressions in this viewpoint are just "left Elementary expressions are left alone: Elementary expressions are alone, that is, numbers, names of built-in procedures, and lambda expressions are left as is ambda expressions. naming procedures iial names of primitive procedures6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 4.1 Slide 4.1.1 In this lecture, we are going to take a careful look at the kinds of procedures we can build. We will first go back to look very carefully at the substitution model, to see how the rules for evaluation help us determine the evolution of a process controlled by a procedure. We will then see how different kinds of process evolution can occur, with different demands in terms of computational resources. And we will see how to characterize those differences formally in terms of orders of growth of a process. Finally, we will explore examples of procedures from different classes of growth, helping you to begin to relate how choices in procedure design may affect performance of the actual use of the procedure. Slide 4.1.2 Now that we have seen two different implementations of the same idea, with different behaviors, we need a way of more formally characterizing why that difference occurs. To do that, we are going to go back to our substitution model. Now we are going to think of our model as a set of rewrite rules, that is, as a set of rules that formally specify, given an expression of a particular form, rewrite it in the following form. Slide 4.1.3 So elementary expressions in this viewpoint are just "left alone", that is, numbers, names of built-in procedures, and lambda expressions are left as is