DOC PREVIEW
MIT 6 001 - Lecture Notes

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Local Disk6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. All rights reserved6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. 6.001 Notes: Section 31.1 Slide 31.1.1 In previous lectures we have seen a number of important themes, which relate to designing code for complex systems. One was the idea of proof by induction, meaning that we could reason formally about whether and why our code would work correctly based on an inductive proof. This specifically said that if we could prove (using basic axioms) that the code correctly handled a base case, and if we could prove that assuming the code ran correctly for all cases whose input was less than some given size, then it ran correctly for input of that given size, then we could conclude that it ran correctly on all correct inputs. A second was the idea that we can gather related information together into higher-level data units, which we could abstract into treating as simple elements. Lists were a good example. And we saw that so long as the constructor and selectors of the abstraction obeyed a contract, we could suppress the details of the abstraction from its use. The third was that code written to manipulate data abstractions frequently had a structure that reflected the underlying structure of the abstraction: often we would use selectors to extract out subparts, manipulate those parts, and then use the constructor to create a new version of the abstraction. Slide 31.1.2 Today we are going to explore these themes in more detail. We are going to use them to build more complex data structures, and are particularly going to see how we can use inductive reasoning to design procedures to manipulate such structures. Specifically, we are going to look at two very useful data abstractions: trees and graphs. And we are going to see how procedures that search for information in large collections can be nicely designed to interact with such structures.6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 31.1.3 Let's start by revisiting lists. Remember that we said a list was simply a sequence of cons cells, connected by cdr's, ending in an empty list (also known as nil). Remember that we said lists had the property of closure. If we were to cons anything onto the beginning of the list, we would get a new sequence of cons cells, ending in the empty list, hence a list. And with the exception of the empty list, taking the cdr of a list results in a sequence of cons cells, ending in the empty list, hence a list. Note that this really has an inductive flavor to it. The base case is an empty list. Given that every collection of cons cells of size less than n, ending in an empty list, is a list; then clearly consing a new element onto such a list yields a list, and thus by induction, every collection of cons cells ending in the empty list is a list. We should be able to use this idea to reason about procedures that manipulate lists. Slide 31.1.4 Here is one of our standard procedures for manipulating lists: our old friend map. Intuitively, we know how this code should work, but can we establish formally that it does what we expect? Sure. We just use our notion of induction here, both on the data structure and on the code itself. For the base case, we have the base case data structure for a list, namely an empty list. Thus, the code clearly returns the right structure. Now, assume that map correctly returns a list in which each element of the input list has had proc applied to it, and that the order of the elements is preserved, for any list of size smaller than the current list. Then we know, given lst, that by induction on the data structure (cdr lst) is a list. By induction on the procedure map we know this willl return a list of the same size, with each element replaced by the application of proc to that element. We can then process the first element of the list, and by induction on the data structure, cons will return a new list of the appropriate size that also satisfies the conditions of map. Thus, by induction, we know that map will correctly perform as expected. Slide 31.1.5 Now, is there anything explicit in the code that says this applies only to lists of numbers? Of course not. It could be lists of symbols, or lists of strings. Or lists of anything. That can be seen by looking at the type definition for a list. As with pairs, we will represent a list by the symbol List followed by angle brackets containing a type definition for the elements of the list. Since lists are created out of pairs, we can be more explicit about this definition, by noting that a List of some type is either a Pair whose first element is of that type, and whose second element is a List of the same type, or (which is indicated by the vertical bar) the list is the special empty list.6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Notice the nice recursive definition of a list, with the closure property that the cdr of a list is itself a list. Notice that nothing in the type definition of a list says that the elements hanging off the cars of the list have to be numbers. In fact, our definition uses the arbitrary type C. This means that those structures could be anything, including other lists. This leads nicely to a more general data structure called a tree, which lets us capture much more complex kinds of relationships and structures. So what does a tree look like, and are there common procedures associated with the manipulation of trees? 6.001 Notes: Section 31.2 Slide 31.2.1 Here is the conceptual idea behind a tree. A tree has a root, or starting point. At the root, and indeed at every other point in the tree, there are a set of branches that connect different parts of the tree together. Each branch is said to contain a child, or sub-tree, and that sub-tree could itself be a tree, or could simply terminate in a leaf. In the example shown here, all the leaves are numbers, but of course they could be other objects such as strings. Note that trees have a nice recursive property, much like lists, in which taking the element hanging off a branch gives us another tree. This suggests that procedures designed to manipulate trees should have a very similar recursive structure. Slide 31.2.2


View Full Document

MIT 6 001 - Lecture Notes

Documents in this Course
Quiz 1

Quiz 1

6 pages

Databases

Databases

12 pages

rec20

rec20

2 pages

Quiz II

Quiz II

15 pages

Streams

Streams

5 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?