6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 6.1 Slide 6.1.1 Types When we first starting talking about Scheme expressions, you may recall we said that(almost )every Scheme expression had three components, a syntax (legal ways of gluing things together ) a semantics(a way of deciding the meanin associated with an expression), and a type. We haven't said much about types yet. Today we are going to look in more detail at types, and especially how we can use types to design procedures with different kinds of behaviors 60015e Types Slide 6.1.2 So let's motivate the idea of a type. Consider the following two examples. The first expression we know will correctly add the i The object hi", passed as the first argument to integer-add not the correct two numbers to get 15. The second expression we expect to type give an error, since while we may like to get "high fives",we know that we can't add a string to a number, as addition is only used on numbers Note what this implies. It suggests that the addition procedure has associated with it an expectation of what kinds of arguments it will get, in particular an expectation about the type of each argument, in this case, numbers Slide 6.1.3 perform its job since it was not given what it expected an of an/Types And here, since we have given a string as an input, instead (+510)=>1 integer, the procedure should complain, stating that it ca i The object"hi", passed as the first argument to integer-add, is not the correct Addition is not defined for strings
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 6.1 Slide 6.1.1 When we first starting talking about Scheme expressions, you may recall we said that (almost) every Scheme expression had three components, a syntax (legal ways of gluing things together), a semantics (a way of deciding the meaning associated with an expression), and a type. We haven't said much about types yet. Today we are going to look in more detail at types, and especially how we can use types to design procedures with different kinds of behaviors. Slide 6.1.2 So let's motivate the idea of a type. Consider the following two examples. The first expression we know will correctly add the two numbers to get 15. The second expression we expect to give an error, since while we may like to get "high fives", we know that we can't add a string to a number, as addition is only used on numbers. Note what this implies. It suggests that the addition procedure has associated with it an expectation of what kinds of arguments it will get, in particular an expectation about the type of each argument, in this case, numbers. Slide 6.1.3 And here, since we have given a string as an input, instead of an integer, the procedure should complain, stating that it can't perform its job since it was not given what it expected
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<A>=PairsA List<A> 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 © 2004 by Massachusetts Institute of Technology. Slide 6.1.7 We have now seen that for procedures we can also associate a type. In particular, we can specify for a procedure that it expects a particular number of arguments, and each argument is expected to be of a particular type. Moreover, the procedure's 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. Slide 6.1.8 So we can denote this as shown, indicating the number and type of arguments, or inputs, and the type of output of a procedure. This type declaration states that this procedure maps two numbers to a number. Slide 6.1.9 This means we can now talk about the types associated with simple expressions, and to procedures. Here are some examples. Note that square, which we defined earlier, is a procedure that takes one input, a number, and produces a number as output. The primitive > is a predicate that takes two numbers 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). Slide 6.1.10 Thus, the type associated with a procedure specifies a kind of contract. It states the number and type of inputs, and basically guarantees that a particular type of output will be returned given those types of inputs, but says "all bets are off" if the types of the inputs are incorrect. Note that it does not guarantee that the correct answer is returned, only that the correct type of answer will be returned. Many languages require that the programmer explicitly state this contract. In strongly typed languages, the programmer 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 © 2004 by Massachusetts Institute of Technology. Slide 6.1.14 For the second example, we also know it is a procedure, due to the lambda. For the input argument, we can see that it must be an expression whose value is a boolean, since if expects such a value as the value of its predicate. The return value of this procedure must be a string, since both the consequent and alternative clauses return strings. Slide 6.1.15 And of course the last expression is just an expression whose type is a number. Slide 6.1.16 So to summarize: a type is a set of values that characterizes a set of things that belong together, due to common behavior. And virtually every expression in Scheme has a value that has a 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 of the returned value. As we are going to see, types provide a very nice mathematical framework for reasoning about programs. First, they can provide a basis for preventing common errors in our code: if we know that a procedure expects a particular type of argument we can 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 helping us design other procedures, by providing a framework for understanding how values are passed between procedures. In the rest of this lecture, we are going to use this idea to explore how we can create complex, but powerful, procedures that manipulate a wide range of information beyond simple numbers. 6.001 Notes: Section 6.2