《Structure and Interpretation of Computer Programs》lecture 6 webhand.pdf_大学文库

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 6.1. 4 Types- simple data So now let's formalize this idea. We want to assign a type to irtually every kind of We have already seen some basic primitives: numbers, which -Number are a type; strings, another type; booleans, a third type; and symbols or names for things, to which we will be returning in a few lectures. For some things, like numbers, we could actually Boolean be more specific, for example distinguishing integers from real numbers As we saw with our motivating example, we typically want to know the type of a data structure in order to decide if some I procedure is appropriate to apply to that type. These basic primitive data types will usually be sufficient to handle the Slide 6.1.5 Types-compound data For compound data, we saw that the basic element was a pair, Pairs, B> and we have a type notation to denote one. Note that we A compound data structure formed by a cons pair, in include in this notation a specification of the types of the type B: e.g(cons 1 2)has type Pairs elements within the pair List=PairsA List or nil> We also saw that we could construct a list out of pairs. So we A compound data structure that is recursively defined can create a type notation for that as well. In essence we are s a pair, whose first element is of type A, and whose second element is either a list of type A or the empty creating a formal definition for a list: we specify that this compound data structure is recursively defined as a pair, whose E.g.(list 1 2 3)has type List snumber?: while( list 1 first element is of some type A, and whose second element is either another list or is the empty list. This exactly reflects the 60015c description we gave when we introduced lists Note that in our type specifications, we can include the possibility of alternative types of elements, as shown in the example Types-procedures Slide 6.1.6 Since procedures operate on objects, and return values, Now, we dont just have data structures in our language, we have procedures that operate on them. So we want to identify We will denote a procedures type by indicating the types of different types of procedures as well. We will do this by plus the symbol] to indicate that the arguments are creating a notation that indicates the number of arguments to a E.g.numbernumber specifies a procedure that takes a procedure, the type of each, and the type of the value returned mapped to the return value number as input, and returns a number as value by the procedure. For example, number maps to number would indicate a procedure that takes a single number as input and returns a number as output

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 6.1.4 So now let's formalize this idea. We want to assign a type to virtually every kind of expression in our language. We have already seen some basic primitives: numbers, which are a type; strings, another type; booleans, a third type; and symbols or names for things, to which we will be returning in a few lectures. For some things, like numbers, we could actually be more specific, for example distinguishing integers from real numbers. As we saw with our motivating example, we typically want to know the type of a data structure in order to decide if some procedure is appropriate to apply to that type. These basic primitive data types will usually be sufficient to handle the cases we will see. Slide 6.1.5 For compound data, we saw that the basic element was a pair, and we have a type notation to denote one. Note that we include in this notation a specification of the types of the elements within the pair. We also saw that we could construct a list out of pairs. So we can create a type notation for that as well. In essence we are creating a formal definition for a list: we specify that this compound data structure is recursively defined as a pair, whose first element is of some type A, and whose second element is either another list or is the empty list. This exactly reflects the description we gave when we introduced lists. Note that in our type specifications, we can include the possibility of alternative types of elements, as shown in the example. Slide 6.1.6 Now, we don’t just have data structures in our language, we have procedures that operate on them. So we want to identify different types of procedures as well. We will do this by creating a notation that indicates the number of arguments to a procedure, the type of each, and the type of the value returned by the procedure. For example, number maps to number would indicate a procedure that takes a single number as input and returns a number as output

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 6.1.7 We have now seen that for procedures we can also associate aTypes type. In particular, we can specify for a procedure that it expects a particular number of arguments, and each argument is(th a - 50 hi", passed as the first expected to be of a particular type. Moreover, the pre s argument to integer-add, is not the correct output is also of a particular type. And going back to our original example, we know that integer addition has a particular expectation on the types of arguments The type of the integcr-add procedure is number,number)number Types (+510)=15 So we can denote this as shown, indicating the number and type f arguments, nd the type of output of a procedu i The object " hi", passed as the first argument to integer-a dd, is not the correct This type declaration states that this procedure maps two numbers to a number The type of the integer-add number, number) number result value of integer-add both numbers s a number 6001 SICP rne Slide 61.9 This means we can now talk about the types associated with evaluates to a value of type simple expressions, and to procedures. Here are some examples. Note that square, which we defined earlier, is a strin procedure that takes one input, a number, and produces a number > number number as output. The primitive is a predicate that takes two lumbers as input, and returns a true or false value hence a boolean, as output(true if the first number is greater than the second one) 4 Type examples Slide 6.1.1o evaluates to a value of typ Thus, the type associated with a procedure specifies a kind of contract. It states the number and type of inputs, and basically h⊥ (> 54)-/ humber, number >boolean those types of inputs, but says"all bets are off" if the types or string guarantees that a particular type of output will be returned give square number number the inputs are incorrect .The type of a procedure is a contra Note that it does not guarantee that the correct answer If the operands have the specified types. returned, only that the correct type of answer will be returned the procedure will result in a value of the specified type Many languages require that the programmer explicitly state maybe an error, maybe random behavior this contract. In strongly typed languages, the programmer 1001 SICP I must specify at time of definition the types of inputs and the type of output. This allows the system to catch errors and help the programmer with debugging but restricts the flexibility of

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology the procedures Scheme is a weakly typed language, meaning that the programmer does not specify the types of inputs and outputs. Thus, errors will not be caught until run-time, which can make debugging harder, but the programmer tends to have more flexibility in creating procedures. Even in a weakly typed language, a good programmer will take advantage of the discipline of type analysis Slide 6l.ll Types, precisely More formally, we see that a type actually describes many A type describes a set of scheme values procedures, basically any procedure that maps the specified number> number describes the set number and type of inputs to the specified type of output all procedures, whose result is a numbe We also see that not only does every Scheme value have a type, which require one argument that must be a number but that in some cases, a value may be described by several types(for example an integer is also a kind of number) .When Every scheme value has a type Some values can be described by multiple types this happens, we will typically choose the type which describes If so, choose the type which describes the largest set the largest set of objects as our designated type. Thus, for example, addition maps two integers to an integer, but it also Special form keywords like define do not name values therefore special form keywords have no type maps two numbers (including real numbers )to a number, so we 6001SC would use this latter type as our specification for addition Finally, note that some special forms do not name values, and hence do not have a type associated with them Your turn Slide 6.1.12 The following expressions evaluate to values of what type? Let's see if you are getting this. Here are three example expressions. If evaluate each of them, you will get some (lambda (a b e)(if(>a o)(+ b e) (- b a))) Scheme object, and you should be able to reason through to determine the type of that returned value. When you are ready to see the answers, go to the next slide (lambda (p) (if p hi "."bye") (3.14(*25) Slide 6.1.13 Your turn We know that the type of the first expression should be a procedure, since we know that lambda will create a procedure The following expressions evaluate to values of what type? We also know that the number of arguments for this procedure (lambda (a b c) (if(>a o)(+ b c)(-b a)) 3. In terms of the types of the arguments, we can see that the number, number, numbe number first one must be a number, since greater than expects a number as argument. The other two arguments must also be numbers, (lambda (p) (if p hi""bye") since they are used with procedures that take numbers as input Finally, the value returned by this procedure is a number, since (*3.14(25)) both the consequent and the alternative clauses of the if expression return numbers. Hence, we have the type declaration 4 shown here, a procedure that maps three numbers to a number

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. the procedures. Scheme is a weakly typed language, meaning that the programmer does not specify the types of inputs and outputs. Thus, errors will not be caught until run-time, which can make debugging harder, but the programmer tends to have more flexibility in creating procedures. Even in a weakly typed language, a good programmer will take advantage of the discipline of type analysis. Slide 6.1.11 More formally, we see that a type actually describes many procedures, basically any procedure that maps the specified number and type of inputs to the specified type of output. We also see that not only does every Scheme value have a type, but that in some cases, a value may be described by several types (for example an integer is also a kind of number). When this happens, we will typically choose the type which describes the largest set of objects as our designated type. Thus, for example, addition maps two integers to an integer, but it also maps two numbers (including real numbers) to a number, so we would use this latter type as our specification for addition. Finally, note that some special forms do not name values, and hence do not have a type associated with them. Slide 6.1.12 Let's see if you are getting this. Here are three example expressions. If evaluate each of them, you will get some Scheme object, and you should be able to reason through to determine the type of that returned value. When you are ready to see the answers, go to the next slide. Slide 6.1.13 We know that the type of the first expression should be a procedure, since we know that lambda will create a procedure. We also know that the number of arguments for this procedure is 3. In terms of the types of the arguments, we can see that the first one must be a number, since greater than expects a number as argument. The other two arguments must also be numbers, since they are used with procedures that take numbers as input. Finally, the value returned by this procedure is a number, since both the consequent and the alternative clauses of the if expression return numbers. Hence, we have the type declaration shown here, a procedure that maps three numbers to a number

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 6.114 Yo For the second example, we also know it is a procedure, due to The following expressions evaluate to values of what type? the lambda. For the input argument, we can see that it must be (lambda (a b c)(f(>a o)(+ b c)(-b c)) an expression whose value is a boolean, since i f expects such a value as the value of its predicate The return value of this number, number, number- number procedure must be a string, since both the consequent and (lambda (p) (if p hi ""bye") alternative clauses return strings Boolean (3.14(*25) Slide 6.1.15 Your tur And of course the last expression is just an expression whose The following expressions evaluate to values of what type? type is a number (lambda (a b c)(if(>a o)(+ bc)(-b c))) number, number, number number (lambda (p) (if p hi""bye") Boolean st2⊥n (*3.14(25) number End of part 1 Slide 6.1.1 type: a set of values So to summarize: a type is a set of values that characterizes a every value has a type set of things that belong together, due to common behavior procedure ty pes(types which include >)indicate And virtually every expression in Scheme has a value that has a number of arguments required type associated with it Of particular interest to us are procedures, which we can also type, based on the number and type of arguments, and the type Types: a mathematical theory for reasoning efficiently of the returned value about pr。 grams As we are going to see, types provide a very nice mathematical basis for many analysis and optimization algorithms framework for reasoning about programs. First, they can I provide a basis for preventing common errors in our code if we an use this to ensure that other procedures or expressions supply the correct kind of input. Second, we are about to see how types of procedures can serve as a key tool in procedures. In the rest of this lecture, we are going to use this idea to explore how we can create complex, blr s helping us design other procedures, by providing a framework for understanding how values are passed betwee powerful, procedures that manipulate a wide range of information beyond simple numbers 6.001 Notes: Section 6.2

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 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 o 2004 by Massachusetts Institute of Technology Slide 6.2. 13 The same reasoning helps us deduce the form for the third Lets check this new procedure out! parameter(a procedure mapping numbers to numbers) for the (define (sum term a nex b) fourth parameter(a number) (+(term a) (sum term (next a) next b)))) What is the type of this procedure? aber] number, number umber?number number)?number Slide 6.2.14 Let's check this new procedure out and overall this procedure, sum, will return a number, since (define (sum term a nex b) both clauses of the if expression that forms the body of the (Ir(e a b) procedure must return a number (+(term a) Thus we can characterize the type of this new procedure, sum. It (sum term(next a) next b))) just happens that some of the parameters for this procedure are What is the type of this procedure? themselves proced ures number number→ number 6001 SICP Slide 6.2.15 o this is a new kind of beast, which we call a higher order Higher order procedures procedure. It is a procedure that takes as inputs other procedures,I. A higher order procedur and it may, as we will see, also return a procedure as its returned takes a procedure as an argument or returns one as a value tsun (lambda (x) x) a(lambda (x) ( x 1))b) square, or they may be pure lambda expressions. In either o Note that those input procedures may be named procedures, like (define (sun-squares1 a b) a(1 anda《x)什x1))b)) (define (pi- case, we know that the value of the expression will be a procedure oda lambda object that can then be substituted into the body of sum And now we see that we have captured the common pattern of summation, and that our three earlier expressions are just special versions of this general computation 1 001 SICP Does this really work? Well, just use the substitution model to check that procedures get substituted in the right places in the body of sum and that as a consequence the three expressions shown here will compute the appropriate series of terms 6.001 Notes: Section 6.3

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 6.3.1 So we have now seen how procedures can be passed in as Computing derivatives arguments to other procedures. But we can also have procedures return procedures as values Where might that be f:x→x2 f Df:x→>2x Well here is a simple mathematical example. What is a derivative? First, we know that given some function f, such as We can easily write f in either case (define f (lambda(x)(x xx))) the two shown here, there are standard rules for finding the But what is D2? derivative of f which we denote Df as shown We can easily write down a procedure to compute f, but what is )? In particular, can we write a procedure for D that would take the derivative of any function? Computing derivatives Slide 6.3.2 So what do we know about this beast? Well, it needs to map a f: f:x→x3 function to another function, or said slightly differently, it needs Df x→)2x Df:x→3x2 to take as input any procedure that represents a numerical function, and it needs to return a procedure with the property that applying that returned procedure to any value will give us a maps a function(or procedure)to a different function good approximation to the derivative of the original function at that value D(x)≈/(x+a)-f Numerically the equation shown will do a decent job for us 48 6001 SICP Slide 6.3.3 Computing derivatives o how do we then capture the idea of D? Well, here it is Look carefully at the form Deriv takes one argument, which we f:x> x→ see must be a procedure of one numerical argument. Inside the body of the lambda associated with deriv is a second lambda D(x)=(x+)f(x) This is also a procedure of one numerical argument, that returns(define deriv a numerical value lambda (n) So the type of this procedure is as shown (lambda(x)(((f (+ x epsilon))(f x)) epsilon))) 60015 Using Slide 6.3. 4 M(yy) Now does this make sense? Sure (define ensile Suppose we define square as shown, and we take the derivative Notice the nested parentheses: the first compound ambda(x)t( lambda的)yy》( x epsilon ambda的)ryy》x) subexpression should return a procedure as a value, for this to make sense. And to see that it does. use the substitution model We substitute the value of square everywhere in the body of C(((ambda b)t yy))(+ 5 epsilon)) deriv that we see the formal parameter f. The mess that we get da bCyyn5)) tly that Now, if we complete the process, we substitute 5 for x, which 10001 me reduces to an expression similar to those we have seen before So we see that this kind of higher order procedure also has a

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 6.3.1 So we have now seen how procedures can be passed in as arguments to other procedures. But we can also have procedures return procedures as values. Where might that be useful? Well here is a simple mathematical example. What is a derivative? First, we know that given some function f, such as the two shown here, there are standard rules for finding the derivative of f, which we denote Df, as shown. We can easily write down a procedure to compute f, but what is D? In particular, can we write a single procedure for D that would take the derivative of any function? Slide 6.3.2 So what do we know about this beast? Well, it needs to map a function to another function, or said slightly differently, it needs to take as input any procedure that represents a numerical function, and it needs to return a procedure with the property that applying that returned procedure to any value will give us a good approximation to the derivative of the original function at that value. Numerically, the equation shown will do a decent job for us. Slide 6.3.3 So how do we then capture the idea of D? Well, here it is. Look carefully at the form. Deriv takes one argument, which we see must be a procedure of one numerical argument. Inside the body of the lambda associated with deriv is a second lambda. This is also a procedure of one numerical argument, that returns a numerical value. So the type of this procedure is as shown. Slide 6.3.4 Now does this make sense? Sure. Suppose we define square as shown, and we take the derivative. Notice the nested parentheses: the first compound subexpression should return a procedure as a value, for this to make sense. And to see that it does, use the substitution model. We substitute the value of square everywhere in the body of deriv that we see the formal parameter f. The mess that we get does exactly that. Now, if we complete the process, we substitute 5 for x, which reduces to an expression similar to those we have seen before. So we see that this kind of higher order procedure also has a