6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 6.2.1 So why bother with types? We are going to see that they are What is procedure abstraction? very useful in helping us reason about procedures, to catch errors and to deduce what kinds of inputs and outputs different (5757) procedures that we create must have Ckk) In the rest of this lecture, we are going to explore how we capture complex patterns in procedures, using types to help reason things through To do this, let's go back to the basic idea of a procedure, which was to capture some common pattern of computation. For example, here are three expressions that have a common pattern, that of multiplying a value by itself. We know that this 4 6001S is a common pattern, and we would like to be able to refer to it using a name. To do this, we first need to capture this pattern of computation in a procedure abstraction Slide 6.2.2 What is procedure abstraction? and here is how we do that. We create a lambda. with a formal Capture a common pattern parameter to capture the part of the expression that can change (5757) and with a body that actually specifies the common pattern, using the formal parameter as a place holder for input values. The key lambda(x)( xx) point is that this lambda expression captures that common pattern so that we can reuse it many times ctual pattern mal parameter tor pattern Slide 6.2.3 Once we have captured that common pattern, we want to be ableWhat is procedure abstraction? to refer to it, so we give a name to the procedure Capture a common pattern (22) (5757) (lambda(x)(x x)) ctual pattern Give it a name (define square (lambda(x)(Xx))) Slide 6.2.4 What is procedure abstraction? And note that now we can specify the type of this procedure, in Capture a common pattern this case a procedure that takes a single number as input, and (22) returns a number as its value (5757) Ckk ctual pattern Give it a name (define square(lambda(x)(xx))) Note the type: number number
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 6.2.1 So why bother with types? We are going to see that they are very useful in helping us reason about procedures, to catch errors and to deduce what kinds of inputs and outputs different procedures that we create must have. In the rest of this lecture, we are going to explore how we can capture complex patterns in procedures, using types to help us reason things through. To do this, let's go back to the basic idea of a procedure, which was to capture some common pattern of computation. For example, here are three expressions that have a common pattern, that of multiplying a value by itself. We know that this is a common pattern, and we would like to be able to refer to it using a name. To do this, we first need to capture this pattern of computation in a procedure abstraction. Slide 6.2.2 ... and here is how we do that. We create a lambda, with a formal parameter to capture the part of the expression that can change, and with a body that actually specifies the common pattern, using the formal parameter as a place holder for input values. The key point is that this lambda expression captures that common pattern so that we can reuse it many times. Slide 6.2.3 Once we have captured that common pattern, we want to be able to refer to it, so we give a name to the procedure. Slide 6.2.4 And note that now we can specify the type of this procedure, in this case a procedure that takes a single number as input, and returns a number as its value
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 6.2.5 So the key idea in procedure abstraction is to capture a common Other common patterns pattern, give it a name, then use that name as if it were a primitive +2++100=(100"10 operation, without having to worry about the details of how that +9+…+1002=(100·101201)0 1+132+152+…+11012=m218 concept is computed. Thus, for example, we now have the notion of squaring, and we can use square as if it were a basic operation Let's take the idea of capturing common patterns and push on it Here are three expressions from mathematics, adding up the integers, adding up the square of the integers(notice that we have used the concept of squaring here as a primitive )and adding up the recipricals of the odd squares. Note that the last expression is interesting, as it gives us a pretty good approximation to pi Slide 6.2.6 Other common patterns We can easily write procedures to compute these expressions 1+2+…+100=(100101y2 Each has the form we expect. For example, the first procedure has 1002=(100·1012016 1+132+152+…+11012=2 a nice recursive structure in which we add the value of the input parameter a to whatever we get by summing the rest of the e(sum-integers a b) [if p a b) integers from a+ l to b. The other procedures similarly use the idea of reducing a problem to a simpler version of the same define(sum-squares a b) problem, plus a simple operation. Notice how we have already incorporated the abstraction of square, burying the details of how (+1 a)b) it is computed behind the procedural abstraction we just built (pi-sum(+a 2)b)))) 6001 ScP Slide 6.2.7 If we stop here, however, we haven, t quite captured all of the Other common patterns common pattern here. In particular, each of these three mathematical expressions is a summation, that is, a pattern in 100·101·201)一 1+132+152+ which we add up a series of values, starting from some specified point, ending at some specified point, with some method of sum-integers a b incrementing our place, and with some particular thing that we sum"at each stage. In fact, the mathematicians have notation for this the summation notation shown Note that this is more than just a convenient notation. The idea of n-squares (+1 a)b)l) summation is a general pattern that we would like to capture, the (+(1(square a) same way the mathematicians have (pl-sum(+ a 2)b)))) Slide 6.2.8 Other common patterns If we look at our procedures, we can see that there clearly is a 1+2++ common pattern to them. Here are highlights for the two things 1+4+9+…+1002=(100·101·201)6 1+132+152+…+11012=2 that are different in these procedures. There is the term that w Ee add at each stage, shown in red, and there is the way in which we (if p a b) move to the next value in the sequence, shown in green. Now, how did we go from(22)or(aa)to the idea of squaring? We gave a name to each part of the pattern that was going to have to change, and we capture the pattern in a define(pi-sum a b] that parameter. Let's do the same thing here. We ripasamys m m 4.the next stage in the procedure, and of course the two existing parameters, a and b. Let's now capture the commonality of this computation in a procedure that uses these parameters
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 6.2.5 So the key idea in procedure abstraction is to capture a common pattern, give it a name, then use that name as if it were a primitive operation, without having to worry about the details of how that concept is computed. Thus, for example, we now have the notion of squaring, and we can use square as if it were a basic operation. Let's take the idea of capturing common patterns and push on it. Here are three expressions from mathematics, adding up the integers, adding up the square of the integers (notice that we have used the concept of squaring here as a primitive) and adding up the recipricals of the odd squares. Note that the last expression is interesting, as it gives us a pretty good approximation to pi. Slide 6.2.6 We can easily write procedures to compute these expressions. Each has the form we expect. For example, the first procedure has a nice recursive structure in which we add the value of the input parameter a to whatever we get by summing the rest of the integers from a+1 to b. The other procedures similarly use the idea of reducing a problem to a simpler version of the same problem, plus a simple operation. Notice how we have already incorporated the abstraction of square, burying the details of how it is computed behind the procedural abstraction we just built. Slide 6.2.7 If we stop here, however, we haven't quite captured all of the common pattern here. In particular, each of these three mathematical expressions is a summation, that is, a pattern in which we add up a series of values, starting from some specified point, ending at some specified point, with some method of incrementing our place, and with some particular thing that we "sum" at each stage. In fact, the mathematicians have notation for this, the summation notation shown. Note that this is more than just a convenient notation. The idea of summation is a general pattern that we would like to capture, the same way the mathematicians have. Slide 6.2.8 If we look at our procedures, we can see that there clearly is a common pattern to them. Here are highlights for the two things that are different in these procedures. There is the term that we add at each stage, shown in red, and there is the way in which we move to the next value in the sequence, shown in green. Now, how did we go from (* 2 2) or (* a a) to the idea of squaring? We gave a name to each part of the pattern that was going to have to change, and we capture the pattern in a procedure using that parameter. Let's do the same thing here. We will need a parameter for the term to be added in, a parameter for the next stage in the procedure, and of course the two existing parameters, a and b. Let's now capture the commonality of this computation in a procedure that uses these parameters
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 6.2.9 So here is the procedure, with those four parameters. All I have Other common patterns ∑ done is substitute the formal parameter for the right spot in the +2++100=(100"10 pattern of the computation, which forms the body of this 1+4+9++100=(100·101201)6 1+132+152+…+11012=m218 procedure. But this looks a little different from things we have seen before so let's look more carefully at this in the next slide (a(sum-integers(+1 a)bIll (detine(sum term a next b) (if( a b) Slide 6.2.10 Let's check this new procedure out Up to this point, every procedure we have written has expected a (define (sum term a nex b) primitive object as a parameter, typically a number. This (Ir(e a b) procedure is different, however. We can see from where the (+(term a) parameters term and next appear in the body of the procedure (sum term(next a) next b)))) that this procedure expects these parameters to be themselves What is the type of this procedure? Does this really work? Well, what is the type of this procedure? 6001 SICP Slide 6.2.11 y using the same kind of reasoning we did earlier, we can see Let' s check this new procedure out! that this procedure requires four input parameters, and the output deine (sum b) value must be a numbers, since both clauses of the if expression ir( a b) should return a numb 0 What is the type of this procedure? ber→ number, number, number→ number, number)→ number 1 001 SICP Slide 6.2.12 Let's check this new procedure out And what are the inputs? Well, the first parameter is used in a (define (sum term a nex b) place that expects a procedure. That procedure has one input that (ir(a b) we will shortly see is a number, and it must produce a number (+(term a output, as that value will be used by the addition operation. The term(next a) next b)))) second parameter we can see must be a number, since we are going to use the greater than operation on it. Thus, we see the inumber* number, number, number> number, number + number formalism for the first two inputs to sum, a procedure mapping numbers to numbers and a number 1001 SICP
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 6.2.9 So here is the procedure, with those four parameters. All I have done is substitute the formal parameter for the right spot in the pattern of the computation, which forms the body of this procedure. But this looks a little different from things we have seen before so let's look more carefully at this in the next slide. Slide 6.2.10 Up to this point, every procedure we have written has expected a primitive object as a parameter, typically a number. This procedure is different, however. We can see from where the parameters term and next appear in the body of the procedure that this procedure expects these parameters to be themselves procedures! Does this really work? Well, what is the type of this procedure? Slide 6.2.11 By using the same kind of reasoning we did earlier, we can see that this procedure requires four input parameters, and the output value must be a numbers, since both clauses of the if expression should return a number. Slide 6.2.12 And what are the inputs? Well, the first parameter is used in a place that expects a procedure. That procedure has one input that we will shortly see is a number, and it must produce a number as output, as that value will be used by the addition operation. The second parameter we can see must be a number, since we are going to use the greater than operation on it. Thus, we see the formalism for the first two inputs to sum, a procedure mapping numbers to numbers, and a number