《Structure and Interpretation of Computer Programs》lecture 8 webhand

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 30.1 Slide 30l1 In this lecture, we are going to go back to several themes that 6.001: Structure and Interpretation of we have been exploring over the past few weeks, and stitch Computer Programs using the tools we have been building for dealing with stea.see them together into a single demonstration. We are going to see Today how quickly we can describe and control a complex system, by Building a new language using data and procedure abstractions abstractions 8n003 60015e Slide 30.1.2 Themes to be integrated The themes we are going to utilize include the following We are going to build on the idea of data abstraction, especially arate use of data structure from details of data the idea of separating the use of a data structure from the details Procedural abstraction of its implementation. We are going to see how that abstraction apture common patterns of behavior and treat as black barrier enables us to quickly describe complex structures box for generating new patterns Means of combination without getting lost in their details, and how to focus on the use Create complex combinations, then treat as primitives of such structures as entire units, while being assured that the interior details will be handled correctly Use modularity of components to create new language for particular problem domain We are going to also build on the idea of procedural abstraction d 8n/403 l especially the idea of capturing common patterns inside a black box, and using such abstractions to capture more complex And we are going to build on the idea of means of combination, that is, the idea that we can create simple methods for combining primitive objects into complex things, then treating the result as a primitive within a still more don plex thing. This will allow us to control complexity by utilizing a modular decomposition of the problem So our goal is to pull these pieces together to build a new language, one that is specifically designed for a particular problem domain

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 30.1 Slide 30.1.1 In this lecture, we are going to go back to several themes that we have been exploring over the past few weeks, and stitch them together into a single demonstration. We are going to see how quickly we can describe and control a complex system, by using the tools we have been building for dealing with abstractions. Slide 30.1.2 The themes we are going to utilize include the following. We are going to build on the idea of data abstraction, especially the idea of separating the use of a data structure from the details of its implementation. We are going to see how that abstraction barrier enables us to quickly describe complex structures without getting lost in their details, and how to focus on the use of such structures as entire units, while being assured that the interior details will be handled correctly. We are going to also build on the idea of procedural abstraction, especially the idea of capturing common patterns inside a black box, and using such abstractions to capture more complex patterns. And we are going to build on the idea of means of combination, that is, the idea that we can create simple methods for combining primitive objects into complex things, then treating the result as a primitive within a still more complex thing. This will allow us to control complexity by utilizing a modular decomposition of the problem domain. So our goal is to pull these pieces together to build a new language, one that is specifically designed for a particular problem domain

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 30.1.3 So what problem domain should we use? Well, we are going to target-the art of M. C. Escher create a language that describes pictures such as this famous one by m.C. Escher, called"quadratlimit"or"square limit". Not only will our language let us describe the process by which such pictures can be created, it will also let us create our own variations on this theme, leading to pictures that have a resemblance to the kind of elegant structure shown here in this Escher print 8m00 Slide 30.1. 4 So how do we describe such a system? Well, let's start with a simpler example. Here is a picture of my friend George. At an abstract level. what kinds of things would i like to do with George? 6001 SICP Slide 30.1.5 First, I might like to flip him, either about the vertical axis or about the horizontal one. By this I mean literally taking this portrait of George and spinning it 180 degrees out of the plane, then setting it back down 4 87/2003 6m13P Slide 30.1.6 V/ Alternatively, I might like to rotate him about an axis coming out the picture, causing him to do a cartwheel as I rotate his picture by increments of 90 degrees. Conceptually this is easy If I think of George as a picture, I can easily envision grabbi the whole picture and doing something to it. But how do i do this in practice? 6001S1CP

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 30.1.3 So what problem domain should we use? Well, we are going to create a language that describes pictures such as this famous one by M.C. Escher, called "quadratlimit" or "square limit". Not only will our language let us describe the process by which such pictures can be created, it will also let us create our own variations on this theme, leading to pictures that have a resemblance to the kind of elegant structure shown here in this Escher print. Slide 30.1.4 So how do we describe such a system? Well, let's start with a simpler example. Here is a picture of my friend George. At an abstract level, what kinds of things would I like to do with George? Slide 30.1.5 First, I might like to flip him, either about the vertical axis or about the horizontal one. By this I mean literally taking this portrait of George and spinning it 180 degrees out of the plane, then setting it back down. Slide 30.1.6 Alternatively, I might like to rotate him about an axis coming out the picture, causing him to do a cartwheel as I rotate his picture by increments of 90 degrees. Conceptually this is easy. If I think of George as a picture, I can easily envision grabbing the whole picture and doing something to it. But how do I do this in practice?

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 30.1.7 Here is one straightforward way. Assume that we have some a procedural definition of geor primitive drawing method called ( define(ge。 rge rect) (draw-line reet .250.35.5) draw-line r x1xt4:5.35 that takes a rectangle as input, and a set of coordinate values (e.g. x and y start point, and x and y end point), and draws a 89911.0g line from start to end within that rectangle. Note, details of the rectangle are irrelevant, we are just burying them beneath the abstraction. Thus, the first expression would draw a line starting 25 units to the right of the lower left hand corner, and ending at /4 enmatdtraw-line rect.15.60,85)) a point. 35 units to the right and 5 units up from the lower left hand corner Given that, here is a definition of George. Note what this does. Each expression gives a start and end point relative to the origin of the rectangle, and draw-line then sketches the line between those points Blech! This is far too specific, right? Given this definition of George, how do i create a rotated George or a flipped George? This is not obvious, and for an important reason. Here I have intertwined the action of drawing with the data representing George. I have not separated those actions, and moreover, I have chosen a very low-level representation for the elements of George. I really need to isolate these two aspects if I am to have any hope of drawing different pictures of George Slide 30.1.8 Data abstractions for lines So lets fix this. first we need some data abstractions to isolate points from the use of points. What is a point or a vector? It is define p1(make-vect 23))just a way of gluing together an x coordinate and ay (xcor p1))2 coordinate. so we can create an abstraction for this This has a (ycor p1)+3 constructor(called ma ke-vect) and two selectors(called xcor and yor) 48 1001 SICP Slide 30.1.9 Note that there is an inherent contract between these two Data abstractions for lines components: whatever method we use to glue things together in the constructor, we can get the parts back out using the efine pi(make-vect23》 selectors but the details of how we do that don t matter to p1)→2 things that simply want to use these objects rp1)→3 48m 6001CP

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 30.1.7 Here is one straightforward way. Assume that we have some primitive drawing method called draw-line, that takes a rectangle as input, and a set of coordinate values (e.g. x and y start point, and x and y end point), and draws a line from start to end within that rectangle. Note, details of the rectangle are irrelevant, we are just burying them beneath the abstraction. Thus, the first expression would draw a line starting .25 units to the right of the lower left hand corner, and ending at a point .35 units to the right and .5 units up from the lower left hand corner. Given that, here is a definition of George. Note what this does. Each expression gives a start and end point, relative to the origin of the rectangle, and draw-line then sketches the line between those points. Blech! This is far too specific, right? Given this definition of George, how do I create a rotated George or a flipped George? This is not obvious, and for an important reason. Here I have intertwined the action of drawing with the data representing George. I have not separated those actions, and moreover, I have chosen a very low-level representation for the elements of George. I really need to isolate these two aspects if I am to have any hope of drawing different pictures of George. Slide 30.1.8 So let's fix this. First, we need some data abstractions, to isolate points from the use of points. What is a point or a vector? It is just a way of gluing together an x coordinate and a y coordinate, so we can create an abstraction for this. This has a constructor (called make-vect) and two selectors (called xcor and ycor). Slide 30.1.9 Note that there is an inherent contract between these two components: whatever method we use to glue things together in the constructor, we can get the parts back out using the selectors, but the details of how we do that don’t matter to things that simply want to use these objects

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Data abstractions for lines Similarly, we can glue two endpoints or vectors together to eate a line segment. T data abstractie contract between the constructor (make-segment)and (define p1((make-vect 2 3) the selectors(start-segment and end p1)→3 segment (define p2 (make-vect 5 4)) So this gives us a way of abstracting vectors and segments Define s1 tmake-segmentp1 p2" Note the key point: I don' t need to know the details of how Ixcor tstart-segment s 1>2 vectors and segments are built, I just rely on the contract.This lycor tend-segment s ))>4 means we could think of George in terms of the appropriate elements, namely lines, rather than details of how those lines are represented Slide 30.1.l1 a better George So here is george in this format. Now, it looks like we have just put some window dressing around the line segments. But hang ta mm pf mahe wd 由mnr9-11m on, as we will see how treating George as an abstraction is going to make life much easier for us. In particular, note that fmet here we have created an abstraction for the points, and a separate abstraction for the line segments. Moreover, these are mm w omarm now defined with respect to some coordinate frame, they are not actually being drawn yet. So we have also separated the act mm l mrm of drawing from the representation of the data to be drawn dtn p22 trau veet.,》》 6 001 SICP Slide 30.1.12 Gluing things together First though, how could we actually build these vectors and For pairs, use a cons: 凵 Well, you saw this in the last lecture. For pairs of things (i.e things that come naturally in twos), we could just use a cons For larger structures. use a list: cell or a pair. And for larger collections, we could use lists. And of courses lists are just sequences of cons cells glued together into a spine, with the elements hanging off of it. ist1234) (cons I(cons 2(cons 3(cons d niD)))

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 30.1.10 Similarly, we can glue two endpoints or vectors together to create a line segment. This again is a data abstraction, with a contract between the constructor (make-segment) and the selectors (start-segment and end￾segment). So this gives us a way of abstracting vectors and segments. Note the key point: I don't need to know the details of how vectors and segments are built, I just rely on the contract. This means we could think of George in terms of the appropriate elements, namely lines, rather than details of how those lines are represented. Slide 30.1.11 So here is George in this format. Now, it looks like we have just put some window dressing around the line segments. But hang on, as we will see how treating George as an abstraction is going to make life much easier for us. In particular, note that here we have created an abstraction for the points, and a separate abstraction for the line segments. Moreover, these are now defined with respect to some coordinate frame; they are not actually being drawn yet. So we have also separated the act of drawing from the representation of the data to be drawn. Slide 30.1.12 First though, how could we actually build these vectors and segments? Well, you saw this in the last lecture. For pairs of things (i.e. things that come naturally in twos), we could just use a cons cell or a pair. And for larger collections, we could use lists. And of courses lists are just sequences of cons cells glued together into a spine, with the elements hanging off of it

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 30.1.13 Remember that there are several important properties to pairs Properties of data structures and lists. They have a contract between constructor and Contract between constructor and selectors selectors. They have the property of closure that is, that the Property of closure result of creating an instance of an object can itself be used to A list is a sequence of pairs, ending in the create a new object empty list, nil This is worth exploring a bit more carefully. So what is a list? It Consing anything onto a list results in a list(by is a sequence of pairs, ending in the special symbol nil, or definition) empty list. Thus, consing anything onto a list gives you a new Taking the cdr of a list results in a list(except perhaps for the empty list) sequence of pairs, ending in the empty list, hence a list Would be better to use adjoin, first and rest, Similarly, taking the cdr of a sequence of pairs ending in the instead of cons car and cdr. empty list results in a shorter sequence of pairs ending in the 4 &2003 6001S empty list, and hence is a list. Thus lists are closed under the operations of cons and cdr Note that this is not quite right. What happens if you try to take the cdr of nil? In MIT Scheme you get an error, but by this definition it would be better to just return the empty list Also notice that it would really be better to have distinctive operations for lists, as compared to pairs, e.g. adjoin first and rest, instead of cons, car and cdr, to distinguish operations on lists from operations on pairs. For historical reasons, we stick with the latter, even though the better would be conceptually much cleaner Slide 30.1.14 Completing our abstraction So let's use this to build a specific version of our abstraction Note how our abstraction nicely inherits its contract from the Points or vectors: underlying contract for pairs and lists. And note how points create a nested structure underneath lines. That is a line (define yor cdr] segment is a list of two elements, each of which points to Line segments: 山啁 another abstraction, namely a pair representing a vector (define makesegment list) (define start-segment car) 6 001 SICP Slide 30.1.15 Okay, now let's put the pieces together. George is just defined Drawing in a rectangle or frame as a collection(a list in this case)of line segments. All we need to do is take a rectangle or frame(which is just a pair of orthogonal line segments), and draw these segments within that rectangle. But as we start thinking towards the kinds of operations we did on George earlier. we would like to be able to draw george in different frames. So we would like to be able to define any frame. either of different size. or even non-orthogonal. and draw George inside of it. What does that mean? Ideally, we could take George( defined as a set of segments within a frame) and stretch those segments to fit within a new frame

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 30.1.13 Remember that there are several important properties to pairs and lists. They have a contract between constructor and selectors. They have the property of closure, that is, that the result of creating an instance of an object can itself be used to create a new object. This is worth exploring a bit more carefully. So what is a list? It is a sequence of pairs, ending in the special symbol nil, or empty list. Thus, consing anything onto a list gives you a new sequence of pairs, ending in the empty list, hence a list. Similarly, taking the cdr of a sequence of pairs ending in the empty list results in a shorter sequence of pairs ending in the empty list, and hence is a list. Thus lists are closed under the operations of cons and cdr. Note that this is not quite right. What happens if you try to take the cdr of nil? In MIT Scheme you get an error, but by this definition it would be better to just return the empty list. Also notice that it would really be better to have distinctive operations for lists, as compared to pairs, e.g. adjoin, first and rest, instead of cons, car and cdr, to distinguish operations on lists from operations on pairs. For historical reasons, we stick with the latter, even though the better would be conceptually much cleaner. Slide 30.1.14 So let's use this to build a specific version of our abstraction. Note how our abstraction nicely inherits its contract from the underlying contract for pairs and lists. And note how points create a nested structure underneath lines. That is a line segment is a list of two elements, each of which points to another abstraction, namely a pair representing a vector. Slide 30.1.15 Okay, now let's put the pieces together. George is just defined as a collection (a list in this case) of line segments. All we need to do is take a rectangle or frame (which is just a pair of orthogonal line segments), and draw these segments within that rectangle. But as we start thinking towards the kinds of operations we did on George earlier, we would like to be able to draw George in different frames. So we would like to be able to define any frame, either of different size, or even non-orthogonal, and draw George inside of it. What does that mean? Ideally, we could take George (defined as a set of segments within a frame) and stretch those segments to fit within a new frame