6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 9.1 Slide 9.1.1 Manipulating complex numbers In the last lecture, we introduced symbols into our language And we showed how to intermix them with numbers to create magnitude mixed expressions. We saw how to use that idea to create a mbolic differentiation program that could reason about algebraic expressions, rather than just numeric expressions. In this lecture, we are going to take the idea of symbols, and combine them with lots of different data structures to create tagged data structures Why do we need a tag?. and what is a tag? We'll answer these questions by considering an example. Suppose I want to build a 6001 SICP system to manipulate complex numbers. Remember that a complex number is a number with two parts, standardly epresented as a real and an imaginary part. Think of these as two axes in a vector space, or as a point in the plane (though we will see that there are special rules for how to manipulate such points that are different from normal vectors) Because we can represent a complex number as a vector, we can also think about representing such numbers in terms of a magnitude(or length) and an angle(typically with respect to the real axis) Manipulating complex numbers Slide 9.1.2 Now, let's assume we have some data abstractions for complex numbers. We have a constructor, and appropriate selectors, Real, imag, mag angle ncluding selectors for both the real and imaginary part, and for he magnitude and angle As we saw earlier, given such constructors and selectors, we can proceed to write code to manipulate complex numbers, without worrying about internal details. So let's do that C001 SICP
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 9.1 Slide 9.1.1 In the last lecture, we introduced symbols into our language. And we showed how to intermix them with numbers to create mixed expressions. We saw how to use that idea to create a symbolic differentiation program that could reason about algebraic expressions, rather than just numeric expressions. In this lecture, we are going to take the idea of symbols, and combine them with lots of different data structures, to create tagged data structures. Why do we need a tag? .. and what is a tag? We'll answer these questions by considering an example. Suppose I want to build a system to manipulate complex numbers. Remember that a complex number is a number with two parts, standardly represented as a real and an imaginary part. Think of these as two axes in a vector space, or as a point in the plane (though we will see that there are special rules for how to manipulate such points that are different from normal vectors). Because we can represent a complex number as a vector, we can also think about representing such numbers in terms of a magnitude (or length) and an angle (typically with respect to the real axis). Slide 9.1.2 Now, let's assume we have some data abstractions for complex numbers. We have a constructor, and appropriate selectors, including selectors for both the real and imaginary part, and for the magnitude and angle. As we saw earlier, given such constructors and selectors, we can proceed to write code to manipulate complex numbers, without worrying about internal details. So let's do that
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 9.1.3 When manipulating complex numbers, I can take advantage ofManipulating complex numbers the fact that some things are easy to do in Cartesian(or real and magnitude Complex number has maginary)coordinates, and some things are easy to do in polar (or magnitude and angle)coordinates. For example, adding two m TRAs o eal, imag. mag, angle complex numbers is most easily conceptualized in Cartesian (define (+e z1 22) coordinates, while multiplying two complex numbers is most Eron-rect ( (real z1)(real easily conceptualized in polar coordinates. Addition is in fact just vector addition, so I use the selectors to get the parts of each (define(+o a 2) complex number, add them together using standard addition, make-comp1ex-Ex。np。1ax《 (nag 32)) (angle z2)))) Here i will need to use a constructor that is making a compler a then glue the two parts together to make a new complex number 6001 SICP number given Cartesian coordinates as input. For multiplication, I will use the polar selectors to get out the parts, so that I can just use normal multiplication on the magnitudes, and normal addition on the angles to get the new components. Here, I will use a constructor to make a new complex number that knows its inputs are provided in p of a data abstraction from its impementation. I can write code that lar coordinates Note once more how we are separating the use uses complex numbers, while assuming that someone else will eventually provide a specific implementation. And note the standard form of such procedures: we use selectors to get out the parts, apply more primitive operations to those parts, then reglue the parts back into a data abstraction Berts data structure Slide 9. 1. 4 While it is convenient to separate data abstraction implementation from data abstraction use, ultimately we will have to provide a detailed implementation, that is, we will need to build the "guts " of this abstraction Suppose we ask our friend Bert to provide an implementation for complex numbers 6001 SICP Slide 9.1.5 Bert's data structure First, Bert will need a way of gluing things together. He decides (define(make-complex-from-rect rl im)(list ni im)) rather naturally, just to use lists to glue pieces together. He still (define(make-complex-from-polar mg an) has a choice, though, and being a rather "square"guy, Bert (ist (mg(cos an)) simply opts to use rectangular coordinates as his basis. That means that Bert's representation of a complex number is as a list of a real and imaginary part Note what this means. If we hand bert a real and imaginary part for a new complex number, he can simply glue them together using list as this directly meets his representation. On the other hand, if we hand Bert a magnitude and angle, he will needd 6001联0 to convert these to real and imaginary equivalents(using the these numbers. Thus, Bert's internal representation is always as a list of real and imaginary part ow he represents appropriate trigonometry)so that he can then make a list of the real and imaginary part, which is
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 9.1.3 When manipulating complex numbers, I can take advantage of the fact that some things are easy to do in Cartesian (or real and imaginary) coordinates, and some things are easy to do in polar (or magnitude and angle) coordinates. For example, adding two complex numbers is most easily conceptualized in Cartesian coordinates, while multiplying two complex numbers is most easily conceptualized in polar coordinates. Addition is in fact just vector addition, so I use the selectors to get the parts of each complex number, add them together using standard addition, then glue the two parts together to make a new complex number. Here I will need to use a constructor that is making a complex number given Cartesian coordinates as input. For multiplication, I will use the polar selectors to get out the parts, so that I can just use normal multiplication on the magnitudes, and normal addition on the angles to get the new components. Here, I will use a constructor to make a new complex number that knows its inputs are provided in polar coordinates. Note once more how we are separating the use of a data abstraction from its implementation. I can write code that uses complex numbers, while assuming that someone else will eventually provide a specific implementation. And note the standard form of such procedures: we use selectors to get out the parts, apply more primitive operations to those parts, then reglue the parts back into a data abstraction. Slide 9.1.4 While it is convenient to separate data abstraction implementation from data abstraction use, ultimately we will have to provide a detailed implementation, that is, we will need to build the "guts" of this abstraction. Suppose we ask our friend Bert to provide an implementation for complex numbers... Slide 9.1.5 First, Bert will need a way of gluing things together. He decides, rather naturally, just to use lists to glue pieces together. He still has a choice, though, and being a rather "square " guy, Bert simply opts to use rectangular coordinates as his basis. That means that Bert's representation of a complex number is as a list of a real and imaginary part. Note what this means. If we hand Bert a real and imaginary part for a new complex number, he can simply glue them together using list as this directly meets his representation. On the other hand, if we hand Bert a magnitude and angle, he will need to convert these to real and imaginary equivalents (using the appropriate trigonometry) so that he can then make a list of the real and imaginary part, which is how he represents these numbers. Thus, Bert's internal representation is always as a list of real and imaginary parts
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 9.1.6 Bert's data structure To complete the representation, Bert just has to ensure that he (define( make-complex-from-rect rl im)(list ri im)) implements selectors that together with the constructors meet (define(make-complex-from-polar mg an) the contract for complex number abstractions For real and (st ( mg(cos an)) C mg(sin an)))) imag parts, this is easy, as we can just rely on the contract for lists For mag and angle, however, we must get out the real (define(imag cx)(cadr cx)) and imaginary parts(since these are the underlying representational pieces )using the appropriate selectors, then (define (angle cx)(atan o(real cx) compute the appropriate values from those parts This then complete Bert's implementation DOt sIcP Slide 9.1.7 Notice that bert made a design choice. He made a decision to Ernie s data structure represent complex numbers by a list of their real and imaginary(define(make-complex-from-rect rl im) (list (sqrt(+(square rl)(square im))) parts. Let's suppose at the same time we also asked Bert's friend (atan im rl))) Ernie, to create an implementation of complex numbers. Since (define( make-complex-from-polar mg an)(list mg an)) Ernie is Canadian he likes cold weather. and thus decides to implement complex numbers in polar form. Thus, his basic representation is a list of magnitude and angle, which means his constructor for polar form is just a list, but if he is given a real and imaginary part, he will first have to convert them to polar form then store those values as a list Ernies data structure Slide 9. 8 (define(make-complex-from-rect rl im) Completing Ernie's task is similar to Berts. For the magnitude (list(sqrt(+(square rl)(square im))) and angle selectors, we can just use the underlying list selectors (atan im rl))) to complete the contract. For selectors for Cartesian coordinates, ( define(make-complex-from-polar mg an)(list mg an)) I we will need to select out the underlying parts, convert using some trigonometry to the appropriate values, and then return 仰(m those values Notice that Ernie's implementation for complex numbers thus also meets the contract for such objects. All that has changed with respect to Bert's implementation is the choice of how to 6001 SICP glue basic components together Slide 9. 1.9 Whose number is it? So far this sounds fine. We have two different implementations of complex numbers, one in Cartesian coordinates and one in uppose we pick up the following object lar coordinates, but both seem to satisfy the contract for data abstraction. what's the big deal? I, suppose we find a complex number lying on the floor, such as the one shown
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 9.1.6 To complete the representation, Bert just has to ensure that he implements selectors that together with the constructors meet the contract for complex number abstractions. For real and imag parts, this is easy, as we can just rely on the contract for lists. For mag and angle, however, we must get out the real and imaginary parts (since these are the underlying representational pieces) using the appropriate selectors, then compute the appropriate values from those parts. This then completes Bert's implementation. Slide 9.1.7 Notice that Bert made a design choice. He made a decision to represent complex numbers by a list of their real and imaginary parts. Let's suppose at the same time we also asked Bert's friend, Ernie, to create an implementation of complex numbers. Since Ernie is Canadian, he likes cold weather, and thus decides to implement complex numbers in polar form. Thus, his basic representation is a list of magnitude and angle, which means his constructor for polar form is just a list, but if he is given a real and imaginary part, he will first have to convert them to polar form, then store those values as a list. Slide 9.1.8 Completing Ernie's task is similar to Bert's. For the magnitude and angle selectors, we can just use the underlying list selectors to complete the contract. For selectors for Cartesian coordinates, we will need to select out the underlying parts, convert using some trigonometry to the appropriate values, and then return those values. Notice that Ernie's implementation for complex numbers thus also meets the contract for such objects. All that has changed with respect to Bert's implementation is the choice of how to glue basic components together. Slide 9.1.9 So far this sounds fine. We have two different implementations of complex numbers, one in Cartesian coordinates and one in polar coordinates, but both seem to satisfy the contract for the data abstraction. What's the big deal? Well, suppose we find a complex number lying on the floor, such as the one shown
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 9.1.10 Whose number is it? then here is the key question. What actual number does this Suppose we pick up the following object object represent? This may sound odd, as after all, it is just a complex number. But suppose this is a complex nu 1+「 by Bert. Then what number would this represen( amber made What number does this represent 0O1 sIcP Slide 9.1.11 Whose number is it? In that case, we know that the first part of this list represents the real part of the number, and the second part of the list represents uppose we pick up the following object the imaginary part. Thus, in this case, this number would correspond to the vector or point shown on the diagram What number does this represent? 4 Whose number is it? Slide 9. 1.12 Suppose we pick up the following object On the other hand, if this were a complex number made by Ernie, we know that the first part of the list is the magnitude and is the angle of the vector. In that this number represents the red vector or point shown on the Thus, we have a problem. Depending on who made the complex number we found, we get a different answer to the question of What number does this represent? what number this is so how do we tell who made it? That is exactly the problem we are raising. Given what we have shown OI SICP "designer"complex numbers let's have the designer of eachate so far, we can't tell. Fortunately the solution is easy. Let's crea kind of complex number sign his work on the back. That means we will have each creator of complex numbers but a label on the object that either says this is a"Bert"or Cartesian number, or this is an"Ernie"or polar number
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 9.1.10 .. then here is the key question. What actual number does this object represent? This may sound odd, as after all, it is just a complex number. But suppose this is a complex number made by Bert. Then what number would this represent? Slide 9.1.11 In that case, we know that the first part of this list represents the real part of the number, and the second part of the list represents the imaginary part. Thus, in this case, this number would correspond to the vector or point shown on the diagram. Slide 9.1.12 On the other hand, if this were a complex number made by Ernie, we know that the first part of the list is the magnitude and the second part of the list is the angle of the vector. In that case, this number represents the red vector or point shown on the diagram. Thus, we have a problem. Depending on who made the complex number we found, we get a different answer to the question of what number this is. So how do we tell who made it? That is exactly the problem we are raising. Given what we have shown so far, we can't tell. Fortunately the solution is easy. Let's create "designer" complex numbers, let's have the designer of each kind of complex number sign his work on the back. That means we will have each creator of complex numbers but a label on the object that either says this is a "Bert" or Cartesian number, or this is an "Ernie" or polar number
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 9.1.13 How do we add a label to our complex numbers? Let's just glue Labeled complex numbers it onto the front We can change our constructor to have the ( define(make-complex-from-rect rl im) following behavior. Given two parts, we will just glue them list ' rect rl im)) together into a list. But if the parts represent real and imaginary ( define( make-complex-from-polar mg an) components, we will put a symbolic label at the front to tell us(define (tag obj)(car obi) this, while if the parts are magnitude and angle, we will still just( define(contents obi) (edr objy glue them together but we'll put a different label at the front to tell us this What else do I need? I'll want a selector to pull the labels off of hese new abstractions, as well as a selector to get out the actual contents of the abstraction Notice the use of cdr in this cased 6001 SCP to get the remaining list of elements from the representation Note that in this case we are not doing any work to convert representations. We just glue the parts together, and put label on it so we know what those parts mean Labeled complex numbers Slide 9.1.14 ( define(make-complex-from-rect rl im To make sure my contract holds, I'll need to adjust my selectors Here is where I am going to bury the work I just saved in (define(make-complex-from-polar mg an constructing numbers. i will have a single selector real that (define(tag obj)(car obj) works with numbers represented in either form. This selector (define(contents obj)(cdr obj)) will first rip the tag off of the number to see who made it. Notice how we use eq? to test equality of symbols, and how we use (cond ((eq?(tag z)rect)(car(contents z))) the selector tag to get out the tag, and how we use the quoted (eq?(tag 2)polan( e lf adr (contents z2):angle symbols to represent the things to check against the tag (else (error "unknown for object ))) If this is in fact a Cartesian number. we use contents to 03P get everything but the tag, then can use car to get the real part since that is where it is stored in this representation, just as Bert did it If this is a polar number, then we have to do the work to convert the underlying representation from polar form to the real part. In this case, contents will get the actual representation, and the car of that list we know is the magnitude of the vector. Similarly the cadr gets us the angle, and we can then do the trigonometry to convert to the real part Thus in this case, my constructor just glues pieces together, with an appropriate label. My selectors use the label to tell me how to interpret the pieces, and thus what additional work I may have to do to convert those pieces to the esired value Slide 9.1.15 Labeled complex numbers Note the key point here. It's not that I am dealing with complex (define(make-complex-from-rect rl im numbers,they simply provide the motivation. The key point is(list rect rd im) that now I can use any of the procedures I wrote to manipulate (define(make-complex-from-polar mg an complex numbers on any kind of complex number. Thus (list polar mg an)) independent of whether a complex number is actually glued (define(tag obj)(car ob)) together in Cartesian or polar form, the same procedure applies To make this happen, I use tags(or types)to tell the selectors (cond ((eq?(tag z)rect)(car(contents z))) which pieces to pull out, and what to do to convert the pieces to (eq?(tag z)polar)((car(contents z)'mag the right form. And these tags are exactly what support the idea (else (error "unknown form of object)))) of having different versions of the same abstraction be handled 6001联0 by the same procedures
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 9.1.13 How do we add a label to our complex numbers? Let's just glue it onto the front. We can change our constructor to have the following behavior. Given two parts, we will just glue them together into a list. But if the parts represent real and imaginary components, we will put a symbolic label at the front to tell us this, while if the parts are magnitude and angle, we will still just glue them together but we'll put a different label at the front to tell us this. What else do I need? I'll want a selector to pull the labels off of these new abstractions, as well as a selector to get out the actual contents of the abstraction. Notice the use of cdr in this case to get the remaining list of elements from the representation. Note that in this case we are not doing any work to convert representations. We just glue the parts together, and put a label on it so we know what those parts mean. Slide 9.1.14 To make sure my contract holds, I'll need to adjust my selectors. Here is where I am going to bury the work I just saved in constructing numbers. I will have a single selector real that works with numbers represented in either form. This selector will first rip the tag off of the number to see who made it. Notice how we use eq? to test equality of symbols, and how we use the selector tag to get out the tag, and how we use the quoted symbols to represent the things to check against the tag. If this is in fact a Cartesian number, we use contents to get everything but the tag, then can use car to get the real part, since that is where it is stored in this representation, just as Bert did it. If this is a polar number, then we have to do the work to convert the underlying representation from polar form to the real part. In this case, contents will get the actual representation, and the car of that list we know is the magnitude of the vector. Similarly the cadr gets us the angle, and we can then do the trigonometry to convert to the real part. Thus in this case, my constructor just glues pieces together, with an appropriate label. My selectors use the label to tell me how to interpret the pieces, and thus what additional work I may have to do to convert those pieces to the desired value. Slide 9.1.15 Note the key point here. It's not that I am dealing with complex numbers, they simply provide the motivation. The key point is that now I can use any of the procedures I wrote to manipulate complex numbers on any kind of complex number. Thus, independent of whether a complex number is actually glued together in Cartesian or polar form, the same procedure applies. To make this happen, I use tags (or types) to tell the selectors which pieces to pull out, and what to do to convert the pieces to the right form. And these tags are exactly what support the idea of having different versions of the same abstraction be handled by the same procedures
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology The concept of a tag Slide 9.1.16 Tagged data This simple example thus motivates the key idea we are going to attach an identifying symbol to all nontrivial data values explore in this lecture: by putting tags on data structures, we can identify the right operations to apply to that data structure. In define ( make-poant x y) (ist "point x y) fact, a careful programmer would always put tags on data system, and to provide a means verifying that correct operations are being applied to data Thus, tagged data now refers to the concept of attaching an ing label to all non-trivial data types in my 6001 SICP convention, we will try to always check the label on the data structure before applying any procedures to manipulate those structures Slide 9.1.17 Benefits of tagged data As we will see, there are two key reasons for wanting to use tagged data. The first is that it makes available to use the functions that decide what to do based on the arguments owerful idea of data directed programming. Here, the idea to let the type of an object direct the procedure to the right cample: in a graphics program area: triangle square -> number method to apply to that type of object. This means that our style will be to write procedures that look at the type of the argument, and use that information to apply a procedure specifically tuned to that type of object. This, in fact, is exactly what we just did ith complex numbers. In that case, the selectors used the data type to direct the system to the right method 6001 sICP another example, suppose you are writing a graphics program, and want to be able to compute the area of a figure Rather than writing one giant procedure to do this for all types of figures, we could let the type of the figure(a triangle, a square, some other form) direct the procedure to a subprocedure specifically designed for that type of figure. Such an approach leads to very modular code, which is much easier to modify and maintain Benefits of tagged data Slide 91.18 data-directed programming The second key reason is that this approach allows us to practice functions that decide what to do based on the arguments defensive programming. We want to be careful to ensure that we don't have unwarranted assumptions about inputs to our area: triangle square l circle - number procedures, and in particular, we want our procedures to fail gracefully when they unexpected receive inputs of the wrong type. As we saw in the previous example, when we created a selector for a complex number, we did exactly that. I checked .much better to give an error message than for specific types of objects, specifying the method to use, but if I did not recognize the type of the object as something I was set to handle, I returned an error message with appropriate debug code if the error doesn't show up until several stages of additional processing have been applied to thay s 6001 SICP information. The point is that by handling unknown types rather than assuming something about a data object, we catch errors before they can propagate. It is much harder to incorrect data type
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 9.1.16 This simple example thus motivates the key idea we are going to explore in this lecture: by putting tags on data structures, we can identify the right operations to apply to that data structure. In fact, a careful programmer would always put tags on data structures, exactly to provide the flexibility to extend his or her system, and to provide a means verifying that correct operations are being applied to data. Thus, tagged data now refers to the concept of attaching an identifying label to all non-trivial data types in my system. By convention, we will try to always check the label on the data structure before applying any procedures to manipulate those structures. Slide 9.1.17 As we will see, there are two key reasons for wanting to use tagged data. The first is that it makes available to use the powerful idea of data directed programming. Here, the idea is to let the type of an object direct the procedure to the right method to apply to that type of object. This means that our style will be to write procedures that look at the type of the argument, and use that information to apply a procedure specifically tuned to that type of object. This, in fact, is exactly what we just did with complex numbers. In that case, the selectors used the data type to direct the system to the right method. As another example, suppose you are writing a graphics program, and want to be able to compute the area of a figure. Rather than writing one giant procedure to do this for all types of figures, we could let the type of the figure (a triangle, a square, some other form) direct the procedure to a subprocedure specifically designed for that type of figure. Such an approach leads to very modular code, which is much easier to modify and maintain. Slide 9.1.18 The second key reason is that this approach allows us to practice defensive programming. We want to be careful to ensure that we don't have unwarranted assumptions about inputs to our procedures, and in particular, we want our procedures to fail gracefully when they unexpected receive inputs of the wrong type. As we saw in the previous example, when we created a selector for a complex number, we did exactly that. I checked for specific types of objects, specifying the method to use, but if I did not recognize the type of the object as something I was set to handle, I returned an error message with appropriate information. The point is that by handling unknown types here, rather than assuming something about a data object, we catch errors before they can propagate. It is much harder to debug code if the error doesn't show up until several stages of additional processing have been applied to that incorrect data type
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 9.1. 19 To summarize we have introduced the idea of tagged data Benefits of tagged data types, and used that to consider clean ways to modularize data-directed program systems. We now want to explore in more detail how using functions that decide what to do based on the arguments tagged data makes it easier to build large systems ole: in a graphics program functions that fail gracefully if given bad arguments . much better to give an error message that 6001 SICP 6.001 Notes: Section 9. 2 Slide 9.2.1 Example: Arithmetic evaluation To show how to use these two ideas: data directed programming and defensive programming, the rest of this lecture is going to (define expl (make-sum (make-sum 3 15)20) consider an extended example. Because this example involves expl 仆+(+315}20 fair amount of code, it is important to keep in mind the key points being illustrated, so you don,'t lose sight of them amidst all the code fragments. To make this easier, we are going to incremental build new versions of the example on top of simpler versions, thus highlight key ideas and changes The example we are going to use to illustrate the ideas of data directed programming and defensive programming is a system 6001 sICP to manipulate arithmetic expressions. This will be similar to our example of symbolic derivatives, but now applying to more general expressions. So what does this mean? Not only do i want to be able to create symbolic arithmetic expressions, using appropriate constructors, I also want to be able to reduce those expressions to simpler forms, whenever possible. Thus, I would like to create symbolic expressions, such as exp l, as shown. Thus the value of the exp l will be the actual expression. And, I want to create a system that can evaluate expressions such as expl, that is, reduce this expression to a simpler form, in this case, the simpler expression 3 8
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 9.1.19 To summarize, we have introduced the idea of tagged data types, and used that to consider clean ways to modularize systems. We now want to explore in more detail how using tagged data makes it easier to build large systems. 6.001 Notes: Section 9.2 Slide 9.2.1 To show how to use these two ideas: data directed programming and defensive programming, the rest of this lecture is going to consider an extended example. Because this example involves a fair amount of code, it is important to keep in mind the key points being illustrated, so you don't lose sight of them amidst all the code fragments. To make this easier, we are going to incremental build new versions of the example on top of simpler versions, thus highlight key ideas and changes. The example we are going to use to illustrate the ideas of data directed programming and defensive programming is a system to manipulate arithmetic expressions. This will be similar to our example of symbolic derivatives, but now applying to more general expressions. So what does this mean? Not only do I want to be able to create symbolic arithmetic expressions, using appropriate constructors, I also want to be able to reduce those expressions to simpler forms, whenever possible. Thus, I would like to create symbolic expressions, such as exp1, as shown. Thus the value of the exp1 will be the actual expression. And, I want to create a system that can evaluate expressions such as exp1, that is, reduce this expression to a simpler form, in this case, the simpler expression 38
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 9.2.2 Example: Arith metic evaluation Building a system to evaluate expressions such as those just shown would be interesting in its own right, but I would like to (define expl m"m+t3120 add more to my system. In particular, I want my system to not (eval-1 expl) ==>38 only simplify standard arithmetic expressions, but also expressions that involve numbers that are only known to lie Expressions might include values other than numbers within a particular range. For example, I want my system to be e unknown number between min and may able to simplify expressions where the numbers are only known arithmetic:3,7]+[13]=[4,10] to lie between specific bounds of uncertainty. In the example Limited pr shown, I may only know that one number lies between 3 and 7, some value t some error amount rithmetic:(100±1)+(3±0.5)=(103±1.5) and another number lies between I and 3, but I still want my OOt sIcP system to be able to simplify an addition involving these numbers whose result i know must lie between 4 and 10 Moreover, I would like my system to be able to deal with expressions involving data from scientific experiments, in which I know the ostensible value of a number and a specified range of precision, that is, that the true value may lie within some plus/minus range of the ostensible value. In the example shown, I want my system to be able to add together expressions where I know one number is 100 plus/minus 1 and the other number is 3 plus/minus 0.5, and ave the system deduce that the sum should be 103 plus/minus 1.5 Thus, my goal is to build an arithmetic evaluation system that reduces arithmetic expressions, consisting of a mix of symbols and numbers, to simplest form; where the expressions may be standard numbers, ranges of values or imited precision values Slide 9.2.3 Approach: start simple, then extend The basic approach we are going to take is to start with easy Characteristic of all software engineering projects things first, an obvious thing to do! In our case, we will first tart with eval for numbers, then add support for build a system to handle normal numbers, and then we will look at how to build on top of that to handle other expressions, like ranges and limited precision values This does sound obvious, but it is important to stress that this is an important characteristic of a well-designed software engineering project, (and one that all too often is not followed, even in commercial systems). It is almost al ways easier to extend a base system, than to try to do the whole thing at once. 4 This is an important lesson to learn, and one that hopefully you will see in this extended example Approach: start simple, then extend Slide 9.2.4 Characteristic of all software engineering projects One of the things to watch for as we go through this exercise is Start with eval for numbers, then add support fo ranges and limited-precision values to notice how, by doing the development in stages, we make extensions to the system much easier to conceptualize Indee -Goal: build eval in a way that it will extend easily safely our goal is to build our simple evaluator so that extensions are Easily: requires data-directed pro safely requires defensive programming both easy and safe So what does that mean To allow for easy extensions, we will need to utilize tools from data-directed programming. That is, if we use data-directed programming tools(e.g. tagged data, dispatch to methods based on tag types), we will see it is easy to 6001 SICP I add new types of expressions to our system(create a new structure, an appropriate tag, and a dispatch to a method to handle that new type) To allow for safe extensions, we will need to use methods from defensive programming. This will require explicit
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 9.2.2 Building a system to evaluate expressions such as those just shown would be interesting in its own right, but I would like to add more to my system. In particular, I want my system to not only simplify standard arithmetic expressions, but also expressions that involve numbers that are only known to lie within a particular range. For example, I want my system to be able to simplify expressions where the numbers are only known to lie between specific bounds of uncertainty. In the example shown, I may only know that one number lies between 3 and 7, and another number lies between 1 and 3, but I still want my system to be able to simplify an addition involving these numbers, whose result I know must lie between 4 and 10. Moreover, I would like my system to be able to deal with expressions involving data from scientific experiments, in which I know the ostensible value of a number and a specified range of precision, that is, that the true value may lie within some plus/minus range of the ostensible value. In the example shown, I want my system to be able to add together expressions where I know one number is 100 plus/minus 1 and the other number is 3 plus/minus 0.5, and have the system deduce that the sum should be 103 plus/minus 1.5. Thus, my goal is to build an arithmetic evaluation system that reduces arithmetic expressions, consisting of a mix of symbols and numbers, to simplest form; where the expressions may be standard numbers, ranges of values or limited precision values. Slide 9.2.3 The basic approach we are going to take is to start with easy things first, an obvious thing to do! In our case, we will first build a system to handle normal numbers, and then we will look at how to build on top of that to handle other expressions, like ranges and limited precision values. This does sound obvious, but it is important to stress that this is an important characteristic of a well-designed software engineering project, (and one that all too often is not followed, even in commercial systems). It is almost always easier to extend a base system, than to try to do the whole thing at once. This is an important lesson to learn, and one that hopefully you will see in this extended example. Slide 9.2.4 One of the things to watch for as we go through this exercise is to notice how, by doing the development in stages, we make extensions to the system much easier to conceptualize. Indeed, our goal is to build our simple evaluator so that extensions are both easy and safe. So what does that mean? To allow for easy extensions, we will need to utilize tools from data-directed programming. That is, if we use data-directed programming tools (e.g. tagged data, dispatch to methods based on tag types), we will see it is easy to add new types of expressions to our system (create a new structure, an appropriate tag, and a dispatch to a method to handle that new type). To allow for safe extensions, we will need to use methods from defensive programming. This will require explicit
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology tests for types, error checks to catch unexpected types of arguments, and disciplined use of tags to tell use how to handle expressions rather than assuming an expression is of a particular type Thus, as we go through this exercise, watch how both of these themes guide the development of the system Slide 9. 2.5 Approach: start simple, then extend Here is our plan to accomplish this. We will first build an evaluator to simplify expressions involving normal numbers nges and limited-precision values Our second version will extend this base version in an obvious manner. We will see that this obvious extension is actually Goal: bu a way that it will extend easily safely flawed, and we will use the insights from its failure to create a data-directed programming Safel es defensive programming correct extension using a series of versions of the evaluator This will be a cycle in which we extend the system, observe it .Today: multiple versions of eval behavior, and use the observation to guide the next extension Thus this series of extensions will highlight how data-directed " Extend the evaluator, observe bugs eval-3 through-7 Do it again with tagged data programming and defensive programming intertwine to guide 6001 ICP the development of a complex system 1. ADT (Abstract Data Type)for sums Slide 9.2.6 type: ExP, Exp Let's start with our simple"sum"expressions. First we build a (define (make-sum addend augen constructor, as shown. Notice the type of this constructor. It (list 1+ addend augend)) takes in any two expressions, and returns a SumExp something of a more particular type, which is identified by the symbol t at the front of the expression. This symbol serves as the tag for the expression, and we are taking advantage of the fact that the operator itself identifies the type of expression Thus this constructor creates a tagged data type of particular type"sum", by gluing together the subordinate expressions with 0O1 sIcP the te Slide 9.2.7 1. ADT (Abstract Data Type)for sums Associated with this object type will be a predicate to detect type: ExP, Exp - SumExp objects. Sum-exp? takes in an expression(define(make-sum addend augend of any type, and returns a boolean value, that value indicating (list addend augend)) whether the input expression is a sum. Check out the body of type: anytype - boolean this procedure. We first check to see that the expression is a pair (and (pair? e)(eq? (car e). +)) (not that and evaluates its arguments in a left to right order, and stops as soon as one of its arguments returns a false value). If it is not, we stop, and return false. If it is a pair, then we can safely take the car of it, and check for the symbol 6001 SICP + Note that this is an instance of defensive programming Also note how we are using the tag to identify the type of object
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. tests for types, error checks to catch unexpected types of arguments, and disciplined use of tags to tell use how to handle expressions rather than assuming an expression is of a particular type. Thus, as we go through this exercise, watch how both of these themes guide the development of the system. Slide 9.2.5 Here is our plan to accomplish this. We will first build an evaluator to simplify expressions involving normal numbers. Our second version will extend this base version in an obvious manner. We will see that this obvious extension is actually flawed, and we will use the insights from its failure to create a correct extension, using a series of versions of the evaluator. This will be a cycle in which we extend the system, observe its behavior, and use the observation to guide the next extension. Thus this series of extensions will highlight how data-directed programming and defensive programming intertwine to guide the development of a complex system. Slide 9.2.6 Let's start with our simple "sum" expressions. First we build a constructor, as shown. Notice the type of this constructor. It takes in any two expressions, and returns a SumExp, something of a more particular type, which is identified by the symbol + at the front of the expression. This symbol serves as the tag for the expression, and we are taking advantage of the fact that the operator itself identifies the type of expression. Thus this constructor creates a tagged data type of particular type "sum", by gluing together the subordinate expressions with the tag. Slide 9.2.7 Associated with this object type will be a predicate to detect instances of such objects. Sum-exp? takes in an expression of any type, and returns a Boolean value, that value indicating whether the input expression is a sum. Check out the body of this procedure. We first check to see that the expression is a pair (not that and evaluates its arguments in a left to right order, and stops as soon as one of its arguments returns a false value). If it is not, we stop, and return false. If it is a pair, then we can safely take the car of it, and check for the symbol +. Note that this is an instance of defensive programming. Also note how we are using the tag to identify the type of object
6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 9.2.8 1. ADT(Abstract Data Type)for sums And of course we will need selectors for the data objects The type definitions for these procedures are that they convert (define (make-sum addend augend) SumExp's to Exp. Note that we can assume that the selectors are given SumExp's as input, that is, we have used defensive programming to check the type of the object (and (pair? e)(eq? (car e)t +)) before apply ing the selector. This means that we can safely i type: sumEzp -> Exp usecadr and caddr rather than first checking that the (define (sum-augend (caddy sum)) argument is a list, since the procedure already knows it is getting SumE DOt sIcP Slide 9. 2.9 1. ADT(Abstract Data Type)for sums The last thing to keep in mind is that here we are just dealing type: Exp, Exp with sums, so the type of expression returned by the selectors will just be"sums". But obviously, as we add other kinds of (list 1+ adden expressions to our system, we will need to the tags to help use: type: anytype -> direct the system to the correct subprocedure (define (sum-exp? e) (and (pair? e) (eq? (car e) ++))) (sum-addend sum)(cadr sum)) (sum-augend sum (caddy sum)) Type Exp will be different in different versions of eval 1. Eval for numbers only Slide 9.2.10 type: number I SumExp->number Given this starting point, it is straightforward to implement an (define (eval-1 exp) evaluator for reducing"sums"of numbers and variables. First notice the type of this procedure. It takes as input either a (number? exp) [(sum-exp? exp) number or a SumExp, which we know is a list of three (eval-1 (sum-addend exp)) (eval-1 (sum-augend exp)))) things, the first of which is the tag +, the other two of which are themselves numbers or sums. Our desired output of this (error"unknown expression"exp)))) procedure is a number, that is, we want it to reduce the input expression to a simple form So how do we do this? Well, if the expression is just a numbe OI SICP there is nothing to do, as it is already in simple form. notice g hat this is doing. We are using a data-directed style to check expression types, looking for the base or primitive types first. In this case, we use the built-in Scheme predicate for numbers to decide if the expression is already in simple form If it is not a number, we then use defensive programming to check if the expression is a sum. If it is a sum expression, then we use the selectors to get out the pieces, and recursively apply the evaluator to those expressions to reduce them to simplest form. Note that we are safe in applying the selectors here, since the defensive programming style has ensured that the expression is a sum This recursive application of the evaluator will allow us to deal with expressions whose subexpressions are themselves sums, and so on. If we have built eval-l correctly, then we are guaranteed that once these subexpressions have been processed, no matter how deep a nesting of expressions they contain, the result will be a number. Thus we can then add the results of evaluating to the parts of the sum, and return a number as the final value Finally, notice the defensive programming. If the argument is not a type that we know how to handle, we exit with an error. We don't just assume that if the expression is not a number, it must be a sum, we check explicitly. This
6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 9.2.8 And of course we will need selectors for the data objects. The type definitions for these procedures are that they convert SumExp's to Exp's.Note that we can assume that the selectors are givenSumExp's as input, that is, we have used defensive programming to check the type of the object, before applying the selector. This means that we can safely usecadr and caddr rather than first checking that the argument is a list, since the procedure already knows it is getting aSumExp as input Slide 9.2.9 The last thing to keep in mind is that here we are just dealing with sums, so the type of expression returned by the selectors will just be "sums". But obviously, as we add other kinds of expressions to our system, we will need to the tags to help use direct the system to the correct subprocedure. Slide 9.2.10 Given this starting point, it is straightforward to implement an evaluator for reducing "sums" of numbers and variables. First, notice the type of this procedure. It takes as input either a number or a SumExp, which we know is a list of three things, the first of which is the tag +, the other two of which are themselves numbers or sums. Our desired output of this procedure is a number, that is, we want it to reduce the input expression to a simple form. So how do we do this? Well, if the expression is just a number, there is nothing to do, as it is already in simple form. Notice what this is doing. We are using a data-directed style to check expression types, looking for the base or primitive types first. In this case, we use the built-in Scheme predicate for numbers to decide if the expression is already in simple form. If it is not a number, we then use defensive programming to check if the expression is a sum. If it is a sum expression, then we use the selectors to get out the pieces, and recursively apply the evaluator to those expressions to reduce them to simplest form. Note that we are safe in applying the selectors here, since the defensive programming style has ensured that the expression is a sum. This recursive application of the evaluator will allow us to deal with expressions whose subexpressions are themselves sums, and so on. If we have built eval-1 correctly, then we are guaranteed that once these subexpressions have been processed, no matter how deep a nesting of expressions they contain, the result will be a number. Thus we can then add the results of evaluating to the parts of the sum, and return a number as the final value. Finally, notice the defensive programming. If the argument is not a type that we know how to handle, we exit with an error. We don't just assume that if the expression is not a number, it must be a sum, we check explicitly. This
